POI2011

13 / 17

Link(需要权限号)

Tree Rotations

线段树合并,统计一下子树大小。合并的时候把顺序对和逆序对取min。

注意空间要开到nlogn。

Difference

设$S_{ij}$表示前$i$位字母$j$的出现次数。
$$
\max (S_{ra}-S_{la})-(S_{rb}-S_{lb})=\max (S_{ra}-S_{rb})-(S_{la}-S_{lb})\\
S_{rb} \neq S_{lb}
$$
对于第$i$个数,它要么作为a,要么作为b(且b只出现了一次),这样可以分开考虑。

维护一下$Mn[i][j]$表示前缀中$\min_x S_{xi}-S_{xj}$,由于$S_{rb}\neq S_{lb}$所以也要维护转移的位置。

如果上次当前字母出现位置刚好是转移位置,则不满足$S_{rb}\neq S_{lb}$,答案减一。

复杂度$O(26 \cdot n)$

Shift

这个题很妙。考虑如果已经把前$i-1$个数放好了,第$i$个怎么放。把第$i$个放到第一个,要做的是解决掉$i-1$后面到最后的数,方法是不断1两下,然后2一下,一次可以解决两个。如果只剩一个,需要1一下,然后2两下。

但是这样对于n-1,1,2,3,…n这样的情况会有问题。那么可以不断执行2两下,然后把$n-1$提到最前面,这样每次可以把n-1往右边挪两个。如果距离是奇数,则无解。注意输出。

Conspiracy

直接输出方案的个数有点复杂,不妨考虑如果构造一个可行方案。如果把$i$选到团中,那么所有和他没有边的一定在独立集中;如果$i$选到独立集中,那么所有和他有边的一定在团中。于是就可以2-sat了。

然后你发现答案并不会很大,原因是如果$u$,$v$在同一个集合中,那么他们不可能同时存在于另一个集合。也就是说如果用现在这一组可行的方案去构造其他的方案,改变只有三种。

  • 一个人从立集中转换到团中
  • 一个人从团中转换到独立集中
  • 一个团中的和一个独立集中的交换

那么分别讨论一下,处理一下冲突即可。复杂度$O(n+m)$。

Lightning Conductor

听说是决策单调性的模板题,但是并不会,会一个$O(n\sqrt n)$的暴力,但是会T。
把式子移项,变成一个求最大值的形式。考虑到式子中的$sqrt$,那么这部分的取值只有根号种。这根号种的每一种对应了一个区间,在里面用st表查询最大值即可。

Lollipop

维护一个前缀和,对于每个询问x,如果x大于所有数的和就无解。因为元素是1或者2,前缀和中一定有一个x或者x+1。如果有x直接输出,否则就需要减去1。那么维护一下“从$i$开始有多少个2”,讨论一下位置就行了。

Temperature

考虑加入一个点$i$,如果$\max L \leq R_i $,那么可以加入。
于是可以维护一个单调队列。

Strongbox

如果x在集合中,gcd(n,x)也在集合中。所以最后的答案一定是$x, 2x, …$,那么要最小化x。
把$gcd(x_k,n)$求出约数,分解质因数。然后$gcd(a[i],gcd(x_k,n))$这些约数都是不能选的。
复杂度$O(d(n) \times n的质因子个数)$

Garbage

如果两个环相交,因为相同的部分抵消,一个环也能达到同样的效果。
所以答案一定可以表示为多个不相交的环。

只考虑需要遍历的边。此时如果有奇数度点则无解。
然后dfs找欧拉回路即可,此时需要当前弧优化,也就说走一条边删一条。
复杂度$O(n+m)$

Plot

先二分一个答案,然后二分一个段。对于每一段跑一个最小圆覆盖。
复杂度$O(n\log INF \log n)$。
因为忘记怎么求三个点外接圆了,就咕了。

Dynamite

二分答案,然后记$f[i]$表示子树中最远的未被处理的点,$g[i]$表示最近的被选择的点。从下往上转移dp。
用vector在loj和luogu被卡常了。

Inspection

考虑到如果最大的子树大小大于$n/2$,那么一定是无解。
所以只有重心满足有解。

答案为所有点的深度和减去最长链。
如果有两个重心,那么最后的那条边一定是在另一个子树中而不是自己这个子树中,需要特殊地考虑一下。

Meteors

整体二分。先咕。

Periodicity

神仙构造,不会。咕咕。

Party

每次选两个点,如果没有边就删掉。剩下的一定是一个不小于$n/3$大小的团。
证明:如果两个点没有边,要么一个在团里,一个在外;或者两个在外。
对于第一种情况。最后删掉$n/3$个在团里面的点就删不了了,最后剩下的一定是一个大于等于$n/3$大小的团。

Sticks

先按照长度sort,顺着扫一遍,维护三种颜色,每一种的最大值。判断一下即可。

Programming Contest

暴力一点可以费用流。S连人连题连T,听说会T啊。
题解是匈牙利,并不是很会。咕咕咕

Leave a Reply

Your email address will not be published. Required fields are marked *