前言

多校系列的起始，被各路神仙虐了一顿，感觉暑假末尾时候的网络赛要凉了…

以及没有队友，几乎是单挑，人很麻，发现往往自己打两小时左右就想鸽了（CF后遗症）

后面是系列复盘文章，希望能够学明白多校的题目多一点点，毕竟这样的高质量比赛相当难得（

复盘

这场比赛总体写的很麻，本来一个签到题可以很快解决结果写了数位DP还调炸了…

据出题人说本场难度略低于区域赛，换句话说这场都麻了区域赛就更麻了（

A - Alice and Bob

博弈论经典题，直观上来看复杂度在$O(N^4)$​​，难点在于优化转移的复杂度。

最开始的时候冲了个很典的记忆化Dfs，喜提TLE，大概只过了$25\%$的点。

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
/* vegetable1024 | oi-liu.com | Maybe Lovely? */

#include <bits/stdc++.h>
#define maxn 5005
using namespace std;
int t, n, m, dp[maxn][maxn];
int dfs(int n, int m){
    if(n >= m)
        swap(n, m);
    //printf("%d %d %d\n", n, m, dp[n][m]);
    if(~dp[n][m])
        return dp[n][m];
    if(n == 0 && m == 0)
        return 0;
    int flag = 0;
    for(int i = 1; i <= n; i++)
        for(int j = 0; j <= m / i; j++)
            flag |= !dfs(n - i, m - j * i);
    for(int i = 1; i <= m; i++)
        for(int j = 0; j <= n / i; j++)
            flag |= !dfs(m - i, n - j * i);
    return dp[n][m] = flag;
}
int main(void)
{
    memset(dp, -1, sizeof(dp));
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d %d", &n, &m);
        printf(dfs(n, m) ? "Alice\n" : "Bob\n");
    }
    return 0;
}

后面想着拿来打表，但是并没有什么作用，打表没看出什么规律（甚至开始口胡素数的规律，当然很明显是错的）。后面学习正解，发现有个$trick$​，即：

• 结论：如果某堆石子数量是i，另一堆石子最多只有一种数量满足后手胜。

反证法：假设 $(i, p)$​​ 和 $(i, q)$​​ 都是后手必胜，且 $q > p$​。那么在状态 $(i, q)$​ 时，先手可以在第二堆选 $q-p$​ 个，第一堆选 $0$​ 个，转移到后手胜的 $(i, p)$，说明 $(i, q)$ 是先手胜，矛盾。

于是，我们就可以只从必败态开始往后拓展，以一个类似埃筛的形式，标记出所有的先手必胜态。

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
/* vegetable1024 | oi-liu.com | Maybe Lovely? */

#include <bits/stdc++.h>
#define maxn 5005
using namespace std;
int t, n, m;
bool dp[maxn][maxn];
int main(void)
{
    dp[0][0] = 0;
    for(int i = 0; i <= 5000; i++)
        for(int j = 0; j <= i; j++)
            if(dp[i][j] == false)
            {
                for(int k = 1; i + k <= 5000; k++)
                    for(int l = 0; j + l * k <= 5000; l++)
                        dp[i + k][j + l * k] = true,
                        dp[j + l * k][i + k] = true;
                for(int k = 1; j + k <= 5000; k++)
                    for(int l = 0; i + l * k <= 5000; l++)
                        dp[j + k][i + l * k] = true,
                        dp[i + l * k][j + k] = true;
            }
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d %d", &n, &m);
        if(n < m)    swap(n, m);
        printf(dp[n][m] ? "Alice\n" : "Bob\n");
    }
    return 0;
}

B - Ball Dropping

简单几何题，推公式就可以了。

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
/* vegetable1024 | oi-liu.com | Maybe Lovely? */

#include <bits/stdc++.h>
#define maxn 100005
#define pi acos(-1.0)
using namespace std;

double r, a, b, h;
int main(void)
{
    scanf("%lf %lf %lf %lf", &r, &a, &b, &h);
    if(2 * r < b)
        printf("Drop\n");
    else
    {
        printf("Stuck\n");
        double tsita = 2 * h / (a - b);
        double sita = atan(tsita);
        double K = b / (2 * cos(sita));
        double H = (b * tan(sita) / 2);
        double ans = K / H * r * tan(sita) - H;
        printf("%.8lf\n", ans);
    }
    return 0;
}

D - Determine the Photo Position

签到题，前缀和优化一下就没了。

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
/* vegetable1024 | oi-liu.com | Maybe Lovely? */

#include <bits/stdc++.h>
#define maxn 2005
using namespace std;
int n, m;
int sum[maxn][maxn];
char board[maxn][maxn];
char qread(){
    char ch = getchar();
    while(ch != '0' && ch != '1' && ch != '2')    ch = getchar();
    return ch;
}
int main(void)
{
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            board[i][j] = qread();
    for(int i = 1; i <= m; i++)    qread();
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            sum[i][j] = sum[i][j - 1] + (board[i][j] == '0' ? 1 : 0);
    int cnt = 0;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
        {
            int lf = j - m + 1;
            if(lf >= 1 && sum[i][j] - sum[i][lf - 1] == m)
            {
                cnt++;
            }
        }
    printf("%d\n", cnt);
    return 0;
}

F - Find 3-friendly Integers

这题一看，哇，数位DP裸题（

然后我就写挂了，调了好一会细节，大概是太久没写数位DP了（

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#define maxn 100005
#define int long long
using namespace std;
int t, l, r, cnt;
//dp[len][r1][r2][r3][mod]
int dis[maxn], dp[25][5][5][5][2];
int dfs(int x, int lim, int zero, int mod, int r0, int r1, int r2){
    if(x == 0)    return mod == 1 ? 1 : 0;
    if(~dp[x][r0][r1][r2][mod] && !lim && !zero)
        return dp[x][r0][r1][r2][mod];
    int limm = lim ? dis[x] : 9;
    int res = 0;
    for(int i = 0; i <= limm; i++)
    {
        int can, nowr0, nowr1, nowr2;
        can = 0;
        nowr0 = i % 3 == 0;
        nowr1 = i % 3 == 1;
        nowr2 = i % 3 == 2;
        if(r1)
        {
            int nres = (i + 1) % 3;
            if(nres == 0)    nowr0 = 1;
            if(nres == 1)    nowr1 = 1;
            if(nres == 2)    nowr2 = 1;
        }
        if(r2)
        {
            int nres = (i + 2) % 3;
            if(nres == 0)    nowr0 = 1;
            if(nres == 1)    nowr1 = 1;
            if(nres == 2)    nowr2 = 1;
        }
        if(((!zero) || (zero && i)) && nowr0)    can = 1;
        res += dfs(x - 1, lim && i == limm, zero && i == 0, mod || can, nowr0, nowr1, nowr2);
    }
    if(!lim && !zero)
        dp[x][r0][r1][r2][mod] = res;
    return res;
}
int solve(int x){
    memset(dp, -1, sizeof(dp));
    cnt = 0;
    while(x)
    {
        dis[++cnt] = x % 10;
        x /= 10;
    }
    //if(cnt == 0)    cnt = 1;
    return dfs(cnt, 1, 1, 0, 1, 0, 0);
}
signed main(void)
{
    scanf("%lld", &t);
    while(t--)
    {
    	scanf("%lld %lld", &l, &r);
    	printf("%lld\n", solve(r) - solve(l - 1));
    }
    return 0;
}

实际上并不需要这么复杂。

根据鸽笼原理，只要位数不少于 3 位，必然出现一组前缀和 %3 相同的位置。

因此只要对$n < 100$的情况暴力计算就可以了。

G - Game of Swapping Numbers

题解指出：

问题等价于给序列$A,B$分配等量的正负号（$|A_i-B_i|=(+A_i)+(-B_i) \ or \ (-A_i)+(+B_i)$​）

如果$k$不受限制，可以将$A,B$放在一起排序，取前$n$个大数（正号）减去后$n$​个小数（负号），即为答案。

如果$k$受限制呢？

首先要知道，$n>2$​时，恰好$k$​步与至多$k$​​步是等价的。

由鸽巢原理，当$n>2$的时候，存在两个位置满足$A_i \geq B_i$或$A_i \leq B_i$，交换这两个位置的数，答案不会变得更劣，由此可得$n>2$时，恰好$k$步与至多$k$步是等价的。

因此，假设$k$受限制，只要按照恰好$k$​步来贪心就好了。

由我们$k$​不受限制时的思路启发，将所有的$min(A_i, B_i)$​和$max(A_i, B_i)$排序，依次取前$k$大相减取和即可。

比赛时候我想着可能要分奇偶讨论，然后就麻掉了…这个是非常巧妙的一个贪心题！

赛后我翻了翻，发现hei____hei交了一个很牛的反悔贪心，首先按照原序列把贡献算出来，再做两个优先队列用于计算交换后的贡献。若要构造最优的答案，则必然是交换后使得前$n$大的某个数减去前$n$小的某个数，构造出最优解后不需要在进行交换，因此取$min(q.size(), k)$即可。

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
#include <bits/stdc++.h>
#define maxn 2000005
#define int long long
using namespace std;
int n, k, a[maxn], b[maxn], ida[maxn], idb[maxn];
struct Node{
    int id;
    int val;
    int type;
}num[maxn];
bool cmp(const Node &A, const Node &B){
    return A.val < B.val;
}
signed main(void)
{
    scanf("%lld %lld", &n, &k);
    for(int i = 1; i <= n; i++)
        scanf("%lld", &a[i]), 
        num[i] = (Node){i, a[i], 0};
    for(int i = 1; i <= n; i++)
        scanf("%lld", &b[i]),
        num[i + n] = (Node){i, b[i], 1};
    if(n == 2)
    {
        printf("%lld\n", k & 1 ? abs(a[1] - b[2]) + abs(a[2] - b[1]) : abs(a[1] - b[1]) + abs(a[2] - b[2]));
        return 0;
    }
    sort(num + 1, num + n + n + 1, cmp);
    for(int i = 1; i <= n + n; i++)
        !num[i].type ? ida[num[i].id] = i : idb[num[i].id] = i;
    int sum = 0;
    priority_queue<int> q1, q2;
    for(int i = 1; i <= n; i++)
    {
        sum += abs(a[i] - b[i]);
        if(ida[i] <= n && idb[i] <= n)
            q1.push(-a[i] - b[i] - abs(a[i] - b[i]));
        if(ida[i] > n && idb[i] > n)
            q2.push(a[i] + b[i] - abs(a[i] - b[i]));
    }
    int qsize = q1.size();
    for(int i = 1; i <= min(k, qsize); i++)
        sum += q1.top() + q2.top(), q1.pop(), q2.pop();
    printf("%lld\n", sum);
    return 0;
}

H - Hash Function

差卷积的一个模板题（虽然说是板子但我也是第一次接触）

实际上就是用多项式的幂次来代表某个差值是否有出现，且用FFT来加速多项式乘法。

由于$FFT$​这里不便使用负数下标，因此$a_i-b_i$​​改为$a_i+(MAX-b_i)$​​

这里可以枚举$5e5 \rightarrow 1e6$的数（因为按照定义$a_i-b_i+MAX > MAX$​才能表示绝对值的差）。

也可以枚举$0 \rightarrow 1e6$的数，再取个绝对值，同样符合题目的定义。​

最后求出哪些差值会出现后，枚举$mod$的倍数是否有在差值中出现就可以了。

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
/* vegetable1024 | oi-liu.com | Maybe Lovely? */

#include <bits/stdc++.h>
#define maxn 2000005
#define MAX 500005
#define PI acos(-1.0)
using namespace std;
struct Complex{
    double x, y;
    Complex(double _x = 0.0, double _y = 0.0){
        x = _x; y = _y;
    }
    Complex operator + (const Complex &b) const{
        return Complex(x + b.x, y + b.y);
    }
    Complex operator - (const Complex &b) const{
        return Complex(x - b.x, y - b.y);
    }
    Complex operator * (const Complex &b) const{
        return Complex(x * b.x - y * b.y, x * b.y + y * b.x);
    }
};
void change(Complex y[], int len){
    int i, j, k;
    for(int i = 1, j = len / 2; i < len - 1; i++){
        if(i < j)    swap(y[i], y[j]);
        k = len / 2;
        while(j >= k){
            j -= k;
            k /= 2;
        }
        if(j < k)    j += k;
    }
}
void fft(Complex y[], int len, int inv){
    change(y, len);
    for(int h = 2; h <= len; h <<= 1){
        Complex wn(cos(-inv * 2 * PI / h), sin(-inv * 2 * PI / h));
        for(int j = 0; j < len; j += h){
            Complex w(1, 0);
            for(int k = j; k < j + h / 2; k++){
                Complex u = y[k];
                Complex t = w * y[k + h / 2];
                y[k] = u + t;
                y[k + h / 2] = u - t;
                w = w * wn;
            }
        }
    }
    if(inv == -1)
        for(int i = 0; i < len; i++)
            y[i].x /= len;
}
int n, num[maxn], vis[maxn], len = (1 << 20);
Complex a[maxn], b[maxn];
int main(void)
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &num[i]);
        a[num[i]].x = 1;
        b[MAX - num[i]].x = 1;
    }
    fft(a, len, 1);
    fft(b, len, 1);
    for(int i = 0; i < len; i++)
        a[i] = a[i] * b[i];
    fft(a, len, -1);
    for(int i = 0; i <= len; i++)
    {
        int x = (int)(a[i].x + 0.5);
        if(x > 0)
            vis[abs(MAX - i)] = 1;
    }
    //这样也是可以的
    /*
    for(int i = MAX; i <= len; i++)
    {
        int x = (int)(a[i].x + 0.5);
        if(x > 0)
            vis[i - MAX] = 1;
    }
    */
    for(int i = n; i <= MAX; i++)
    {
        bool flag = true;
        for(int j = i; j <= MAX; j += i)
            if(vis[j])
            {
                flag = false;
                break;
            }
        if(flag)
        {
            printf("%d\n", i);
            break;
        }
    }
    //putchar('\n');
    return 0;
}