【做题记录】Codeforces做题记录

最近决定写一些CF Div.1的题，练习一下速度和代码能力。
暂定从中考后的Codeforces Round #572开始。
大部分比较简单的题直接把题解写在这里，不单独开文章了。

Codeforces Round #572 (Div. 1)

Codeforces Round #573 (Div. 1)

Codeforces Global Round 4

Codeforces Round #576 (Div. 1)

A

省略

B

省略

Codeforces Round #580 (Div. 1)

B

显然若某一位上有\(3\)个数，那么就会形成环，答案为\(3\). 因此该图点数不超过\(2\log A\le 120\), 边数也是\(O(\log A)\)级别。
然后就要求一个新图的最短环，这个可以枚举环上的一条边，然后删掉这条边，求两端点的最短路。
时间复杂度\(O(n+\log^2 A\log\log A)\)
代码: 59195761

C

题解: https://www.cnblogs.com/suncongbo/p/11389254.html

Codeforces Round #583 (Div. 1 + Div. 2)

Codeforces Round #584 (Div. 1 + Div. 2)

E

原问题可以转化为，每列轮换后每行选一个数，使得总和最大。
设\(dp[i][S]\)表示前\(i\)列已选的行的集合是\(S\), 枚举轮换状态进行转移。提前求出这一行每个子集在所有轮换中的和的最大值即可得到一个时间复杂度为\(O((3^n+2^nn^2)m)\)的算法，可以通过E1题。
有个性质是只有按列最大值从大到小排序后的前\(n\)个列是有用的，因此只需考虑前\(n\)列。
时间复杂度\(O(3^nn+2^nn^3+nm+m\log m)\)
代码: 60827873

Codeforces Round #586 (Div. 1 + Div. 2)

E

以起点为根建DFS树，对于所有子树内没有任何一条返祖边指向子树外的子树，我们无法获得它内部的点权，但是可以获得其内部最大权垂直链的点权，而其他点的点权都可以获得，因此答案就是所有这种子树的内部最大权垂直链的最大值加上其余点的点权和。
时间复杂度\(O(n+m)\).
代码: 60831008

Codeforces Round #588 (Div. 1)

Codeforces Round #591 (Div. 1)

Codeforces Global Round 5

A

省略

B

省略

C

考虑二维怎么做: 按\(x\)排序，把每个\(x\)的点两两配对，消到只剩最多一个。然后相邻的配对，显然不会有相交。
三维就先按\(z\)排序，对每个二维平面执行二维算法，消到只剩最多一个。然后相邻的配对，显然也不会有交。
时间复杂度\(O(n\log n)\).
代码: 62854906

D

显然答案要么全是\(-1\), 要么全都不超过\(3n\). 将数组复制\(3\)倍，预处理\(r_i\)表示第\(i\)个点后面第一个小于其一半的位置，则某个点能延伸到的最远点就是上述数组的后缀最小值，减去该点的原始位置就是答案。
也可以对每个点二分然后用数据结构实现。
时间复杂度\(O(n\log n)\).
代码: 62725216

E

树的形态是一棵满二叉树下面挂若干个儿子，且要求每个点的左儿子的右儿子大小为奇数，右儿子的左儿子大小为偶数。那么考虑在两棵深度相同的树上加一个根合并起来，右儿子的左端点个数奇偶性会限制右儿子最左边的链上左儿子的有无，归纳易证只有左儿子最左边的链上儿子可有可无，其余的方案是确定的，答案一定为\(0\)或\(1\), 且对于一种深度，只有两个相差\(1\)的\(n\)答案是\(1\).
考虑生成答案为\(1\)的集合，归纳可证每次将两个数同时加上两数中的偶数\(+1\)，就可以得到下一层的两个数。
时间复杂度\(O(\log n)\).
代码: 62864619

Codeforces Round #594 (Div. 1)

Codeforces Round #596 (Div. 1)

A

显然答案不超过\(\log n\). 枚举答案，转化为\(k\)个\(2\)的幂次和为\(n-ak\). 求出最少需要几个（\(\text{bitcnt}(n-ak)\)）和最多需要几个（\(n-ak\)），若\(i\)介于两数之间则可以。
时间复杂度\(O(\log n)\)或\(O(\log^2n)\).
代码: 63769126

B

把一个数看作长度为\(10^5\)的数组，第\(i\)个位置若\(i\)不是质数则为\(0\), 否则为这个质数的幂次\(\mod m\). 将这个数组用\(m\)进制进行Hash并插入map中，在map中查询其每一位取负后的Hash值。
时间复杂度\(O(n\sqrt n)\)或\(O(n\log n)\).
代码: 63771856

C

某个位置的操作不会影响在它右下方的矩形。
设\(f[i][j]\)表示从\((1,1)\)到\((i,j)\)且在\((i,j)\)点由朝右转向朝下的方案数，\(g[i][j]\)表示从\((1,1)\)到\((i,j)\)且在\((i,j)\)由朝下转为朝右的方案数。
则有转移方程: \(f[i][j]=\sum^{j-1}_{k=lf[i][j]}g[k][j], g[i][j]=\sum^{i-1}_{k=lg[i][j]}f[i][k]\), 其中\(lf[i][j]\)等于最大的\(k\)使得\(sumx[i][k+1]\le n-k\), \(sumx[i][j]\)是第\(i\)行\(j\)处的后缀和，\(lg\)同理。这两个数组可以\(O(nm)\)双指针预处理，前缀和优化DP即可。
更简单的实现方式: 从后往前DP, 这样无需处理\(lf\)和\(lg\), \(lf[i][j]\)直接等于\(m-sumx[j]-1\).
时间复杂度\(O(nm)\).
代码: 63768042

D

题解: https://www.cnblogs.com/suncongbo/p/11768950.html

Codeforces Round #599 (Div. 1)

Codeforces Round #601 (Div. 1)

C

题解: https://www.cnblogs.com/suncongbo/p/11994646.html

Codeforces Round #602 (Div. 1)

Codeforces Round #604 (Div. 1)

C

题解: https://www.cnblogs.com/suncongbo/p/11996219.html

Codeforces Round #606 (Div. 1)

A

twone删o, 否则删中间那一个即可。
时间复杂度\(O(n)\).
代码: 66841692

B

建圆方树，统计经过两个点的点对数目即可。以第一个点为根建可以降低代码量。
时间复杂度\(O(n)\).
代码: 66848795

C

题解: https://www.cnblogs.com/suncongbo/p/12041672.html

D

题解: https://www.cnblogs.com/suncongbo/p/12072371.html

Codeforces Round #607 (Div. 1)

A

显然一次操作只会往原串后面加字符。直接模拟前\(m\)位，后面的计算即可。
时间复杂度\(O(n+m)\).
代码: 66904577

B

显然答案是\(0,1,2,3,4\)或无法完成。如果所有的都是A就是\(0\), 所有的都是P是无法完成，第一行、第一列、最后一行、最后一列中至少有一个全是A就是\(1\), 四角的至少一格或者中间的至少一行或一列为A则是\(2\), 与边界相邻的格子中有至少一个A就是\(3\), 否则为\(4\).
时间复杂度\(O(nm)\).
代码: 66912353

C

求最小: 显然答案的下界是所有两端子树大小为奇数的边的边权之和。考虑转换为有根树后每个点奇数的儿子的随意匹配即可达到下界。
求最大: 显然答案的上界是所有边两端子树大小最小值之和。通过重心（点或边）的不同子树内任意匹配容易证明可以达到上界。
时间复杂度\(O(n)\).
代码: 66919108

D

设\(f[u][i]\)表示\(u\)子树内分成\(i\)个连通块最多有多少个正的，\(g[u][i]\)表示\(u\)子树内分成\(i\)个连通块，在保证正的个数最多的前提下根节点所在连通块点权和最大是多少。背包转移即可。由于根所在的连通块最多产生\(1\)的影响，因此优先保证\(f[u][i]\)最大是正确的。
时间复杂度\(O(n^2+nm)\).
代码: 66959746

E

首先对于一个电路来说，等效电阻与电路中所用电阻值之和成正比。那么对于一个串联电路，我们最优策略一定是贪心地选择最小的儿子去分担全部等效电阻。这就意味着答案一定是若干并联嵌套的结构。而且并联之间的嵌套没有意义，就相当于一层所有电阻并联的并联电路，因此所有电阻均分阻值即可。做法就是先建树然后树形DP(串联求最小值并联求和)求出最少用多少个电阻，然后均分阻值。
时间复杂度\(O(n)\).
代码: 66977391

巴特西