1.
Problem A: 逆序对(reverse)
根据冒泡，只要逆序对个数够就有方案
经过思考，我们找到第一个操作个数大于的前缀，然后操作前一个前缀，这样前边变有序后，与当前数成逆序对一定是个后缀，然后根据需要选任意个即可
所以我们对任意方案构造出了 \(= 2\) 的解
等于一可以扫描线
等于 0 可以特判
码
2.
Problem B: 追忆(recall)
发现第一问求树高
考虑方案
选择一个节点，只有在没有同深度的时候才合法
感性理解只有消掉小的一边，大的一边才能操作
所以只能操作最长链
考虑对这条长链 \(dp\)，
设 \(f(l,r,k)\) 表示长链上的区间 \([l,r]\)，\(l\) 的子树总共受到了 \(k\) 次操作的影响的操作方案数。
转移在判断操作合法性后从 \(f(l,i,k)\) 和 \(f(i+1,r,k+1)\) 转移。
时间复杂度 \(O(d^4)\)。
码先鸽会
3.
Problem C: 字符串(string)
首先看数据范围，不能贪心
然后考虑经典 \(dp\) ，考虑 \(t\) 的前 \(i\) 个，匹配 \(s\) 的前 \(j\) 个是否合法
然后考场上就觉得 \(dp\) 存 0/1 太浪费，但不会了
到这一步发现都是位运算，直接用 \(bitset\) 优化即可
码
4.
Problem D: 浮夸(grandiloquence)
这是一道浮夸的题目
考场上一点不会，我是数据结构低手
发现对于操作一，\((dep_{u,v} + c - 1) % k + 1\) -> \((dep_v - dep_u + c - 1) % k + 1\)
发现在 \(dep_v\) 确定时这就是区间覆盖
于是因为 \(k\) 很小，所以直接开 \(k\) 颗树存 \(dep % k == i\) 的节点
然后没了
对于 \(3\) 操作，子树 \(siz\) 不固定，有经典 \(trick\) 就是维护欧拉序（括号序）
左右括号之间的就是其子树
用平衡树维护即可
码
相关新闻
