A.进攻
对战机和基地分别按破坏力和防御值从小到大排序，维护一个前缀最大值即可，复杂度O(n)
B.二进制
我们考虑对于二进制下每一位分开处理，记录该位若是 1 会变成几，若是 0 会变成几，以此为标准分配三种运算即可，3 次操作之内即可满足条件，复杂度O(nloga)
C.积木
首先可以发现当 n 为奇数时必然无解
对于 n 是偶数，我们给出两种构造方案
1：从外向内一圈一圈黑白染色，上下两层颜色相反即可
2：以一个 
的方块为基本单位，黑白相间摆满整个立方体即可
D.种树
二分答案，考虑如何 check 答案 mid 是否合法我们将 val > mid 的权值定义成 0 ，将
用 f[i][0/1] 表示该节点获得 0/1 最多能用几次 min ，显然 min 操作用 max 替换不会变的更劣，故当
在比赛中，发现最多只能获得深度小于等于操作次数的点的子树min传到根，这个做法也是对哒
E.考试
贪心，把一样的尽量当他是对的，不一样的尽量当他是错的即可
F.项链
用双向链表模拟即可
G.涂色
输出 n+1 即可，模数是来吓人的
H.圆
分类讨论一下即可，这里出题人可能没说清楚，有交的是指有交点，故相切也算
I.修改
为什么？可以这样考虑：由于所有点的值为 0，所以其差分数组也都为 0
把操作视为在差分数组的
而上面的边的含义是差分值的转移，所以充要条件是：每个点都可以通过选择的有向边到达虚点
由于边都是从前往后连的，所以有向边可以视为无向边，最后必然形成了一棵以虚点为根的树，最小代价为最小生成树大小
J.克隆
我们发现这个 很有趣，显然所有的 k 个人能走的点数总和 >=2n
很自然的想到一个叫欧拉序的东西，这个序列的长度是 n+m=2n-1 的
那么把欧拉序拉下来，让分身在欧拉序上走即可
全部评论
(1) 回帖