CF 高分档题目做题记录

AsunderSquall · 2021-09-22 20:00:23 · 个人记录

看到了的点个赞吧 qwq

顺便宣传
顺便宣传

前言

我也不知道为什么要开这个坑，可能是只是为了装逼（虽然也没什么好装的，被所有同学吊着打），可能是为了以后供自己凭吊（？？？），或者是为了让自己的博客有一点有意义的东西（实际上大概也并没有什么意义），也可能只是想颓废又不想看着太颓罢了。

可能也可以说是为了把自己以前含糊不清的题目给弄懂吧。
二刷的时候不知道怎么做的题用*标注，并且打算重新搞懂之后去写篇题解。

按照时间顺序，从暑假开始，AC 时间是 CF 上显示的时间，和实际差多少小时我也不清楚。（update：实际上差 5 个小时）

可能有遗漏的，不管了。

题号都是链接，链的是洛谷的题面。题目链接为红色的说明为独立想出的（嘴巴出来的也算），蓝色为大体思路方向是对的，黑色的大概说明当时思路偏了或完全没有思路（（（

除了题目链接只有做法简述，因为大概是给自己看的所以可能不会特别清晰。

目前 cnt=31，其中有 4 道还在咕。

最后一次施工：11.3。

\color{black}{\texttt{CF788D}}

*3000 Jul/17/2021 08:43

考虑直线 y=x 会和横着的和竖着的直线都产生交点，那么我们在这条直线上进行分治。

考虑递归 [l,r] 的时候，查询 (mid,mid)，返回值为 k。如果 k=0 那么找到一个交点，递归 [l,mid-1] 和 [mid+1,r]。否则递归 [l,mid-k] 和 [r,mid-k]。

找到所有交点之后取一个没有直线的位置 (t,t)。考虑一个 (k,k) 有交点。我们询问 (k,t) 答案为 0 就说明有一条 x=k 的直线，如果 (t,k) 答案为 0 说明有一条 y=k 的直线。

\color{black}{\texttt{*CF1392H}}

*3000 Jul/21/2021 14:59

二刷已经没法独立做出了，说明这题差点被我浪费了，还好挖了这个坑让我意识到了这一点。

先咕。

\color{red}{\texttt{CF1119G}}

*3100 Jul/23/2021 04:41

考虑我们分成了 m 组，敌人的个数也是 m 个。
我们每次集中火力打 1 个，等到快要死了就把总人数分出一部分来打它，其他部分打下一个。
这么递归下去。
然后我们发现我们需要满足的是有 m 个限制，即为若干个 a_i 加起来为 k。
因为我们分成 m 组所以必然可以构造。
细节有点多，可能和我第一次的做法不同。

\color{blue}{\texttt{CF715D}}

*3100 Aug/05/2021 04:36

见此。

其实感觉这题我还胡出了一个吊打标算的做法，但是没仔细去想，可能是假的，具体来说 6 进制->20 进制。

\color{red}{\texttt{CF1423N}}

*3500 Aug/05/2021 16:45

见此。

\color{red}{\texttt{CF1190E}}

*3100 Aug/06/2021 15:47

首先一看就知道是二分答案，使直线距离尽量仅一定不劣。
接下来考虑怎么判定。

我们令一条直线的一个参数 t 为，原点到这条直线的垂足的极角。
那么一个关键点 i 实际上需要满足的是至少要有一条参数为 t \in [l_i,r_i] 的直线。
我们将点按照 l_i 排序，破环成链再倍长。
从前往后扫，我们要使直线的 t 尽可能大，即 r_i。
我们设 nxt[i] 表示取了一条 t=r_i 的直线后下一个需要放直线的关键点的位置。
然后倍增处理。
对于每个可能的起始点求出往后 m 个之后的长度是否超过了 n。

\color{blue}{\texttt{CF1190F}}

*3400 Aug/09/2021 14:36
见此。

\color{black}{\texttt{CF1305G}}

*3500 Aug/10/2021 09:23

这题有两种做法，一种的复杂度更优秀但我并不想去写，反正大概是一种非常规最小生成树+高维前缀和。

另一种做法非常符合 brute force 的 tag，我也比较喜欢。

首先考虑他给钱的规则。
首先取一个 0 号点满足 a_0=0，并且已经在里面了。如果有边 i,j 那么边权为 a_i+a_j，然后求一个最大生成树再减去 \sum a_i。

怎么求最大生成树？复杂度不允许把所有边都建出来。

但是我们还是可以用 Kruskal。由于只有 a_i\ \text{and}\ a_j=0 才会连边因此 a_i + a_j = a_i\ \text{xor}\ a_j。
我们从大到小枚举这个 a_i + a_j，然后再枚举 a_i + a_j 的子集，用并查集维护，时间复杂度 w^{\log _2 3} \alpha (n)= 3^{18} \alpha (n)。

\color{blue}{\texttt{CF1534F2}}

*3000Aug/11/2021 09:14

见此。

\color{blue}{\texttt{CF1508D}}

*3000 Aug/20/2021 13:38

考虑假如所有点形成 1 个置换环，那么我们只需要钦定一个中心，然后不停地交换中心和周围的点就可以换好，并且显然没有相交线段。

对于两个置换环，我们知道可以通过交换两个点来使他们合并成一个大的置换环，但是要注意交换的这两个点的连线不能跨过钦定的中心和周围的连线。

那么我们钦定中心之后极角排序，只选择交换极角排序后相邻的点即可。

\color{black}{\texttt{*CF1375H}}

*3300 Aug/20/2021 15:01

又是一道忘了怎么做的题目，先咕。

\color{black}{\texttt{CF1383C}}

*3100 Aug/23/2021 14:59

见此。

\color{blue}{\texttt{*CF1558E}}

*3000 Aug/30/2021 06:18

~~其实这个*的原因是我忘记翻译少了点东西。~~

见此。

\color{black}{\texttt{CF1474F}}

*3000 Aug/30/2021 10:49

显然 x 没有半点 P 用。
第一问显然很简单，记录一下前缀最小值和当前值啥的就做完了，重点是第二问。
设第一问答案为 ans。

显然 LIS 的取值是一段连续的区间 [l,r]，而且第二问中求的这些 [l,r] 是不交的（否则可以构造出更大的），并且在序列上的位置也是不交的。
那么可以分开来计算。

如果暴力 dp 是 O(nv) 的。但是考虑到很多情况下一段连续的区间的 dp 值是相同的，所以可以合并再转移。

感觉这个好嘴巴啊，可能是有问题的？

或者可以列出转移的方程，然后发现很多区间的转移是相同的，用矩阵快速幂来优化。这个看上去不那么嘴巴。

\color{black}{\texttt{CF1558F}}

*3300 Aug/31/2021 05:16
见此。

\color{red}{\texttt{CF1428G2}}

*3000 Sep/02/2021 14:45

口胡的做法，没实现过，比二进制优化背包不知道低到哪里去了。

首先是我 G1 的做法，放个代码：

int F[7],p[7];
int n,k,q;
int S[N][6],v[N][6];
int f(int n,int x)
{
    if (n>k*(p[x+1]-1)) return -inf;
    if (x==0) return ((n/9==k-1 && n%3!=0)?n/9*3:n/3)*F[0];
    if (v[n][x]) return S[n][x];
    int ret=0,l=max(0LL,(n-k*(p[x]-1)+p[x]-1)/p[x]),r=min(9*k,n/p[x]);
    for (int i=l;i<=r;i++) ret=max(ret,f(n-i*p[x],x-1)+((i/9==k-1 && i%3!=0)?i/9*3:i/3)*F[x]);
    v[n][x]=1;S[n][x]=ret;
    return ret;
}
signed main()
{
    rd(k);for (int i=0;i<=5;i++) rd(F[i]);
    p[0]=1;for (int i=1;i<=6;i++) p[i]=p[i-1]*10;
    rd(q);while (q--) rd(n),cout<<f(n,5)<<"\n";
}

总之就是记忆化搜索，f(n,x) 表示用位数 \le x 的数表示 x 的最大价值。
然后观察一些这个转移式子，可以分几种情况然后对上一层搞个 rmq 啥的。
这样复杂度似乎就是对的了，但是太屎了没写。

\color{black}{\texttt{CF1428H}}

*3500 Sep/03/2021 11:57

见此。

\color{black}{\texttt{CF1053E}}

*3500 Sep/05/2021 08:56

见此。

\color{blue}{\texttt{*CF1434E}}

*3500 Sep/05/2021 14:58

先咕。

\color{red}{\texttt{CF1017H}}

*3300 Sep/06/2021 09:33

见此。

\color{black}{\texttt{CF1320F}}

*3500 Sep/07/2021 12:44

见此。

\color{black}{\texttt{CF1019C}}

*3000 Sep/09/2021 17:02

虽然不是很甘心，但是这道构造题我当时就是思路偏了然后在死胡同里出不来。

for (int i=1;i<=n;i++) if (!v[i]) for (int j:G[i]) if (j>i) v[j]=1;
for (int i=n;i>=1;i--) if (!v[i]) for (int j:G[i]) if (j<i) v[j]=1;

做完了，正确性显然。

\color{blue}{\texttt{CF1442E}}

*3000 Sep/10/2021 09:16

把边连接的两个点相同的权值定为 0，不同定为 1，那么类似于一个求树的直径。考虑到灰色点，用树型 dp，记录一下染成黑色/白色的状态即可。

\color{black}{\texttt{*CF1439D}}

*3100 Sep/11/2021 03:09

打算去学一个 O(n^2) 或 O(n \operatorname{polylog}(n)) 的做法。

\color{red}{\texttt{CF1411F}}

*3000 Sep/18/2021 15:33

见此。

\color{black}{\texttt{CF1466H}}

*3300 Sep/27/2021 15:53

听说翻译是已经简化过了的题意，已经转化了一部分了。我不管，我就按照翻译来做。

考虑把 a 形成的置换环看成若干个点，那么连出来的黑色边必须保证是个 DAG。

设每个点连出去的边数为 d_i，则每个 DAG 对应的排列 b 的数量为 \prod d_i!(n-d_i-1)!

然后得到一个状压 dp 的式子：

f_S = \sum _{T \subset S} (-1)^{|S-T|-1} f_T \cdot g(|T|,|S-T|)

有 $g(a,b)=(g(a,1))^b

而 g(a,1)= \sum_{i=0}^a {a \choose i}i!(n-i-1)!=\dfrac{n!}{n-a}。

复杂度 3^n \operatorname{poly}(n)，不够快。

把状态压为“每种大小的环分别有多少个”，状态数降为 1440 个，然后就做完了。

\color{red}{\texttt{CF1599B}}

*3100 Oct/09/2021 15:13

这篇文章居然更了.jpg。

第一次在比赛中做出 *3000+ 呢。

见此。

\color{red}{\texttt{CF1237H}}

*3300 Oct/12/2021 14:42

彩蛋：

Orz MoonPie

乱搞过的也算自己做出来的对吧。

\color{blue}{\texttt{CF1396E}}

*3200 Oct/15/2021 04:18

感谢 Clovers 给我推荐此题。

见此。

\color{black}{\texttt{CF1470E}}

*3200 Oct/28/2021 11:47

居然更新了.jpg

设 F(i,c,k)，表示仅考虑 [i,n] 这段后缀，花费的总代价不超过 c 的，结果第 k 小的翻转操作组中的，第一个翻转操作。

预处理一个列表 L(i,c) 表示 [i,n] 这段后缀，花费的总代价不超过 c，按得到的序列的字典序小到大排序的，“第一次操作”的序列。

然后注意到从 i \to i+1 的时候只会在 L 的头部和尾部添加元素。于是求出 L(1,c) 后可以用一个区间 [l_i,r_i] 表示 L(i,c)。

然后二分求出 F 即可。

\color{red}{\texttt{CF1572E}}

*3000 Oct/29/2021 15:47

二分答案+区间 dp 就做完了，为啥有 3000+，而且场上过的人还这么少？
~~都像我这个傻逼一样调不出 C 自闭了？~~

还有一些题，做了没写啊……可惜我，到此为止了。