没想清就写->细节爆炸

1333A Little Artem

记$W$为相邻至少有一个黑格的白格数，$B$为相邻至少有一个白格的黑格数，给出一种涂色使$B=W+1$成立。

就是交叉放，分个小类讨论下，$O(nm)$。
一看觉得很简单，决定手模，然后 （+1）

A.cpp
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
#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        if (n * m & 1) {
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < m; ++j)
                    cout << "BW"[(i + j) & 1];
                cout << endl;
            }
        } else {
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < m; ++j)
                    cout << "WB"[(i + j) & 1 | (i==0&&j==0)];
                cout << endl;
            }
        }
    }
    return 0;
}

1333B Kind Anton

一个仅有$0,-1,1$构成的序列$a$，现在可以把前面的一个数加到这个数上，问能不能通过若干次这样的操作得到序列$b$。

就是看前面有没有$+1，-1$，$O(n)$。

B.cpp
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
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;

int a[N], b[N], has[N][2];

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];
            has[i][0] = has[i - 1][0];
            has[i][1] = has[i - 1][1];
            if (a[i] > 0) has[i][0] = 1;
            else if (a[i] < 0) has[i][1] = 1;
        }
        for (int i = 1; i <= n; ++i) {
            cin >> b[i];
        }
        int f = 1;
        for (int i = n; i > 0; --i) {
            if (b[i] == a[i]) continue;
            else if (b[i] < a[i]) {
                if (!has[i - 1][1]) {
                    f = 0;
                    break;
                }
            } else if (!has[i - 1][0]) {
                f = 0;
                break;
            }
        }
        if (f) puts("YES");
        else puts("NO");
    }
    return 0;
}

1333C Eugene and an array

有一个序列，求有多少个子段，它的子段内没有求合为$0$的段。

从前往后枚举$r$也就是右边界，找到最右的左边界$l$，使得$\sum_{j=l}^{r}a_j = 0$,可以通过前缀和找。
那么这样可以得到很多对$(l,r)$，左右任选都是不合法的答案，也就是$l\times (n-l+1)$。很明显这样有重复，因此稍微（+4，写到最后发现一开始斥飞了）容斥一下。
可以发现多算的部分就是$min(l_i,l-j)\times (n +1 -max(r_i,r_j))$，那么按$r$排序，每次保留最右的$l$的答案就好了，具体看代码吧，$O(n\log n)$。

C.cpp
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
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, f = 0;
    cin >> n;
    map<ll, ll> mp;
    ll pre = 0, ans = 0, l = 1;
    mp[0] = 0;
    for (int i = 1, t; i <= n; ++i) {
        cin >> t;
        pre += t;
        if (mp.count(pre)) {
            if (mp[pre] + 1 >= l) {
                if (f) ans -= min(mp[pre] + 1, l) * (n - i + 1);
                l = mp[pre] + 1;
                ans += l * (n - i + 1);
                f = 1;
            }
        }
        mp[pre] = i;
    }
    ans = ll(n + 1) * n / 2 - ans;
    cout << ans << endl;
    return 0;
}

1333D Challenges in school №41

有一堆小孩在一列，向左或向右看，每次可以操作一对相互看的小孩反向，问能否精确$k$轮使得没有一对小孩可以继续操作。

因为题目保证答案存在就一定在$n^2$内，那么就可以暴力预处理，每轮把可以操作的位置都操作，到最后一定在$n^2$内结束。
然后就变成了构造题，一共操作$mx$个位置，最少操作$cnt$轮，那么此外的$k$都是无法构造出来的，从尾开始“伸展”是一种比较简单的写法（我自己的写法+3…）。

D.cpp
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
#include <bits/stdc++.h>
using namespace std;
const int N = 3e6 + 5;

vector<int> ans[N];

int main() {
    int n, k;
    cin >> n >> k;
    vector<char> c(n);
    for (char &t : c) cin >> t;
    int cnt = 0, mx = 0;
    while (1) {
        int f = 0;
        for (int i = 0; i < n; ++i) {
            if (c[i] == 'R' && c[i + 1] == 'L') {
                ans[cnt].emplace_back(i + 1);
                swap(c[i], c[i + 1]);
                ++i; ++mx; f = 1;
            }
        }
        if (!f) break;
        else ++cnt;
    }

    if (mx < k || k < cnt) cout << -1 << endl;
    else {
        --cnt;
        for (int i = k - 1; i > 0; --i) {
            if (ans[cnt].empty()) --cnt;
            if (i == cnt) break;
            ans[i] = vector<int>{ans[cnt].back()};
            ans[cnt].pop_back();
        }
        for (int i = 0; i < k; ++i) {
            cout << ans[i].size() << ' ';
            for (int &j : ans[i]) 
                cout << j << ' ';
            cout << endl;
        }
    }
    return 0;
}

1333E Road to 1600

国际象棋车走四个方向，后走八个方向，对于一个棋盘，每次都走可达位置中权值最小的点，如果没位置可走就要花一代价跳跃至权值最小点，要求构造一个$n\times n$的矩阵，使得后走完所有点的代价比车大。

可以通过先构造一个小的矩阵使得 后的代价$>$车的代价，然后剩下的构造一条路使得二车代价一样即可，$O(nm)$。
这里构造的是：

E.cpp
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
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    if (n < 3) {
        cout << -1 << endl;
        return 0;
    }
    vector<vector<int>> ans(n + 1, vector<int> (n + 1));
    int cnt = n * n;
    ans[2][3] = cnt--; ans[1][1] = cnt--; ans[2][1] = cnt--;
    ans[3][1] = cnt--; ans[1][2] = cnt--; ans[2][2] = cnt--;
    ans[3][2] = cnt--; ans[3][3] = cnt--; ans[1][3] = cnt--;
    for (int i = 4; i <= n; ++i) {
        if (i % 2 == 0) {
            for (int j = 1; j <= i; ++j) ans[j][i] = cnt--;
            for (int j = i - 1; j > 0; --j) ans[i][j] = cnt--;
        } else {
            for (int j = 1; j <= i; ++j) ans[i][j] = cnt--;
            for (int j = i - 1; j > 0; --j) ans[j][i] = cnt--;
        }
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j)
            cout << ans[i][j] << ' ';
        cout << endl;
    }
    return 0;
}

1333F Kate and imperfection

对于$1…n$个数，选择一个子序列，他的权值为序列里最大的$gcd(i,j),(i!=j)$，现在问子序列长度从$2…n$的全部答案。

很明显和质数有点关系

  • 如果答案是$1$的话，那么所有的数都必须是互质的，这样一直选$1$和质数是最多的；
  • 如果是$2$的话，那么最多选$1$和质数和$4$；
  • 如果是$3$的话，那么最多选$1$和质数和$4$，以及$6,9$；
  • 也就是说，对于答案为$x$，那么序列最长长度和$x$以及$\leq x$的质数有关。
    那么就可以操作了，直接按下面代码贪就好了，$O(n\log n)$
F.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) {
        for (int j = i * 2; j <= n; j += i)
            a[j] = i;
    }
    sort(a.begin(), a.end());
    for (int i = 2; i <= n; ++i) {
        cout << a[i] << ' ';
    }
    cout << endl;
    return 0;
}