跳转至

260224 模拟赛

T1

称一个正整数序列是好的，当且仅当它的长度为 \(n\) 并且值域为 \([1,m]\) 并且值域内的每个数都至少出现一次。

称两个序列是本质相同的，当且仅当对于序列的每个子区间，两个序列的区间最大值位置相同（如有多个最大值，取最左边的一个）。请统计本质不同序列数量。

\(T\le 20,~n\le 10^6\)

只需对笛卡尔树计数。问题在于如何将值域压缩到 \([1,m]\)（显然扩展值域是容易的）。这等价于笛卡尔树上不能存在一条根链包含 \(m-1\) 条向左的边。

注意到我们不关心向右的边，因此直接将这些边拉平，并接到同一个父亲上（这时，我们区分多条出边的顺序），这样问题转化为统计树高不超过 \(m\) 的多叉树数量。由于我们区分出边的顺序，因此树可以用括号序列统计。这显然是一个格路计数问题，要从 \((0,0)\) 走到 \((2n,0)\)，\(y\) 坐标不能低于 \(0\) 或者高于 \(m\)。直接反射容斥即可。

代码 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<iostream>
using namespace std;
typedef long long ll;
const int N = 2e6 + 10;
const int MOD = 1e9 + 7;

inline void add(int &a, int b) { a += b; (a >= MOD) && (a -= MOD); }

int T, n, m, ans;
int inv[N], fac[N], ifac[N];
inline int C(int a, int b) { return (ll)fac[a] * ifac[a - b] % MOD * ifac[b] % MOD; }

int main() {

#ifndef LOCAL
    freopen("counting.in", "r", stdin);
    freopen("counting.out", "w", stdout);
#endif

    inv[1] = fac[0] = ifac[0] = 1;
    for(int i = 2; i < N; i++) inv[i] = MOD - (ll)inv[MOD % i] * (MOD / i) % MOD;
    for(int i = 1; i < N; i++) fac[i] = (ll)fac[i - 1] * i % MOD;
    for(int i = 1; i < N; i++) ifac[i] = (ll)ifac[i - 1] * inv[i] % MOD;

    cin >> T >> T;
    while(T--) {
        cin >> n >> m;
        ans = C(2 * n, n);
        for(int y = 0; abs(y) <= 2 * n; ) {
            y = -2 - y;
            if(abs(y) > 2 * n) break;
            add(ans, MOD - C(2 * n, n + y / 2));
            y = 2 * m + 2 - y;
            if(abs(y) > 2 * n) break;
            add(ans, C(2 * n, n + y / 2));
        }
        for(int y = 0; abs(y) <= 2 * n; ) {
            y = 2 * m + 2 - y;
            if(abs(y) > 2 * n) break;
            add(ans, MOD - C(2 * n, n + y / 2));
            y = -2 - y;
            if(abs(y) > 2 * n) break;
            add(ans, C(2 * n, n + y / 2));
        }
        cout << ans << '\n';
    }

    return 0;
}

T2

给定一个 \(n\times m\) 的 01 矩阵。你可以选择两个参数 \(p,q\) 满足 \(1\le p\le n,~1\le q\le m\)，然后你可以进行任意多次轰炸操作，每次会轰炸一个 \(p\times q\) 的子矩形（必须完全包含于原矩阵），不能轰炸到 1，至少轰炸 \(k\) 个 0。问有多少个合法的 \((p,q)\)。

\(n,m\le 3000\)

显然具有单调性，因此枚举 \(p\) 然后对 \(q\) 双指针。考虑怎么快速 check，我们将所有 \(i\bmod p=0\) 的行标出来，注意到一个轰炸的区域一定会跨过恰好一行，因此我们在每行处统计贡献，求出每个长为 \(q\) 的子区间向上/向下最远拓展到哪里，然后保留 \(\ge p\) 的区间，再更新每一列的最远覆盖位置。容易用一些单调队列做到 \(O(\frac{nm}{p})\)。对称的，也可以做到 \(O(\frac{nm}{q})\)，合并起来就是 \(O(\frac{nm}{\max(p,q)})\)。

这玩意放到外面就形如两个调和级数，因此时间复杂度 \(O(nm\log nm)\)。

代码 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include<iostream>
#include<cassert>
using namespace std;
const int N = 3010;

int n, m, k, p, q, ans;
bool a[N][N]; int up[N][N], dw[N][N], lf[N][N], rt[N][N];
int mu[N], md[N], len[N], pre[N], que[N], hd, tl;

inline bool check() {
    int res = 0;
    if(p >= q) {
        for(int j = 1; j <= m; j++) pre[j] = 0;
        for(int i = 1; i <= n; i += p) {
            hd = 1, tl = 0;
            for(int j = 1; j <= m; j++) {
                while(hd <= tl && up[i][j] <= up[i][que[tl]]) --tl;
                while(hd <= tl && que[hd] < j - q + 1) ++hd;
                que[++tl] = j;
                mu[j] = up[i][que[hd]];
            }
            hd = 1, tl = 0;
            for(int j = 1; j <= m; j++) {
                while(hd <= tl && dw[i][j] <= dw[i][que[tl]]) --tl;
                while(hd <= tl && que[hd] < j - q + 1) ++hd;
                que[++tl] = j;
                md[j] = dw[i][que[hd]];
            }
            for(int j = 1; j <= m; j++) {
                if(mu[j] + md[j] - 1 < p) mu[j] = md[j] = 0;
            }
            hd = 1, tl = 0;
            for(int j = m; j >= 1; j--) {
                while(hd <= tl && que[hd] > j + q - 1) ++hd;
                if(j >= q) {
                    while(hd <= tl && mu[j] >= mu[que[tl]]) --tl;
                    que[++tl] = j;
                }
                len[j] = mu[que[hd]];
            }
            hd = 1, tl = 0;
            for(int j = m; j >= 1; j--) {
                while(hd <= tl && que[hd] > j + q - 1) ++hd;
                if(j >= q) {
                    while(hd <= tl && md[j] >= md[que[tl]]) --tl;
                    que[++tl] = j;
                }
                int tmp = min(p, md[que[hd]]);
                assert((bool)tmp == (bool)len[j]);
                if(tmp) {
                    assert(tmp + len[j] - 1 >= p);
                    res += tmp + min(p + 1 - pre[j], len[j]) - 1;
                }
                pre[j] = tmp;
            }
        }
    } else {
        for(int j = 1; j <= n; j++) pre[j] = 0;
        for(int i = 1; i <= m; i += q) {
            hd = 1, tl = 0;
            for(int j = 1; j <= n; j++) {
                while(hd <= tl && lf[i][j] <= lf[i][que[tl]]) --tl;
                while(hd <= tl && que[hd] < j - p + 1) ++hd;
                que[++tl] = j;
                mu[j] = lf[i][que[hd]];
            }
            hd = 1, tl = 0;
            for(int j = 1; j <= n; j++) {
                while(hd <= tl && rt[i][j] <= rt[i][que[tl]]) --tl;
                while(hd <= tl && que[hd] < j - p + 1) ++hd;
                que[++tl] = j;
                md[j] = rt[i][que[hd]];
            }
            for(int j = 1; j <= n; j++) {
                if(mu[j] + md[j] - 1 < q) mu[j] = md[j] = 0;
            }
            hd = 1, tl = 0;
            for(int j = n; j >= 1; j--) {
                while(hd <= tl && que[hd] > j + p - 1) ++hd;
                if(j >= p) {
                    while(hd <= tl && mu[j] >= mu[que[tl]]) --tl;
                    que[++tl] = j;
                }
                len[j] = mu[que[hd]];
            }
            hd = 1, tl = 0;
            for(int j = n; j >= 1; j--) {
                while(hd <= tl && que[hd] > j + p - 1) ++hd;
                if(j >= p) {
                    while(hd <= tl && md[j] >= md[que[tl]]) --tl;
                    que[++tl] = j;
                }
                int tmp = min(q, md[que[hd]]);
                assert((bool)tmp == (bool)len[j]);
                if(tmp) {
                    assert(tmp + len[j] - 1 >= q);
                    res += tmp + min(q + 1 - pre[j], len[j]) - 1;
                }
                pre[j] = tmp;
            }
        }
    }
    return res >= k;
}

int main() {

#ifndef LOCAL
    freopen("bomb.in", "r", stdin);
    freopen("bomb.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
#endif

    cin >> n >> m >> k;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            char c; cin >> c;
            a[i][j] = c == '1';
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(!a[i][j]) up[i][j] = up[i - 1][j] + 1, lf[j][i] = lf[j - 1][i] + 1;
        }
    }
    for(int i = n; i >= 1; i--) {
        for(int j = m; j >= 1; j--) {
            if(!a[i][j]) dw[i][j] = dw[i + 1][j] + 1, rt[j][i] = rt[j + 1][i] + 1;
        }
    }

    for(p = n, q = 1; p >= 1; p--) {
        while(q <= m && check()) ++q;
        ans += q - 1;
    }
    cout << ans << '\n';

    return 0;
}

T3

神秘构造。第二个包的最后一个东西需要特殊处理，需要把它夹在前面两半之间。考虑正解，需要注意到分组处理是非常有前途的，观察到隔板数是 \(\frac{7}{6}n+\epsilon\)，又需要观察到 \(\frac{7}{6}=\frac{1}{2}+\frac{2}{3}\)，然后给左边分两组，右边分三组（分别记为 \(A_1,A_2\) 和 \(B_1,B_2,B_3\)），把隔板分配给 \(A_1,B_1,B_2\)。

然后先做 \(A_1B_1\) 和 \(A_1B_2\)，然后尝试做 \(A_1B_3\)，需要把 \(B_1\) 的板翻过来用，但为了不让 \(B_1\) 污染 \(A_1\) 的板，需要额外开一个板用来保护。这样 \(A_1\) 就做完了。然后把 \(A_1\) 翻过来做 \(A_2\)，先做 \(A_2B_3\)，然后隔着做 \(A_2B_2\)，然后把 \(B_2\) 翻过来做 \(A_2B_1\)。

代码 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<iostream>
#include<vector>
using namespace std;

int n, nn;
vector<string> ans;
char tmp[100];

int main() {

    freopen("construct.in", "r", stdin);
    freopen("construct.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;

    for(int i = 1; i <= 305; i++) {
        for(int j = 1; j <= 203; j++) {
            sprintf(tmp, "2 %d %d %d %d", i, i, 305 + j, j);
            if(i <= n && j <= n) ans.push_back(tmp);
        }
        for(int j = 1; j <= 203; j++) {
            sprintf(tmp, "2 %d %d %d %d", i, i, 508 + j, 203 + j);
            if(i <= n && 203 + j <= n) ans.push_back(tmp);
        }
    }
    for(int i = 1; i <= 305; i++) {
        for(int j = 1; j <= 203; j++) {
            sprintf(tmp, "3 %d %d 712 -%d %d", i, i, 305 + j, 406 + j);
            if(i <= n && 406 + j <= n) ans.push_back(tmp);
        }
    }
    for(int i = 1; i <= 304; i++) {
        for(int j = 1; j <= 203; j++) {
            sprintf(tmp, "2 %d -%d -%d %d", 305 + i, i, 305 + j, 406 + j);
            if(305 + i <= n && 406 + j <= n) ans.push_back(tmp);
        }
        for(int j = 1; j <= 203; j++) {
            sprintf(tmp, "3 %d -%d -712 %d %d", 305 + i, i, 508 + j, 203 + j);
            if(305 + i <= n && 203 + j <= n) ans.push_back(tmp);
        }
    }
    for(int i = 1; i <= 304; i++) {
        for(int j = 1; j <= 203; j++) {
            sprintf(tmp, "2 %d -%d -%d %d", 305 + i, i, 508 + j, j);
            if(305 + i <= n && j <= n) ans.push_back(tmp);
        }
    }
    cout << 712 << '\n';
    for(string s : ans) cout << s << '\n';

    return 0;
}