EducationalCodeforcesRound51

EducationalCodeforcesRound51

A.Vasya And Password

题目大意 : 给你一个长度为\(N(N \ge 6)\)包含大写, 小写字母, 和数字的字符串(可能不会全部包含), 要求你将字符串改成三种都包含的字符串的最小花费, 定义花费为 : 修改的两个字符串的距离

题解 :

  • 如果包含上述字符的任意两种, 就将其中字符集大于\(2\)的其中任意一个字符修改成你所需要的
  • 如果只包含一种, 就将任意相邻的字符改为你所需要的两个字符

可以证明这样修改花费一定最小

代码 :

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
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e3 + 5;

inline int read() {
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) {u = u * 10 + ch - 48; ch = getchar();} return u * f;
}

int T, n, f0, f1, f2, p[3];

char s[maxn];

inline int get(char si) {
if(si >= 'a' && si <= 'z') return 0;
if(si >= 'A' && si <= 'Z') return 1;
if(si >= '0' && si <= '9') return 2;
}

int main() {
T = read();
while(T--) {
memset(p, 0, sizeof(p));
scanf("%s", s + 1);
n = strlen(s + 1); f0 = f1 = f2 = 0;
for(register int i = 1; i <= n; i++) {
if(s[i] >= 'a' && s[i] <= 'z') f0 = 1, p[0]++;
if(s[i] >= 'A' && s[i] <= 'Z') f1 = 1, p[1]++;
if(s[i] >= '0' && s[i] <= '9') f2 = 1, p[2]++;
}

if(f0 && f1 && f2){puts(s + 1); continue;}

if(f0 + f1 + f2 > 1) {
for(register int i = 1; i <= n; i++) {
if(p[get(s[i])] > 1) {
if(!f0) s[i] = 'a';
else if(!f1) s[i] = 'A';
else s[i] = '0';
break;
}
}
}
else {
if(f0) s[1] = 'A', s[2] = '0';
else if(f1)s[1] = 'a', s[2] = '0';
else s[1] = 'a', s[2] = 'A';
}

puts(s + 1);
}
return 0;
}

B.Relatively Prime Pairs

题目大意 : 给定一个区间\([l, r]\), \(l, r \le 10^{18}, (r - l + 1) = 0 (mod \ \ 2)\), 要你求出\(\frac {r - l + 1}{2}\)对二元组, 使得每个数都属于上述区间, 并且选出的元素不重复, 并且二元组中的元素互质

题解 : 显然\(gcd(n, n+1) = 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
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int maxn = 1e3 + 5;

inline LL read() {
char ch = getchar(); LL u = 0, f = 1;
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) {u = u * 10 + ch - 48; ch = getchar();} return u * f;
}

inline LL gcd(LL x, LL y) {return y == 0 ? x : gcd(y, x % y);}

LL l, r;

int main() {
l = read(); r = read();
if((r - l + 1) % 2 == 1) puts("NO");
puts("YES");
for(register LL i = l; i <= r; i += 2)
printf("%lld %lld\n", i, i + 1);
return 0;
}

C.Vasya and Multisets

题目大意 : 给你一个可重集, 定义一个集合的价值为这个集合中出现次数为一的元素的个数, 要求你将集合分为两个, 使得两个集合的价值相同

题解 : 我们记原集合出现过一次的元素的个数为\(cnt\), 出现过两次的元素的个数为\(con\), 去重后集合的元素的个数为\(tot\)

然后我们可以不管出现过两次的元素, 因为你如果把这个元素分开放, 那么两个集合的价值都会加\(1\), 如果都放在一个集合里面, 两个集合的价值并不会改变, 所以出现过两次的元素并不会影响答案

如果\(con \& 1\)并且\(tot = cnt + con\)就是不行的, 因为你并不能通过放置出现次数大于三的元素, 来改变答案

最后我们分类讨论一下

  • 如果\(con = 0\), 直接全部丢到一个集合里去
  • 如果\(con = 0 (mod \ \ 2)\), 把出现次数大于一的全部丢到一个集合, 然后把出现次数为一的平均的丢到两个集合
  • 如果\(con \& 1\), 把某一个出现次数大于二的丢到\(B\)集合, 剩余的出现次数大于一的元素丢到\(A\)集合, 然后\(\lfloor \frac{cnt}{2} \rfloor\)个出现次数为一的丢到\(A\)集合, 剩余的出现次数为一的丢到\(B\)集合

然后就轻松\(A\)掉了这道题

代码 :

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
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int maxn = 1e3 + 5;

inline int read() {
char ch = getchar(); LL u = 0, f = 1;
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) {u = u * 10 + ch - 48; ch = getchar();} return u * f;
}

int n, a[maxn], vis[maxn], cnt, b[maxn], c[maxn], con[maxn], o, z, u, A, B;

int main() {
n = read();

for(register int i = 1; i <= n; i++)
con[a[i] = b[i] = read()]++;


sort(a + 1, a + 1 + n);
a[0] = unique(a + 1, a + 1 + n) - a - 1;

for(register int i = 1; i <= a[0]; i++)
if(con[a[i]] == 2) cnt++;
else if(con[a[i]] == 1) o++;

if((a[0] - o - cnt) <= 0 && (o & 1)) {puts("NO"); return 0;}

puts("YES");

if(o <= 0) {
for(register int i = 1; i <= n; i++)
putchar('A'); return 0;
}

for(register int i = 1; i <= n; i++) {
int p = lower_bound(a + 1, a + 1 + n, b[i]) - a;
if(con[b[i]] == 2) {putchar('A'); continue;}

if(o & 1) {
if(vis[p]) {putchar(vis[p] == 1 ? 'B' : 'A'); continue;}
if(u && con[b[i]] > 2) {putchar('A'); continue;}
if(A < (o + 1) / 2) {
putchar('A'); A++;
if(con[b[i]] > 2) vis[p] = 1, u = 1;
}
else {
putchar('B'); B++;
if(con[b[i]] > 2) vis[p] = 2, u = 1;
}
}
else {
if(con[b[i]] > 2) {putchar('A'); continue;}
if(A < o / 2) putchar('A'), A++;
else putchar('B'), B++;
}
}
return 0;
}

D.Bicolorings

题目大意 : 给出一个\(N \times 2\)的矩阵, 定义两个块联通仅当两个块有公共边且两个块的颜色相同, 要求求出当这个矩阵的联通为\(k\)时的黑白染色的方案数

题解 : 我们考虑\(dp\), 设状态\(f[i][j][0/1][0/1]\), 表示染色染到第\(i\)列, 当前联通块的个数为\(j\), 第\(i\)列的第一行为黑色或白色, 第二列为黑色或白色的方案数

然后就是转移, 首先我们知道如果增加一列最多只会增加两个联通块, 所以我们可以以此为依据来转移

  • 当增加两个联通块时, 只有可能是黑白变白黑或者白黑变黑白

  • 当增加一个联通块时, 黑黑变黑白, 白白变黑白(白黑同理), 或者白白变黑黑, 黑黑变白白

  • 当不增加联通块时, 白黑变黑黑, 白黑变白白(黑白同理), 或者直接不变

然后就完了, 或者直接向官方题解一样状压\(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
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e3 + 5;
const int P = 998244353;

inline int read() {
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) {u = u * 10 + ch - 48; ch = getchar();} return u * f;
}

inline int pls(int x, int y) {x += y; return x >= P ? x - P : x;}

int n, k, f[maxn][maxn << 1][2][2];

int main() {
n = read(); k = read();

f[1][1][0][0] = f[1][1][1][1] = 1;
f[1][2][0][1] = f[1][2][1][0] = 1;

for(register int i = 2; i <= n; i++)
for(register int j = 1; j <= 2 * n; j++) {
if(j > 2) {
f[i][j][0][1] = pls(f[i][j][0][1], f[i - 1][j - 2][1][0]);
f[i][j][1][0] = pls(f[i][j][1][0], f[i - 1][j - 2][0][1]);
}
if(j > 1) {
f[i][j][0][1] = pls(f[i][j][0][1], pls(f[i - 1][j - 1][0][0], f[i - 1][j - 1][1][1]));
f[i][j][1][0] = pls(f[i][j][1][0], pls(f[i - 1][j - 1][0][0], f[i - 1][j - 1][1][1]));
f[i][j][1][1] = pls(f[i][j][1][1], f[i - 1][j - 1][0][0]);
f[i][j][0][0] = pls(f[i][j][0][0], f[i - 1][j - 1][1][1]);
}
f[i][j][0][1] = pls(f[i][j][0][1], f[i - 1][j][0][1]);
f[i][j][1][0] = pls(f[i][j][1][0], f[i - 1][j][1][0]);
f[i][j][0][0] = pls(f[i][j][0][0], f[i - 1][j][0][0]);
f[i][j][1][1] = pls(f[i][j][1][1], f[i - 1][j][1][1]);
f[i][j][1][1] = pls(f[i][j][1][1], pls(f[i - 1][j][0][1], f[i - 1][j][1][0]));
f[i][j][0][0] = pls(f[i][j][0][0], pls(f[i - 1][j][0][1], f[i - 1][j][1][0]));
}

cout << pls(pls(f[n][k][0][0], f[n][k][1][1]), pls(f[n][k][1][0], f[n][k][0][1]));
return 0;
}

E.Vasya and Big Integers

题目大意 : 给你一个很大的数字, 你可将其分成若干段, 要求每段数不含前导零, 并且每段数的大小都在\([l, r]\)这个区间内的方案数, \(l, r\)包括这个数的范围都小于\(10^{1000000}\)

题解 : 我们考虑\(dp\), 设状态\(f[i]\)表示到第\(i\)包括第\(i\)位有多少种合法的方案, 转移很好想, 我们直接考虑从第\(i\)为开始的后\(len_l\)个数拼成的数和\(l\)的大小, 和后\(len_r\)个数拼成的数和\(r\)的大小, 如果小于\(l\)直接往后挪一位, 如果大于\(r\)直接往前挪一位, 设最后确定的左端点为第\(i\)位往后挪\(d_l\)个数, 右端点为第\(i\)往后挪\(d_r\)位, 则转移方程为 \[ f[i] = \sum_{j = i + d_l}^{j \le i +d_r} f[j] \] 这个很显然是个前缀或者后缀和的形式, 直接维护一下就好了, 那么至此问题就被转化为了如何比较两个位数相同的数的大小, 显然是直接比较两个字符串\(LCP\)后一位的那个数的大小, 求\(LCP\)可以直接用\(O(1)\)\(Z-function\)或者\(O(logn)\)\(Hash\)

最后有个小\(trick\)就是我们可以直接倒着\(dp\)就可以很好的避免前导零的问题了

\(PS\): \(Hash\)可能会被卡常

代码 :

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
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int maxn = 2e6 + 50;
const int P = 998244353;

int ln, rn, n, z1[maxn], z2[maxn], f[maxn], S[maxn];

char s0[maxn], s1[maxn], s2[maxn];

inline int read() {
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) {u = u * 10 + ch - 48; ch = getchar();} return u * f;
}

inline int pls(int x, int y) {x += y; return x >= P ? x - P : x;}
inline int dec(int x, int y) {x -= y; return x < 0 ? x + P : x;}

inline void Zfunction(char *s, int *z, int n) {
z[1] = n; int j = 2, k = 0;
for(register int i = 2; i <= n; i = k) {
if(j < i) j = i;
while(j <= n && s[j] == s[j - i + 1]) j++;
z[i] = j - i; k = i + 1;
while(k + z[k - i + 1] < j) {
z[k] = z[k - i + 1]; k++;
}
}
}

inline char cmp(char *s0, char *s1, int z, int pos, int len) {
if(pos + len - 1 > n) return '<';
if(z == len) return '=';
if(s0[pos + z] < s1[z + 1]) return '<';
return '>';
}

int main() {
scanf("%s%s%s", s0 + 1, s1 + 1, s2 + 1);
ln = strlen(s1 + 1); rn = strlen(s2 + 1);
n = strlen(s0 + 1);

s1[ln + 1] = 0; s2[rn + 1] = 0;
for(register int i = 1; i <= n; i++)
s1[ln + 1 + i] = s0[i], s2[rn + 1 + i] = s0[i];

Zfunction(s1, z1, ln + n + 1); Zfunction(s2, z2, rn + n + 1);

f[n + 1] = S[n + 1] = 1;
for(register int i = n; i >= 1; i--) {
if(s0[i] == '0') {
if(s1[1] == '0' && ln == 1) f[i] = f[i + 1];
S[i] = pls(S[i + 1], f[i]); continue;
}

int l = i + ln, r = i + rn;
int p1 = z1[i + ln + 1], p2 = z2[i + rn + 1], rnt = 0;

if(cmp(s0, s1, p1, i, ln) == '<') l++;
if(cmp(s0, s2, p2, i, rn) == '>') r--;

if(l <= n + 1 && l <= r) {
rnt = S[l]; r = min(r, n + 1);
//if(r != n + 1)
rnt = dec(rnt, S[r + 1]);
}
S[i] = pls(S[i + 1], f[i] = rnt);

//cerr << "#Case : " << i << endl;
//cerr << l << " " << r << endl;
//cerr << "f[" << i << "] = " << f[i] << ", S[" << i << "] = " << S[i] << endl;
} cout << f[1];
return 0;
}

F.The Shortest Statement

题目大意 : 给你一张无向图, 现在有\(Q\)次询问, 每次询问一个点对\((u, v)\)求这两个点之间的最短路, 保证\(m - n \le 20\)

题解 : 我们关注一下题面中给的数据范围, 边的数量减去点的数量不超过二十, 很显然要从这个条件入手, 我们考虑一个问题, 如果只有\(n-1\)条边的话就是一颗树了, 在树上我们可以直接查询\(LCA\)来解决询问, 那么对于一颗树, 每加一条边就会多出一个环, 最多多加\(20\)条边, 也就说最多只有二十个环, 而如果把这些环拆开来就是一棵树了, 那我们直接对每个环上拆开的那个断点进行\(Dij\)就好了啊, 剩下的构成一棵树, 最后的答案就是 \[ min(dis[u] + dis[v] - 2 * dis[LCA(u, v)], min\{d[i][v] + d[i][u]\}) \] \(i\)代表二十个断点中点的编号

那具体怎么实现呢? 步骤如下

  • 直接从一号节点开始\(dfs\), 每搜到一个点就打标
  • 如果要访问的这个点没有被打标, 就直接像搜树一样记录\(fa\), \(deep\)
  • 如果要访问的这个点被打标了, 那么将这个点记录下来, 最后直接迪杰斯特拉

感觉很水, 比赛的时候想是想出来了, 但没有敢打

代码 :

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>

typedef long long LL;

const int maxn = 1e5 + 5;
const LL inf = 1ll << 60;

using namespace std;

int n, m, Q, fa[maxn][18];
int head[maxn], cnt = 1, C[maxn];
int deep[maxn], vis[maxn], tot;
LL d[maxn], dis[45][maxn];

priority_queue<pair<LL, int> > q;

struct Graph {int to, nt, w;} e[maxn << 2];

inline int read() {
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) {u = u * 10 + ch - 48; ch = getchar();} return u * f;
}

inline void ini(int x, int y, int w) {e[++cnt] = (Graph){y, head[x], w}; head[x] = cnt;}

inline void dfs(int now) {
vis[now] = 1;
for(register int i = 1; (1 << i) <= deep[now]; i++)
fa[now][i] = fa[fa[now][i - 1]][i - 1];
for(register int i = head[now]; i; i = e[i].nt) {
int v = e[i].to;
if(v == fa[now][0]) continue;
if(!vis[v]) {
fa[v][0] = now; deep[v] = deep[now] + 1;
d[v] = d[now] + e[i].w;
dfs(v);
}
else C[++tot] = now, C[++tot] = v;
}
}

inline int LCA(int x, int y) {
if(deep[x] < deep[y]) swap(x, y);
int tot = deep[x] - deep[y];
for(register int i = 17; ~i; i--)
if(tot & (1 << i)) x = fa[x][i];
if(x == y) return x;
for(register int i = 17; ~i; i--)
if(fa[x][i] != fa[y][i])
x = fa[x][i], y = fa[y][i];
return fa[x][0];
}

inline void Dij(int S, LL *dis) {
for(register int i = 1; i <= n; i++)
dis[i] = inf, vis[i] = 0;
while(!q.empty()) q.pop();
q.push(make_pair(dis[S] = 0, S));
while(!q.empty()) {
int now = q.top().second; q.pop();
if(vis[now]) continue; vis[now] = 1;
for(register int i = head[now]; i; i = e[i].nt) {
int v = e[i].to;
if(dis[v] > dis[now] + e[i].w) {
dis[v] = dis[now] + e[i].w;
q.push(make_pair(-dis[v], v));
}
}
}
}

inline LL Query(int x, int y) {
int lca = LCA(x, y); LL ans = 0;
ans = d[x] + d[y] - 2 * d[lca];
for(register int i = 1; i <= C[0]; i++)
ans = min(ans, dis[i][x] + dis[i][y]);
return ans;
}

int main() {
n = read(); m = read();

for(register int i = 1; i <= m; i++) {
int x = read(), y = read(), w = read();
ini(x, y, w); ini(y, x, w);
}
deep[1] = 1; fa[1][0] = 1;
dfs(1);

sort(C + 1, C + 1 + tot);
C[0] = unique(C + 1, C + 1 + tot) - C - 1;
for(register int i = 1; i <= C[0]; i++)
Dij(C[i], dis[i]);

Q = read();
while(Q--) {
int x = read(), y = read();
printf("%lld\n", Query(x, y));
}
return 0;
}

Summary

  • 打的时候尽量在不出错的情况下提高手速
  • 读题读快一点
  • 有想法就尽量去实现