2022-10-22总结

啊

Description

给定一个 $n \times m$ 的 $01$ 矩阵，求包含 $[l,r]$ 个 $1$ 的子矩形个数。

Input

第一行读入两个正整数 $n,m$。

接下来 $n$ 行，每行一个长度为 $m$ 的 $01$ 串，表示给定的矩阵。

接下来一行，两个自然数 $l,r$。

Output

一行一个整数表示答案。

Hint

$n\le 30, m \le 5 \times 10^4$。

Solution

裸题，枚举上下边界 $up,down$ ，左右边界直接用双指针算，时间复杂度 $O(n^2m)$。

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
 
typedef long long ll;
const int N = 35;
const int M = 5e4+10;
 
int n, m, L, R;
char s[N][M];
int val[M];
ll ans;
 
ll solve();
 
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        cin >> (s[i]+1);
    cin >> L >> R;
     
    for(int u = 1; u <= n; u++)
    {
        memset(val, 0, sizeof(val));
        for(int d = u; d <= n; d++)
        {
            for(int i = 1; i <= m; i++)
                val[i] += (s[d][i]=='1');
            ans += solve();
        }
    }
    cout << ans << "\n";
}
 
ll solve()
{
    ll cnt = 0, sum1 = 0, sum2 = 0;
    for(int l = 1, r1 = 1, r2 = 1; l <= m; l++)
    {
        r1 = max(l, r1); r2 = max(l, r2);
        while(r1 <= m and sum1+val[r1] < L)
            sum1 += val[r1++];
        while(r2 <= m and sum2+val[r2] <= R)
            sum2 += val[r2++];
        cnt += r2-r1;
        if(l != r1) sum1 -= val[l];
        if(l != r2) sum2 -= val[l];
    }
    return cnt;
}

波

Description

给定 $n$ 个 正整数序列 $a_1,a_2,\cdots,a_n$ 每个序列长度为 $m$ 。 选择至少 $1$ 个序列，然后在每个被选择的序列中选择恰好一个元素，求出所有被选择的元素的 $\gcd$ 。 求所有方案的结果之和，答案对 $10^9+7$ 取模。 两种方案不同，当且仅当存在至少一个元素， 在一种方案中被选择，在另一种中没有。

Input

第一行两个整数 $n,m$。

接下来 $n$ 行，每行 $m$ 个正整数，第 $i$ 行代表第 $i$ 个序列 $a_i$ 。

Output

输出一个整数表示答案。

Hint

$0 \le n \le 20, 0 \le m \le 10^5, 1 \le a_{i,j} \le 10^6$

Solution

直接求 $\gcd = d$ 的方案数不好求，改成求 $\gcd | d$ 的方案数，这个只需要满足选的数都是 $d$ 的倍数即可，最后做一个类似差分的操作就行。

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
 
typedef long long ll;
const int N = 21;
const int M = 1e5+10;
const int A = 1e6+10;
const int P = 1e9+7;
 
int n, m;
int a[N][M];
int cnt[N][A];
ll f[A];
 
int main()
{ 
    const int maxv = 1e6;
     
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            cin >> a[i][j], cnt[i][a[i][j]]++;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= maxv; j++)
            for(int k = j*2; k <= maxv; k += j)
                cnt[i][j] += cnt[i][k];
    }
     
    ll ans = 0;
    for(int i = maxv; i >= 1; i--)
    {
        f[i] = 1;
        for(int j = 1; j <= n; j++)
            (f[i] *= (cnt[j][i]+1)) %= P;
        f[i]--;
        for(int j = i*2; j <= maxv; j += i)
            f[i] = (f[i]-f[j]+P)%P;
        (ans += f[i]*i%P) %= P;
    }
    cout << ans;
}

呲

Description

在二维母世界诞生的你，第一次见到了三维世界的恢弘壮阔。可惜你无暇过多欣赏，你接收到的命令是：斩草除根！

三维世界可以看成是一个 $A \times B \times C$ 的立方体，由于你的文明还没有完全掌握三维世界的结构，现在你还只有三种不够成熟的进攻路线：

• 1 a b: 将所有 $x \leq a, y \leq b$ 的世界毁灭。
• 2 a b: 将所有 $y\leq a, z \leq b$ 世界毁灭。
• 3 a b: 将所有 $z \leq a, x \leq b$ 的世界毁灭。

最终你计划了 $n$ 次进攻，你想知道你摧毁了这个世界多少的体积。

Input

第一行四个数 $n,A,B,C$。接下来 $n$ 行，每行三个数 $type, a, b$，表示一次进攻，其中 $type$ 表示进攻路线， $a,b$ 为进攻的参数。

Output

一个数表示答案。

Hint

$n \le 3 \times 10^5, 1 \le A,B,C \le 10^6, u \le A, v \le B, w \le C$。

Solution

题目的要求就是对三个阶梯图形求并，我们可以任选一维进行扫描面，这样有两个阶梯图形就被分解为矩形了，然后并的部分可以二分分界线解决。(大粪题)

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <regex>
using namespace std;
 
typedef long long ll;
const int N = 3e5+10;
const int M = 1e6+10;
 
struct pir { int x, y; };
 
struct cube {
    pir s[N];
    int height[M];
    ll sum[M];
    int tot, A, B, C;
     
    void init(int _A, int _B, int _C)
        { A = _A, B = _B, C = _C; }
    void add(int x, int y)
        { s[++tot] = {x, y}; }
    pir& operator [] (int id) { return s[id]; }
     
    void prework()
    {
        sort(s+1, s+tot+1, [](pir a, pir b){
            if(a.x != b.x)
                return a.x < b.x;
            else
                return a.y < b.y;
        });
         
        int tmp = tot; tot = 0;
        for(int i = 1; i <= tmp; i++)
        {
            while(tot and s[tot].y <= s[i].y) tot--;
            s[++tot] = s[i];
        }
         
        for(int i = 1; i <= tot; i++)
            for(int j = s[i-1].x+1; j <= s[i].x; j++)
                height[j] = s[i].y;
         
        for(int i = 1; i <= A; i++)
            sum[i] = sum[i-1]+height[i];
    }
    ll calc1()
    {
        return sum[A]*C;
    }
    ll binary_search(int x, int y)
    {
        if(height[x] >= y) return (ll)x*y;
         
        int l = 1, r = x, mid;
        while(l < r)
        {
            mid = (l+r)>>1;
            if(height[mid] >= y)
                l = mid+1;
            else
                r = mid;
        }
        return sum[x] - sum[l-1] + (ll)(l-1)*y;
    }
} X, Y, Z;
 
ll operator * (cube &a, cube &b)
{
    ll ans = 0;
    for(int i = 1; i <= b.tot; i++)
    {
        int x = b[i].y, y = a.B;
        ans += a.binary_search(x, y) * (b[i].x-b[i-1].x);
    }
    return ans;
}
 
ll common(int l1, int r1, int l2, int r2)
{
    if(r1 < l2 or r2 < l1) return 0;
    return min(r1, r2) - max(l1, l2) + 1;
}
 
ll lastcalc()
{
    ll ans = 0;
    for(int i = 1; i <= Z.tot; i++)
        swap(Z[i].x, Z[i].y);
    reverse(Z.s+1, Z.s+Z.tot+1);
     
    int ind = 1;
    for(int i = 1, tmp; i <= Z.tot; i++)
    {
        while(ind <= X.tot and !common(X[ind-1].x+1, X[ind].x, Z[i-1].x+1, Z[i].x)) ind++;
         
        if(ind > X.tot) break;
         
        for(; ind <= X.tot and (tmp = common(X[ind-1].x+1, X[ind].x, Z[i-1].x+1, Z[i].x)); ind++)
            ans += Y.binary_search(X[ind].y, Z[i].y)*tmp;
        ind--;
    }
    return ans;
}
 
int n, A, B, C;
 
 
int main()
{
    cin >> n >> A >> B >> C;
     
    X.init(B, C, A);
    Y.init(C, A, B);
    Z.init(A, B, C);
     
    for(int i = 1; i <= n; i++)
    {
        int opt, a, b;
        cin >> opt >> a >> b;
        switch(opt)
        {
            case 1: Z.add(a, b); break;
            case 2: X.add(a, b); break;
            case 3: Y.add(a, b); break;
        }
    }
    X.prework();
    Y.prework();
    Z.prework();
     
    ll ans = X.calc1() + Y.calc1() + Z.calc1();
    ans -= X*Z + Z*Y + Y*X;
    ans += lastcalc();
     
    cout << ans;
}