A Lily
直接做即可。
B Code With No Forces
考虑状压 DP:\(f(S,T,R)\) 表示对于每个人,时间是否达到要求的状态压缩为 \(S\),空间是否达到要求的状态压缩为 \(T\),运行结果是否达到要求的状态压缩为 \(R\),转移直接枚举下一个跑的测试点即可。
C Array Concatenation
实际上最终序列只有两种答案不同的情况:\(A^{2^m}\) 或者 \(A^{2^{m-1}}(A^R)^{2^{m-1}}\)。分别算一下即可。
D Alice's Dolls
Poly 题,跳过。
E Draw a triangle
我们令 \(AB:ax+by+c=0\),\(C(x_0+x',y_0+y')\),那么我们实际上只需要要求 \(|ax'+by'|\) 最小即可。裴蜀定理告诉我们这个结果是 \(\gcd(a,b)\),然后 exgcd 求一下即可。
F Union of Circular Sectors
几何题,跳过。
G Group Homework
最优情况要么是两个路径无交,要么是路径有一个交点。分很多很多类情况讨论一下即可。
H Hysteretic Racing
考虑直接连续段均摊后,用单侧递归线段树去维护。会比较复杂。
I Invincible Hotel
可能这场唯一的厉害题是这道吧。考虑枚举大串,然后枚举大串的前缀,通过 fail 树得到其最长与次长后缀。把这些串拿出来,形成可重集。一个串可以当小串当且仅当它在可重集中出现次数等于它在大串中的真实出现次数,并且这些串去重以后能覆盖它的串只有一个。两个都可以通过 BIT 来求。
K Barrel Theory
特判掉 \(n=1,2,3\)。然后分四类情况讨论:\(n\) 偶 \(m\) 偶(\(1,1,\dots\)),\(n\) 偶 \(m\) 奇(\(2,3,2,2,\dots\)),\(n\) 奇 \(m\) 偶(\(2,3,1,\dots\)),\(m\) 奇 \(n\) 偶(\(2,4,7,2,2,\dots\))。
L Largest Unique Wins
\([0,0,\dots,0,1],[0,0,\dots,0,1],[0,0,\dots,1,0],[0,0,\dots,1,0],\dots,[1,0,\dots,0]\) 这样填即可。
M Youth Finale
考虑用 deque 维护序列,然后注意到 R 操作的影响容易,S 操作的影响只需看序列的第一个数即可。
标签:dots,大串,Guilin,CCPC,枚举,即可,2022,序列 From: https://www.cnblogs.com/TetrisCandy/p/17969832