StarSilk 题单笔记-2000
Link
- Lexicographically Largest
- LuoTianyi and the Floating Islands (Hard Version)
- Koxia and Number Theory
- Keshi in Search of AmShZ
- Another Array Problem
- Nezzar and Nice Beatmap
- Hospital Queue
- [Iris and the Tree](https://codeforces.com/problemset/problem/2006/B
Lexicographically Largest
首先，第 \(i\) 位数字最大贡献是 \(a_i+i\)，并且可以全部取到（倒着丢数即可）。
但因为 \(S\) 是不可重集，为了最大化字典序，我们需要把重复的同一个数字 \(x\) 变成 \(x-1,x-2,x-3\dots\)。
这很简单，我们把每个 \(a_i+i\) 丢进一个数组 \(b\) 里排倒序，然后 \(b_i>b_{i-1}\) 时把 \(b_i\) 推成 \(b_{i-1}-1\) 就好。
这总是能做到的吗？
是的，因为假设有两个数字相同，它们一定下标不同，把下标小的先拿走就好了。
LuoTianyi and the Floating Islands (Hard Version)
非常好题，使我的大脑旋转。
\(k\) 为奇数时，最优点一定是一个有人的节点。每远离最优点走一步都会使答案更劣，故答案为 \(1\)。
\(k\) 为偶数时，最优点可以不是有人的节点。并且不难注意到，最优点集合应当是被最优有人节点包络的连通块。
数点的期望就是每个点对应合法方案数之和再除以总方案数，但是数点要考虑当前点是不是有人点，所以我们不妨数边，点的期望就是边的期望 \(+1\)。
使一条边 \((u,v)\) 合法的方案数就是 \(\large \binom{siz_u}{\frac{k}{2}}\binom{siz_v}{\frac{k}{2}}\)。
Koxia and Number Theory
存在正整数 \(x\)，使得 \(a_i+x\) 两两互质。
反过来就是任意正整数 \(x\)，\(a_i+x\) 总有至少两个模 \(k\) 余 \(0\)。
对存在两个数相等的情况，肯定是 NO。
对元素两两互异的情况呢？
考虑原来模 \(k\) 同余的数在 \(+x\) 后依然同余。所以若对某个数 \(k\)，数组分落在每个同余类的元素个数都大于等于 \(2\)，则为 NO，否则为 YES。
Keshi in Search of AmShZ
“随机走一条”+“最多 \(d\) 天”=走最坏的一条，所以我们若要 Keshi 走一条边，一定要把指向距离终点更远的目标点的边全部断掉。
于是我们从 \(d_n=0\) 开始，每次删去目前 \(d\) 最小的点 \(v\)，对所有指向它的点 \(u\)：
其中 \(out_u\) 表示点 \(u\) 的出度。
显然每个点被删去时 \(d\) 已经取到最小值。
Another Array Problem
\(n>3\) 时答案必然是 \(n \cdot mx\)，构造方案：选择 \(mx\) 不在的一侧最靠边的两个元素，操作两次都变为 \(0\)，然后选端点和 \(mx\)，可以把数组的半边刷成 \(mx\)，对面重复上面的操作就好。
\(n=3\) 时，全局可以刷成 \(a_1,a_3\)，但不能刷成 \(a_2\)，所以还要考虑刷成 \(|a_1-a_2|,|a_2-a_3|\) 的情况。
\(n=2\) 时，要么是原状，要么全部刷成 \(|a_1-a_2|\)。
Nezzar and Nice Beatmap
蠢了一下下。
一开始想的任意 \(A_{i-1},A_{i},A_{i+1}\) 不合法，\(A_{i-1},A_{i+1},A_{i}\) 必然合法，秒了啊。
然后就 Wrong answer on test 7 了。
因为 \(A_{i-2},A_{i-1},A_{i+1}\) 可能不合法啊。
怎么办怎么办？
其实每跑一次所有不合法位置都会前移一位，那么跑 \(n\) 次就好了啊，看看数据范围，还是秒了啊。
Add：相邻向量点积应该是可以到 8e18 的，理论应该开 __int128，但是 i64 日过去了。
Hospital Queue
建议先写：[HNOI2015] 菜肴制作 和 [NOI2010] 航空管制。
套路地，我们将条件二转化为对反图做拓扑，条件一就变为必须在 \(n-k_i\) 次操作后取出。
于是我们用一个小根堆维护各点按 \(n-k_i\) 优先拓扑，则可得到一个合法方案。
然后考虑某个点尽早出现等价于拓扑时尽量晚出堆，那么我们每次把它取出时，考察一下能不能取堆下一位，能则二者交换就好。
[Iris and the Tree](https://codeforces.com/problemset/problem/2006/B
每条边只会在两对节点的 dist 上，我们暴力维护每对节点 dist 涉及的不确定边，修改复杂度是 \(\mathcal{O}(1)\) 的。
对于所有边都确定的一条 dist，答案是固定的。
否则答案就是 dist 上固定边权值和加上剩余的 \(w\)。