一开始队长秒了 B ，队友秒了 D ，我秒了 C 。

然后和队长讨论 F ，这道题目让我们想起了一个之前 CF 的一个题目，猜测结论是一样的，但是不会证明，后面队长去搞别的题目，我开始思考结论是不是一样的。

然后发现结论真的是一样的，直接开写，过了。

然后忘了是 Imakf 还是队长，上机过了 L ，这时一个小时过去了。

然后和队长讨论 H ，队长声称了一个贪心思路，我觉得很对，后面尝试证明其做法的时候发现了更本质的东西，上机过了。

Imakf 上机过了 J ，期间我和队长讨论 G ，由于注意到一个传统的一堆石子拿 $k$ 个的 NIM 游戏，总是尝试拼出 $k+1$ ，所以发现这道题目应该和 $\mod (A+B)$ 的余数有关，然后感觉剩下的部分只剩下了讨论，队长就去和 Imakf 讨论别的题，然后我讨论到两小时时过了此题，感觉其实是慢了的，没道理讨论这么久，或者说，我感觉我大部分时间是在寻找优美的讨论，而不是在讨论，真要正赛就一个劲的讨论了，估计这样虽然结果丑了点，但是速度应该会快些，毕竟寻找优美讨论这个行为在重要比赛的性价比本来就不高。

期间队友一直在讨论 I （后面发现他们一直在图上讨论，这其实方向错了），我看了一眼，我也没有思路，我去看了 A 题意，也没有思路，但是突然发现 I 很多时候专注于某一个集合是好的。

顺藤摸瓜发现应该答案 $\le$ 两个集合，这个时候提出了一个错误的原因：理论上你知道得到一个出现次数 $>1$ 的数字就应该不断地操作包含其地最小地集合，然后写出如下地代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int inf = 1e9;
int n;
vector<int> c[N];
int m1[N], m2[N];
void push(int x, int y){
	if(!m1[x]) m1[x] = y;
	else{
		if(y < m1[x]) m2[x] = m1[x], m1[x] = y;
		else if(!m2[x]) m2[x] = y;
	}
}
int getans(int x, int y){
	if(y != m1[x]) return m1[x];
	else if(!m2[x]) return inf;
	else return m2[x];
}
bool v[N];
int siz[N];
int main(){
	cin >> n;
	for(int i = 1; i <= n; i++){
		int k;
		cin >> k;
		for(int j = 1; j <= k; j++){
			int x;
			cin >> x;
			if(!v[x]) siz[i]++;
			v[x] = 1;
			c[i].push_back(x);
		}
		for(auto x : c[i]){
			push(x, siz[i]);
			v[x] = 0;
		}
	}
	int ans = inf;
	for(int i = 1; i <= n; i++){
		int tmp = 0, base = 0;
		for(auto x : c[i]){
			if(!m2[x]) base++;
		}
		for(auto x : c[i]){
			if(!m2[x]) continue;
			tmp = max(tmp, base + 1 + getans(x, siz[i]));
			ans = min(ans, siz[i] + 1);
		}
		if(!tmp) tmp = inf;
		ans = min(ans, tmp);
	}
	cout << ans << "\n";
	return 0;
}

但实际上是错的，后面 Imakf 提出质疑，两个集合那个性质真的证明了吗？我思考了一下，好像真没证明，举个例子，如果我中间得到了一个需要次数更少地有效次数，显然更优的操作是去操作这个更优地数字，因此我前面地证明显然是错的。只能说急了，在没有想明白地情况下就开写了，太急了，以后打比赛能不能别那么急，想清楚了再上。（不过当时机时空着也确实闹腾，但现在看来确实更稳地打法是想好再上，我宁愿什么都不做，也不愿意犯错）

然后讨论着突然发现好像确实是至多两个集合，但是不太一样的是先找到最优的位置再跳，原因是如果真有一个过程有多个集合，那么直接从倒数第二个集合开始答案一定不劣，所以就做完了。

然后接近三个小时过了 I 。

这个时候和队友讨论 A ，容斥容斥不行，dp dp 不行，因此我在想能不能直接计数，突然发现好像直接在有根树上给每个连通块在最浅的 meet room 计数就能保证不重，遂上机。

在四个半小时的时候通过 A 。

最后和队友讨论 E,K ，期间队长说 E 交叉字母能互相唯一确定位置，但是无法处理不相交的情况，我当时想的是如果不相交就像区间 dp 一样合并一下就行了，但是想想就难写，最后半小时肯定写不出来，但是这里我并没告诉队友这个事情，算是小错误，但也不大，毕竟这个搞法赛后队友听了也觉得是史，当时写这个做法确实就是写不出来（更何况还是在当时没想明白的基础之上），其次就是赛后看了别人做法，发现不长，因此这个做法也没道理是正解。

然后 K 也没啥思路，当时觉得 dp 不了有考虑过什么指数搞法，但是也没什么思路，最终遗憾离场，虽然最后看题解发现确实是带指数的，但是显然想到方向和想到做法之间的差距还是很大的，总之菜就得多练。

总之我这场的错误：

I 急了多了好几发罚时。
没有及时的和队友交流我 E 和 K 的想法。
开天眼和队友说 E 赛时没人过（因为赛前看到一堆 11 题队，以为都是过的 K ），导致最后重心落在 K ，但不仅天眼开错了，而且还错失了一个 11 题的机会（赛后看了 E 的代码，理论上如果全力想 E ，如果在最后 15 分钟前想出来，那还是有机会写出来的），总之以后真不能开天眼了，开天眼打比赛这种行为纯 SB 。

队友问题：真不能在想不出题时玩手机吧！怒！

部分题解：

D

行列独立，check 一下。

C

选择个数最多的字母单独作为子序列，答案是 $\frac{n^2}{9}$ ，所以只需要关心周期长度 $<9$ 的。（一开始搞成 $\le 9$ 的，还在犹豫要不要写，唐完了）

直接枚举然后贪心匹配即可，时间复杂度：$O(3^8n)$

和正解一致。

F

首先整个串不是回文串，答案为 $1$ 。

否则如果可以切成一个前缀一个后缀都不是回文串，则答案为 $2$ 。

思考一下上面两个都打不成的情况。

首先如果一个长度为 $len$ 的回文串，其有一个长度为 $len-k$ 的回文前缀，则有长度为 $k$ 的周期。

下面讨论不妨认为首字母是 $a$ ，剩下的依次为 $bc..$ 。

首先一种情况：$aaaa…aa$

不妨考虑字符串 $S[1…i],S[i+1…n]$ 是不是回文串。

如果 $S[1]$ 是，$S[1…2]$ 不是，那么 $S[1…i],S[1…i+1]$ 不可能同时是回文串，否则 $S[1…2]$ 就是回文串，又由于 $S$ 是回文串，那么 $S[i…n],S[i+1…n]$ 同理。

所以 $S[1…i],S[i+1…n]$ 总是随着 $i$ 的变化交替成为回文串，根据 $S$ 是回文串，$S[1…n-2]$ 是，$S[1…n-1]$ 不是可以得到这种串一定是：$ababa….a$ 。

类似的，直接找到第一个 $i$ ，使得：$S[1…i]$ 是回文串，$S[1…i+1]$ 不是，显然只要不是 $aaa..aa$ ，那么 $i$ 一定存在，而且显然 $i\ge 2$。

对应的，有最大的 $j=n-i+1$ 满足：$S[j…n]$ 是回文串，$S[j-1…n]$ 不是，显然 $i+1\le j-1$。

若 $i+1=j-1$ ，即 $S=aaa…aba…aaa$ ，那么 $S$ 显然无解。

否则在 $[i,j]$ 在，$S[i+1,j-1]$ 的范围内，前后缀必须反复交换回文串，也就是 $S[1…j-1]$ 是周期为 $2$ 的，如果 $i>2$ ，那么 $S[1…j-1]$ 是全 $a$ 串，则对称一下，得到 $S$ 是全 $a$ 串，矛盾，而 $i=2$ 则在上面讨论过了，是 $abab…a$ 。

所以综上，只有三种特殊串：$aaa..aa,ababa….a,aaa…aba…aaa$ ，而这三种显然无解。

证毕。

时间复杂度：$O(n)$ 。

与题解一致。

H

首先，如果从起点可以直接跳到终点，那么答案为 $0$ 。

其次，如果存在 $a[i]-a[i-1]>d$ ，那么肯定会想答案为让最小 $c_{i}$ 的走过全程，然后其余直接大跳到终点。

不妨来证明一下：

将 $1,a_{1},…,a_{k},n$ 根据 $a[i]-a[i-1]>d$ 切成若干段，每一段都能从开头直接小跳到结尾，不妨设有 $cnt$ 段。

那么除了最后一段外，每一段里面的每一个青蛙都得大跳才能跳到后面的段，所以每个青蛙的系数至少是 $1$ 。

其次，每一段至少有一只青蛙，所以第一段 $k$ 只青蛙，后面 $[2,cnt-1]$ 段 $\ge 1$ 只，所以系数和 $\ge k+cnt-2$ 。

所以显然 $cnt-1$ 的系数分配给 $c$ 最小的，其余都为 $1$ 是最优答案。

然后如果不存在这样的 $>d$ 的 gap ，那肯定会想，那是不是每次把最远的不用大跳的点跳过来就行了呢？（队长给出的贪心）

这看起来很对，但是为什么呢？

我们不妨考虑最大化系数为 $0$ 的青蛙个数，考虑上述本质过程，是找到最大的 $t$ 满足 $a[i]-a[i-t+1]\le d$ 。

那么我们考虑放 $t-1$ 只青蛙全程小跳，显然每次都能让最远那只过来。

但是如果放 $t$ 只青蛙，考虑将 $i$ 递增并不断地把青蛙跳到 $a[i]$ ，来模拟这 $t$ 只青蛙的行进路线，在 $a[j]-a[j-t]>d$ 的这个位置，会发现最远那只青蛙的位置 $\le a[j-t]$ ，而 $a[j-t+1]…a[j-1]$ 的位置都已经走过，所以无论如何最远的青蛙都不可能不借助大跳跳到 $a[j]$ 及以后，所以矛盾，证毕。

那现在知道至多多少只青蛙系数为 $0$ ，剩下的青蛙系数为 $1$ 自然为最优解。

证毕。

时间复杂度：$O(m+k)$

和题解一致。

G

update ：喜报，写题解的时候发现自己赛时写的做法讨论出了点小问题，但是 AC 了，乐麻了。

太狗屎了，还要讨论。

如果 $A=B$ ，做法显然，考虑剩下的情况。

如果存在 $min(A,B)\le a_{i}\mod {(A+B)} < max(A,B)$ ，那么显然 $min(A,B)$ 取胜，不妨考虑这一堆为第一堆，无论先后手，如果 $max(A,B)$ 操作了一次这个堆，$min(A,B)$ 就操作回来，只有当其余堆都无法操作的时候，$min(A,B)$ 才会先操作这个堆，这种情况下，$min(A,B)$ 显然必胜。

其余情况：

如果 $A<B$ ：

如果存在 $a_{i}\mod {(A+B)} \ge 2A$ ，那么先手操作这一堆能造出上面的情况。

否则，统计 $a_{i}\mod {(A+B)} \ge B$ 的数量，如果为奇数先手必胜，否则后手必胜。

原因：偶数：不妨认为是第 $1,2…,k$ 堆 $\ge B$ ，剩下的堆都满足：$a_{i}\mod {(A+B)} < A$ ，$A$ 若操作了 $1,…,k$ 其中的一堆，则 $B$ 操作另外一堆，然后这两堆可以直接扔到 $a_{i}\mod {(A+B)} < A$ 去，如果 $A$ 操作了别的堆，则 $B$ 操作一样的堆，最后只会剩下一堆 $<A$ 的堆，卡死 $A$ 。

奇数：先手操作其中一堆，这一堆丢到后面，其余操作一样，虽然和上面不太一样的是，一个 $-A$ ，一个 $-B$ ，但都变成了 $<A$ ，效果一样。

如果 $A>B$ ：

设 $a_{i}\mod {(A+B)} \ge 2B$ 的个数为 $cnt$ 个，根据上面的前提，显然有 $\ge A$ 成立。

如果 $cnt=1$ ，则直接操作这个数字，判断剩下的数字中 $a_{i}\mod {(A+B)} \ge A$ 的个数，偶数先手赢，否则后手赢。
如果 $cnt\ge 2$ ，后手赢。

$cnt=0$ 则考察 $a_{i}\mod {(A+B)} \ge A$ 的个数，为奇数则先手赢。

那么剩下的情况先手是否必败呢，例如能否操作那些 $a_{i}\mod {(A+B)} < B$ 的数字完成翻盘呢，思考一下，如果 $B\le (a_{i}-A)\mod {(A+B)}<A$ 则后手胜，$B\le (a_{i}-A)\mod {(A+B)}$ 则后手也胜（$\ge B$ 的个数为奇数个）。

则只有 $<B$ 才可以，但是 $-A$ 等于 $+B$ ，设 $r=a_{i}\mod {(A+B)}$ ，而 $r+B<2B<A+B$ ，所以 $r+B$ 就是操作后模意义下的值，显然 $r+B\ge B$ ，所以 $<B$ 是不可能的，所以这种情况后手必胜。

做闭，时间复杂度：$O(n)$ 。

经过若干次修改后的代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, a[N], A, B;
bool work(){
	cin >> n >> A >> B;
	for(int i = 1; i <= n; i++) cin >> a[i];
	if(A == B){
		int cnt = 0;
		for(int i = 1; i <= n; i++) cnt += a[i] / A;
		return cnt & 1;
	}
	if(A < B){
		int cnt = 0;
		for(int i = 1; i <= n; i++){
			int res = a[i] % (A + B);
			if(res >= A && res < B) return 1;
			if(res >= A + A) return 1;
			cnt += (res >= B);
		}
		return cnt & 1;
	}
	//A > B
	int cnt = 0;
	bool bk = 0, bbk = 0;
	for(int i = 1; i <= n; i++){
		int res = a[i] % (A + B);
		if(res >= B && res < A) return 0;
		if(res >= B + B){
			if(bk) return 0;
			bk = 1;
		}
		cnt += (res >= A);
		if(res < B && a[i] > res && (a[i] - A) % (A + B) >= A) bbk = 1;
	}
    if(bk) return cnt & 1;
	return (cnt & 1) || bbk;
}
int main(){
	if(work()) cout << "Zenyk\n";
	else cout << "Marichka\n";
	return 0;
}

无语了，赛后写小结把赛时代码 hack 了，what can i say ，man ！

感觉这样讨论好烦，去看看别人的讨论。

咕咕咕。。。

I

注：

后面的讨论中都认为集合的修改是及时的，即只要球被摸出后，这个集合后续都没有这个球。
关于我后面为什么这么思考这个问题，可以看本博客的 “关于如何思考有向图游戏上的不对称博弈问题” 。

首先注意到一个事情，一个方案中的某个看起来不那么愚蠢的世界线中（即后手的某种决策会导向的结果，且后手如果存在不立即结束的决策，就一定不会选会立即结束的决策），最后选择的那个集合设置为 $S$ ，如果 $S$ 有重复的元素。

那么显然，答案一定 $\ge S$ 的颜色个数 $+1$ ，原因是考虑 DAG 上，后手在这个状态的答案一定不为 $0$ ，所以一开始直接操作这个集合颜色个数 $+1$ 就可以得到不劣的方案。

但是呢，这是否意味着我们只要有一个可以成为答案的有效颜色就可以直接操作含有这个颜色的最小集合呢？这是不一定的，因为这个有效颜色不一定是我们目标中的有效颜色，即不一定等于我们最后一步操作的集合中有的颜色，当时赛时犯了这个错误。

那么正确的结论是怎样子的呢？

注意到一个事情，在游戏结束前，每种颜色至多存在一个，这启示我们其实可以不用访问过多的集合，可以直接访问原本计划在后面访问的集合，这感性上对称于原来方案的后半部分，不同的是，手里少了一些颜色，多了一些步数。因此我们期望能在后续通过步数换取回这些颜色，如果最后能够结束，那么我们没换回的颜色说明是用来卡我们的，那我们正好节省了他们对应的步数，如果全部换回来了，说明都需要，那也不劣，但问题是有可能我们去掉前面的访问，只执行后面的决策，后可能在决策结束时没办法使游戏结束，但这依旧是一个很好的想题方向，顺着这个方向想，我们或许可以得到下面的结论（“或许” 是因为我当时是通过错误的思路和证明想到该结论的，我实际上并不知道这道题目一个正常的、自然的思考过程，这上面的思考过程是我口胡的，但我个人感觉其实也不自然）：

我们认为最终的决策只会询问至多两个集合：一个集合询问数字，然后找到最后一个颜色所在的颜色数最少的集合然后狂问。

所以答案是询问一个集合的答案和询问两个集合的答案：两个集合每次选择一个集合

证明就考虑对于任意一个决策，如果不是

没清空栈 WA 了一发，唐完了。

A

A 一开始还想着容斥，后面发现竟然是直接计数？？？

先给树定根，注意到如果 $x,y$ 可以作为 meet room ，那么 $x,y$ 的 LCA 一定能作为 meet room ，所以一定存在一个最浅的 meet room ，在这个位置计数就行了。

注意到需要统计距离 $x$ 为 $L$ 的点的个数，以及 $x$ 子树内距离 $x$ 距离在 $L-c<d\le L$ 的点的个数，$c$ 是到父亲的距离。

前者点分治，后者二维数点（在 DFS 序上的二维数点）。

计数的话，后者必须至少选一个点，这个是简单容斥，注意根节点可能需要额外处理一下，我的处理是让根节点的 $c=L+1$ 。

时间复杂度：$O(n\log^2 n)$ 。

和题解基本一致。

Plan

剩余： G 的官方题解和 I 题解/官方题解。

Moscow International Workshops 2017 Day 4 赛后小结

D

C

F

H

G

I

A

Plan