第一要务是收心,不要去在意杂事,不担心以后,最后几个月专心做竞赛,不留下遗憾。

8.25~8.26 Codeforces Round #767 (Div. 1)

1628A Meximum Array

对每个位置分别选。要使得字典序最大,那么第一要务是保证当前选的 $MEX$ 尽可能大。然后,相同值之中,我们选最左的那个,以此来保证在选取 $MEX$ 相同的条件下,整个 $b$ 的长度尽可能长。

于是我们可以用一个队列按顺序存各个数出现的位置,模拟一下保证这两个条件。

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
#include <bits/stdc++.h>
#define int long long
#define lson k << 1
#define rson k << 1 | 1
using namespace std;
const int maxn = 2e5 + 10;
const int mod = 998244353;
int a[maxn];
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t = 1;
cin >> t;
while (t--) {
int n;
cin >> n;
map<int, queue<int>> pos;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
pos[a[i]].push(i);
}
vector<int> b;
for (int i = 1; i <= n; ++i) {
int st = i;
int mex = -1;
// 寻找 mex+1,直到没有.
while (!pos[mex + 1].empty()) {
if (pos[mex + 1].front() < st) {
pos[mex + 1].pop();
continue;
}
if (pos[mex + 1].front() <= i) {
while (!pos[mex + 1].empty() && pos[mex + 1].front() <= i) {
pos[mex + 1].pop();
}
mex++;
continue;
}
i = pos[mex + 1].front();
pos[mex + 1].pop();
mex++;
}
b.push_back(mex + 1);
}
cout << b.size() << endl;
for (int i = 0; i < b.size(); ++i) {
cout << b[i] << " ";
}
cout << endl;
}
return 0;
}

1628B Peculiar Movie Preferences

水题,每个字符串的长度都小于等于 3,首先单一个字符串自己组成回文的情况先处理掉,然后剩下的情况字符串数量都 $\geq2$.

假设我们能够造出一个使用的字符串数量为 $x\geq2$ 的回文串,那么最左边和最右边是一定可以构造成一个回文串的。如果最左边最右边长度相等,那么他们拼起来肯定是回文;如果长度不等,一个是 2,一个是 3,那么最前面两个和最后面两个肯定也相等,总长度 5,还是可以构成回文。

所以只需要对每个串看前面存不存在与他构成回文的串就行啦,字符串哈希或者 map 即可过。

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
#include <bits/stdc++.h>
#define int long long
#define lson k << 1
#define rson k << 1 | 1
using namespace std;
const int maxn = 2e5 + 10;
const int mod = 998244353;
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t = 1;
cin >> t;
while (t--) {
// 17576 - 780.
// 规模最多为 2???

int n;
cin >> n;
map<string, int> mp;
map<string, int> mp32;
bool flag = 0;
for (int i = 1; i <= n; ++i) {
string s;
cin >> s;
if (flag) continue;
mp[s]++;
if (s.size() == 1) {
flag = 1;
}
else if (s.size() == 2 && s[0] == s[1]) {
flag = 1;
}
else if (s.size() == 2) {
reverse(s.begin(), s.end());
if (mp.count(s) || mp32.count(s)) {
flag = 1;
}
}
else if (s.size() == 3) {
string tmp;
tmp += s[1];
tmp += s[2];
reverse(tmp.begin(), tmp.end());
if (mp.count(tmp)) {
flag = 1;
continue;
}
tmp.clear(); tmp += s[0], tmp += s[1];
mp32[tmp]++;
reverse(s.begin(), s.end());
if (mp.count(s)) {
flag = 1;
}
}
}
cout << (flag ? "YES" : "NO") << endl;
}
return 0;
}

1628C Grid Xor

纯构造题…尝试了构造各个位置异或次数为奇数的方法,和不同的组合来容斥求答案的思路,越弄越复杂,但是其实很简单就能够造出每个位置被异或一次的方法……

按各个位置的奇偶性分别去手画几下即可(国际象棋棋盘染色),奇偶性不同的位置是互不影响的。具体可以参考洛谷上的题解。

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
#include <bits/stdc++.h>
#define int long long
#define lson k << 1
#define rson k << 1 | 1
using namespace std;
const int maxn = 1005;
int a[maxn][maxn];
int f1[maxn][maxn];
int f2[maxn][maxn];
bool v[maxn][maxn];
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t = 1;
cin >> t;
for (int i = 1; i <= 1000; ++i) {
for (int j = 1; j <= 1000; ++j) {
if ((i + j) & 1) {
f1[i][j] = 1, f2[i][j] = 0;
}
else f2[i][j] = 1, f1[i][j] = 0;
}
}
while (t--) {
int n;
cin >> n;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
cin >> a[i][j];
v[i][j] = 0;
}
}
int ans = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (!f1[i][j]) continue;
if (i > 1 && v[i - 1][j]) continue;
if (j > 1 && v[i][j - 1]) continue;
if (i < n && v[i + 1][j]) continue;
if (j < n && v[i][j + 1]) continue;
v[i - 1][j] = v[i][j - 1] = v[i + 1][j] = v[i][j + 1] = 1;
ans ^= a[i][j];
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (!f2[i][j]) continue;
if (i > 1 && v[i - 1][j]) continue;
if (j > 1 && v[i][j - 1]) continue;
if (i < n && v[i + 1][j]) continue;
if (j < n && v[i][j + 1]) continue;
v[i - 1][j] = v[i][j - 1] = v[i + 1][j] = v[i][j + 1] = 1;
ans ^= a[i][j];
}
}
cout << ans << endl;
}
return 0;
}

1628D1 Game on Sum (Easy Version)

由 $2000$ 数据范围很容易想到需要构造一个 $dp$ 状态。设 $dp_{i,j}$ 表示已经选择了 $i$ 个数字,其中 $j$ 次相加的答案。

但因为存在二元博弈,这个 $dp$ 既不是最大值也不是最小值。考虑单独的每一步:
如果 Alice 给的数较大,那么 Bob 将会选择减。但若 Alice 给的数小,那么 Bob 在次数还没加够时可以选择加。因为 Bob 是在 Alice 给数之后选的,他会将答案最小化。

所以有

那么 Alice 现在可以决定 $x$,她会使得答案尽可能大。在和不变的条件下让二者最小值最大,因为显然有 $dp_{i-1,j}\geq dp_{i-1,j-1}$,且差值一定不大于 $k$,所以我们可以选择一个值使得 $dp_{i-1,j}-x=dp_{i-1,j-1}+x=avr$,这样就是最优的选择。

所以转移方程为

但要注意有个边界条件是不同的,即 $i=j$ 时,因为 Bob 只能选择加,所以 Alice 会最大化答案为 $ik$.

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 int long long
#define lson k << 1
#define rson k << 1 | 1
using namespace std;
const int maxn = 2005;
const int mod = 1e9 + 7;
int dp[maxn][maxn];
int fpow(int x, int k) {
int ans = 1;
while (k) {
if (k & 1) {
ans = (ans * x) % mod;
}
x = (x * x) % mod;
k >>= 1;
}
return ans;
}
int inv(int x) {
return fpow(x, mod - 2);
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t = 1;
cin >> t;
int i2 = inv(2);
while (t--) {
int n, m, k;
cin >> n >> m >> k;
for (int i = 0; i <= n; ++i) {
dp[i][i] = i * k % mod;
}
dp[0][0] = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (i == j) continue;
dp[i][j] = ((dp[i - 1][j] + dp[i - 1][j - 1]) * i2) % mod;
}
}
cout << dp[n][m] << endl;
}
return 0;
}

1628D2 Game on Sum (Hard Version)

范围扩大,由 D1 解法可知答案只与 $k$ 有关,故我们应该时可以找到一个公式的。

考虑各个 $dp$ 值对 $dp_{n,m}$ 的贡献,每个 $dp$ 值理应包括:

若干个 $dp_{1,1}$ 及其 $\frac{1}{2^x}$ 倍,若干个 $dp_{2,2}$ 及其 $\frac{1}{2^x}$ 倍……所有的 $dp$ 值都可以只通过 $dp_{i,i}$ 的贡献推出来。

那么 $dp_{i,i}$ 对 $dp_{n,m}$ 的贡献,每个来自 $dp_{i,i}$ 的分贡献一定是走的不同的路径,从 $dp_{i,i}$ 走到 $dp_{n,m}$,路径不同,长度相同,所以最后的分贡献值都一样。这是经典的走楼梯组合问题,走法为 $C_{n-i-1}^{m-i}$,每次都贡献了 $\frac{dp_{i,i}}{2^{n-i}}$. 全部求和即可。

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
#include <bits/stdc++.h>
#define int long long
#define lson k << 1
#define rson k << 1 | 1
using namespace std;
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
int f[maxn];
int pi[maxn];
int fpow(int x, int k) {
int ans = 1;
while (k) {
if (k & 1) {
ans = (ans * x) % mod;
}
x = (x * x) % mod;
k >>= 1;
}
return ans;
}
int inv(int x) {
return fpow(x, mod - 2);
}
void pre(int n) {
pi[0] = pi[1] = 1;
for (int i = 1; i <= n; ++i) {
pi[i] = (pi[i - 1] * i) % mod;
}
}
int C(int n ,int m) {
return ((pi[n] * inv(pi[m]) % mod) * inv(pi[n - m])) % mod;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
pre(maxn - 5);
int t = 1;
cin >> t;
while (t--) {
int n, m, k;
cin >> n >> m >> k;
if (m == 1) {
cout << (inv(fpow(2, n - 1)) * k) % mod << endl;
continue;
}
else if (n == m) {
cout << m * k % mod << endl;
continue;
}
else if (m == 0) {
cout << 0 << endl;
continue;
}
int ans = 0;
for (int i = 1; i <= m; ++i) {
int x = C(n - i - 1, m - i);
int y = fpow(inv(2), n - i);
ans = (ans + (i * ((x * y) % mod)) % mod) % mod;
}
cout << ans * k % mod << endl;
}
return 0;
}

8.27~8.28 吉林省赛复现

四天三个训练赛,多补补题吧。

The 15th Jilin Provincial Collegiate Programming Contest I. Nim Game

复习 Nim 博弈,其条件是集合各数异或和为 0 即必败,否则必胜。

那么嘉然小姐想要赢,必定是集合中存在一个子集,其异或和为 0.

我们可以用线性基来判断。每次将一个数加入线性基,如果加入时更新了 $a_0$,说明现在有异或和为 0 且非空的子集了。又因为位数不会超过 $32$,所以当至少有 $32$ 个数时,线性基一定会更新到 $a_0$,一定存在一个异或和为 0 的子集,不用判断。小于 $32$ 的暴力判断即可。

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
#include <bits/stdc++.h>
#define endl '\n'
#define lson k << 1
#define rson k << 1 | 1
#pragma GCC optimize(3)
#define int long long
using namespace std;
const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;
struct node {
int l, r, sum, tag;
}a[maxn << 2];
int num[maxn];
void pushup(int k) {
a[k].sum = a[lson].sum + a[rson].sum;
}
void build(int k, int l, int r) {
a[k].l = l, a[k].r = r;
if (l == r) {
a[k].l = l, a[k].r = r;
a[k].sum = num[l];
return;
}
int mid = l + r >> 1;
build(lson, l, mid);
build(rson, mid + 1, r);
pushup(k);
}
void pushdown(int k) {
if (!a[k].tag) return;
a[lson].sum += a[k].tag * (a[lson].r - a[lson].l + 1);
a[lson].tag += a[k].tag;
a[rson].sum += a[k].tag * (a[rson].r - a[rson].l + 1);
a[rson].tag += a[k].tag;
a[k].tag = 0;
}
void add(int k, int l, int r, int x) {
if (a[k].l > r || a[k].r < l) return;
if (a[k].l >= l && a[k].r <= r) {
a[k].sum += x * (a[k].r - a[k].l + 1);
a[k].tag += x;
return;
}
pushdown(k);
add(lson, l, r, x);
add(rson, l, r, x);
}
int b[33];
int insert(int x) {
for (int i = 32; i >= 0; --i) {
if (!(x & (1 << i))) continue;
if (!b[i]) {
b[i] = x;
break;
}
x ^= b[i];
}
return x;
}
int query(int k, int x) {
if (a[k].l > x || a[k].r < x) return 0;
if (a[k].l == a[k].r && a[k].l == x) return a[k].sum;
pushdown(k);
return query(lson, x) + query(rson, x);
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; ++i) cin >> num[i];
build(1, 1, n);
for (int i = 1; i <= m; ++i) {
int op, l, r, x;
cin >> op >> l >> r;
if (op == 1) {
cin >> x;
add(1, l, r, x);
}
else {
if (r - l + 1 >= 33) {
cout << "Yes" << endl;
continue;
}
else {
bool flag = 1;
memset(b, 0, sizeof(b));
for (int i = l; i <= r; ++i) {
int y = query(1, i);
y = insert(y);
if (!y) {
flag = 0;
break;
}
}
cout << (flag ? "No" : "Yes") << endl;
}
}
}
return 0;
}

8.29~8.30 Educational Codeforces Round 134

1721D Maximum AND

贪心,优先保证高位能异或为 1.

为了 $a,b$ 异或为1,我们将 $a,b$ 分组。假设现在考虑到了第 $i$ 位,那么 $a$ 中第 $i$ 位为 1 的和 $b$ 中第 $i$ 位为 0 的分一组,反之亦然。如果分完组后,$a_i=1$ 和 $b_i=0$ 的数个数是相同的,说明这个分组是有效的,不会出现多余的数,于是我们分组继续下去就可以。如果出现了分不齐的情况,就说明在保证某几个高位能够达到 $1$ 的条件下,我们是无法保证这一位为 1 的,所以不进行分组,直接判断下一位。

(场上没有注意将大小为 0 的分组剔除,导致 vector 爆了,还不知道错在哪)

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<bits/stdc++.h> 
#define int long long
using namespace std;
const int maxn = 2e5 + 10;
const int mod = 998244353;
int xx;
struct pvv {
vector<int> a, b;
};
vector<pvv> v, tmp;
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--) {
xx = 0x7fffffff;
int n;
cin >> n;
vector<int> a, b;
for (int i = 1; i <= n; ++i) {
int x;
cin >> x;
a.push_back(x);
}
for (int i = 1; i <= n; ++i) {
int x;
cin >> x;
b.push_back(x);
}
v.push_back({a, b});
for (int j = 30; j >= 0; --j) {
tmp.clear();
bool flag = 1;
for (int i = 0; i < v.size(); ++i) {
pvv a0b1, a1b0;
for (int k = 0; k < v[i].a.size(); ++k) {
if (v[i].a[k] & (1 << j)) a1b0.a.push_back(v[i].a[k]);
else a0b1.a.push_back(v[i].a[k]);
}
for (int k = 0; k < v[i].b.size(); ++k) {
if (v[i].b[k] & (1 << j)) a0b1.b.push_back(v[i].b[k]);
else a1b0.b.push_back(v[i].b[k]);
}
if (a0b1.a.size() == a0b1.b.size()) {
if (!a0b1.a.empty()) {
tmp.push_back(a0b1);
}
if (!a1b0.a.empty()) {
tmp.push_back(a1b0);
}
}
else {
xx -= (1 << j);
flag = 0;
break;
}
}
if (flag)
v = tmp;
}
cout << xx << endl;
v.clear();
}
return 0;
}

8.31~9.1 Codeforces Round #698 (Div. 1)

A. Nezzar and Board

把所有的数放在数轴上,可以发现任取两个数,通过不断地往集合中加 $2x-y$,最后得到的数的间隔不会大于 $|x-y|$.

所以通过这两个数能构造出所有以 $x$ 或者 $y$ 为某项,公差为 $\gcd(x,y)$ 的等差数列。

扩展到所有元素可知,所有元素构造出来的应该是以某个 $a_i$ 为首项,公差为 $\gcd(a_1,a_2,…,a_n)$ 的等差数列。

先求出 $g=\gcd(a_1,a_2,…,a_n)$,然后枚举各个 $a_i$,看是否 $(k-a_i)\%g=0$.

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
#include <bits/stdc++.h>
// #pragma GCC optimize(3)
// #define endl '\n'
#define lson k << 1
#define rson k << 1 | 1
#define int long long
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
int a[maxn];
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while (t--) {
// k = 2x - y
// 2(x1a1 + x2a2 + ... + xnan) - (y1a1 + y2a2 + ...)
// = (2x1 - y1)a1 + (2x2 - y2)a2 + ...
// x + d = k --> d = m * |x - y|.
// k - x = d = m * |x - y|
// (k - x) % |x - y| = 0
// x, y 从集合中任取。
// 存在整数列使得 k - ax = x1(a1 - a2) + x2(a2 - a3) + ... + x_{n-1}(a_{n-1} - an)
// xi \in integer
// 存在互质的数时一定yes... --> gcd = 1
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
int g = a[2] - a[1];
for (int i = 3; i <= n; ++i) {
g = __gcd(a[i] - a[i - 1], g);
}
bool flag = 0;
for (int i = 1; i <= n; ++i) {
if ((k - a[i]) % g == 0) {
flag = 1;
break;
}
}
cout << (flag ? "YES" : "NO") << endl;
}
return 0;
}

B. Nezzar and Binary String

意外的简单题,但是卡壳了一会。

只要逆向考虑就能发现,因为每次操作都是要求 strictly less than half of the characters,所以其实倒过来的修改是固定,没有选择的。一开始没注意严格更少,还想了一会二者相等的情况。。

所以逆向考虑,操作用线段树维护即可,遇到数量相等的情况直接 break 输出 $NO$,最后 $n\log n$ 判断一下最终得到的字符串,再比较一下。

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
#include <bits/stdc++.h>
// #pragma GCC optimize(3)
// #define endl '\n'
#define lson k << 1
#define rson k << 1 | 1
#define int long long
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
int ql[maxn], qr[maxn];
struct node {
int l, r;
int cnt0, cnt1;
int tag;
}a[maxn << 2];
string s, f;
void pushup(int k) {
a[k].cnt0 = a[lson].cnt0 +a[rson].cnt0;
a[k].cnt1 = a[lson].cnt1 + a[rson].cnt1;
}
void build(int k, int l, int r) {
a[k].l = l, a[k].r = r;
a[k].tag = -1;
if (l == r) {
if (f[l] == '0') a[k].cnt0 = 1, a[k].cnt1 = 0;
else a[k].cnt1 = 1, a[k].cnt0 = 0;
return;
}
int mid = l + r >> 1;
build(lson, l, mid);
build(rson, mid + 1, r);
pushup(k);
}
void pushdown(int k) {
if (a[k].tag == -1) return;
a[lson].cnt0 = (a[lson].r - a[lson].l + 1) * (!a[k].tag);
a[rson].cnt0 = (a[rson].r - a[rson].l + 1) * (!a[k].tag);
a[lson].cnt1 = (a[lson].r - a[lson].l + 1) * a[k].tag;
a[rson].cnt1 = (a[rson].r - a[rson].l + 1) * a[k].tag;
a[lson].tag = a[rson].tag = a[k].tag;
a[k].tag = -1;
}
void change(int k, int l, int r, int x) {
if (a[k].l > r || a[k].r < l) return;
if (a[k].l >= l && a[k].r <= r) {
if (x) {
a[k].tag = 1;
a[k].cnt1 = a[k].r - a[k].l + 1;
a[k].cnt0 = 0;
}
else {
a[k].tag = 0;
a[k].cnt0 = a[k].r - a[k].l + 1;
a[k].cnt1 = 0;
}
return;
}
pushdown(k);
change(lson, l, r, x);
change(rson, l, r, x);
pushup(k);
}
int query0(int k, int l, int r) {
if (a[k].l > r || a[k].r < l) return 0;
if (a[k].l >= l && a[k].r <= r) return a[k].cnt0;
pushdown(k);
return query0(lson, l, r) + query0(rson, l, r);
}
int query1(int k, int l, int r) {
if (a[k].l > r || a[k].r < l) return 0;
if (a[k].l >= l && a[k].r <= r) return a[k].cnt1;
pushdown(k);
return query1(lson, l, r) + query1(rson, l, r);
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while (t--) {
int n, q;
cin >> n >> q;
cin >> s >> f;
s = 'X' + s, f = 'X' + f;
for (int i = 1; i <= q; ++i) {
cin >> ql[i] >> qr[i];
}
build(1, 1, n);
bool flag = 1;
for (int i = q; i >= 1; --i) {
int cnt0 = query0(1, ql[i], qr[i]);
int cnt1 = query1(1, ql[i], qr[i]);
if (cnt0 == 0 || cnt1 == 0) continue;
if (cnt0 == cnt1) {
flag = 0;
break;
}
else if (cnt0 < cnt1) {
change(1, ql[i], qr[i], 1);
}
else change(1, ql[i], qr[i], 0);
}
string x;
x += "X";
for (int i = 1; i <= n; ++i) {
int c = query0(1, i, i);
if (c) x += "0";
else x += "1";
}
if (x != s) flag = 0;
cout << (flag ? "YES" : "NO") << endl;
}
return 0;
}

C. Nezzar and Nice Beatmap

我还手画有没有不可能的情况呢,一直画不出来。

结果题解给了一个非常简洁优雅的方法:每次选取未加入点中距离最远的点连起来。

于是就保证每个角都是锐角……太强了。

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 <bits/stdc++.h>
// #pragma GCC optimize(3)
// #define endl '\n'
#define lson k << 1
#define rson k << 1 | 1
#define int long long
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
struct point {
int x, y;
int id;
};
int dis(point p1, point p2) {
return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
}
vector<point> v1, v2;
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t;
t = 1;
while (t--) {
int n;
cin >> n;
v1.clear();
v1.resize(n);
for (int i = 0; i < n; ++i) {
cin >> v1[i].x >> v1[i].y;
v1[i].id = i + 1;
}
while (1) {
cout << v1[0].id << " ";
v2 = v1;
int mxi = 1, mxd = 0;
if (v1.size() == 1) break;
for (int i = 1; i < v2.size(); ++i) {
int d = dis(v2[0], v2[i]);
if (d > mxd) {
mxi = i, mxd = d;
}
}
v1.clear();
v1.push_back(v2[mxi]);
for (int i = 1; i < v2.size(); ++i) {
if (i == mxi) continue;
v1.push_back(v2[i]);
}
}
cout << endl;
}
return 0;
}

2022“杭电杯”中国大学生算法设计超级联赛(9)1008 Shortest Path in GCD Graph

  1. 任何两点间的距离都不大于 $2$,因为 $\gcd(1,i)=1$. 故答案只能是 $1$ 或者 $2$.

  2. 对于 $a,b$ 的距离,若 $\gcd(a,b)>1$,问题等价于找到满足 $\gcd(a,i)=1,\gcd(b,j)=1$ 的 $i,j$ 数量。

  3. 对于 $n\leq10^7$ 条件,任何数的素因子数量都不会超过 $15$ 个(大概 $12$ 个左右)。可以先筛出 $a$ 和 $b$ 的所有素因子,然后计算它们在 $[1,n]$ 内整除的数,再用总数减去即可。
  4. 要求 $a,b$ 的素因子在 $[1,n]$ 内整除的数。假设素因子是 $\{x_1,x_2,…,x_m\}$,例如 $x_1$ 在范围内的倍数有 $\lfloor \frac{n}{x_1} \rfloor$ 个,然后再算 $x_2,x_3,…$ 的,这里 $x_1,x_2$ 的倍数肯定有重合的部分,发现这是一个容斥模型,于是可以二进制枚举容斥,这样单次询问复杂度上限就是 $O(2^{12})$.

std 的容斥模板是好的(

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
#include <bits/stdc++.h>
#pragma GCC optimize(3)
// #define endl '\n'
using namespace std;
// #define int long long
const int mod = 998244353;
const int maxn = 1e7 + 10;
int st[maxn], primes[maxn / 10], f[maxn];
int n, q;
int cnt;
void ola(int n) {
for (int i = 2; i <= n; ++i) {
if (st[i] == 0) primes[++cnt] = i, f[i] = i;
for (int j = 1; primes[j] <= n / i; ++j) {
st[primes[j] * i] = 1;
f[primes[j] * i] = primes[j];
if (i % primes[j] == 0) break;
}
}
}
set<int> myset;
vector<int> vec;
void add(int x) {
while (x > 1) {
int y = f[x];
myset.insert(y);
while (x % y == 0) x /= y;
}
}
int ans = 0;
void dfs(int x, int s, int o) {
if (s > n) return;
if (x == vec.size()) {
ans += o * (n / s);
// ans = (ans + mod) % mod;
return;
}
dfs(x + 1, s, o);

// 不可写成乘法. 因为取个数就是要向下取整,不能不舍去.
if (s <= n / vec[x]) dfs(x + 1, s * vec[x], -o);
}
void solve(int x, int y) {
myset.clear(); vec.clear();
add(x), add(y);
for (auto &xx : myset) vec.push_back(xx);
ans = 0;
dfs(0, 1, 1);
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
// freopen("1008.in", "r", stdin);
// freopen("1008.out", "w", stdout);
int t;
// cin >> t;
t = 1;
while (t--) {
cin >> n >> q;
ola(n + 1);
for (int i = 1; i <= q; ++i) {
int u, v;
cin >> u >> v;
if (__gcd(u, v) == 1) {
cout << "1 1" << endl;
continue;
}
solve(u, v);
if (__gcd(u, v) == 2) ans++;
cout << 2 << " " << ans << endl;
}
}
return 0;
}

9.2~9.15

记忆丢失……这段时间补的题懒,没写题解

(其实是因为没 vp div. 1)

CCPC网络赛 H. Multiple Set

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
#include <bits/stdc++.h>
// #pragma GCC optimize(3)
// #define endl '\n'
using namespace std;
#define int __int128
const int mod = 998244353;
const int maxn = 2e5 + 10;
const int N = 1e7 + 5;
int L, R, K;
int st[N], primes[N / 4], f[N], cnt;
void ola(int n) {
for (int i = 2; i <= n; ++i) {
if (st[i] == 0) primes[cnt++] = i, f[i] = i;
for (int j = 0; primes[j] <= n / i; ++j) {
st[primes[j] * i] = 1;
f[primes[j] * i] = i;
if (i % primes[j] == 0) break;
}
}
}
set<int> fac;
vector<int> vec;
bool vis[N / 4];
void fj(int x) {
fac.clear();
for (int i = 0; i < cnt; ++i) {
if (x < primes[i]) break;
if (x % primes[i] == 0) {
fac.insert(primes[i]);
}
while (x % primes[i] == 0) x /= primes[i];
}
if (x > 1) fac.insert(x);
vec.clear();
for (auto &e : fac) {
vec.push_back(e);
}
memset(vis, 0, sizeof(vis));
}
int fpow(int x, int k) {
int ans = 1;
while (k) {
if (k & 1) {
ans = ans * x;
}
if (ans > K) return 0;
x = x * x;
k >>= 1;
}
return ans;
}
int ans = 0;
vector<int> res;
void dfs(int prod, int n, int lp, bool z) {
int l = (L / prod) + (L % prod > 0), r = R / prod;
int fp = fpow(2, r - l);
if (fp > 0 && z && K == fp * (l + r) * (r - l + 1) * prod / 2) ans++, res.push_back(prod);
if (lp >= vec.size()) return;
dfs(prod, n, lp + 1, 0);
for (int i = 1; prod * vec[lp] <= K; ++i) {
prod *= vec[lp];
dfs(prod, n + 1, lp + 1, 1);
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
signed t;
cin >> t;
ola(1e7 + 1);
while (t--) {
long long LL, RR, KK;
cin >> LL >> RR >> KK;
L = LL, R = RR, K = KK;
ans = 0;
fj(K);
res.clear();
dfs(1, 0, 0, 1);
if (res.size() == 0) {
cout << "No Solution" << endl;
}
else if (res.size() > 1e5) {
cout << "Too Many!" << endl;
}
cout << (long long)ans << endl;
sort(res.begin(), res.end());
for (auto &x : res) cout << (long long)x << " ";
cout << endl;
}
return 0;
}

9.16~9.17

【模板】普通平衡树(数据加强版) (替罪羊树实现)

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
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e7 + 10;
const double alpha = 0.7;
struct node {
int ch[2];
int cnt;
int val;
int sz;
}tree[maxn];
int cnt;
void pushup(int x) {
tree[x].sz = tree[tree[x].ch[0]].sz + tree[tree[x].ch[1]].sz + tree[x].cnt;
}
vector<int> fp, fn, fv;
int flat(int p) {
if (tree[p].ch[0]) {
flat(tree[p].ch[0]);
}
int id = fp.size();
if (tree[p].cnt) {
fp.push_back(p);
fv.push_back(tree[p].val);
fn.push_back(tree[p].cnt);
}
if (tree[p].ch[1]) {
flat(tree[p].ch[1]);
}
return id;
}
void rebuild(int p, int l = 0, int r = fp.size() - 1) {
int mid = l + r >> 1;
if (l < mid) {
tree[p].ch[0] = fp[(l + mid - 1) >> 1];
rebuild(tree[p].ch[0], l, mid - 1);
}
else tree[p].ch[0] = 0;
if (mid < r) {
tree[p].ch[1] = fp[(mid + 1 + r) >> 1];
rebuild(tree[p].ch[1], mid + 1, r);
}
else tree[p].ch[1] = 0;
tree[p].cnt = fn[mid];
tree[p].val = fv[mid];
pushup(p);
}
void check_and_rebuild(int p) {
pushup(p);
double lchp = 1. * tree[tree[p].ch[0]].sz / tree[p].sz;
if (lchp > alpha || lchp < 1 - alpha) {
fp.clear(), fv.clear(), fn.clear();
int id = flat(p);
swap(fp[id], fp[(fp.size() - 1) / 2]);
rebuild(p);
}
}
void __insert(int x, int p, int f, bool which) {
if (!p) {
p = tree[f].ch[which] = ++cnt;
tree[p].val = x;
tree[p].sz = tree[p].cnt = 1;
return;
}
check_and_rebuild(p);
if (x == tree[p].val) {
tree[p].cnt++;
tree[p].sz++;
return;
}
if (x < tree[p].val) {
__insert(x, tree[p].ch[0], p, 0);
}
if (x > tree[p].val) {
__insert(x, tree[p].ch[1], p, 1);
}
pushup(p);
}
void insert(int x) {
if (!cnt) {
tree[++cnt].cnt = 1;
tree[cnt].val = x;
tree[cnt].sz = 1;
return;
}
__insert(x, 1, 0, 0);
}
void __remove(int x, int p, int f, bool which) {
check_and_rebuild(p);
if (x < tree[p].val) {
__remove(x, tree[p].ch[0], p, 0);
}
else if (x > tree[p].val) {
__remove(x, tree[p].ch[1], p, 1);
}
else {
tree[p].cnt--;
tree[p].sz--;
}
pushup(p);
}
void remove(int x) {
// guarantee it exists
if (tree[1].val == x) {
tree[1].cnt--;
tree[1].sz--;
return;
}
__remove(x, 1, 0, 0);
}
int countl(int x, int p) {
if (x < tree[p].val) {
return tree[p].ch[0] ? countl(x, tree[p].ch[0]) : 0;
}
if (x > tree[p].val) return tree[tree[p].ch[0]].sz + tree[p].cnt + (tree[p].ch[1] ? countl(x, tree[p].ch[1]) : 0);
return tree[tree[p].ch[0]].sz;
}
int countg(int x, int p) {
if (x > tree[p].val) {
return tree[p].ch[1] ? countg(x, tree[p].ch[1]) : 0;
}
if (x < tree[p].val) return tree[tree[p].ch[1]].sz + tree[p].cnt + (tree[p].ch[0] ? countg(x, tree[p].ch[0]) : 0);
return tree[tree[p].ch[1]].sz;
}
int rk(int x) {
return countl(x, 1) + 1;
}
int __kth(int k, int p) {
if (tree[tree[p].ch[0]].sz >= k) {
return __kth(k, tree[p].ch[0]);
}
if (tree[tree[p].ch[0]].sz + tree[p].cnt < k) {
return __kth(k - tree[tree[p].ch[0]].sz - tree[p].cnt, tree[p].ch[1]);
}
return tree[p].val;
}
int kth(int k) {
return __kth(k, 1);
}
int pre(int x) {
int r = countl(x, 1);
return __kth(r, 1);
}
int suc(int x) {
int r = tree[1].sz - countg(x, 1) + 1;
return __kth(r, 1);
}
signed main()
{
// freopen("test.in", "r", stdin);
ios::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
int x;
cin >> x;
insert(x);
}
int last = 0, op, x;
int ans = 0;
for (int i = 1; i <= m; ++i) {
cin >> op >> x;
x ^= last;
if (op == 1) insert(x);
else if (op == 2) remove(x);
else if (op == 3) {
last = rk(x);
ans ^= last;
}
else if (op == 4) {
last = kth(x);
ans ^= last;
}
else if (op == 5) {
last = pre(x);
ans ^= last;
}
else if (op == 6) {
last = suc(x);
ans ^= last;
}
}
cout << ans << endl;
return 0;
}