Infinite Fraction Path(ICPC 2017 Shenyang)

这不是我们 SA 基数排序的倍增法嘛！怎么出板子，而且似乎两只 log⁡\log 就可以跑过，所以可以把我经常写错的基排扔掉。

对于没有接触过 SA 的同学，讲讲倍增法是怎样运行的。先处理出每一个节点长度为 11 的字符串的排名，然后下一步求出长度为 22 的字符串的排名，具体地，相当于把一些两个长度为 11 的，已经排名过的字符串接起来然后字典序排序。唉，这不就是双关键字排序嘛！前面的字符串第一关键字，后面字符串第二关键字，然后排序完重新更新一下每个节点出发长度为 22 字符串的排名。

扩展一下，对于节点 ii，设移动 2k2^k 步后的节点为 (i,k)(i,k)，从 ii 出发的长度为 2k2^k 的字符串为 S(i,k)S(i,k)。已经求出了 S(i,k−1)S(i,k-1) 的排名，要求 S(i,k)S(i,k) 的排名，即将两个字符串 S(i,k−1),S((i,k−1),k−1)S(i,k-1),S((i,k-1),k-1) 首尾相接在一起。排序的时候根据 rkS(i,k−1)rk_{S(i,k-1)} 为第一关键字，rkS((i,k−1),k−1)rk_{S((i,k-1),k-1)} 为第二关键字进行排序，就可以求出 rkS(i,k)rk_{S(i,k)} 了。然后 kk 可以取到 ⌈lg⁡n⌉\lceil\lg n\rceil。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
REP(i,0,n-1)st[0][i]=(1ll*i*i+1)%n;
REP(i,0,n-1)f[i]=s[i];
REP(j,1,K-1){
	REP(i,0,n-1){
		st[j][i]=st[j-1][st[j-1][i]]; // 倍增求出 (i,k) 的节点编号
		a[i+1]=node{f[i],f[st[j-1][i]],i};
	}
	sort(a+1,a+n+1);
	int rk=0;
	REP(i,1,n){
		int id=a[i].id;
		++rk;
		if(a[i].v1==a[i-1].v1&&a[i].v2==a[i-1].v2)--rk; // 求排名，相等就复制前面的
		g[id]=rk; // 记录排名
	}
	REP(i,0,n-1)f[i]=g[i];
}
int p=0;
REP(i,1,n-1)if(f[i]==1)p=i; // 求出对应字符串字典序最小的节点编号
REP(i,1,n){
	putchar(s[p]);
	p=st[0][p];
}

精灵对战(SCCPC 2026)

小模拟也好 ** 恶心。

直接扫过一遍序列。贪心地考虑问题，如果第 i−1i-1 只最多战斗到 jj，那么第 ii 只尽可能延长对局局数。由于没有后效性，所以局部最优解等同于全局最优解。

接下来考虑第 ii 只从 ll 出发最大能到达的 rr 是多少。首先我们希望前面的尽可能打败对手，维护一个集合 SS 存储前面所有局能战胜对方的种类的交集，处理第 jj 个对手的时候也是与对手的压制集合取交。

当交集为空集的时候，当前就无法做到赢对方，那么剩下两个结果，两败俱伤和输掉尽可能选择两败俱伤。能做到两败俱伤必须是当前集合至少存在一个元素的压制集合不包含对手 jj。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
REP(i,1,m){
	vector<int>vec;
	for(auto v:E[a[i]])if(s.count(v))vec.push_back(v); // vec 是两个集合的交集
	if(vec.empty()){ // 交集为空，赢不了了
		if(s.empty()){ // 己方精灵刚刚开始比赛，s 必定为空
			++res;
			for(auto v:E[a[i]])s.insert(v);
		}else{
			if(check(s,a[i])){ // 判断是否能平局
				s.clear();
			}else{
				s.clear();
				for(auto v:E[a[i]])s.insert(v);
				++res; // 不能平局
			}
		}
	}else{
		s.clear();
		for(auto v:vec)s.insert(v); // 取交
	}
}

时间复杂度 Θ(nk)\Theta(nk)。把这份代码的 set 改成 vector 就可以实现了，但是有些麻烦。

Reverse Permutation

来源：AT_abc465_c

难度：443

这个入想着要去噗叽组炸街，所以有了这篇题解。这题讲思路好像没啥意义，所以直接上做法。

提供一个简单的双指针做法。倒序扫描 SS 数组，对于答案数组 AA 会有一段可能为空的后缀 p,p+1,…,np,p+1,\dots,n。当扫描到第一个 SkS_k 为 o 时，说明 [1,k][1,k] 作为一个整体最后被翻转。由于 kk 只被翻转过一次，所以 kk 必然填在下标为 11 的位置上，即：

A[]={k,empty,…,empty,k+1,k+2,…,n}A[]=\{k,\text{empty},\dots,\text{empty},k+1,k+2,\dots,n\}

。其中，empty\text{empty} 表示这个位置暂时不确定位置。然后由于 [1,k][1,k] 做了一次翻转，所以原先填充 [k+1,n][k+1,n] 时是从右往左填充，现在要换个方向，从左往右填充。当第二次遇到 SpS_p 为 o 时，需要再次翻转填充的顺序，从左往右变为从右往左。那么只需要维护左右两个指针，初始移动右指针从大到小填充 [1,n][1,n]。遇到 o 时则换成另外一个指针，即：

A[]={k,k−1,…,p+1,empty,…,empty,p,k+1,k+2,…,n}A[]=\{k,k-1,\dots,p+1,\text{empty},\dots,\text{empty},p,k+1,k+2,\dots,n\}

。依此递推，只要是在倒序扫描 SS 的过程中出现 o，则变换扫描方向。如果是从左到右，变为从最右边开始往左扫描；如果是从右到左，变为从最左边开始往右扫描。

1
2
3
4
5
6
bool flag=0;int p=1,q=n; // flag = 0 移动右指针，= 1 移动左指针，p,q 分别代表左、右指针
PER(i,n,1){ // 记得倒序
	if(s[i]=='o')flag^=1; // 换一个指针
	if(flag)a[p++]=i; // 左指针从左到右填充值
	else a[q--]=i; // 右指针从右到左填充值
}