机房颓废合集。
一把 VP 2h，我每天在机房 10h+，那我是不是每天能打 5 把啊？
\(\mathbb{ARC \ 143}\)
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| 300(3) | 500(1) | 600(1) | 700 | 700 | - |
| 8:14 | 16:18 | 31:35 | 57:21 | 86:10 | - |
performance: 2706
找了近几场里面难度最平和的一场。 /kk
脑子还算清醒，但是这套题属实是送我技能树上了。
A
哈哈，WA 了三发因为不开 long long。
如果两个小的加起来都耗不完最大的，那就无解，否则每次都拿最大和次大的耗，等到三个数相同了就一起减小，发现次数就是最大数。
B
容斥算算就行了，具体做法是钦定不合法的位置用总数减去即可。
式子是 \((n^2)! - ((n - 1)^2)! \cdot n^2 \cdot \binom{n^2}{2n - 1}((n - 1)!)^2\)，推导过程还算 ez。
C
博弈中跟棋操作非常常见，于是上来就把所有的 \(a_i\) 对 \((x + y)\) 取模。
然后分类讨论一下 \(a_i\) 和 \(x, y\) 的大小关系，分别统计先后手能够取的堆数，但是注意一下先后手能同时取到的情况，这时先手只能先去取这一堆才能更优。
D
这是什么？一眼二分图？
拆一下，每个点拆成入度和出度，所以这道题变成了给无向边定向，然后这题我会了。
丢一个很相似的problem。
做法是在 dfs 树上的边方向不变，返祖边从后代指向祖先。
因为性质是原图上的 \((u, v)\) 如果是桥，那么现在无论怎么连都还是桥。
如果 \(\exists u \rightarrow v, v \rightarrow u\)，那么我删一条边无所谓，这是不影响连通性的。
E
又来？首先保证有解，老套路了，从叶子开始（我想了很久，为什么这一类在树上操作的题从叶子开始能很快突破，核心在于叶子节点的性质很强，只需要考虑它和它父亲的联系，后续的操作可以向上合并）如果它是白色，那么必须比它的父亲先操作，否则它会因为父节点的操作变成黑色，导致无解，反之，必须比它的父亲后操作。
于是反复利用这个性质往上合并，
这样可以把 DAG 建出来，直接优先队列贪。是否有解直接看根节点计算后颜色即可。
F
全网就没啥人过，做不动了。
\(\mathbb{ARC \ 154}\)
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| 300 | 400(1) | 500(1) | (3) | - | - |
| 3:42 | 10:23 | 30:21 | - | - | - |
performance: 2133
绷，这个 D 做得确实下饭 😣 但是好消息是没做出来（这样就没有罚时了）
\(\mathbb{ARC \ 154 \ A}\)
贪心换，小的全放 \(A\) ，大的全放在 \(B\) 。
\(\mathbb{ARC \ 154 \ B}\)
发现操作等价于把前面 \(k\) 个拿出来随便插，那么直接判断后面的是否是 \(s\) 的子串就可以了，套二分就可以过了。
\(\mathbb{ARC \ 154 \ C}\)
直接模拟即可。。。
\(\mathbb{ARC \ 154 \ D}\)
这个交互有点意思，我们可以首先把 \(1\) 的位置用 \(n\) 次问出来。
问出来之后就可以 stable_sort 排序直接过了。
\(\mathbb{ARC \ 154 \ E}\)
首先改写这个贡献的式子
假设我已经拿到了最后的序列，那么根据定义，每个点的贡献是
考虑这个贡献用动态的方式呈现，首先这个序列有序，对于一个位置 \(i\) ，将他右边的一个数 \(j\) 放在前面去，这个位置变成 \(i + 1\) ，此时贡献是让 \(g(i)+1\) ，反之，放一个左边的到后面去，位置变成 \(i - 1\) 贡献 \(g(i) - 1\) ，那么可以得到 \(g(i)=i(i - Q_i)\) 。
那么此时计算 \(Q_i\) 在某个位置上的期望就可以了，很容易发现，这个期望很对称，将 \(Q_i\) 放在 \(i\) 和放在 \(n - i + 1\) 这两个位置上的方案数相同，那么最后位置的期望就是 \(\frac{n + 1}{2}\) 。