Codeforces Round #674 (Div. 3)

A. Floor Number

第一楼有2个房间，二楼及以上的楼层每一层有x个房间，房间的序列号从1号开始从低到高进行编号。根据房间的数量n求楼层数量。

$n\le 2$，答案为$1$ $n\ge 3$, 答案为$1+\lceil \frac{n-2}{x}\rceil$

# include <iostream> # include <cstdio> # include <cmath> void solve() { int n; int x; scanf("%d%d", &n, &x); if (n <= 2) { puts("1"); return; } int ans = ceil(1.0 * (n - 2) / x) + 1; printf("%d\n", ans); } int main() { int T; std::cin >> T; while (T--) { solve(); } return 0; }

B. Symmetric Matrix

每块砖有4个正方形瓦片，每个瓦片的边长为1.每个瓦片上有一个数字，用若干不同的砖块拼成一个边长为m的瓦片，问能否让拼成的瓦片呈主对角线对称。砖块不能旋转，不能重叠，不能拆分。

若$m$为奇数，那么一定不可以拼成一个正方形。 假设一个砖块的4个瓦片的坐标为a[1][1], a[1][2], a[2][1], a[2][2]。 如果存在砖块的a[1][2]==a[2][1]，那么就可以拼接，否则就不能拼接。

# include <iostream> # include <cstdio> struct M { int a[3][3]; }; const int N = 205; M mat[N]; void solve() { int n, m; scanf("%d%d", &n, &m); int flag1 = 0; for (int i = 1; i <= n; i++) { scanf("%d%d%d%d", &mat[i].a[1][1], &mat[i].a[1][2], &mat[i].a[2][1], &mat[i].a[2][2]); if (mat[i].a[1][2] == mat[i].a[2][1]) { flag1 = 1; } } if (m & 1) { puts("NO"); return; } if (flag1) { puts("YES"); } else { puts("NO"); } } int main() { int T; std::cin >> T; while (T--) { solve(); } return 0; }

C. Increase and Copy

初始数组$a$只有一个元素$a_1=1$。 每次操作可以从一下两种方案中选一个：

将数组$a$中任意一个元素+1选择数组$a$中的任意一个元素值，在数组尾部添加这个元素值。

求最少的操作次数使得数组里面的所有元素的和大于等于$n$

该问题等价于： 数字的初始值为$1$。 先将该数字$+1$共$a$次，再将该数字乘以$b$次得到结果。

证明：如果如果要尽量操作数少并且数组的和最大，则应该先将原始数组的$a_1$加一若干次之后再将该$a_1$复制若干次得到最后的值。如果不是用此操作所得到的数组元素和一定小于等于此操作的数组元素和。因为其他操作进行简单的交换操作次序后在复制元素值的时候复制的元素值一定小于等于最优解的第一个元素值，因此元素的和一定小于等于最优解的元素的和。

该问题等价于：已知整数$n$的值，求满足$(1+a)\ast (1+b)\ge n$的情况下，$a+b$的最小值（$a,b$为整数）。 求$a+b$的最小值也相当于求$a+b+2$的最小值。因此枚举从$\lfloor n\rfloor -1$到$\lfloor n\rfloor +4$的$a$和$b$,求满足$(1+a)\ast (1+b)\ge n$的$a+b$的最小值即可

# include <iostream> # include <cstdio> # include <cmath> void solve() { int n; scanf("%d", &n); int root = sqrt(n) - 1; int ans = 0x3f3f3f3f; for (int a = root; a <= root + 5; a++) { for (int b = root; b <= root + 5; b++) { if ((1 + a) * (1 + b) >= n) { ans = std::min(ans, a + b); } } } printf("%d\n", ans); } int main() { int T; std::cin >> T; while (T--) { solve(); } return 0; }

D. Non-zero Segments

数组$a$含有$a_1,a_2,...,a_n$这$n$个非零整数。每次操作可以在数组的任意两个元素之间插入一个任意值的整数来使得该数组所有的子区间的和不为$0$。求最小操作次数。 先求前缀和 $s[n]={\sum }_{i=1}^{n}a[i]$。如果$a$的$[l,r]$区间和为$0$，那么$s_r-s_{l-1}=0$。从下标1开始遍历，将目前下标的前缀和放入$set$中，如果某个下标$i$的前缀和是set里的元素，就在下标$i$的左边加一个很大的数，那么前面所有区间的前缀和就都不等于$0$。

# include <iostream> # include <cstdio> # include <set> typedef long long ll; const int N = 2e5 + 5; ll a[N]; int main() { int n; std::cin >> n; for (int i = 1; i <= n; i++) { scanf("%lld", &a[i]); } std::set<ll> st; ll cur = 0; ll cnt = 0; st.insert(0); for (int i = 1; i <= n; i++) { cur += a[i]; if (st.find(cur) != st.end()) { cnt++; st.clear(); st.insert(0); cur = a[i]; } st.insert(cur); } std::cout << cnt; return 0; }

E. Rock, Paper, Scissors

Alice和Bob玩石头剪刀布。 Alice出$a_1$次石头，$a_2$次剪刀，$a_3$次布。 Bob出$b_1$次石头，$b_2$次剪刀，$b_3$次布。 $a_1+a_2+a_3=b_1+b_2+b_3$ 求在所有的出拳方式中Alice能赢的最少次数以及Alice能赢的最多次数。

Alice的所有没有赢的情况为石头对石头，石头对布，剪刀对剪刀，剪刀对石头，布对布，布对剪刀。用总局数减去所有没有赢的情况的最大值就是赢的最少次数。 Alice的所有赢的情况为石头对剪刀，剪刀对布，布对石头。加上这三个的值就是答案。

答案：赢的最少次数为 $n-min(a1,b1+b3)-min(a2,b1+b2)-min(a3,b2+b3)$ 赢的最多次数为$min(a_1,b_2)+min(a_2,b_3)+min(a_3,b_1)$

# include <iostream> # include <cstdio> # include <algorithm> typedef long long ll; int main() { int n; std::cin >> n; int a1, a2, a3; int b1, b2, b3; std::cin >> a1 >> a2 >> a3 >> b1 >> b2 >> b3; ll res1 = n - std::min(a1, b1 + b3) - std::min(a2, b1 + b2) - std::min(a3, b2 + b3); ll res2 = std::min(a1, b2) + std::min(a2, b3) + std::min(a3, b1); std::cout << res1 << " " << res2; return 0; }

F. Number of Subsequences

字符串$s$包含四种字符 ‘$a$’，’$b$’，’$c$’，’$?$’。 ‘$?$‘可以被替换成 ‘$a$’，’$b$’，’$c$'这三个字符的任意一种。求字符串中所有包含"$abc$"的子序列。答案对$10^9+7$取模。 子序列(subsequence)和子字符串(substring)以及子数组(subarray)不同。subsequence可以是不连续的子串，而substring和subarray必须是连续的子串。

先说一个如果字符串中没有’$?$'字符的写法。 令$dp[i][j](j=1,2,3$$)(i$从下标$1$开始计数$)$表示前$i$个字符中，匹配了"$abc$"的前多少位。转移方程为：

$dp[0][0]=1$

$dp[i][1]=(dp[i-1][1]+(s[i]={=}^{\prime }{a}^{\prime }))\%Mod$ $dp[i][2]=(dp[i-1][2]+(s[i]={=}^{\prime }{b}^{\prime })\ast dp[i-1][1])\%Mod$ $dp[i][3]=(dp[i-1][3]+(s[i]={=}^{\prime }{c}^{\prime })\ast dp[i-1][2])\%Mod$

求$dp[n][3]$。

因为$dp[i]$的状态只与$dp[i-1]$有关，所以如果二维数组的内存不够的话，可以使用滚动数组来优化空间开销，去掉第一维的状态，只保留第二维的状态。状态的转移方程为： $dp[0]=1$ $dp[1]=(dp[1]+(s[i]={=}^{\prime }{a}^{\prime }))\%Mod$ $dp[2]=(dp[2]+(s[i]={=}^{\prime }{b}^{\prime })\ast dp[1])\%Mod$ $dp[3]=(dp[3]+(s[i]={=}^{\prime }{c}^{\prime })\ast dp[2])\%Mod$

求经过$n$次循环后的$dp[3]$。

考虑加上${}^{\prime }{?}^{\prime }$的情况。 $dp[0][0]=1$ $dp[i][1]=(dp[i-1[[1]+(s[i]={=}^{\prime }{a}^{\prime })\ast dp[i][0])\%Mod$ $dp[i][2]=(dp[i-1[[2]+(s[i]={=}^{\prime }{b}^{\prime })\ast dp[i][1])\%Mod$ $dp[i][3]=(dp[i-1[[3]+(s[i]={=}^{\prime }{c}^{\prime })\ast dp[i][2])\%Mod$

$if(s[i]={=}^{\prime }{?}^{\prime })$ $dp[i][0]=3\ast dp[i-1][0]\%Mod$ $dp[i][1]=(3\ast dp[i-1[[1]+dp[i-1][0])\%Mod$ $dp[i][2]=(3\ast dp[i-1[[2]+dp[i-1][1])\%Mod$ $dp[i][3]=(3\ast dp[i-1[[3]+dp[i-1][2])\%Mod$

# include <iostream> # include <cstring> # include <cstdio> # include <vector> const int mod = 1e9 + 7; const int N = 2e5 + 5; char s[N]; std::vector<std::vector<int>> dp(N, std::vector<int>(4)); int main() { int len; scanf("%d%s", &len, s + 1); dp[0][0] = 1; for (int i = 1; i <= len; i++) { dp[i] = dp[i - 1]; // ! if (s[i] == 'a') { dp[i][1] = (1ll * dp[i-1][1] + dp[i-1][0]) % mod; } if (s[i] == 'b') { dp[i][2] = (1ll * dp[i-1][2] + dp[i-1][1]) % mod; } if (s[i] == 'c') { dp[i][3] = (1ll * dp[i-1][3] + dp[i-1][2]) % mod; } if (s[i] == '?') { dp[i][0] = 3ll * dp[i-1][0] % mod; dp[i][1] = (3ll * dp[i-1][1] + dp[i-1][0]) % mod; dp[i][2] = (3ll * dp[i-1][2] + dp[i-1][1]) % mod; dp[i][3] = (3ll * dp[i-1][3] + dp[i-1][2]) % mod; } } std::cout << dp[len][3]; return 0; }

滚动数组优化后的代码：

# include <iostream> # include <cstring> # include <cstdio> const int mod = 1e9 + 7; const int N = 2e5 + 5; char s[N]; int dp[4]; int main() { int len; scanf("%d%s", &len, s + 1); dp[0] = 1; for (int i = 1; i <= len; i++) { if (s[i] == 'a') { dp[1] = (1ll * dp[1] + dp[0]) % mod; } if (s[i] == 'b') { dp[2] = (1ll * dp[2] + dp[1]) % mod; } if (s[i] == 'c') { dp[3] = (1ll * dp[3] + dp[2]) % mod; } if (s[i] == '?') { int t0 = dp[0]; int t1 = dp[1]; int t2 = dp[2]; dp[0] = 3ll * dp[0] % mod; dp[1] = (3ll * dp[1] + t0) % mod; dp[2] = (3ll * dp[2] + t1) % mod; dp[3] = (3ll * dp[3] + t2) % mod; } } std::cout << dp[3]; return 0; }

Codeforces Round #670 (Div. 2)

A. Subset Mex

给定一个由非负整数构成的数组，将这个数组拆分成两个子数组$A$和$B$。$mex\{X\}$代表$X$数组中没有的非负整数中最小的那个整数。例如$mex\{0,1,2,4\}$的值为3。 求$mex\{A\}+mex\{B\}$的最大值。

用cnt数组标记原数组的每一个元素的出现次数，从小到大遍历，cnt数组中第一个为$0$的元素就是$mex\{A\}$，第一个小于等于$1$的元素就是$mex\{B\}$。

# include <iostream> # include <cstdio> # include <cstring> typedef long long ll; int cnt[105]; void solve() { int n; std::cin >> n; memset(cnt, 0, sizeof(cnt)); int t; for (int i = 1; i <= n; i++) { scanf("%d", &t); cnt[t]++; } int ans = 0; for (int i = 0; i <= 100; i++) { if (!cnt[i]) { ans += i; break; } } for (int i = 0; i <= 100; i++) { if (cnt[i] <= 1) { ans += i; break; } } std::cout << ans << "\n"; } int main() { int T; std::cin >> T; while (T-- ) { solve(); } return 0; }

B. Maximum Product

从$n$个数中选$5$个数，使得这$5$个数的乘积最大。 从$n$个数中选$k$个数的方法，使得这$k$个数的乘积最大的方法：

# include <iostream> # include <cstdio> # include <algorithm> typedef long long ll; const int N = 2e5 + 5; const ll mod = 1e18; int a[N]; void solve() { int n, k; // scanf("%d%d",&n, &k); scanf("%d", &n); k = 5; for(int i = 1; i <= n; i++) { scanf("%d", &a[i]); } std::sort(a + 1, a + 1 + n); ll res = 1; int l = 1, r = n; int sign = 1; if (k & 1) { res = a[r]; r--; k--; if (res < 0) { sign = -1; } } while (k) { ll x = 1ll * a[l] * a[l + 1]; ll y = 1ll * a[r] * a[r - 1]; if(x * sign > y * sign) { res = x % mod * res % mod; l += 2; } else { res = y % mod * res % mod; r -= 2; } k -= 2; } printf("%lld\n", res); } int main() { int T; std::cin >> T; while (T--) { solve(); } return 0; }

C. Link Cut Centroids

唯一化树的重心

对于树上的每一个点，计算将该点删除后剩余的所有子树中最大的子树节点数，这个值最小的点就是这棵树的重心。

题目要求删去树的一条边，然后加一条边，使树的重心唯一化。 一棵树最少有一个重心，最多有两个重心。 如果树只有一个重心，把任意一个边删除然后重连，树的重心仍然唯一。 如果树有两个重心$x$和$y$，让$y$作为$x$的父亲，然后将$x$的一个子树的叶子节点切掉，将该叶子节点与$y$相连，$y$就变成了唯一重心。 证明：删除$y$节点后，剩余的子树的节点数为$\frac{n}{2}$；删除$x$节点后，剩余的子树的节点数为$\frac{n}{2}$。在执行完删除边以及增边操作后，若将$x$节点删除，其剩余子树的最大节点数为$\frac{n}{2}+1$，而若是将$y$节点删除，其剩余子树的节点数为$\frac{n}{2}-1$。因此$y$变成了唯一的树的重心。

邻接矩阵写法：

# include <iostream> # include <cstdio> # include <algorithm> # include <vector> const int INF = 0x3f3f3f3f; const int N = 1e5 + 5; int n, size[N], fa[N], min = INF, cent1, cent2; std::vector<int> g[N]; void dfs(int x, int f) { fa[x] = f; size[x] = 1; //size[x]表示以x为根的当前子树中，所有节点的数量。 int max = 0; for (int y : g[x]) { if(y == f) { continue; } dfs(y, x); size[x] += size[y]; max = std::max(max, size[y]); //max表示删掉y点后，当前所有连通块中节点数的最大值 } max = std::max(max, n - size[x]); //删除掉x点后当前所有连通块中点节点数的最大值 if (max < min) { min = max; cent1 = x; cent2 = 0; } else if (max == min) { cent2 = x; } } int S; void dfs2(int x, int f) { if (g[x].size() == 1) { S = x; return; } for (int y : g[x]) { if (y == f) { continue; } dfs2(y, x); } } void solve() { std::cin >> n; cent1 = cent2 = 0; min = INF; for(int i = 1; i <= n; i++) { g[i].clear(); fa[i] = 0; } for(int i = 1; i < n; i++) { int x, y; scanf("%d%d", &x, &y); g[x].push_back(y); g[y].push_back(x); } dfs(1, 0); if(!cent2) { printf("1 %d\n1 %d\n", g[1][0], g[1][0]); return; } if(fa[cent1] != cent2) { std::swap(cent1, cent2); } dfs2(cent1, cent2); printf("%d %d\n%d %d\n", S, fa[S], S, cent2); } int main() { int T; std::cin >> T; while (T--) { solve(); } return 0; }

链式前向星写法：

# include <iostream> # include <cstdio> # include <cstring> # include <algorithm> const int N = 1e5 + 5; const int INF = 0x3f3f3f3f; int n, min = INF, cent1, cent2, fa[N]; int h[N], e[N * 2], ne[N * 2], idx; bool add(int a, int b) { e[idx] = b; ne[idx] = h[a]; h[a] = idx++; } int dfs(int x, int f) { fa[x] = f; int sum = 1; int max = 0; for (int i = h[x]; ~i; i = ne[i]) { int y = e[i]; if (y == f) { continue; } int s = dfs(y, x); sum += s; max = std::max(max, s); } max = std::max(max, n - sum); if (max < min) { min = max; cent1 = x; cent2 = 0; } else if (max == min) { cent2 = x; } return sum; } int S; void dfs2(int x, int f) { if (ne[h[x]] == -1) { S = x; return; } for (int i = h[x]; ~i; i = ne[i]) { int y = e[i]; if (y == f) { continue; } dfs2(y, x); } } void solve() { scanf("%d", &n); cent1 = cent2 = 0; min = INF; idx = 0; memset(h, -1, sizeof(h)); for (int i = 1; i < n; i++) { int u, v; scanf("%d%d", &u, &v); add(u, v); add(v, u); } dfs(1, 0); if(!cent2) { printf("1 %d\n1 %d\n", e[h[1]], e[h[1]]); return; } if(fa[cent1] != cent2) { std::swap(cent1, cent2); } dfs2(cent1, cent2); printf("%d %d\n%d %d\n", S, fa[S], S, cent2); } int main() { int T; std::cin >> T; while (T--) { solve(); } return 0; }

在学习此题之后，建议练习此题：WIT OJ 1514 树的重心

D. Three Sequences

数组$a$含有$a_1,a_2,...,a_n$这$n$个整数。构建含有$n$个整数的数组$b$和$c$，满足以下三个条件：

对于每一个下标$i$$(1\le i\le n)$，$b_i+c_i=a_i$$b$数组一定是一个非递减序列$c$数组一定是一个非递增序列

共有$q$次操作，每次操作将$a$数组$[l,r]$区间的每一个元素的值增加$x$。求每次操作后的$mi{n}_1^{n}max(b_i,c_i)$

因为$b$数组非递减，$c$数组非递增，因此$b$数组的最大值为$b_n$，$c$数组的最大值为$c_1$，$mi{n}_1^{n}max(a_i,b_i)=max(b_n,c_1)$