Conspiracy
考虑如果已经有了一组方案怎么得到其它的方案,可以发现只有以下三种情况:团内的一个点移了出去、团外的一个点移了进来、交换了团内和团外的两个点。只需要求出每个点是不是之和对方集合中的一个点冲突即可。
于是考虑构造一组方案。注意到每个点只能在团内或团外,于是 2-SAT 即可。
可能会有些卡空间。
Lollipop
可以发现如果存在一段和为 $w$,则一定存在一段和为 $w-2$,因为当其端点要么有一个 $2$,要么是两个 $1$。
于是我们只需要找到最大的和为奇数和偶数的段即可。其中一定有一个是 $[1,n]$,另一个一定是整段去掉最左边的 $1$ 及其左边或者去掉最右边一个 $1$ 及其右边。
Lightning Conductor
首先正反各做一遍把绝对值拆掉。
设 $dp_i$ 表示 $\max\left\{a_j+\sqrt{i-j}-a_i\right\}$,显然这个东西具有决策单调性,于是维护二分栈即可。
Shift
Plot
Strongbox
显然所有密码构成一个群 $(G,+)$。于是可以给出一些结论:
- 如果 $a$ 和 $b$ 都是密码,则 $\gcd(a,b)$ 也是密码。
- 如果 $a$ 是密码,则 $\gcd(a,n)$ 也是密码。
- 设 $G$ 中的最小非零元素为 $d$,则 $G=\left\{0,d,2d,\cdots\right\}$。
- 设 $G$ 中最小非零元素为 $d$,则 $d|n$,$|G|=\frac{n}{d}$。
一个想法是直接枚举 $\gcd(m_k,n)$ 的所有约数然后判断是否合法,然而直接判断是 $\mathcal{O}(k\mathbf{d}(n))$ 的,无法通过。于是可以先标记哪些约数是某个 $m_i(i\neq k)$,这样子检查时只要枚举倍数即可,就可以过了?
Difference
考虑枚举出现次数最多和最少的字符,把前者看作 $1$,后者看作 $-1$,则问题变为求一个包含至少一个 $-1$ 的最大子段和。
这个东西比较好求,只要先把和设为 $-1$,在遇到第一个 $-1$ 时不把和 $-1$,在和 $<0$ 时把和设为 $-1$ 即可。
需要先预处理出每个字符对应的位置然后归并。
Garbage
只保留前后权值变化的边,每次找一个环出来消掉即可。正确性显然。
Tree Rotations
首先,对于每个节点我们只计算它不同儿子贡献的逆序对数,累加即可得到总的逆序对数。
这样子交换儿子是不会影响到祖先的贡献的,于是我们可以选择两个儿子产生的逆序对数较小的顺序。
两种顺序产生的逆序对数可以在线段树合并时计算出来。
Temperature
维护一个最低温递减的单调队列,每次弹掉队头最低温比当前最高温高的元素,然后最后一个弹出的元素 $+1$ 到当前位置都是合法的,更新答案即可。
Dynamite
显然二分答案,问题变为每个点可以覆盖距离 $\leq mid$ 的点,求能否用 $m$ 个点覆盖整棵树。
有一个显然的贪心,即每次选一个没被覆盖的最深的点。于是我们只要在 DFS 时维护一下子树内最浅的选出来的点和最深的未被覆盖的点,然后随便搞一下就好了。注意特判根。
Party
枚举两个点,如果它们之间没有连边就给这两个点打一个标记然后 break
。
这样子每个不在团中的点会标记掉至多一个在团中的点,于是至少剩下 $\frac{1}{3}n$ 个点。
Inspection
如果 $u$ 满足条件,显然应有其最大的子树的大小 $\leq\left\lfloor\frac{n}{2}\right\rfloor$,而这样的点一定是重心。
而从一个点出发的答案显然为所有点的深度和乘 $2$ 再减去最深的点的深度。因为重心只有至多 $2$ 个所以可以直接暴力。
但是需要注意的是当 $n$ 为偶数且存在一棵大小恰好为 $\frac{n}{2}$ 的子树时最后访问的点一定在其中,所以我们这时只能减掉这棵子树中最深的点的深度。
Periodicity
咕了,可以看 Itst 的题解。
Meteors
整体二分,用树状数组实现区间加、单点查询即可。
注意累加的时候如果超过了希望的数量就可以直接 break
了,否则可能会爆 long long
。
Sticks
显然三根木棍长度接近最有可能,所以可以把所有木棍按长度排序然后从前往后扫一遍,同时维护三根颜色不同的木棍即可。
Programming Contest
容易想到一个利用费用递增的费用流,即源点向每个人连若干条费用为 $r,2r,3r,\cdots$ 的边,然而并跑不过。
考虑动态加边,每次对于所有人加一条源点流向它的边,然后求最大流即可得到新增的流量,再乘 $ir$ 即可得到新增的罚时。当没有新增流量时 break
即可。
方案根据残量网络构造即可。