A. Connection and Disconnection
题目链接：https://atcoder.jp/contests/agc039/tasks/agc039_a
题目大意：字符串 $S$ 放置 $K$ 次，对字符串修改最少的字符满足使相邻字符不同。
做法
我的做法是找到所有相同的字符构成的连续段，然后统计答案，开头和结尾特判一下就行了。
时间复杂度：$O(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
| #include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e2 + 5;
void get_char_array(char *s){
static char ss[N];
cin >> ss;
memcpy(s + 1, ss, sizeof(char) * (strlen(ss) + 1));
}
char st[N];
int n;
LL K;
int main(){
get_char_array(st);
n = strlen(st + 1);
cin >> K;
int len0 = 0;
LL ans = 0ll;
for(int l = 1; l <= n; l++){
int r = l;
while(r < n && st[r + 1] == st[l]) r++;
if(l > 1 && r < n) ans += (r - l + 1) / 2 * K;
else if(l == 1 && r < n){
len0 = r - l + 1;
if(st[1] != st[n]) ans += (r - l + 1) / 2 * K;
else ans += (r - l + 1) / 2;
}
else if(l > 1 && r == n){
if(st[1] != st[n]) ans += (r - l + 1) / 2 * K;
else ans += (r - l + 1) / 2 + (r - l + 1 + len0) / 2 * (K - 1);
}
else ans += n * K / 2;
l = r;
}
cout << ans << "\n";
return 0;
}
|
其余做法
看到一个很有意思的搞法：先统计 $S$ 的答案，再统计 $SS$ 的答案，两者相减得到在已经有字符串的情况下再添加字符串的贡献。
需要特判所有字符相同的情况。
这个做法感觉很牛啊。
B. Graph Partition
题目链接：https://atcoder.jp/contests/agc039/tasks/agc039_b
题目大意：给你一张无向图，将点分成尽可能多的部分满足任何一条边只会出现在相邻两个部分之间。
我的做法
首先注意到一个事情，这个图没有奇环是这个图有解的充要条件。（证明方法就是沿着奇数走一圈）
换个角度来看：题目的要求等价于相邻两个点的部分编号奇偶性不同，由这一点可以很自然的联想到二分图染色，从而知道如果二分图染色失败则无解，从而自然的想到有解的充要条件。
然后发现，$x\to y$ 的任何一条路径的边数都一定 $\ge |id_x-id_y|$ 。
我们不妨考虑从部分 $1$ 的角度来看，由于这个图是联通的，设 $h_x$ 表示 $1$ 中的点到 $x$ 的最短路，那么 $id_x\le h_x+1$ 。
我们不妨直接拉满，就设置一个中心 $st$ ，$id_x=h_x+1$，可以发现，在二分图上，这样子划分是一定合法的。
而且不难证明最优解一定长这样。
直接枚举 $st$ 就行了。
时间复杂度：$O(n^3)$ 。
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<bits/stdc++.h>
using namespace std;
const int N = 2e2 + 5;
void get_char_array(char *s){
static char ss[N];
cin >> ss;
memcpy(s + 1, ss, sizeof(char) * (strlen(ss) + 1));
}
int n;
char st[N][N];
struct node{
int y, next;
}a[N * N]; int len, las[N];
void ins(int x, int y){a[++len] = {y, las[x]}; las[x] = len;}
int h[N];
int bfs(int spos){
queue<int> q;
q.push(spos);
memset(h, 0, sizeof(h));
h[spos] = 1;
int laspos = spos;
while(!q.empty()){
int x = q.front();
laspos = x;
q.pop();
for(int k = las[x]; k; k = a[k].next){
int y = a[k].y;
if(!h[y]){
h[y] = h[x] + 1;
q.push(y);
}
else if((h[y] & 1) == (h[x] & 1)) return -1;
}
}
return h[laspos];
}
int main(){
cin >> n;
for(int i = 1; i <= n; i++){
get_char_array(st[i]);
for(int j = 1; j <= n; j++){
if(st[i][j] == '1') ins(i, j);
}
}
int ans = -1;
for(int i = 1; i <= n; i++) ans = max(ans, bfs(i));
cout << ans << "\n";
return 0;
}
|
C. Division by Two with Something
题目链接：https://atcoder.jp/contests/agc039/tasks/agc039_c
题目大意：给 $n,X(X<2^{n})$ ，求 $[0,X]$ 的权值和，权值定义为一个数字 $x$ 经过下述操作最少花几次回到自己。
操作：$x$ 是奇数就除二向下取整，偶数就除二后，加上 $2^{n-1}$ 。
我的做法
注意到一个事情，上面这个操作等价于把一个 $n$ 位二进制的最低位翻转放到最高位。
于是，所有数字都一定会在 $2n$ 次操作后回到自己。
注意到，如果存在 $x,y(x<y)$ 都能让 $x$ 回到自己，那么 $y-x$ 也可以，因此存在一个最小的次数 $ans$ 整除所有可行的次数，且 $ans$ 的所有倍数都可行。
也就是答案一定是 $2n$ 的因子。
又注意到 $n$ 次后一定回不到自己，因此 $ans$ 是 $2n$ 的因子而不是 $n$ 的因子。
注意到 $\frac{ans}{2}$ 整除于 $n$ ，我们不妨以 $\frac{ans}{2}$ 审视 $S$ ，可以发现 $S$ 可以写成 $010101010…0$ 。
即在 $len|n$ 的条件下，$S$ 可以以 $len$ 为单位写成 $010101…0$ 等价于 $S$ 在 $2len$ 后会回到自己。
综上可以得到以 $len$ 为单位的 $0101…0$ 的字符串数量等于 $ans|2len$ 的字符串数量。
容斥一下就可以得到每个 $ans$ 对应的字符串数量了。
时间复杂度：$O(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
| #include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod = 998244353;
const int N = 2e5 + 5;
void get_char_array(char *s){
static char ss[N];
cin >> ss;
memcpy(s + 1, ss, sizeof(char) * (strlen(ss) + 1));
}
char st[N], t[N];
int n;
LL solve(int len){
LL now = 0ll;
for(int i = 1; i <= len; i++) now = (now * 2 + st[i] - '0') % mod;
int pos = 1, type = 0;
for(int i = 1; i <= n; i++){
t[i] = ((st[pos] - '0') ^ type) + '0';
if(pos == len) pos = 1, type ^= 1;
else pos++;
}
for(int i = 1; i <= n; i++){
if(t[i] < st[i]) return (now + 1) % mod;
else if(t[i] > st[i]) return now;
}
return (now + 1) % mod;
}
LL cnt[N];
int main(){
cin >> n;
get_char_array(st);
LL ans = 0;
for(int i = 1; i <= n; i++){
if(n % i == 0 && n % (i * 2) != 0){
cnt[i] = (cnt[i] + solve(i)) % mod;
for(int k = 2; k <= n / i; k++){
if(n / i % k == 0) cnt[i * k] = (cnt[i * k] - cnt[i] + mod) % mod;
}
ans += cnt[i] * i * 2;
ans %= mod;
}
}
cout << ans << "\n";
return 0;
}
|
