0103abc 的网站

先找不变量，可以发现进行一次操作后数组的长度会减少 $2$，数组相邻元素差的绝对值最多增加 $1$。因此记 $f(a)$ 表示 $a$ 序列的长度加上 $a$ 序列相邻元素差的绝对值的和，则所有合法的序列均满足 $f(a)\le n$。然后分析奇偶性可得合法序列的长度和 $n$...

先把题意转化为对一个给定的集合 $S$，选取一个模数 $m$ 和余数 $r$ 使得集合 $S$ 中 $\bmod\ m = r$ 的数尽量多。很明显 $m$ 取质数一定不会更差，因为若 $m$ 取了一个合数，则取 $m$ 的任何一个质因数都不会比取 $m$...

可以发现若 $n\neq 1$，则可确定数字数量的上界是 $\max(0,n-4)$。下面考虑证明这一点： 若 $n<3$，则显然无法询问出任何有效信息。 若 $n=3$，则显然询问出全局中位数无法确定任何一个位置的值。 若 $n>3$，则考虑 $a$ 序列中最小的两个数，设其分别位于 $p,q$...

考虑区间 dp。设 $f_{l,r,i,j}$ 表示当前删除了区间 $[l,r]$，整个区间都删除完后 $r+1$ 后面的下一个存活点是 $i$，且 $j$ 必须在 $[l,j-1]$ 区间内点全部删除完后才能被删除。 这个状态看着就很奇怪，考虑这个 $j$ 有什么用。设 $[l,r]$...

设 $f{i,j}$ 表示以 $i$ 为根的子树中满 $j$ 叉树的深度最大值是多少。由满 $j$ 叉树的性质可知若 $i$ 点共有 $ci$ 个子结点，则 $j>ci$ 时必有 $f{i,j}=1$。因此合法的 dp 状态数是 $O(n)$ 级别的。转移也是容易的，直接在其子树内找 $f$...

首先考虑一个更简单的问题：如果有一个长度为 $n$ 的有序序列 $a$ 和一个长度为 $m$ 的有序序列 $b$，如何通过 $n+m$ 次操作简单的归并这两个序列。容易想到循环移位一轮序列 $b$，然后再循环移位的过程中把序列 $a$ 中的元素直接对应插入到序列 $b$ 内即可。...

又一遍又一遍那天相见 又一遍又一遍思绪万千 在夏日尽头的你能否回忆起最初时的誓约 临走前你最后露出笑脸 我们的夏日在这里完结 暑假结束了/ll 有一个显然的观察是：深度不同的弹珠永远也不会相遇。 考虑计数转概率，记 $f{u,i}$ 表示 $u$ 为根的子树中，距离 $u$ 点恰好为 $i$...

容易想到平面图转对偶图，然后记 $disi$ 表示 $i$ 区域到海边所需要经过的最少区域数量，则对相邻两个区域 $u,v$ 必有 $|disu-dis_v|\le 1$，证明简单调整即可。 然后考虑什么时候存在点对 $(u,v)$ 满足 ...

考虑把整个合并的过程看作一个二叉树的结构，每个非叶子结点都恰好有左儿子和右儿子两个子结点，表示把左儿子结点对应的所有书放到有儿子对应的书的上面。则如果这个二叉树的结构已经确定，则总费用可以被拆分为重量和磨损两个部分。具体的：记 $cnti$ 表示 $i$...

部分参考了官方题解。 题目给的操作直接用起来很不方便，因此套路的考虑先构造几个操作。若两个集合 $A,B$ 都已经被确定为是独立集，则考虑先把 $A$ 集合按照任意顺序加入 $S$ 中，然后再把 $B$ 集合按照任意顺序加入 $S$ 中。则此时必然可以得到集合 $N(A)\cap B$ 的信息（即...