CCPC 2024 北京市赛打铁记
前言
没想到自己参加的第一场 ACM/ICPC 正式比赛竟然会在高中。
Day 0
机房用 SEERC 2018 的题出了场模拟赛。
我们队只切了三个题,说实话表现比较惨。隔壁小朋友 hyf 他们的队伍竟然切了 6 题,能不能每一队都发一个小朋友来 carry。
切掉的三个题里只有 E - [SEERC2018] Fishermen 是我自己做出来的,明明是签到题还花了好久时间。zzj 写掉了 [B - SEERC2018] Broken Watch 和 C - [SEERC2018] Tree,思路是 cyx 和 zzj 两个人一块想出来的,我参与的比较少。唉还是只能靠队友带飞。赛时还和 cyx 想了 D - [SEERC2018] Space Station 和 H - [SEERC2018] Modern Djinn,但是毫无结果。
赛后一翻题解,卧槽 H 正解怎么是个随机化,有病吧。J 明明这么可爱场上却没人做,应该是被题面吓跑了。
希望今天的发挥能给明天涨点 rp。
Day 1
昨天晚上没睡好,可能也有一部分是【数据删除】的缘故,早上不到六点就爬起来了。
带了一本紫书和 C ...
CF1930C Lexicographically Largest 题解
前言
很有意思的一道题。
做法参考了 CF 官方题解。
思路
考虑进行一次操作会对其他元素造成的影响。
删除 aia_iai 会使其右边的所有元素下标减少 111,而我们的任务是让最后得到的集合 SSS 字典序最大,所以我们希望每个数的下标都尽量不要减少。
但问题在于 SSS 并不是一个可重集,故我们不能直接从右往左执行操作,因为这样给 SSS 带来的元素虽然是最大的,但可能会出现重复的情况,例如样例里的 2 1,如果先删右边的 111 再删 222 就会带来两个重复的 333,去重后字典序小于答案 3 2。
于是我们可以考虑每个数的下标减小了几次,记作 ci (0≤ci<i)c_i\ (0\leq c_i<i)ci (0≤ci<i),则任务就变成了对于每个 aia_iai 找到最小的 cic_ici,使得对于任意 j<ij<ij<i,ai+i−ci≠aj+j−cja_i+i-c_i≠a_j+j-c_jai+i−ci=aj+j−cj。发现无论求解 cic_ici 的顺序如何,答案最优性都不会受到影响。
同时,由于 c1=0c ...
Sth.
1ac26911158bb0a0335098254784b1df401a9a7299d482560702102f8d41a2ac5859957abeb416857fbc04b087c5fb2074335ec31d6efcdb66cf5b48859746fdefc6e4250f78b87129c3d3002ad4a375c3226128a2a4faf56902924bc91b309e20c21f1d52ad5c02a527e66e8f69a87c7d115b8fe1183892ab607dff0706219fdd234c89db47f5d993b5af8287d7c6f63f170c1cbe621333eccf0ca37f63334c30468a00397ef34a9ca65e927e16c1308a57db645427c0f983ab42665189b0ecc44f5f739920fb29ce220eec944837df8c54ed3ab315a5eab1596b437d0ac1ebb1a03983c4d79add12a33f0274b18a00da7071e73ea0c56d0 ...
[省选联考 2021 A/B 卷] 卡牌游戏 做题笔记
前言
非常有趣的一道双指针好题,前前后后思考了好几天并写了一天半,终于实现了题解大佬的线性做法,做完这道题也让我对双指针以及函数单调性有了更深的理解。目前已经在所有 oj 上都 AC 了,正确性应该是没有问题的。这篇做题笔记思路与该大佬的题解基本一致,在细节方面有一些补充。
思路
这道题的切入点就是观察最终序列的翻转方式。
性质 1
观察可得性质 1:
最终序列被翻转的卡片一定是一段前缀和一段后缀。
证明 1
由于给出的 aaa 是升序的,所以翻转中间的卡片要么对最小值和最大值无影响(因为中间的 aia_iai 一定 ≥a1\geq a_1≥a1,≤an\leq a_n≤an),要么会使最小值更小/使最大值更大,而我们要求的是最小极差,所以翻转中间的卡片没有意义。
思考怎么用这个性质去解题。
设已经翻转了长度为 lll 的一段前缀和长度为 rrr 的一段后缀,可以定义如下变量:
lmaxl=max{bi}(1≤i≤l)lmax_l=\max\{b_i\}(1\leq i\leq l)lmaxl=max{bi}(1≤i≤l);
lminl=min(min{bi ...
AtCoder Beginner Contest 345 E - Colorful Subsequence 题解
题意
有 NNN 个球,每一个球有一个颜色 CiC_iCi 和价值 ViV_iVi,现在要删除其中的 KKK 个球,使得剩下的球没有相邻的两个球颜色相等。求剩下的球的最大价值总和。
数据范围
1≤K<N≤2×1051\leq K < N \leq 2\times 10^51≤K<N≤2×105
K≤500K \leq 500K≤500
思路
考虑 dp。
设计状态 fi,jf_{i,j}fi,j 代表不删除第 iii 个球,在前面删除 jjj 个球时最大的价值总和。
则 fi,jf_{i,j}fi,j 一定由前面的第 kkk 个球删除 (k,i)(k,i)(k,i) 之间的全部 i−k−1i-k-1i−k−1 个球转移而来,状态转移方程为 fi,j=max{fk,j−(i−k−1)}(j≤K,i−j−1≤k<i,ci≠ck)+vif_{i,j}=\max\{f_{k,j-(i-k-1)}\}(j\leq K,i-j-1\leq k<i,c_i≠c_k)+v_ifi,j=max{fk,j−(i−k−1)}(j≤K,i−j−1≤k<i ...
CF1764G2 Doremy's Perfect DS Class (Medium Version) 题解
前言
更可爱的阅读体验
思路
前置芝士:CF1764G1 的解法。
考虑在 G1 的基础上进行一个小小的优化。
G1 的最大询问次数是 3logn3\log n3logn,其瓶颈在于当 nnn 为偶数时,我们需要预先额外花费 logn\log nlogn 的时间去找到 nnn 的位置,从而消除后续询问里 nnn 的影响,因为这时 nnn 与 111 一样都具有除以 222 向下取整的结果唯一的性质。
而 G2 把最大询问次数限制到了 252525 次,所以我们需要找一种更高效的辨别 nnn 和 111 的方式来代替预先询问。
当我们对 [1,k][1,k][1,k] 和 [k+1,n][k+1,n][k+1,n] 两个区间进行询问时,除了 111 和 nnn 之外,两个区间里无法配对数字的数量一定是相等的,那我们可以分类讨论 111 和 nnn 的位置:
当 111 和 nnn 在同一个区间里时,这个区间里未配对的数字个数会比另一边大 222,于是继续处理这个区间就好。
当 111 和 nnn 分居在两个区间里时,两个区间里未配对的数字个数相等,我们只需要对其中一个区间进行一次 ...
CF1932D Card Games 题解
思路
赛时没想出来贪心,于是写了爆搜但一直 WA,赛后发现是 dfs 函数忘记回溯了。
时间复杂度看起来是假的,但是跑得很快,推测是一堆卡牌里面能够进行匹配的数量实际上并没有那么多,实测最慢的点才 15ms,提交记录:link
爆搜的方法就是先用 (2n)2(2n)^2(2n)2 的时间预处理每两张牌是否能够匹配(匹配条件即两张牌中有且只有一张能赢过对方),然后再从第一张牌开始搜:对于每一张牌枚举和它匹配的另一张牌,标记之后接着搜下一张,搜不到就回溯继续搜,终止条件就是搜到第 2n2n2n 张牌时 return 1 以及无解时 return 0。
代码
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667constexpr int N = 40;char trump;int n;struct card{ char suit;int rank; inline void ...
AtCoder Beginner Contest 340 E - Mancala 2 题解
题意
有编号为 000 到 N−1N-1N−1 的 NNN 个盒子。最初,盒子 iii 里有 AiA_iAi 个球。
高桥君将按顺序对 i=1,2,…,Mi=1,2,\ldots,Mi=1,2,…,M 执行以下操作:
将一个变量 CCC 设置为 000。
从盒子 BiB_iBi 中取出所有球并拿在手里。
当手里至少还有一个球时,重复以下过程:
将 CCC 的值增加 111。
将手里的一个球放入盒子 (Bi+C) mod N(B_i+C) \bmod N(Bi+C)modN 中。
在完成所有操作后,确定每个盒子中的球数。
思路
题面中的操作可以被转化为以下步骤:
把位置 iii 的值归零;
将整个序列的值增加 ⌊AiN⌋\lfloor\frac{A_i}{N}\rfloor⌊NAi⌋;
将 (i,min(i+Aimod N,N)](i,\min(i+A_i\mod N,N)](i,min(i+AimodN,N)] 的值增加 111;
如果 i+Aimod N>Ni+A_i\mod N>Ni+AimodN>N,再将 [1,i+Aimod N− ...
AtCoder Beginner Contest 340 D - Super Takahashi Bros. 题解
题意
有一个包含 NNN 个关卡的游戏。起初,只有第 111 个关卡可以游玩。
在每个可以被游玩的关卡 iii 中,你可以进行以下两种操作:
花费 AiA_iAi 的时间通关,并解锁关卡 i+1i+1i+1。
花费 BiB_iBi 的时间通关,并解锁关卡 XiX_iXi。
输出解锁关卡 NNN 所需的最短时间。
思路
看到这种题首先想到的当然是 dp,但对于这道题来说 dp 的转移顺序并不好确定,于是交了一发记忆化搜索却 WA 了。
这种情况下我们可以考虑建图,把关卡编号看成点,解锁关卡花费的时间看成边,然后我们就只需要对每个点 iii 到点 i+1i+1i+1 连一条长度为 AiA_iAi 的边,到点 XiX_iXi 连一条长度为 BiB_iBi 的边,直接以点 111 为起点跑最短路即可,最终到点 NNN 的距离就是答案。
代码
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263co ...