2024.10 做题记录 /

CF2004E

套用 SG 函数的结论，我们先打单个游戏的表再异或即可得到答案。首先对于一个大小为 \(i\) 的堆有 \(SG[i]=\text{mex}_{j\bot i}\{SG[i-j]\}\)，容易暴力 dp。

int SG[N];
int f(int x) {
	if(SG[x]!=-1) return SG[x];
	if(x==0) return SG[0]=0;
	vector<int> g;
	up(i,1,x) if(__gcd(i,x)==1) g.pb(f(x-i));
	sort(g.begin(),g.end());
	if(g[0]>0) return 0;
	up(i,0,(int)g.size()-2) if(g[i]+1!=g[i+1]&&g[i]!=g[i+1]) return g[i]+1;
	return g[g.size()-1]+1; 
}

首先 \(SG[0]=0,SG[1]=1\)，然后第 \(i\) 个质数的 SG 值是 \(i\) 强相关的，合数的 SG 是最小质因子的 SG，线性筛求出即可。

CF2005E1/2

E1 的话直接按照博弈论的东西暴力 dp 即可，是 \(O(lnm)\) 的，具体而言对于一个位置考虑其子矩阵中代表这一轮的格子，如果不能到达必胜态就是必败，暴力 dp 即可，\(f[i][j][k]\) 表示 \((i,j)\) 往下的矩阵中第 \(k\) 轮的状态，注意定义是从 \((i,j)\) 走而不是走到 \((i,j)\)，容易倒序 dp。

现在就要优化 dp 了，这个转移本身形式感觉没啥简便优化，找找题目性质，注意到如果一次转移可以走到多个点 \(x=p_1,\dots,p_x\)，一定走一个右下方没有 \(x\) 的位置，因为如果走到下面都输那走上面一定会输但是走下面会赢的走上面不一定会赢（下一手选择被包含了），那有用的点按照横/纵坐标排序之后纵/横坐标会有单调性，这代表了按照横/纵坐标排序之后任意矩阵能覆盖到的合法点集是一个区间。那直接对每一轮记一下合法位置，对 \(f\) 做一个前缀和，查询的时候二分之后差分，判断一个子矩阵有没有胜态即可，复杂度 \(O(nm\log nm)\)。

CF2005D

经典结论：序列上固定一个左端点之后向右拓展右端点，本质不同的 \(\gcd\) 至多只有 \(\log\) 种。因为后面的 \(\gcd\) 一定是前面的 \(\gcd\) 的因数，每次变化至少使得值 \(\times\frac{1}{2}\)。

对于每一个点预处理出每一个作为左端点之后序列上的 \(\gcd\) 的段，一个段放在一起考虑，显然是拿最右边的不劣，因为左边的贡献一样的话，右边留下的数少更容易让后面部分的 \(\gcd\) 变大，设 \(L_{a/b}[i]\) 表示序列 \(a/b\) 第 \(i\) 个数作为左端点的 \(\gcd\) 段的右端点集合，预处理可以递推，求答案暴力枚举即可，复杂度控制在几只 \(\log\) 呢。

CF2002E

按照连续的颜色的段考虑，在删出空段前是频繁的每次去头，删除空段之后如果该段左右段颜色相同则会导致合并，感觉容易拿数据结构维护。

维护当前删除减量 \(\Delta\)，用 stl set（不熟练 set 可以写带删除标记的 priority_queue）维护二元组 \((x,y)\) 表示段 \(x\) 的长度是 \(y+\Delta\)，以 \(y\) 为关键字排序。每次找出最先被删空的那一段，向前推进时间，更新一下用 stl map 维护一个前后指针即可。

CF2003 E2

首先先考虑往序列里面投一个数会得到什么，设序列中第一/二个没有出现的数为 \(L,R\)，则投机 \(L\) 得 \(R\)，否则得到 \(L\)。

先形式化描述一下，首先 \(L\to L\) 这种当成没有发生就行了，所以是我们可以选择 \(?\to R\) 或者 \(L\to R\)。碍于两种移动相互限制，先想办法找点性质，感觉第一类操作这个凭空变出某个数只用一次够了，那只连 \(L\to R\) 的边，可以发现因为只有小往大所以是 DAG 这很方便，设 \(f_i\) 表示从 \(i\) 走能到达的最大的点是什么，按 topu 序倒序 dp 即可。具体而言度数 \(>1\) 的点和 \(x\) 可以作为根，然后任意 \(L\) 可以作为答案，然后就是求出从任意根开始走能走到的最大点。