ICPC 2017 地区赛沈阳站做题笔记

A - BBP Formula

难度：medium

一开始是有打算逐位预处理 $\pi$，然后发现精度炸了。看到数据范围 $T\le 32$，然后发现可以暴力，对于前面的每一位快速幂求出在第 $n$ 位意义下的真分数，将分数所有值加起来取整就行，后面的位贡献不大，可以忽略。

REP(i,0,n){
	res+=1.0*qpow(16,n-i,(8*i+1)*16,4)/(8*i+1);
	res-=1.0*qpow(16,n-i,(8*i+4)*16,2)/(8*i+4);
	res-=1.0*qpow(16,n-i,(8*i+5)*16,1)/(8*i+5);
	res-=1.0*qpow(16,n-i,(8*i+6)*16,1)/(8*i+6);
	while(res<0.0)res+=16.0; // 可能越上下界，所以别忘了调整到有意义的区间上
	while(res>=16.0)res-=16.0;
}

B - Bridge

难度：hard

场切的最难题，纪念一下。

我们称形如 $(x,y)-(x,y+1)$ 的边为 横边，形如 $(0,y)-(1,y)$ 的边为 竖边。不难发现如果在 $(y,y+1)$ 之间的两条竖边有一条断掉了，那么另外一条必然为桥。

扩展一下，对于最靠近任意一个 $y$ 左边的横边 $L$ 和最靠近 $y+1$ 右边的横边 $R$ 所代表的区间 $[L,R]$ 中的所有横边，断边的数量最多只能有一条，否则图不连通。当断边数为 $0$ 时，所有边都不是桥边，因为会成一个 $[L,R]$ 环；当断边数为 $1$ 时，桥边的数量为 $2(R-L)-1$。

这下我们可以快速判断横边是否为桥了。接下来是竖边。设存在竖边 $x$，靠近的最左、右竖边分别为 $L,R$，那么竖边 $x$ 为桥边的充要条件是 $[L,x]$ 和 $[x,R]$ 中的所有横边中各有一条是断边，否则成环就不是桥边了。

综上所述，我们需要维护所有的竖边和快速求区间横边数量。分别用 $\text{set}$ 和 $\text{Fenwick Tree}$ 维护即可。

set<int>s;
int getL(int x){ // 找到左侧最近竖边
	auto it=s.lower_bound(x);--it;
	return *it;
}
int getR(int x){ // 找到右侧最近竖边
	auto it=s.upper_bound(x);
	return *it;
}
int query1(int x){ // 查询 x 所代表的竖边是否为桥边
	if(x==1||x==n)return 0;
	int L=getL(x),R=getR(x);
	if(!query_bit(L,x-1))return 0;
	if(!query_bit(x,R-1))return 0;
	return 1; // 当且仅当 [L,x],[x,R] 中不含横边断边才不会成环
}
int query2(int l,int r){ // 查区间 [L,R] 中的桥边数量，包括所有横边竖边
	int res=0;
	res+=query1(l); // 别忘记加上竖边贡献
	res+=query1(r);
	if(query_bit(l,r-1))res+=(r-l)*2-1;
	return res;
}
void solve(){
	n=read()+2,m=read(); // 加 0 和 n+1 两个虚拟竖边特殊点，防止查 s 时越界报错
	init_bit();
	add_bit(1,1),add_bit(n-1,1); // 连通 (0,1) 和 (n,n+1) 横边
	s.clear();
	REP(i,1,n)s.insert(i);
	int res=0; // 答案
	REP(i,1,m){
		int tp=read(),x1=read(),y1=read()+1,x2=read(),y2=read()+1;
		if(y1>y2)swap(y1,y2);
		int L=getL(y2),R=getR(y1);
		if(tp==1){ // 加边
			if(x1==x2){ // 加横边，会影响一个极小区间
				res-=query2(L,R);
				add_bit(y1,1);
				res+=query2(L,R);
			}else{ // 加竖边，会影响两个左右极小区间
				res-=query2(L,R);
				s.insert(y1);
				res+=query2(L,y1);
				res+=query2(y1,R);
				res-=query1(y1);
			}
		}else{ // 断边，反之同理
			if(x1==x2){
				res-=query2(L,R);
				add_bit(y1,-1);
				res+=query2(L,R);
			}else{
				res-=query2(L,y1);
				res-=query2(y1,R);
				res+=query1(y1);
				s.erase(s.find(y1));
				res+=query2(L,R);
			}
		}
		writeln(res);
	}
}

F - Heron and His Triangle

难度：easy

好笑吗，打表题。

根据海伦公式 $S=\sqrt{p(p-a)(p-b)(p-c)},p=\frac{a+b+c}{2}$，可以得出面积关于 $t$ 的等式是 $\frac{t}{4}\sqrt{3(t^2-4)}$。干眼瞪不出什么规律，然后打完表发现是一个二阶递推数列。除了前两项 $4,14$，后面项的递推公式是 $A_n=4A_{n-1}-A_{n-2}$。然后直接把这个数列递推打表出来，每一个询问暴力查询即可。

G - Infinite Fraction Path

难度：medium

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

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

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

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];
}

H - Legends of the Three Kingdoms

难度：medium

难点在于模拟的概率题。预处理所有状态倒过来转移，转移全是 $\Theta(1)$ 的；询问直接 $\Theta(1)$ 查询。直接上代码吧，思路没啥好讲的。

const double eps=1e-16; // 你咋知道我 dps 精度设太小吃了一发
// dp 状态设计后两位分别是当前出牌的人[主公/反贼/忠臣/内奸]，以及[主公、忠臣/反贼/内奸]（这里/的优先级比、大）获胜概率
double f[N][N][N][N][4][3];int id[4]={0,3,2,1};// 注意这里的 id 数组
int main(){
	int n=40;
	REP(a,0,n)REP(b,0,n)REP(c,0,n)REP(d,0,n)REP(x,0,3){ // 主公、反贼、忠臣、内奸
		int i=id[x]; // 钦定转移顺序，就是在 x 对应的当前人物实际上已经没了要直接从前一个状态转移；由于不存在主公没了对局还没结束的情况，所以从主公开始倒序遍历
		int j=(i+1)&3; // j 为下一个出牌的人
		double maxn=-0.5;double sum=0;

		if(!a){ // 主公没了
			if(!b&&!d){ // 不存在的情况，赋值 -1 在取 max 操作时不会干扰正常转移
				REP(p,0,2)f[a][b][c][d][i][p]=-1.0;
			}else if(!b&&!c){ // 内奸获胜
				f[a][b][c][d][i][0]=0.0;
				f[a][b][c][d][i][1]=0.0;
				f[a][b][c][d][i][2]=1.0;
			}else{ // 反贼获胜
				f[a][b][c][d][i][0]=0.0;
				f[a][b][c][d][i][1]=1.0;
				f[a][b][c][d][i][2]=0.0;
			}
			continue;
		}

		if(!b&&!d){ // 主公/忠臣获胜
			f[a][b][c][d][i][0]=1.0;
			f[a][b][c][d][i][1]=0.0;
			f[a][b][c][d][i][2]=0.0;
			continue;
		}

		if(!b&&i==1||!c&&i==2||!d&&i==3){ // 当前出牌的人已经没了，直接把下一个人的状态直接复制过来
			memcpy(f[a][b][c][d][i],f[a][b][c][d][j],sizeof(f[a][b][c][d][j]));
			continue;
		}
        
        // ABCD 分别对应这一轮刀的是[主公/反贼/忠臣/内奸]
        
        // 转移 1 阶段，确定最优概率值

		auto A1=[&](int v){
			if(a&&f[a-1][b][c][d][j][v]>maxn-eps)maxn=f[a-1][b][c][d][j][v];};
		auto B1=[&](int v){
			if(b&&f[a][b-1][c][d][j][v]>maxn-eps)maxn=f[a][b-1][c][d][j][v];};
		auto C1=[&](int v){
			if(c&&f[a][b][c-1][d][j][v]>maxn-eps)maxn=f[a][b][c-1][d][j][v];};
		auto D1=[&](int v){
			if(d&&f[a][b][c][d-1][j][v]>maxn-eps)maxn=f[a][b][c][d-1][j][v];};
        
        // 转移 2 阶段，计算有多少种转移取到最优概率
		
		auto A2=[&](int v){
			if(a&&f[a-1][b][c][d][j][v]>maxn-eps)sum+=1.0;};
		auto B2=[&](int v){
			if(b&&f[a][b-1][c][d][j][v]>maxn-eps)sum+=1.0;};
		auto C2=[&](int v){
			if(c&&f[a][b][c-1][d][j][v]>maxn-eps)sum+=1.0;};
		auto D2=[&](int v){
			if(d&&f[a][b][c][d-1][j][v]>maxn-eps)sum+=1.0;};
        
        // 转移 3 阶段，计算转移概率和
		
		auto A3=[&](int v){
			if(a&&f[a-1][b][c][d][j][v]>maxn-eps)REP(p,0,2)
				f[a][b][c][d][i][p]+=1.0/sum*f[a-1][b][c][d][j][p];};
		auto B3=[&](int v){
			if(b&&f[a][b-1][c][d][j][v]>maxn-eps)REP(p,0,2)
				f[a][b][c][d][i][p]+=1.0/sum*f[a][b-1][c][d][j][p];};
		auto C3=[&](int v){
			if(c&&f[a][b][c-1][d][j][v]>maxn-eps)REP(p,0,2)
				f[a][b][c][d][i][p]+=1.0/sum*f[a][b][c-1][d][j][p];};
		auto D3=[&](int v){
			if(d&&f[a][b][c][d-1][j][v]>maxn-eps)REP(p,0,2)
				f[a][b][c][d][i][p]+=1.0/sum*f[a][b][c][d-1][j][p];};
		
		if(i==0){ // 主公
			B1(0),D1(0);
			B2(0),D2(0);
			B3(0),D3(0);
		}else if(i==1){ // 反贼
			A1(1),C1(1),D1(1);
			A2(1),C2(1),D2(1);
			A3(1),C3(1),D3(1);
		}else if(i==2){ // 忠臣
			B1(0),D1(0);
			B2(0),D2(0);
			B3(0),D3(0);
		}else if(i==3){ // 内奸
			A1(2),B1(2),C1(2);
			A2(2),B2(2),C2(2);
			A3(2),B3(2),C3(2);
		}
	}
	int T=read();
	while(T--){
		int a=read(),c=read(),b=read(),d=read();
		printf("%.6lf %.6lf %.6lf\n",f[a][b][c][d][0][0],f[a][b][c][d][0][1],f[a][b][c][d][0][2]);
	}
	return 0;
}

I - Little Boxes

难度：simple

不喜欢 __int128 的小朋友你们好啊，我是（请输入文本）。

K - Rabbits

难度：simple

咋要特判 $(1,2)$ 和 $(n-1,n)$ 有一个区间绝对够不到的情况，吓死我了，差点没测样例就交了。

L - Tree

难度：easy

简单结论题，评黄很合理吧。

结论：一个点与题目所求交集的边有公共部分，当且仅当以这个点为根时，存在两个不同儿子的子树大小 $\le k$，可以有一个子树包含该节点。

必要性大家都会证，如果不存在两个不同儿子的子树大小 $\le k$，那么这个点就一定没有任何相邻边被 $k$ 个颜色经过。接下来是充分性，感性理解一下，将不满足结论的点称作关键点，满足条件的，且与至少一个关键点相邻的非关键点称作临界点。将所有临界点（如果必须要【有一个子树包含该节点】，那么同时染上该临界点）所连的关键点子树染上 $k$ 种颜色，那么所有关键点的 $sz\ge k$ 的方向均至少存在一个临界点及其关键点子树染上了 $k$ 种颜色。构造成立。

void dfs(int u,int fa){
	sz[u]=1;
	int sum=0;
	for(auto v:E[u]){
		if(v==fa)continue;
		dfs(v,u);
		sum+=sz[v]>=m-1;
		sum+=sz[v]>=m-1&&n-sz[v]>=m; // 这里是【有一个子树包含该节点】的情况
		sz[u]+=sz[v];
	}
	sum+=(n-sz[u])>=m-1;
	sum+=(n-sz[u])>=m-1&&sz[u]>=m;
	if(sum>=2)++res;
}

M - Wandering Robots

难度：medium

镜像赛场上没切出来的人均题之一。

设在 $(x,y)$ 停留的概率为 $f_{x,y}$，$(x,y)$ 可以通往的相邻点有有 $d_{x,y}$ 个，那么显然有 $f_{x,y}=\frac{f_{x,y}}{d_{x,y}+1}+\frac{f_{x-1,y}}{d_{x-1,y}+1}+\frac{f_{x+1,y}}{d_{x+1,y}+1}+\frac{f_{x,y-1}}{d_{x,y-1}+1}+\frac{f_{x,y+1}}{d_{x,y+1}+1}$。然后还注意到 $\sum f_{x,y}=1$，所以可以联立一个概率方程组，解这个方程组就行。

然后观察样例，会发现一个很有趣的结论，概率即为目标点集的出度和/总点集的出度和。有些佬用这个方法写出来了但是不会证，但是你会发现，只要满足上面的概率方程组就行了，而这是易证的。

然后会发现相对于正常的图而言，被截掉的出度只与 $k$ 有关，所以我们暴力找到这些点，去重一下就可以算出实际出度了。