赛时时间分配

读题

8:10-8:20 读完题，目前感觉没有太不可做的题

T1

8:20-8:40 T1思路比较明显，很快码完了T1，然后这时候顺手一翻题面，才发现居然有T4？？？

T2

8:40-9:05 想了一会儿暂时没头绪，把T2的暴力码了

9:05-9:40 将题目中所要满足的关系式移了下项，发现变得可做一些，就码了

9:40-10:00 拍了会儿T2，然后为了增强代码的鲁棒性，自作聪明地修改了下cmp函数（最终成为了RE的原因。。。）

T3

10:00-10:20 想了会儿，不断hack了自己的各种做法，然后由于如果打暴力的搜索，5pts都有可能会超时，决定先去看看T4

T4

10:20-11:15 迅速想出了一个感觉十分可行的三进制状压算法，由于想出的这个算法对于各种大小的数据都可以用一个代码处理，一度怀疑这题没有部分分做法，码到最后才发现有一个细节不会处理

11:15-11:30 火速翻回头重新想部分分，受最后那个细节的启发，发现了部分分做法，临交卷前打完了1.5档（36pts）

赛后反思

关于cmp语法

以前一直没有注意过这个语法问题：手写cmp函数时，返回值只能是0/1，今天为了代码方便，将返回值设定为了0/1/2，本地不会RE，实测会RE.

关于T3的思路问题

赛场上想了很多关于如何构造最优解的问题，而实际上如果直接从DP角度入手的话，会发现我们并不需要真的构造出最优解，我们只需要考虑如何较快地枚举各种解，然后让DP帮助我们做出决策即可。

题解

T1[eJOI2019]异或橙子

手推一下发现询问区间长度为偶数时答案为\(0\)，长度区间为奇数时答案为从\(L\)开始隔项异或的值，开两个树状数组维护即可，时间复杂度\(O(n\log n)\).

T2[eJOI2017]魔法

从字符集大小为\(2\)的情况入手，发现要满足的条件为

\[S_{B1}-S_{B2}=S_{A1}-S_{A2}\Longleftrightarrow S_{B1}-S_{A1}=S_{B2}-S_{A2} \]

在转化后的关系后，式子一边的值不再和两个位置有关，仅和当前位置有关，我们可以计算当前位置上的值，然后查询在前面的位置上有多少位置的值与当前位置相等，统计答案，可以用Hash或者排序实现，时间复杂度\(O(nk\log n)\).

附cmp函数

int cmp(node x,node y){
	for(int i=1;i<=k;i++){
		if(x.t[i]<y.t[i])return 1;
		if(x.t[i]>y.t[i])return 0;
	}
	return 0;//不可return 2
}

T4[eJOI2017]六

实际上将最后想出的搜索完善完，即可获得\(60pts\)，再套上最开始想的状压，再加上一些剪枝，即可过掉本题，时间复杂度\(O(玄学)\).

通过本题学习到的一种状压思路是：在一步操作就要涉及两位及以上二进制位时，可以将每种操作都分到不同的二进制位上，状压时不再直接枚举最终状态，而是枚举使用了哪个操作，例如\(10|1=11\)和\(00|11=11\)如果按照普通的状压，只看结果的话，在本题中会出现计算错误，需要将涉及的到的\(10、1、00、11\)单独用不同的二进制位表示。

另外在状压过程中，将需要多次用的相同辅助数组提前预处理出来也是非常重要的。

关键代码

map<int128,int>m;
int dfs(int128 x){
	if(m[x])return m[x];
	int res=1;
	for(int i=1;i<(1<<tot);i++){
		int nw=(x>>(i<<1))&3;
		if(nw>1)continue;
		int128 nxt=x;
		for(int j=0;j<(1<<tot);j++){
			if(!(i&j))continue;
			if((nxt>>(j<<1)&3)<2)nxt+=((int128)1<<(j<<1));
		} 
		res=(res+dfs(nxt)*S[i])%mod;
	}
	return m[x]=res;
}
//主函数
	for(int i=1;i<(1<<tot);i++){
		S[i]=1;
		for(int j=0;j<tot;j++)
			if(i&(1<<j))S[i]=S[i]*cnt[j+1]%mod;
	}
	cout<<(dfs(0)-1+mod)%mod<<endl;

T3[JOI 2019 Final]たのしいたのしいたのしい家庭菜園

同一个字符的相对顺序是不变的，如果确定了最终的字符串，最少交换次数即为逆序对个数。

考虑枚举每个位置上放哪个数，设\(f[0/1/2][x][y][z]\)表示当前位置放\(0/1/2\)，放完后还没安置的数分别有\(x,y,z\)个时的逆序对个数，由于发现每个swap操作分别在要swap的两个数的最终位置处被计算了一次贡献，最后答案为\(\min f[0/1/2][0][0][0]/2\).

另外这道题的具体转移方程非常容易写错：每个位置上的数在转移过程中可能已经不在它本来的位置上了，因此不能简单地计算原位置与目标位置的距离，而只能用逆序对的计算思路计算它需要跨过多少个其它两个数。

    if(a[0])f[0][a[0]-1][b[0]][c[0]]=n-a[a[0]];
    if(b[0])f[1][a[0]][b[0]-1][c[0]]=n-b[b[0]];
    if(c[0])f[2][a[0]][b[0]][c[0]-1]=n-c[c[0]];
    for(int i=n-1;i;i--)
        for(int x=0;x<=a[0]&&x<=i;x++)
            for(int y=max(0,i-x-c[0]);y<=b[0]&&x+y<=i;y++){
                int z=i-x-y;
                if(x)F(f[0][x-1][y][z],min(f[1][x][y][z],f[2][x][y][z])+abs(t[1][a[x]]-y)+abs(t[2][a[x]]-z));
                if(y)F(f[1][x][y-1][z],min(f[0][x][y][z],f[2][x][y][z])+abs(t[0][b[y]]-x)+abs(t[2][b[y]]-z));
                if(z)F(f[2][x][y][z-1],min(f[0][x][y][z],f[1][x][y][z])+abs(t[0][c[z]]-x)+abs(t[1][c[z]]-y));
            }
    int ans=min(min(f[0][0][0][0],f[1][0][0][0]),f[2][0][0][0]);