XCPC 赛季好题分享
yummy
·
·
个人记录
| 题号 |
难度 |
yummy 的推荐度 |
| CCPC 预选赛 K |
下位绿 |
可能是套路的，但对我而言很新 |
| ICPC 预选赛 C |
上位蓝 |
牛逼 |
CCPC 预选赛 K
Alice 和 Bob 取石子，初始有 n 颗石子，Alice 先手。
第一次 Alice 可以拿走不超过 k 颗石子，之后每个人取走的石子个数必须是上一个人的约数。请问谁能获胜。
### Solution
从手玩规律开始。
- 如果 $n$ 是奇数，那么 Alice 胜。
- 如果 $k\ge n$，那么 Alice 胜。
- 如果 $n$ 是偶数，那么：
- 如果 $n=4m+2$，$k\ge 2$，那么 Alice 胜。
- 如果 $n=4m$，$k=2$，那么 Bob 胜。如果 $k\ge 2$，那么还要讨论。
我们发现如果接着讨论，其实会获得完全一样的结构。具体地，设 $n=p\cdot 2^q$（其中 $p$ 奇数，$q$ 自然数），那么如果 $k\ge 2^q$，Alice 获胜。具体只要先取 $2^q$ 枚石子，然后直接模仿 Bob 即可。
## ICPC 预选赛 C
给出 $n$ 个区间 $[l_i,r_i]$（$1\le l_i\le r_i\le n$），询问有多少个 $1\sim n$ 的排列 $p$ 使得 $p_i\in [l_i,r_i]$ 恒成立，**输出答案 $\bmod 2$ 的结果即可**。
多测，$1\le \sum n\le 10^6$。
### Gossips
这个题考场上 1 h 的时候就已经开了（跟榜的时候发现此时这题 AC 数不低），但是 3 h 的时候才 AC。（当让中途被打断了两次，一次去切 F，另一次切了 G，两题都切了再回头想的 C）。
当时开题的时候注意到奇偶性和排列，第一步映入脑海的就是矩阵行列式的奇偶性——只要行列式是偶数答案就是偶数，否则就是奇数。
然而没法直接求这玩意的行列式，同时我高等代数学的也实在拉胯，所以面对这么一个行列式也无从下手。（不过后来和同校的 wyh 同学交流的时候，他说他们队伍用行列式做出来了相同结论。不愧是高等代数 A+ 的选手。）
于是开始考虑如何把所有区间转化成一些区间的无交并，然后发现对于两个相交区间 $I_1,I_2$，你只能转化成“$I_1\setminus I_2, I_2$ 或 $I_1\cap I_2, I_2\setminus I_1$” 这种形式，复杂度是指数级。
但是这个方法不是完全没救——不难发现，两种可能的拆法中，不可能两种拆法区间长度都是奇数，只不过你不清楚到底哪种拆法对答案的贡献是奇数罢了。
然后去写 F 和 G 了。
### Solution（不省流版）
回来重新想，我认为容斥应该也可做。
不难发现，如果 $l_i$ 固定为 $1$，那么方案数是简单的——只要把所有 $r_i$ 排序，方案数就是 $\prod\limits_{i=1}^n (r_i-i+1)$。
套一下容斥原理，因为本题模数是 $2$，所以 $(-1)^i$ 也无关紧要。问题变成 $\sum\limits_{R_i\in \{ l_i-1, r_i\}} \prod\limits_{i=1}^n (R_i\text{排序后}-i+1)$。
（队友：你这个含有排序的话，基本没救。）
（静默。思考行列式方案的可行性。）
（队友：答案可能是奇妙推式子，但是绝对不可能是行列式。）
考虑何时答案为奇数，需要每一个 $R_i$ 排序后都放在和奇偶性相同的位置。如果 $R_i$ 有相同的，那么这两个相同数字一定占据一奇一偶两个位置，从而答案是偶数。又 $R_i$ 排过序，所以 $R_i$ 贡献答案当且仅当 $1\sim n$ 各有一个。
换言之，输出 $1$ 当且仅当从一排集合 $\{l_i-1,r_i\}$ 中有奇数种方法每行选一个，使得选出来的数字中 $1\sim n$ 各一个。
在队友建议下，我们检查了样例，发现确实符合上述规律。那么这个问题怎么实现呢？
考虑给所有 $l_i-1,r_i$ 连边。如果每个连通块的边都够用，那么一定会构成一棵基环树。因此只要判断每个连通块是否是基环树即可？
队友：考虑重边的情况。
我：三重边自然答案是 $0$，但是二重边好像还真会被判定为基环树。哎，但二重边应该被当成 $0$ 来着？
我：哦，二重边有偶数种方案，因此整个图必须没环，换言之把 $0$ 也当结点后，原图应该构成 $0\sim n$ 的一棵树。怪不得他们队伍能 $15$ 分钟敲出来。
### Solution（省流、简化版）
如果 $l_i$ 固定为 $1$，那么将 $r_i$ 排序后，方案数就是 $\prod\limits_{i=1}^n (r_i-i+1)$。
如果这些区间中有两个相同区间 $[l_a,r_a],[l_b,r_b]$，那么对于每个方案，交换 $p_a,p_b$ 可得新方案，故答案为偶数。因此 $r_i$ 必须有 $1\sim n$ 各一个，答案才是奇数。
---
对原问题考虑容斥，把 $[l_i,r_i]$ 拆成 $[1,r_i]\setminus [1,l_i-1]$，有答案（$\bmod 2$ 意义下）为 $\sum\limits_{R_i\in \{l_i-1,r_i\}} [R_i \text{ 是排列}]$。
问题变成判定是否有奇数个方案，从 $n$ 个二元集合各选一个数，使得 $1\sim n$ 各选一个。
考虑 $l_i-1$ 和 $r_i$ 之间连无向边，要给每条边定向使得 $1\sim n$ 入度为 $1$。如果图上有环，那么把环上边反向即可得到新方案，故答案必为偶数。因此，要想答案为奇数，必须所有边构成 $0\sim n$ 的一棵树。