Codeforces Global Round 14[CF1515]
题目链接
题解
A. Phoenix and Gold
因为每个数不相等，从小到大排序，遇到相等的，看是否能和后面的交换。不能交换则一定不行。
1 |
|
B. Phoenix and Puzzle
考虑直角边和斜边形成的正方形，即假设其直角边长为 $1$，则正方形个数 $n$ 要满足：
$\frac{n}{2}=x^2$ 或 $\frac{n}{2}=(\sqrt{2}x)^2$。
随便判断。
1 |
|
C. Phoenix and Towers
由于 $1\le h_i\le x$，那么每次选当前最小的塔就可以保证他们的差不超过 $x$ 了。
用一个堆维护即可。
1 |
|
D. Phoenix and Socks
显然，相同颜色的先进行配对。
接下来，不妨设配对完后剩下的左袜子比较多。
那么就先用左袜子变成右袜子与相同颜色的配对。注意不能使左袜子比右袜子少了。
剩下的随便做。
1 |
|
E. Phoenix and Computers
这个连续段DP的思路有点妙。
我们设 $f_{i,j}$ 表示已经填了 $i$ 个数，且共有 $j$ 段距离>1的连续段，每相邻两段的距离不确定时的方案数。
转移分5种情况讨论即可。很好写。
时间复杂度 $O(n^2)$。
也可以像题解那样，算出不自动打开的方案数，然后设 $f_{i,j}$ 为打开前 $i$ 个数，且自动打开 $j$ 个的方案数。但这样的复杂度就是 $O(n^3)$ 的了。
1 |
|
F. Phoenix and Earthquake
有一个十分牛逼的性质：任意一棵生成树，若 $\sum_{i=1}^na_i\geq (n-1)x$，那么一定可以。
考虑构造，对于某个子树 $u$ 以及其儿子 $v$，如果 $a_u+a_v>x$，那么直接操作。否则等后面再操作。若 $a_u+a_v\le x$，那么 $a_v\le x$，那么 $\sum_{i=1}^na_i-a_v\geq (n-2)x$，据归纳法可知，删掉 $v$ 以后还存在一个解。
然后一个dfs就好了。
1 |
|
G. Phoenix and Odometers
显然，$a$ 能走的点必在 $a$ 在内的强联通分量里。
而如果存在从 $u$ 走到 $v$ 的距离为 $l\pmod p$ 的路径，那么必存在 $v$ 到 $u$ 的距离为 $-l\pmod p$ 的路径，因为存在经过 $u,v$ 的环，从 $v$ 开始走这个环 $p-1$ 次，再走到 $u$ ，就可以了。
而显然，如果有两个环，环长分别为 $a,b$，那么 $\gcd(a,b)$ 能走出来。
那么算出来 $a$ 所在强联通分量所有环的环长的 $\gcd$ 即可。
在Kosaraju过程中，记录点到根节点距离，可以算出来。
时间复杂度 $O(n\log m)$。
1 |
|
H. Phoenix and Bits
And操作可以看做是Xor和Or操作的结合。于是我们只需要考虑Xor和Or操作即可。
Xor操作直接在Trie里打标记。
Or操作发现有时候会合并一些节点的左右儿子，有时候相当于打Xor标记。并且，合并左右儿子的时间复杂度不超过 $log^2n$ 。
如何判断什么时候打Xor标记呢？当且仅当Or操作中的数只存在某些位置为 $1$，且该节点中的数在这一位上均为 $0$。
那么记一下节点内所有值的Or，以及取反后的Or就好了。
对于区间操作，我们可以类似平衡树和线段树分裂的操作就可以了。
时间复杂度 $O(n\log^2m)$。
1 |
|