CF记录

CF记录

之前就开始写了，一直没放到blog上来

CF1509(Div.2)

场上通过：ABC

A:4min B:33min C:74min

BC用时太久，考场上最后15min对D中给出3个2n串条件不会用

就去看E，最后大概会E，但没有时间写

改题进度：DE

D

仅需考虑对于一个长度为2n的01串，必有一个字符出现了至少n次，称该字符为其特征字符

三个2n串中必有两个的特征字符相同，将这两个串拿出来构造下就行了

E

考虑1~n总共有多少个满足条件的排列，简单推推可以发现即为 $2^{n-1}$

考虑按位确定排列，随便写下即可

CF1517(Div.1+Div.2)

场上通过：ABCD

A:4min B:16min C:39min D:49min

考场上最后3min写完了E题，但还没调完，考后调完了E

E题场上没过还是挺可惜的，过了就上大分了

发现CFdiv.2E我永远过不了/kk

改题进度：E

B

考场胡了一个每次降序把值分配给升序的最小值序列

标算是考虑将全局最小的 $m$ 个数分别分给 $m$ 个方案即可

C

考场上猜了个写法，大概是从前往后扫排列，每次尽量往左边填

对每一行维护一个已填到哪里的轮廓线，新一个位置沿轮廓线填

这个做法大概是标算的构造2

D

首先考虑 $k$ 为偶数

显然路径不会是一条环路，一定是到某个点后原路返回

然后对于每个点bfs一次即可

这个算法的时间复杂度为 $O(nm4\sum_{i=1}^{\frac k 2}i^2)$

大概接近 $4\times 10^8$ 次运算，考场上过了

事实上，标算给出了一个 $O(nmk)$ 的做法

考虑dp，记 $f_{x,y,k}$ 表示 $(x,y)$ 走 $k$ 步的最短距离

转移很显然 $f_{x,y,k}=\min_{(u,v,x,y)}\{f_{u,v,k-1}+w_{u,v,x,y}\}$

大概比考场上的弱智东西好写点

E

考场上直接大力讨论

注意到连续的 $C$ 或 $P$ 十分特殊，讨论从C段与P段的角度出发

1. 不存在C/P段

   则仅可能为 $PCPCPC...$ 或 $CPCPCP...$

2. 存在C段且不存在P段

   C段左边最多填一个 $P$ 右边只能若干 $PC$ 反复

3. 存在P段且不存在C段

   类似 Case2

4. C/P段均存在

   P段在C段前当且仅当两段之间无其它且左右均无其它

   C段在P段前则两段中间可填若干 $PC$ ，最左最多一个 $P$，最右最多一个 $C$

实现的话Case1,2,3都是 $O(n)$ 的

Case4能二分一下，总复杂度 $O(nlogn)$

大概能双指针做到 $O(n)$

CF1519(Div.2)

场上通过：ABCD

A:6min B:14min C:25min D:15min

大概是手速场，E最后div2过了7个人

AB题速度都太慢了，罚时严重

改题进度：E

E

容易想到对于一个点有两个关键值：$\frac y{x+1},\frac{y+1}x$

若两点任意关键值相同，即可匹配

正解做法考虑离散化所有关键值后两两关键值连边，形成若干连通块

显然，不同连通块间无影响，考虑一个单独的连通块

取出块中的一颗生成树，其仅存在返祖边

首先，考虑没有返祖边的情况，我们容易得到一种至多一条边未匹配的算法，显然最优

目前我们试图解决子树 $x$ 内的边匹配情况，递归其儿子 $y$

若 $y$ 子树中有一边未匹配完全，将其与 $x\to y$ 匹配，否则我们留下了 $x\to y$

所有子节点递归完成后，将剩下的 $x\to y$ 边两两匹配即可

对于返祖边，我们将其放在祖先节点考虑，相当于多了一个叶节点连接 $x$

做法几乎同上

CF1515(CGR14)

场上通过：ABCD

上紫了!

A:5min B:4min C:13min D:47min

C题用时偏久，D题用时过久了，手速一般

改题进度：EF

E

考虑到手动开启的电脑形如若干仅空1个的连续段

考虑一个长度为 $k$ 的连续段的方案数，容易得到其为 $2^{k-1}$

我们仅需以组合数合并若干个连续段即可得到答案

记 $f_{i,j}$ 表示长度为 $i-1$ 的序列，有 $j$ 个位置手动开启的方案数

$f_{i,j}\tbinom{j+k}k2^{k-1}\to f_{i+k+1,j+k}$

转移即可，时间复杂度 $O(n^3)$

F

考虑判断无解

显然，若 $a$ 值总和小于 $(n-1)*x$，显然无解

否则，我们这样一个构造方案

取全局最大的 $a$，随意找一个邻居与其合并，并重复此操作 $n-1$ 次

对于一次操作，若 $maxa\geq x$ 显然正确，否则，所有 $a_i<x$

若存在 $a_i+a_j<x$，则 $\sum_{i}a_i<(n-1)*x$，不符合原先假设

故该策略正确，写个优先队列即可

CF1549(Div.2)

前面应该少写了几场CF的总结，目前已经掉紫了/kk

场上通过：ABCD

A:5min B:17min D:20min C:47min

感觉逐渐没有手速，C题一开始甚至不会，就赶紧去看D把D写了，感觉C非常sb

不懂为啥自己第一眼不会做

E题是个降智题，想到了思路边边上，没有仔细把递推的思路浮出水面，亏麻了，场上只有20人通过了E

改题进度：E