20/3/26
763C. Timofey and remoduling - 2500
题意 在模 (m) 意义下，给 (n) 个数字，能否 shuffle 出等差数列。
复盘 第一想法是好难不会，然后随手抓两个数字作差一下，发现一定是 (kd) 形式的，其中 (-(n-1)leq kleq n-1)，枚举 (k) 可求出 (d)，然后 check (d) 是否合法，怎么 check 呢？先根据元素和等于等差数列之和来算首项 (x)，然后依次判断 (x,x+d,x+2d...) 是否存在。然后TLE on 57，然后企图通过随机扰动解决问题，施展了半天，倒在了第59个点上，遂黔驴技穷。Bad Ending，每次施展随机化都是 Bad Ending 啊，马季恨。
题解
- 求出 (d) 就稳了。
- 先不考虑模域什么的啊。观察等差数列 (a_1,a_2,...,a_n) 发现差为 (kd) 的有序对个数恰为 (n-k) 个，那随手选两个元素作差一下，其结果 (x) 一定是 (kd) 的形式，统计一下几个有序对差为 (kd) 就能确定 (d) 了。
- 考虑模域呢，(i) 向 (i+d) 连边会成一个环，脑补一下长度为 (n) 的子串。
- 发现 (mgeq2n) 以上性质成立！
- (m<2n) 考虑 (a[]) 的补集可归结到上种 case，可求 (d)。
- 很有趣的 Big-Small 战法。
coding time 22(-6) here WA题小能手，能WA的地方都WA了一WA
20/3/27
788C. The Great Mixing - 2500
题意 给出浓度为 (a_i) 的一些溶液，配制指定浓度的溶液。
想法(11)
- 首先 (k leq 1000)
- (v_i=a_i-n)，选出最少个数物品权值之和为 0。
- 若 (v_i) 全正或者全负一定完蛋。
- 否则答案一定小于 2000
- (f[i][j]) 表示选 (i) 个物品能否凑数 (j)
- 思考一下发现 (j) 的取值从 ([-1000,1000]) 就无敌了
- 再思考一下 (f[j]) 表示凑出 (j) 最少用几个元素。BFS 即可。
coding 5 here
786C. Till I Collapse - 2600
想法(解体)
- 对于确定的一个 (k)，贪心地拿
- (sum ans leq nlogn)
- 枚举 (k) 一段一段拿，主席树 + 二分。好，我们得到了一个三个 log 做法。哦豁，完蛋。
- 考虑怎么优化？好难不会。
- 换做法，考虑一个元素一个元素 append？
- 注意到对于确定的 (k)，每 append 一个元素，答案要么 + 1，要么不变。
- 那什么时候 +1 呢？显然是 append 这个元素后，最后一段元素个数超过 (k)。
- 那 (append) 这个元素后哪些 (k) 最后一段元素种类数会 +1 呢？
- 这个得考虑 (append) 的元素上次出现的位置 (x)，如果一个 (k) 上一段结束位置 (leq x) 那么最后一段元素种类数会 +1。
- 权值线段树维护一下上一段结束位置为 (x) 的，元素种类数还需要增加多少，才会新开一段，这么个东西的区间最小值。
- 我觉得这个做法太卜了，5h 肯定写不完。
题解
- 我觉得自己苟狗附体了，主席树+二分....
- 施展主席树，对每个 (l)，将 ([l,n]) 中，每种元素最早出现的位置设为 1，其它位置设为 0，建线段树维护区间和。(O(n(logn)^2))
coding 17 (-1) here 写主席树，请想清楚空间，谢谢。
800C. Vulnerable Kerbals - 2400
想法(10)
- (ax\%m=b) 有解的充要条件是 (gcd(a,m)|b)
- 前缀积为 (a) 如果 append 某个元素后，前缀积变成 (b)，(a) 向 (b) 连边，当然有些节点是被 ban 掉的，求图上求最长路径。
- DP 即可。
coding here
20/3/28
今天起床后队切了场 300iq contest，静坐了 4h 啥也做不出，非常马季恨，然后想参加 ABC160 快活一下，结果又被打了，不幸啊！
CF 800D. Varying Kibibits - 2700 高维前缀和教学怪。基本思想是用 (f(i,x)) 表示 (0) 到 (i-1) 位比 (x) 大，其它位和 (x) 一致的元素集合。
coding here
ABC 160F 考虑以 1 为根，节点 (u) 作为 (u) 的子树中写着的数字最小的概率为 (frac{1}{sz[u]})，且对于不同的 (u) 是独立的，因此答案为 (frac{n!}{prod sz_i})。考虑以其它点为根，换根 dp 即可。（能不能从树推广到 DAG 呢？杨表的性质是怎么来的呢？疑惑！）
2020.3.29
2020.4.1
CF1332G. No Monotone Triples - 3000
题意 给序列 (a)，(q) 组查询，每组给 ([l,r])，求 ([l,r]) 中极长子序列，不存在长度为 3 的子序列单调。
做法
- 打表验证，答案 (leq 4)。
- 四元组 ((i,j,k,l)) 一定满足 (min(a_j,a_k)<a_i,a_l<max(a_j,a_k))。
- 先考虑 (a_i) 两两不同的 case。
- 考虑 (O(n^2)) 做法，枚举 (i)，从小到大枚举 (l)，即可求出每个 (i) 对应的最小 (l)。
- 倒着将元素插入，维护一个递增的，一个递减的单调栈，当前插入了 (a_i)，(a_i) 是栈顶的元素。考虑不出现在单调栈中的元素有什么性质。
- 再小心处理非两两不同的 case，处理答案为 3 的 case。
coding here，写一年，调一年，屡次诈胡，我怎么这么憨啊。
2020.4.2
睡不着，打印度区域赛玩，WA 晕了，遂逃跑。
776F. Sherlock's bet to Moriarty
诈胡
- 建图是树。
- 树分治。
- 胡了。
- 不会建图。
1332D. Walk on Matrix
看蓝猫学蓝猫题。嗯，就是按照样例搞一搞。
2020.4.4
2020.4.5
CF788C. Peterson Polyglot - 2600
启发式合并一下 trie，因为不难发现计算 (sz_1,sz_2) 的两棵 Trie 合并后 size 的复杂度为 (min(sz_1,sz_2))。
VP 了场 CF，玩杂技玩得躺地上了。
Codeforces Round #441 (Div. 1, by Moscow Team Olympiad)
A. Classroom Watch - 1200
枚举 (digsum) 即可。
B. Sorting the Coins - 1500
仔细观察一下操作趟数。
C. National Property - 2100
尝试按位考虑然后完蛋了，然后发现考虑两个相邻的字符串，找到位置最靠前的不同位置，讨论大小关系，good job，然后不知道哪根筋搭错了，开始玩 2-SAT，玩就算了，然后开始对着一份正确的 2-SAT 板子自闭了几乎整场比赛，每个点都被选中，非常令人沮丧！结果发现边建少了。
D. High Cry - 2200
idea 是枚举最大值的位置（有多个取最左边或最右边），单调栈搞一下位置 (pos) 上一个大于的位置，下一个大于等于的位置，再按 bit 预处理一下，在位置 (pos) 前面最近的 1，后面最近的 1。
E. Delivery Club - 2600
二分答案 (d)，考虑怎么 check。 想想这两个人怎么走位，一定是一个人站在原地，另一个到处抽搐，然后抽搐完后站在原地不动，换人抽搐..... 依次类推（好恐怖啊！），哎！我们发现只要相邻两个原地不动的位置 (x[i],x[j](i<j))，(x[i+1],x[i+2],...,x[j]) 到 (x[i]) 距离都小于等于 (d)，win 了啊！
F. Royal Questions - 2500
忽然发现，一个人有两个 choice 的问题，好多可以在这两个 choice 直接连边。问题转化为点向边的最大权 match！然后和派大星抓来一只水母，一看！哇！水母点和边一定存在完美匹配哎！问题转化为最大权水母森林。 （注意！连通性不一定要 keep！）
1328F. Make k Equal - 2400
if 写成 else if，卡一年。
1328E - Tree Queries - 2100
距离为 1？那爸爸一定在根到叶子路径上！
2020.4.19
- 快开学啊！
- 打牛客小白赛衣服被爆了
- 子集卷积 是个好东西
2020/4/23
一年一度的 GCJ！1A 被闹钟叫醒心情不好直接逃跑了。
- R1A Pattern Matching：构造题。(2sum len) 的上限，苟住前后缀，再把各字符串去掉星号拼一拼插在中间。
- R1A Pascal Walk：构造，注意第 k 行加起来是 (2^{k-1})，(1+...+30 < 500) 太令人开心了，从上往下走，要么拿一行，要么拿一个 1。
- R1A Square Dance：链表，小心实现。
- R1B Expogo: 手玩会发现每次四种决策至多只有一种合法，另外 3 种拿头也走不到，从起点出发模拟即可。另解：考虑 (k) 步可以 reach 的集合，倒着枚举每步填什么。
- R1B Blindfolded Bullseye: 先乱随机找到圆内任意一点，向右走到达 P，从 P 上走，从 P 下走，搞出了一条竖直的弦。垂径分弦。
- R1B Join the Ranks: 序列中相同的连续的数字可以 compress 一下，从中间割开很憨，一次操作段数至多减 2，因此答案下界为 (lceil frac{r(s-1)}{2}
ceil)，
[1 2] [3 4 5 1] 2....每次这样打就无敌了，成功取到下界。Corner case 是[5] [1 2 3 4]这样的。