lp2764 网络流24题-最小路径覆盖问题


(其实建图方法已经写在题目里了。)
(这一题是一道匈牙利的裸题,考场上二分图最大匹配仍然建议使用匈牙利(因为在实现复杂度上有巨大优势),我纯粹练一下当前弧优化Dinic。)
首先有一个定理。将一张有向图上的每一个点都拆点成入点和出点,连边后形成一张二分图,那么原图的最小路径覆盖,就是顶点数减去这张二分图的最大匹配。
考虑感性地证明这个定理。
每一次匹配,事实上就意味着,一条路径可以额外走过一个点。这样就减少了一个路径覆盖。
所以,当匹配次数最大的时候,路径覆盖数就最小了。
答案用并查集处理一下输出。


#include<iostream>
#include<cstdio>
#include<queue>
const int INF=0x3f3f3f3f;

inline int Min(int A,int B){
	return A<B?A:B;
}

struct ee{
	int v;
	int w;
	int nxt;
}e[20005];
int h[2005],et=-1;
inline void Eadd(int U,int V,int W){
	e[++et]=(ee){V,W,h[U]};
	h[U]=et;
}
inline void add(int U,int V,int W){
	Eadd(U,V,W);
	Eadd(V,U,0);
}
int dep[2005],nw[2005],f[2005];
int n,m,s,t;

std::queue<int> q;
inline bool bfs(){
	for(int i=1;i<=t;++i){
		dep[i]=INF;
		nw[i]=h[i];
	}
	while(!q.empty()){
		q.pop();
	}
	dep[s]=0;
	q.push(s);
	int p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		for(int i=h[p];i>=0;i=e[i].nxt){
			if(dep[e[i].v]==INF&&e[i].w){
				dep[e[i].v]=dep[p]+1;
				q.push(e[i].v);
			}
		}
	}
	return dep[t]<INF;
}
inline int dfs(int X,int V){
	if(V<=0||X==t){
		return V;
	}
	int cnt=0,val;
	for(int i=nw[X];i>=0;i=e[i].nxt){
		nw[X]=i; 
		if(dep[e[i].v]==dep[X]+1){
			val=dfs(e[i].v,Min(e[i].w,V));
			if(val){
				cnt+=val;
				V-=val;
				e[i].w-=val;
				e[i^1].w+=val;
				if(V<=0){
					break;
				}
			}
		}
	}
	return cnt;
}

inline int fnd(int X){
	for(int i=h[X+n];i>=0;i=e[i].nxt){
		if(1<=e[i].v&&e[i].v<=n){
			if(e[i].w){
				return e[i].v;
			}
		}
	}
	return X;
}
inline int fa(int X){
	return f[X]^X?f[X]=fa(f[X]):X;
}
inline void prnt(int X){
	for(int i=h[X];i>=0;i=e[i].nxt){
		if((n+1)<=e[i].v&&e[i].v<=(n<<1)&&!e[i].w){
			printf("%d ",e[i].v-n
			);
			prnt(e[i].v-n);
			return;
		}
	}
}
bool vis[2005];
void init(){
	scanf("%d%d",&n,&m);
	s=(n<<1)+1,t=(n<<1)+2;
	for(int i=1;i<=t;++i){
		h[i]=-1;
	}
	int u,v;
	for(int i=1;i<=n;++i){
		add(s,i,1);
		add(n+i,t,1);
	}
	for(int i=1;i<=m;++i){
		scanf("%d%d",&u,&v);
		add(u,n+v,1);
	}
	int ans=n;
	while(bfs()){
		ans-=dfs(s,INF);
	}
	for(int i=1;i<=n;++i){
		f[i]=i;
	}
	for(int i=1;i<=n;++i){
		f[i]=fnd(i);
	}
	for(int i=1;i<=n;++i){
		fa(i);
	}
	for(int i=1;i<=n;++i){
		if(f[i]==i){
			printf("%d ",i);
			prnt(i);
			puts("");
		}
	}
	printf("%d\n",ans); 
}

int main(){
	init();
	return 0;
}

lp2763 网络流24题-试题库问题

对于这一题,我们建三层的边来描述题目中的约束。
对于每道题建一个点,源点连一条容量为1的边到每一个点,表示每道题最多只能被选取一次。
对于每个种类建一个点,每一个点连一条容量为1的边到它所属的所有类,表示它仅可以被作为这个类来选取。
每个种类连一条容量为这个种类需要的选取次数的边到汇点,表示这个种类最多需要被选取的次数。
然后,跑一遍当前弧优化Dinic最大流,如果需要选取的总题数都能选取到,流量就等于需要选取的总题数。
当然也可以大力拆点跑二分图匹配,不过那样似乎更难写的样子。

#include<iostream>
#include<cstdio>
#include<queue>
const int INF=0x3f3f3f3f;

inline int Min(int A,int B){
	return A<B?A:B;
}

struct ee{
	int v;
	int w;
	int nxt;
}e[40005];
int h[2005],et=-1;
int dep[2005],nw[2005];

inline void Eadd(int U,int V,int W){
	e[++et]=(ee){V,W,h[U]};
	h[U]=et;
}

inline void add(int U,int V,int W){
	Eadd(U,V,W);
	Eadd(V,U,0); 
}

int n,m,s,t,Sans=0,tot; 

std::queue<int> q;
inline bool bfs(){
	for(int i=1;i<=t;++i){
		dep[i]=INF;
		nw[i]=h[i];
	}
	while(!q.empty()){
		q.pop();
	}
	dep[s]=0;
	q.push(s);
	int p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		for(int i=h[p];i>=0;i=e[i].nxt){
			if(dep[e[i].v]==INF&&e[i].w){
				dep[e[i].v]=dep[p]+1;
				q.push(e[i].v);
			}
		}
	}
	return dep[t]<INF;
} 
//V表示从源点到当前路径上的剩余流量,cnt表示这个点向后流了多少流量。 
inline int dfs(int X,int V){
	if(V<=0||X==t){
		return V;
	}
	int cnt=0,val;
	for(int i=nw[X];i>=0;i=e[i].nxt){
		nw[X]=i;
		if(dep[e[i].v]==dep[X]+1){
			val=dfs(e[i].v,Min(V,e[i].w));
			if(val){
				cnt+=val;
				e[i].w-=val;
				e[i^1].w+=val;
				V-=val;
				if(V<=0){
					break;
				}
			}
		}
	}
	return cnt;
}

void init(){
	scanf("%d%d",&m,&n);
	s=m+n+1,t=m+n+2;
	for(int i=1;i<=t;++i){
		h[i]=-1;
	}
//	注意初始化。 
	int p,x;
	for(int i=1;i<=m;++i){
		scanf("%d",&x);
		Sans+=x;
		add(n+i,t,x);
	}
	for(int i=1;i<=n;++i){
		scanf("%d",&p);
		add(s,i,1);
		for(int j=1;j<=p;++j){
			scanf("%d",&x);
			add(i,n+x,1);
//			注意哈希。 
		}
	}
	int ans=0;
	while(bfs()){
		ans+=dfs(s,INF);
		printf("%d\n",ans); 
	}
	if(ans<Sans){
		puts("No solution!");
		return;
	}
	for(int i=1;i<=m;++i){
		printf("%d: ",i);
		for(int j=h[n+i];j;j=e[j].nxt){
			if((j&1)&&(e[j].w==1)&&(e[j].v!=t)){
				printf("%d ",e[j].v);
			}
		}
		puts("");
	}
}

int main(){
	init();
	return 0;
}

CF1091 Good Bye 2018

不知不觉就到了2018的最后一天。这个博客也有两个多月了。
我的姿势水平固然有了一定长进,但和巨神的距离却是越拉越远了。
这场CF也是,手速场我却没能有足够的手速。尤其是D题那种超简单的题目却死磕了半天才磕出来,F也没做出来。
总之,祝大家新年快乐_(:з」∠)_


CF1091A
依题意即可。
千万别掉进分类讨论的坑里。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
int a,b,c;

void init(){
	scanf("%d%d%d",&a,&b,&c);
	--b,c-=2;
	printf("%d",min(min(a,b),c)*3+3);
}
int main(){
	init();
	return 0;
}

CF1091B
我们将每个宝藏都加上每一个向量箭头,并标记目的地。
答案是任意一个被标记n次的。
可以用map或者hashmap维护。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
using namespace std;
int a[1005],b[1005],c[1005],d[1005];
typedef pair<int,int> pii;
typedef map<pii,int> mppii;
mppii mp;
int n;
void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d%d",a+i,b+i);
	}
	for(int i=1;i<=n;++i){
		scanf("%d%d",c+i,d+i);
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j){
			pii nw(a[i]+c[j],b[i]+d[j]);
			++mp[nw];
		}
	}
	mppii::iterator it=mp.begin();
	while(it!=mp.end()){
		if(it->second==n){
			printf("%d %d\n",it->first.first,it->first.second);
			break;
		}
		++it;
	} 
}
int main(){
	init();
	return 0;
}

CF1091C
观察题意以后我们发现,对于\(k\),当且仅当\(n\%k == 0\)的时候,\(k\)会和其他的本质不同。
依据剩余系的性质容易证明。
那么我们就得到了一个朴素的求答案公式:
$$\forall x,st:n\% x==0,ans_{x}=\sum_{i=0}^{n/gcd(n,x)-1}(1+(ix-1)\%n+1) $$
然后考虑到\(n\%x==0\),所以
$$ans_{x}=\sum_{i=0}^{n/gcd(n,x)-1}(1+(ix-1)\%n)==\sum_{i=0}^{n/gcd(n,x)-1}(1+ix)$$
套上等差数列求和公式即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
inline long long gcd(long long A,long long B){
	return B?gcd(B,A%B):A;
}
long long n;
long long ans[100005],tp=0;

inline void calc(int X){
	long long tms=n/gcd(n,X);
	ans[++tp]=tms+((((tms*(tms-1))>>1)*X));
}

void init(){
	scanf("%I64d",&n);
	for(int i=1;i*i<=n;++i){
		if(!(n%i)){
			calc(i);
			if(i*i!=n){
				calc(n/i);
			}
		}
	}
	sort(ans+1,ans+1+tp);
	tp=unique(ans+1,ans+1+tp)-1-ans;
	for(int i=1;i<=tp;++i){
		printf("%I64d ",ans[i]);
	}
}
int main(){
	init();
	return 0;
}

CF1091D
由于长度为\(n\),显然序列的值必然是\(\frac{(n*(n+1))}{2}-SUM_i+SUM_{i+1}\), 其中\(SUM_{i}\)表示第\(i\)个排列的某个前缀和。
又排列的性质我们会发现,对于任意两个相邻的全排列,它的任意长度前缀和要么增加且前缀序列变化,要么前缀和保持不变且前缀序列保持不变。
故而,如果一个序列要满足要求,它只有两种情况——它本身就是一个排列,或者它横跨的两个排列必然有一部分前缀相同。
对于第一种情况我们可以看成它们的前缀有\(0\)个相同的。
问题转化为了,求所有排列中,两种相邻排列前缀相同的长度的和。
通过打表找规律,或者对全排列性质的精确推演,我们得到了这样一个求和式:
$$ ans=\sum_{pre=0}^{n-2}(n!-(\Pi_{i=n}^{n-pre+1}i))$$
但是暴力计算的复杂度最坏是\(n^2\)的,仍然无法通过此题。
我们考虑优化这个求和。优化的点在于\(\Pi_{i=n}^{n-pre+1}i\),我们(毫不)惊讶地发现,它等价于\(\frac{n!}{n-pre}\),所以我们可以预处理阶乘和阶乘的逆元。
这样就做完了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const long long MOD=998244353;

long long fac[1000005],inv[1000005];
long long n;

void init(){
	scanf("%I64d",&n);
	fac[0]=fac[1]=inv[0]=inv[1]=1;
	for(int i=2;i<=n;++i){
		fac[i]=fac[i-1]*i%MOD;
		inv[i]=(MOD-MOD/i)*inv[MOD%i]%MOD;
	}
	for(int i=2;i<=n;++i){
		inv[i]=inv[i-1]*inv[i]%MOD;
	}
	long long ans=fac[n];
	for(int i=1;i<=n-2;++i){
		ans+=(fac[n]-fac[n]*inv[n-i]%MOD+MOD)%MOD;
		ans%=MOD;
	}
	printf("%I64d",ans);
}
int main(){
	init();
	return 0;
}

lp1640 SCOI2010 连续攻击游戏

一般地,对于兼具可行性和唯一性的问题,我们考虑二分图匹配。
对于这一题来说,我们考虑拆点。
值得一提的是,这里的拆点并不是将一个点的两个属性拆开来,而是将一个点的属性和编号拆开来。然后跑匈牙利。
如果可以匹配,那就继续匹配;如果不能匹配,那就说明这个属性无论如何也取不到;或者取到它需要付出「前面有某个属性无法取到」的代价,那么就是没有答案了。

#include<iostream>
#include<cstdio>
struct ee{
	int v;
	int nxt;
}e[2000005];
int h[10005],et=0;
inline void add(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}

int n;
int vis[1000005],dep;
int usd[1000005];

inline bool dfs(int X){
	for(int i=h[X];i;i=e[i].nxt){
		int v=e[i].v;
		if(vis[v]!=dep){
			vis[v]=dep;
			if(!usd[v]||dfs(usd[v])){
				usd[v]=X;
				return 1;
			}
		}
	}
	return 0;
}

void init(){
	scanf("%d",&n);
	int a,b;
	for(int i=1;i<=n;++i){
		scanf("%d%d",&a,&b);
		add(a,i),add(b,i);
	}
	int ans=0;
	dep=0;
	for(int i=1;i<=n;++i){
		++dep;
		if(dfs(i)){
			++ans;
		}else{
			break;
		}
	}
	printf("%d\n",ans);
}

int main(){
	init();
	return 0;
}

lp1129 ZJOI2007 矩阵游戏

提示:行列匹配。


当知道这一题是行列匹配之后,做法就非常显然了。
我们观察发现,如果将每个行与每个列标上序号的话,题目的要求就是求两个排列,使得黑格子排在主对角线上。
然后我们考虑每一个黑格子,我们发现,在最终情况下的每一个黑格子,它所在的行的序号和列的序号均与开始时的序号相同。
故而,所求的两个排列中,相同位置的行和列在开始时的交点必然是黑色的。
所以,每个黑格子就在行列之间连一条边,用行来匹配列,如果都能一一匹配则说明有解。

#include<iostream>
#include<cstdio>
int mp[205][205];
int n,usd[205],vis[205],dep;
inline bool dfs(int X){
	for(int i=1;i<=n;++i){
		if(!mp[X][i]){
			continue;
		}
		if(vis[i]!=dep){
			vis[i]=dep;
			if(!usd[i]||dfs(usd[i])){
				usd[i]=X;
				return 1;
			}
		}
	}
	return 0;
} 
void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		usd[i]=0,vis[i]=0;
		for(int j=1;j<=n;++j){
			scanf("%d",&mp[i][j]);
		}
	}
	dep=0;
	for(int i=1;i<=n;++i){
		++dep;
		if(!dfs(i)){
			puts("No");
			return;
		}
	}
	puts("Yes");
}

int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		init();
	}
	return 0;
}

lp5030 长脖子鹿放置

观察这一题的攻击方式,我们可以发现一个特点——所有奇数行的长颈鹿都攻击不到偶数行的长颈鹿,反之亦然。
所以,我们对奇偶的长颈鹿分开考虑,这显然是一张二分图。
于是类同于骑士共存问题,我们建一个二分图,跑匈牙利。
对于\(200\)的数据范围,匈牙利的小常数是可以卡过去的。
但是T了两个点,获得了80分的好成绩。
然后我们考虑一个对于vis数组的常数优化。
对于vis数组,我们定义一个变量dep,表示当前是第dep次匹配。这样就不必每次都清空vis数组了。
第二个就是,由于连的边是确定的,故而我们可以在线计算目的边,这样可以减少很多寻址时间。
另外就是对图的遍历顺序的优化。用了出题人的松松松顺序之后最终通过此题。

#include<iostream>
#include<cstdio>

const int dx[8]={3,3,-3,-3,1,1,-1,-1};
const int dy[8]={-1,1,-1,1,3,-3,3,-3};

bool mp[205][205];
int vis[40405],dep=0;
int n,m,q,usd[40405];
//注意数组大小。 

inline int calc(int X,int Y){
	return (X<=0||Y<=0||X>n||Y>m||mp[X][Y])?0:X*m+Y;
} 

inline bool dfs(int X){
	int v;
	for(int i=0;i<8;++i){
		v=calc((X-1)/m+dx[i],(X-1)%m+1+dy[i]);
//		注意还原信息。 
		if(v&&vis[v]!=dep){
			vis[v]=dep;
			if(!usd[v]||dfs(usd[v])){
				usd[v]=X;
				return 1;
			}
		}
	}
	return 0;
}

void init(){
//	mp[n][m]->mp[x][y] 
	scanf("%d%d%d",&n,&m,&q);
	int x,y;
	for(int i=1;i<=q;++i){
		scanf("%d%d",&x,&y);
		mp[x][y]=1;
	}
	int ans=n*m-q;
	for(int i=1;i<=n;i+=2){
		for(int j=1;j<=m;++j){
			if(mp[i][j]){
				continue;
			}
			++dep;
			ans-=dfs(calc(i,j));
		}
	}
//	for(int i=0;i<=n+1;++i){
//		for(int j=0;j<=m+1;++j){
//			printf("%2d ",calc(i,j));
//		}
//		puts("");
//	}
	printf("%d\n",ans);
}

int main(){
	init();
	return 0;
}

lp3355 网络流24题-骑士共存问题

首先我们观察这道题。
暴力地状压DP或者之类的操作显然会MLE/TLE。
我们发现,横坐标和纵坐标相加的和的奇偶性相同的格子永远不可能互相攻击到。
故而我们考虑建一张二分图。将横纵坐标的和的奇偶性不同的格子分别放在左右边,然后在能相互攻击到的点之间连边。依据题意,不能相互攻击到,所以答案即是这张图的最大独立集。

二分图最大独立集应当如何求得?我们有一个定理:一张二分图的最大独立集的大小等同于顶点数它的最大匹配的数量。
我们考虑感性地证明这个定理。
很容易可以发现,两个点不能被同时选取,当且仅当它们之间有连边。
又因为,有连边的两个点必然是属于二分图的两端的。
故而,如果有两个点不能被同时选取,它们必然可以构成一个匹配。
对于二分图上的最大匹配,所有没有被匹配的点都可以被选取。这非常的显然,因为没有被匹配到的点之间必然没有连边。如果有连边,那么就可以增加匹配,与最大匹配矛盾。
而,对于每一个匹配,都可以选取一组匹配中的一个点。这是因为,对于一些连通的匹配,它们有且仅有一个部分(左边或者右边)会和未匹配点连接。
这也是很显然的,因为如果不是这样的话,就存在一条新的增广路径,就可以得到更多的匹配了。
注意:坐标如何哈希成一个数字。

#include<iostream>
#include<cstdio>

const int dx[8]={-2,-1,1,2,-2,-1,1,2};
const int dy[8]={1,2,2,1,-1,-2,-2,-1}; 

struct ee{
	int v;
	int nxt;
}e[160005];
int h[40005],et=0;

inline void add(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et; 
}

bool vis[40005],mp[205][205];
int n=0,m=0,usd[40005];

inline int calc(int X,int Y){
	return (X-1)*n+Y;
//	注意坐标哈希成数字的方式。 
}

inline bool dfs(int X){
	for(int i=h[X];i;i=e[i].nxt){
		if(!vis[e[i].v]){
			vis[e[i].v]=1;
			if(!usd[e[i].v]||dfs(usd[e[i].v])){
				usd[e[i].v]=X;
				return 1;
			}
		}
	}
	return 0;
}
int st[40005],tp=0;
char out[205][205];
void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j){
			mp[i][j]=0;
			usd[calc(i,j)]=0;
			out[i][j]='O';
		}
	}
	int x,y;
	for(int i=1;i<=m;++i){
		scanf("%d%d",&x,&y);
		mp[x][y]=1;
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j){
//			printf("[%d %d] ",i,j);
			if(mp[i][j]||((i+j)&1)){
//				注意不是每次跳2而是判奇偶性。 
				continue;
			}
			st[++tp]=calc(i,j);
			out[i][j]='@'; 
			//注意有障碍的不仅是结束点,还有出发点。 
			for(int k=0;k<8;++k){
				x=i+dx[k],y=j+dy[k];
				if(x<=0||y<=0||x>n||y>n||mp[x][y]){
					continue;
				}
				out[x][y]='X';
				add(calc(i,j),calc(x,y));
			}
		}
	}
//	for(int i=1;i<=n;++i){
//		for(int j=1;j<=n;++j){
//			putchar(out[i][j]);
//		}
//		puts("");
//	}
	int ans=n*n-m;
//	减去被挖掉的点 
	for(int i=1;i<=tp;++i){
		for(int j=1;j<=n*n;++j){
			vis[j]=0;
		}
		ans-=dfs(st[i]);
	}
	printf("%d\n",ans);
}

int main(){
	init();
	return 0;
} 

lp5145 漂浮的鸭子

一道tarjan缩点的裸题。
我们仍然可以考虑一个很有趣的做法。那就是,把非环边删去,然后统计环的边权。

#include<iostream>
#include<cstdio>

struct ee{
	int v;
	int w;
}e[100005];

int n,in[100005];
bool vis[100005];

void init(){
	scanf("%d",&n);
	int v,w;
	for(int i=1;i<=n;++i){
		scanf("%d%d",&v,&w);
		e[i]=(ee){v,w};
		++in[v];
	}
	int ans=0,x,nw;
	for(int i=1;i<=n;++i){
		x=i;
		while(!in[x]&&!vis[x]){
			vis[x]=1;
			--in[e[x].v];
			x=e[x].v;
		}
	}
	for(int i=1;i<=n;++i){
		if(!vis[i]){
			nw=e[i].w;
			x=e[i].v;
			vis[i]=1;
			while(x!=i){
				vis[x]=1;
				nw+=e[x].w;
				x=e[x].v;
			}
			ans=std::max(ans,nw);
		}
	}
	printf("%d\n",ans);
}

int main(){
	init();
	return 0;
}

lp2756 网络流24题-飞行员配对方案问题

这是一个裸的配对问题。
我们可以建成一个二分图然后跑匈牙利。

#include<iostream>
#include<cstdio>
bool mp[105][105],vis[105];
int n,m,usd[105];

inline int dfs(int X){
    for(int i=1;i<=m;++i){
        if(!mp[X][i]){
            continue;
        }
        if(!vis[i]){
            vis[i]=1;
            if(!usd[i]||dfs(usd[i])){
                usd[i]=X;
                return 1;
            }
        }
    }
    return 0;
}

void init(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            mp[i][j]=mp[j][i]=0;
        }
    }
    int x=1,y=1;
    //你绝对想不到的错误——x,y没有初始化,导致判断它们的初始值的时候出现错误。 
    while(x>=0&&y>=0){
        scanf("%d%d",&x,&y);
        y-=n;
        mp[x][y]=1;
    }
    int ans=0;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            vis[j]=0;
        }
//        for(int j=1;j<=m;++j){
//        	printf("%d ",usd[j]);
//		}
//		puts("");
        ans+=(int)dfs(i);
    }
    printf("%d\n",ans);
    for(int i=1;i<=m;++i){
        if(usd[i]){
            printf("%d %d\n",usd[i],i+n);
            //注意这里要将编号还原。并且别输出反了。 
        }
    } 
}

int main(){
    init();
    return 0;
}

lp3376 【模板】网络最大流

全机房就我一个还不会网络流了。
下面我整理一下网络流的基本概念,辅助自己理解。


首先关于网络流的定义。形式化地说,网络流是一张图\(G(V,E)\)(有时也指这张图的一个状态),满足以下性质:
1.流量上限:对于任意一条边\(e\in E\),存在一个属性\(c_{e}\),定义它为这条边的流量上限。
2.流量受限:对于任意一条边\(e\in E\),存在一个属性\(0\le f_{e}\le c_{e}\),定义它为这条边当前的流量。
3.流量守恒:对于任意一个点\(v\),满足:\(\sum_{i\in{a|a_{v}=v,a\in E}}f_{i}=\sum_{j\in{b|b_{u}=v,b\in E}}f_{j}\)
4.源点汇点:存在两个点,分别叫做源点和汇点。其中,源点能够流出无穷多流量,而汇点能够流入无穷多流量。
若一个网络流的某一个状态满足上述所有性质,我们就称这个状态是合法的。
我们定义,对于一张网络流,使得它从源点流向汇点的流量最大的状态,为最大流。
求解最大流,就是指,求解最大流的状态。
为了辅助求解这个问题,我们可以考虑对于每一条边\(e\)都建一条反边\(e’\)。它的方向与原边相反。且\(f_{e’}=f_{e}\)
那么,所有的反边构成了另一张图\(G(E’,V)\),它描述的是它的原边已经走过的流量。
将一张图上的每一条边都只保留它的当前剩余流量\(f_{e}\),这张图可以被认为是对原图的流量空余的描述。故而我们称这张图为残余网络。

我们定义增广路径,指的是,在包括反边的残余网络的一条路径上面的一条路径,使得路径上的每一条原边都是不满的,且路径上每一条反边都是非空的。
对于关于这条路径上的所有原边,将其流量上限减去当前流量的值减去最小值,再对路径上每一条反边的当前流量值取最小值,再对两个最小值取最小值。
然后将所有原边的流量加上这个最小值,并将每一条反边的流量减去这个最小值(对应的反/原边同时减/加相应值)。 我们称这样一个操作为增广,称操作中减少反边流量的子操作为撤销。
如果当前图不是处于最大流的状态,那么一定可以找到一个增广路;如果当前图属于最大流的状态,那么一定没有增广路。
我们朴素地考虑如何利用增广来取得最大路径。如果我们每一次都暴力地寻找整个网络上的一条可行增广路并且增广(这似乎被称作F-F算法),在很糟糕的情况下,可能会出现很多次反复地增广而只增加很少的流量的情况。
在上诉的算法中,可能存在一种情况,就是,一条边被反复地增广-撤销多次。这样无形中增大了很多复杂度。
我们考虑上诉的情况是如何产生的。很显然,经过一次撤销操作之后,当前的路径的长度减少了一条边,而原来经过那条边的那些流量所在的路径上的长度也减少了一条边。
那么反复地增广-撤销操作的一个很大的原因,便是,第一次增广到这条边的时候的路径经过的边数太多。
如果每一次搜索增广路径的时候,都尽可能搜索边数尽可能少的一条边,那么便可以使得增广-撤销操作尽可能少。(这似乎被称作E-K算法)
上述的算法都可以被称作是朴素的算法。但复杂度最坏情况下可能会被卡到非常大,大概是\(O(n\times m^2)\)级。


下面是一个对于这个算法的正确性的感性证明。
我们首先证明,每一次增广之后,图上流过的流量都增多。
对于一次增广,当我们流过一条边的时候,流过的流量存在两种情况:
1.这些流量走过的是反边。
2.这些流量走过的是原边。
对于流过原边的流量,很显然无论如何可以流的,并且会将原图的状况改进得更优。
而对于流过反边的流量,可以视为将这些流量还原,然后原来流到这条边的那些流量,现在从当前路径流过这条边之后的那部分流走;而当前流到这条边的流量,则从之前流过这条边的那些流量的后半部分流走。
所以,每一次增广,总是会导向一个合法状态。
又因为,每一次增广之后,源点都会流出更多的流量,汇点都会收到更多的流量,所以整张图流过的流量增加了。

然后我们考虑证明,当不再能增广的时候,图上处于最大流的状态。
当走过一条边的时候,我们事实上完成了一次「反悔」,也就是指,让之前从这里走的一些流量往另一个方向走了。
如果,不再可以增广,这就意味着,无论反悔到什么程度、无论怎么改变之前已有的流量的路径,都无法找到一条新的路径使得流量可以通过。
即,哪怕是在反悔最多的情况下,也找不到一条能够产生更多流量的路径。
那么,我们就可以断言这个状态已经是最大流的状态了。


回到算法本身上。下面我们考虑优化这个朴素算法。\(O(n\times m^2)\)的复杂度显然是不可接受的。
Dinic算法就是一种对上述朴素算法的优化。
我们考虑一种被称为「多路增广」的操作。这种操作也是Dinic的核心。
对于每一次多路增广,我们首先将整张图dfs一遍,预处理出深度小于源汇距离的所有节点的深度。这样我们得到了一张分层图。
然后我们从源点开始进行一种特殊的DFS——每一次访问的节点的深度必须比前一个节点深,并且搜索经过的边必须是可以增广的边。
当我们搜索到汇点的时候,便开始沿着来路回溯,直到回溯到第一个「来路仍然可以继续增广」并且「连着其他还可以被继续增广的边」的节点为止,然后继续向下搜索。
如果回溯到了源点,多路增广结束。
然后,对剩下可以走的部分,重新计算深度,并重跑增广,直到不能再增广为止。
对于每一次多路增广,我们可以以\(O(nm)\)的复杂度遍历完成对某一个特定深度的所有增广操作。 而多路增广显然是最多只会被执行\(n\)次的。故而这么做的复杂度是\(O(n^2+m)\)的。
我们就得到了一个相对较优的算法。


#include<iostream>
#include<cstdio>
#include<queue>

const int INF = 0x3f3f3f3f;

inline int Min(int A,int B){
	return A<B?A:B;
}

struct ee{
	int v;
	int w;
	int nxt;
}e[200005];
int h[10005],et=-1;
int n,m,s,t,ans=0,dep[10005],nw[10005];
inline void add(int U,int V,int W){
	e[++et]=(ee){V,W,h[U]};
	h[U]=et;
}
std::queue<int> q;
inline bool bfs(){
	for(int i=1;i<=n;++i){
		dep[i]=INF;
		nw[i]=h[i];
	}
	while(!q.empty()){
		q.pop();
	}
	dep[s]=0;
	q.push(s);
	int p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		for(int i=h[p];i>=0;i=e[i].nxt){
			if(dep[e[i].v]==INF&&e[i].w){
				dep[e[i].v]=dep[p]+1;
				q.push(e[i].v);
			}
		}
	}
	return dep[t]<INF;
}

inline int dfs(int X,int V){
	if((V<=0)||(X==t)){
		return V;
	}
	int cnt=0,val;
	for(int i=nw[X];i>=0;i=e[i].nxt){
		nw[X]=i;
		if(dep[e[i].v]==dep[X]+1){
			val=dfs(e[i].v,Min(V,e[i].w));
			if(val){
				cnt+=val;
				V-=val;
				e[i].w-=val;
				e[i^1].w+=val;
				if(V<=0){
					break;
				}
			}
		}
	}
	return cnt; 
}

void init(){
	scanf("%d%d%d%d",&n,&m,&s,&t);
	int u,v,w;
	for(int i=1;i<=n;++i){
		h[i]=-1;
	}
	for(int i=1;i<=m;++i){
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
		add(v,u,0);
	}
	while(bfs()){
		ans+=dfs(s,INF);
		//注意应当填写起始点。 
	}
	printf("%d\n",ans);
}

int main(){
	init();
	return 0; 
}

lp4117 Ynoi2018 五彩斑斓的世界

虽然我没有玩过这个Galgame,但是就截图而言画风还是挺可爱的。
抱歉离题了。
这是一道由乃省的省选题。
大家都知道喜欢由乃的某人最喜欢的就是数据结构了。
仔细观察这道题的数据范围,我们可以想到分块。
对于每个块里面数值相同的数维护一个并查集,对于每一个并查集维护它的大小。那么我们每一次修改,如果是暴力修改就只需要改变一个元素所在的集合,如果是整块修改就将并查集合并。
查询的时候块外部分暴力更新,快内部分按块查询即可。
但是这一题的常数简直丧心病狂,毒瘤lxl简直是魔鬼。SIZE大了T,SIZE小了MLE。我卡了整整十九次,最终结合前人优秀经验,使用unsigned char成功卡了过去。
大家记住这组魔法的数字:253-410

#include<iostream>
#include<cstdio>
#include<cmath>
#define MAXNUM 410
int SIZE,NUM;
int bl[100005],lb[MAXNUM],rb[MAXNUM];
int a[100005],tgb[MAXNUM];
int val[100005],mx[100005],fa[100005];
unsigned char cnt[MAXNUM][100005],loc[MAXNUM][100005];
int n,m;
inline int fthr(int X){
	while(X^fa[X]){
		X=fa[X]=fa[fa[X]];
	}
	return X;
}
inline void uni(int X,int A,int B){
	//将X块中的A合并到B处。若B处存在则直接合并,否则将B移动到A并修改A的值。 
	loc[X][B]?fa[loc[X][A]+lb[X]-1]=loc[X][B]+lb[X]-1:(loc[X][B]=loc[X][A],val[loc[X][A]+lb[X]-1]=B);
	cnt[X][B]+=cnt[X][A],cnt[X][A]=loc[X][A]=0;
}
inline void del(int S,int X){
	//如果X比最大值的一半还要小,那么我们考虑将所有小于X的上移,并且修改标记;否则将所有大于X的下移。 
	if((X<<1)<=mx[S]-tgb[S]){
		for(int i=tgb[S]+1;i<=tgb[S]+X;++i){
			if(loc[S][i]){
				uni(S,i,i+X);
			}
		}
		tgb[S]+=X; 
	}else{
		for(int i=X+tgb[S]+1;i<=mx[S];++i){
			if(loc[S][i]){
				uni(S,i,i-X);
			}
		}
		mx[S]=std::min(mx[S],tgb[S]+X);
	}
}
inline void pshd(int X){
	for(int i=lb[X];i<=rb[X];++i){
		a[i]=val[fthr(i)];
		loc[X][a[i]]=cnt[X][a[i]]=0;
		//应当先清空再修改标记。 
		a[i]-=tgb[X];
	}
	for(int i=lb[X];i<=rb[X];++i){
		fa[i]=0;
	}
	tgb[X]=0;
}
inline void updt(int X){
	mx[X]=0;
	for(int i=lb[X];i<=rb[X];++i){
		mx[X]=std::max(mx[X],a[i]);
		loc[X][a[i]]?(fa[i]=loc[X][a[i]]+lb[X]-1):(fa[i]=i,val[i]=a[i],loc[X][a[i]]=i-lb[X]+1);
		++cnt[X][a[i]];
	}
}
inline void chng(int L,int R,int X){
	if(bl[L]^bl[R]){
		pshd(bl[L]),pshd(bl[R]);
		for(int i=L;i<=rb[bl[L]];++i){
			if(a[i]>X){
				a[i]-=X;
			}
		}
		for(int i=lb[bl[R]];i<=R;++i){
			if(a[i]>X){
				a[i]-=X;
			}
		}
		updt(bl[L]),updt(bl[R]);
		for(int i=bl[L]+1;i<=bl[R]-1;++i){
			del(i,X);
		}
	}else{
		pshd(bl[L]);
		for(int i=L;i<=R;++i){
			if(a[i]>X){
				a[i]-=X;
			}
		}
		updt(bl[L]);
	}
}
inline int qry(int L,int R,int X){
	if(bl[L]^bl[R]){
		int rt=0;
		for(int i=L;i<=rb[bl[L]];++i){
			if(val[fthr(i)]-tgb[bl[L]]==X){
				++rt;
			}
		}
		for(int i=lb[bl[R]];i<=R;++i){
			if(val[fthr(i)]-tgb[bl[R]]==X){
				++rt;
			}
		}
		//注意这里减去的是其所在块的lzytg 
		for(int i=bl[L]+1;i<=bl[R]-1;++i){
			rt+=((X+tgb[i]<=100000)?cnt[i][X+tgb[i]]:0);
		}
		return rt;
	}else{
		int rt=0;
		for(int i=L;i<=R;++i){
			if(val[fthr(i)]-tgb[bl[L]]==X){
				++rt;
			}
		}
		return rt;
	}
}
inline void DEBUG(){
	for(int i=1;i<=n;++i){
		printf("%d/%d ",val[fthr(i)],a[i]);
	}
	puts("");
	for(int i=1;i<=NUM;++i){
		printf("[%d %d|%d|%d],",lb[i],rb[i],tgb[i],mx[i]);
	}
	puts("");
	/*
	for(int i=1;i<=100;++i){
		if(loc[2][i]){
			printf("{%d} ",i);
		}
	} 
	*/
}
void init(){
	scanf("%d%d",&n,&m);
	SIZE=253;
	NUM=std::ceil((double)n/SIZE);
	for(int i=1;i<=NUM;++i){
		lb[i]=(i-1)*SIZE+1;
		rb[i]=i*SIZE;
		for(int j=lb[i];j<=rb[i];++j){
			bl[j]=i;
		}
	}
	rb[NUM]=n;
	for(int i=1;i<=n;++i){
		scanf("%d",a+i);
	}
	for(int i=1;i<=NUM;++i){
		updt(i);
	}
	int op,l,r,x;
	for(int i=1;i<=m;++i){
//		DEBUG();
		scanf("%d%d%d%d",&op,&l,&r,&x);
		if(op==1){
			chng(l,r,x);
		}else{
			printf("%d\n",qry(l,r,x));
		}
	}
}

int main(){
//	freopen("test.out","w",stdout);
	init();
	return 0;
}

AT1219 历史研究

一道回滚莫队的例题。
莫队算法能够解决很多类似于求和的询问问题。但是对于求最值的询问它无能为力。这是因为莫队需要一个区间既能够拓展又能够收缩。
对于求最值类的问题,它只能够拓展,不能够收缩。
这时候我们可以使用一种被称为「回滚莫队」的算法。
具体来说,对于每个块内的询问,我们都分成两部分来处理。一部分是将右端点推进,另一部分则是将左端点推进。对于每一个询问,我们在求得它向右端点推进的值以后,暴力统计上左端点对它的贡献即可。
请注意回滚莫队不能奇偶分块。结合回滚莫队的性质可以很容易理解。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
int BLOCK,NUM;
int bl[100005],lb[100005],rb[100005];
struct Query{
	int l;
	int r;
	int id;
	inline bool operator<(const Query &B)const{
		return (bl[l]^bl[B.l])?(bl[l]<bl[B.l]):(r<B.r);
	}
}q[100005];
int n,m,a[100005],cnt1[100005],cnt2[100005],loc[100005],typ[100005];
long long ans[100005];
void init(){
	scanf("%d%d",&n,&m);
	BLOCK=std::sqrt(n);
	NUM=std::ceil((double)n/BLOCK);
	for(int i=1;i<=NUM;++i){
		lb[i]=BLOCK*(i-1)+1;
		rb[i]=BLOCK*i;
		for(int j=lb[i];j<=rb[i];++j){
			bl[j]=i;
		}
	}
	rb[NUM]=n;
	for(int i=1;i<=n;++i){
		scanf("%d",a+i);
		loc[i]=a[i];
	}
	std::sort(loc+1,loc+1+n);
	int tot=std::unique(loc+1,loc+1+n)-loc-1;
	for(int i=1;i<=n;++i){
		typ[i]=std::lower_bound(loc+1,loc+1+tot,a[i])-loc;
	}
	for(int i=1;i<=m;++i){
		scanf("%d%d",&q[i].l,&q[i].r);
		q[i].id=i;
	}
	std::sort(q+1,q+1+m);
	int p=1;
	for(int i=0;i<=NUM;++i){
		int l=rb[i]+1,r=rb[i];
		long long nw=0;
		for(int j=1;j<=n;++j){
			cnt1[j]=0;
		}
		for(;bl[q[p].l]==i;++p){
			int ql=q[p].l,qr=q[p].r;
			long long tmp=0;
			if(bl[ql]==bl[qr]){
				for(int j=ql;j<=qr;++j){
					cnt2[typ[j]]=0;
				}
				for(int j=ql;j<=qr;++j){
					++cnt2[typ[j]];
					tmp=std::max(tmp,1ll*cnt2[typ[j]]*a[j]);
				}
				ans[q[p].id]=tmp;
				continue;
			}
			while(r<qr){
				++r;
				++cnt1[typ[r]];
				nw=std::max(nw,1ll*cnt1[typ[r]]*a[r]);
			}
			tmp=nw;
			while(l>ql){
				--l;
				++cnt1[typ[l]];
				nw=std::max(nw,1ll*cnt1[typ[l]]*a[l]);
			}
			ans[q[p].id]=nw;
			while(l<rb[i]+1){
				--cnt1[typ[l]];
				++l;
			}
			nw=tmp;
		}
	}
	for(int i=1;i<=m;++i){
		printf("%lld\n",ans[i]);
	}
}

int main(){
	init();
	return 0;
}

CF600E Lomsat gelral

一道树上启发式合并的例题。
首先考虑暴力的做法。统计每一个子节点的信息,然后传到父节点。
我们发现这样做的复杂度是\(O(n^2)\)的。显然,复杂度是错误的。
我们考虑修改统计子节点的顺序。
重链剖分有一个很有意义的性质:一个点通向根的路径上的轻边的数量最多不会超过\(log_n\)。这利用重链剖分的性质可以轻松用反证法证明。
那么,依据这个性质,我们可以统计轻边、上传重边。这也就意味着,对于每一次访问,如果它是一条轻边,那么就把它的信息统计完了清空;如果是一条重边,那么把它的信息上传。
例如,我们现在有一个节点\(X\),那么我们先计算它的所有轻节点,然后我们再计算它的重节点,最后将它除了重节点以外的地方都搜一遍,这样就获得了它的所有信息。
为什么这样做复杂度是对的呢?这就可以基于刚刚那个性质来证明了。具体地来说,一个节点会被清理信息,当且仅当它是一个节点下面的一个轻节点。也就是说,它被清空的次数就是它通向根的路径上轻边的数量。
由刚才那个性质可得,这个值是对数级的,所以复杂度是对的。
注意sm数组的tp的控制。

#include<iostream>
#include<cstdio>
struct ee{
	int v;
	int nxt;
}e[200005];
int h[100005],et=0;
inline void add(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}
int sn[100005],sz[100005],a[100005],cnt[100005];
bool kp[100005];
long long ans[100005];//ans表示每个节点的答案 
long long sm[100005];//sn表示出现次数为cnt次的颜色值的和 
int n;
inline void dfs1(int X,int FA){
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v!=FA){
			dfs1(e[i].v,X);
		}
	}
	sz[X]=1;
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v){
			sz[X]+=sz[e[i].v];
			if(sz[e[i].v]>sz[sn[X]]){
				sn[X]=e[i].v;
			}
		}
	}
}
int tp;
inline void rnw(int X,int FA,int V){
	sm[cnt[a[X]]]-=a[X];
	cnt[a[X]]+=V;
	sm[cnt[a[X]]]+=a[X];
	if(sm[tp+1]){
		++tp;
	}
	if(!sm[tp]){
		--tp;
	}
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v!=FA&&!kp[e[i].v]){
			rnw(e[i].v,X,V);
		}
	}
}
inline void dfs2(int X,int FA,int isSn){
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v!=FA&&e[i].v!=sn[X]){
			dfs2(e[i].v,X,0);
		}
	}
	if(sn[X]){
		dfs2(sn[X],X,1);
		kp[sn[X]]=1;
	}
	rnw(X,FA,1);
	kp[sn[X]]=0;
	ans[X]=sm[tp];
	if(!isSn){
		rnw(X,FA,-1);
	} 
}
void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
	}
	int u,v;
	for(int i=1;i<n;++i){
		scanf("%d%d",&u,&v);
		add(u,v),add(v,u);
	}
	dfs1(1,0);
	dfs2(1,0,1);
	for(int i=1;i<=n;++i){
		printf("%lld ",ans[i]);
	}
}

int main(){
	init();
	return 0;
}

lp1494 国家集训队 小Z的袜子

令颜色为\(c_i\)为第\(i\)种颜色在给定区间内出现的次数。
则,题目所求为:
$$\frac{\sum_{i=1}^{n}c_{i}(c_{i}-1)}{(r-l)(r-l+1)}$$
展开可以得到:
$$\frac{\sum_{i=1}^{n}c_{i}^2-\sum_{i=1}^{n}c_{i}}{(r-l)(r-l+1)}$$
由性质可得:
$$\sum_{i=1}^{n}c_{i}=r-l+1$$
故而,我们需要求的仅有:
$$\sum_{i=1}^{n}c_{i}^2$$
对于这个式子的求法,我们很容易可以想到莫队。
我们考虑一个区间添加上一个数与删除一个数造成的影响。
令修改的颜色为\(x\),则:
$$\Delta v=\sum_{i=1}^{n}c_{i}^2-c_{x}^{2}+(c_{x}±1)^2-\sum_{i=1}^{n}c_{i}^2$$
展开可得:
$$\Delta v=1±2c_{x}$$

下面考虑莫队。
莫队的原理大致是,将原数列分块,然后将询问以左端点在原数列中的块为第一关键字,右端点为第二关键词来排序。
虽然说它是一种优化后的暴力,但是,若令一次修改的复杂度是\(f_{n}\),根据最小直线斯坦纳树的性质,可以证明这么做的复杂度是 \(O(f_{n} n \sqrt{m})\),可以通过此题。
依据毒瘤lxl的说法,莫队最快的分块大小是\(n/\sqrt{m*2/3}\)
故而我们对原数列分块完以后,将询问排序。然后开始移动区间。
扫一遍即可。
另外就是一个小优化,排序的时候分奇偶排序,也就是说,奇数块右端点递增,偶数块右端点递减。
原理很简单,就是移过去再移回来,路上的点都扫了一遍。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
int BLOCK;
int belong[50005];
struct Query{
	int l;
	int r;
	int id;
	int len;
	inline bool operator <(const Query &B)const{
		return (belong[l]^belong[B.l])?(belong[l]<belong[B.l]):((belong[l]&1)?r<B.r:r>B.r);
	}
}q[50005];
long long tot=0;
int cnt[50005];
inline void add(int X){
	tot+=(cnt[X]<<1|1);
	++cnt[X];
}
inline void del(int X){
	tot+=(1-(cnt[X]<<1));
	--cnt[X];
}
inline long long Gcd(long long A,long long B){
	return B?Gcd(B,A%B):A;
}
long long ans1[50005],ans2[50005];
int n,m,a[50005];
void init(){
	scanf("%d%d",&n,&m);
	BLOCK=n/std::sqrt(m*2.0/3.0); 
	for(int i=1;i<=n;++i){
		scanf("%d",a+i);
	}
	for(int i=1;i<=m;++i){
		scanf("%d%d",&q[i].l,&q[i].r);
		q[i].id=i;
		q[i].len=q[i].r-q[i].l+1;
		ans2[i]=1;
	}
	for(int i=1;i<=n;++i){
		belong[i]=(i-1)/BLOCK+1;
	}
	std::stable_sort(q+1,q+1+m);
	int l=q[1].l,r=q[1].l-1;
	long long nwgcd;
	for(int i=1;i<=m;++i){
		while(l<q[i].l){
			del(a[l]);
			++l;
		}
		while(l>q[i].l){
			--l;
			add(a[l]);
		}
		while(r>q[i].r){
			del(a[r]);
			--r;
		}
		while(r<q[i].r){
			++r;
			add(a[r]);
		}
		if(tot!=q[i].len){
			ans1[q[i].id]=tot-q[i].len,ans2[q[i].id]=1LL*(q[i].r-q[i].l)*q[i].len;
			nwgcd=Gcd(ans1[q[i].id],ans2[q[i].id]);
			ans1[q[i].id]/=nwgcd,ans2[q[i].id]/=nwgcd;
		}
	}
	for(int i=1;i<=m;++i){
		printf("%lld/%lld\n",ans1[i],ans2[i]);
	}
}

int main(){
	init();
	return 0;
}

lp1110 ZJOI2007 报表统计

事实上对于第一类询问和第二类询问我们可以分别处理。
第二类询问的处理方法是非常显然的。由于只有插入而没有删除操作,因此,第二类询问的答案只会缩小、不会增大。
故而,我们对整个数列的值维护一个Splay,每一次插入一个新的数以后,用它和它的前驱与它和它的后继的差的绝对值来更新第二类的答案。
这可以用multiset来简易地实现。
对于第一类询问,我们发现,维护这个值其实并不是难点——用线段树或者平衡树都可以轻松实现。问题在于,如何在插入新的数之后保持这个值。
我们仔细思考,发现,对于任意一段区间来说,它对答案的贡献只有三个:这个区间的答案,这个区间的左端点和这个区间的右端点。
故而,我们建一棵线段树或者平衡树,维护这三个信息(个人认为线段树比较科学。)每一次修改则修改对应的节点,然后递归向上更新即可。
这样就做完了,个人觉得实现难度还是比较低的。

#include<iostream>
#include<cstdio>
#include<set>
#define LS (X<<1)
#define RS (X<<1|1)
#define MID ((L+R)>>1)
inline int Abs(int X){
	return X>0?X:-X;
}

inline int Min(int A,int B){
	return A<B?A:B;
}

std::multiset<int> st;
int ansS=0x3f3f3f3f;
int n,m,a[500005];

class SegmentTree{
	private:
		class Node{
			public:
				int l;
				int r;
				int dlt;
			inline Node(){
				dlt=0x3f3f3f3f;
			}
			inline void init(int V){
				l=r=V;
			}
			inline void psh(int V){
				dlt=Min(dlt,Abs(r-V));
				r=V;
			}
		};
		Node tr[1100000];
		inline void updt(int X){
			tr[X].l=tr[LS].l;
			tr[X].r=tr[RS].r;
			tr[X].dlt=Min(Min(tr[LS].dlt,tr[RS].dlt),Abs(tr[LS].r-tr[RS].l));
		}
		inline void build(int L,int R,int X){
			if(L>R){
				return;
			}
			if(L==R){
				tr[X].init(a[L]);
				return;
			}
			build(L,MID,LS),build(MID+1,R,RS);
			updt(X);
		}
		inline void push(int L,int R,int X,int A,int V){
			if(L>R){
				return;
			}
			if(L==R){
				tr[X].psh(V);
				return;
			}
			A>MID?push(MID+1,R,RS,A,V):push(L,MID,LS,A,V);
			updt(X);
		}
		inline void prnt(int L,int R,int X){
			if(L>R){
				return;
			}
			if(L==R){
				printf("%d:[%d,%d,%d] ",X,tr[X].l,tr[X].r,tr[X].dlt);
				return;
			}
			prnt(L,MID,LS),prnt(MID+1,R,RS);
		}
	public:
		inline void PUSH(int X,int K){
			push(1,n,1,X,K);
		}
		inline void BUILD(){
			build(1,n,1);
		}
		inline int QUERYG(){
			return tr[1].dlt;
		}
		inline void PRINT(){
			prnt(1,n,1);
			puts("");
		}
};

inline void STPUSH(int K){
	st.insert(K);
	std::multiset<int> ::iterator it=st.find(K);
	int ans1,ans2;
	++it;
	if(it!=st.end()){
		ans1=*it;
	}else{
		ans1=0x3f3f3f3f;
	}
	--it;
	if(it!=st.begin()){
		--it;
		ans2=*it;
	}else{
		ans2=0x3f3f3f3f;
	}
	ans1=Abs(K-ans1),ans2=Abs(K-ans2);
	ansS=Min(ansS,Min(ans1,ans2));
}

SegmentTree T;
void init(){
	scanf("%d%d",&n,&m);
	int x;
	for(int i=1;i<=n;++i){
		scanf("%d",a+i);
		STPUSH(a[i]);
	}
	T.BUILD();
	char op[10];
	int k;
	for(int i=1;i<=m;++i){
		std::cin>>op;
		switch(op[4]){
			case 'R':{
				scanf("%d%d",&x,&k);
				T.PUSH(x,k);
				STPUSH(k);
				break;
			}
			case 'G':{
				printf("%d\n",T.QUERYG());
				break;
			}
			case 'S':{
				printf("%d\n",ansS);
				break;
			}
			case 'P':{
				T.PRINT();
				break;
			}
		}
	}
}

int main(){
	init();
	return 0;
}

lp2596 ZJOI2006 书架


看到这一题我们就可以想到Splay。
具体来说,这一题要求维护下列四个操作:
将序列中的一个数与它的前一个数/后一个数交换。
将序列中的一个数移到序列头/序列尾。
如果单单如此的话那这一题就太简单了。对于一二操作只需要直接和前驱、后继调换,对于三四操作只需要将左/右子树移动到右/左子树的最左/右节点的左/右孩子。
但事实上并非这样。这一题对序列中数的操作并非是直接给出的,而是对序列中的每一个点编了号,然后每一次访问这个编号。
但仔细思考就会发现,考虑到对序列的操作只会更换位置,
故而,对于这种操作,我们定义一个数组名为loc,储存的是,编号为\(loc_i\)的数在数列中的标号。
要十分注意编号和逆编号的对应关系。以及交换之后对它们原来的关系的影响。

#include<iostream>
#include<cstdio>
#define MID ((L+R)>>1)
int loc[80005],aloc[80005];
class Splay{
	private:
		class Node{
			public:
				int fa;
				int sn[2];
				int sz;
				inline void prnt(){
					printf("(%d,%d,%d)\n",fa,sn[0],sn[1]);
				}
			inline Node(int FA=0,int LS=0,int RS=0,int SZ=0){
				fa=FA,sn[0]=LS,sn[1]=RS,sz=SZ;
			}
		};
		Node tr[80005];
		int rt;
		inline void updt(int X){
			tr[X].sz=tr[tr[X].sn[0]].sz+tr[tr[X].sn[1]].sz+1;
		}
		inline int fndD(int X){
			return tr[tr[X].fa].sn[1]==X;
		}
		inline void splayOne(int X){
			int D=fndD(X),D2=fndD(tr[X].fa);
			tr[tr[X].sn[D^1]].fa=tr[X].fa,tr[tr[X].fa].sn[D]=tr[X].sn[D^1];
			tr[X].sn[D^1]=tr[X].fa,tr[X].fa=tr[tr[X].fa].fa;
			tr[tr[X].fa].sn[D2]=X,tr[tr[X].sn[D^1]].fa=X;
			updt(tr[X].sn[D^1]),updt(X);
		}
		inline void splayTwo(int X){
			int D=fndD(X),D2=fndD(tr[X].fa);
			tr[X].fa?(tr[tr[X].fa].fa?(D==D2?(splayOne(tr[X].fa),splayOne(X),0):(splayOne(X),splayOne(X),0)):(splayOne(X),0)):0; 
		}
		inline void splayRnw(int X){
			while(tr[X].fa){
				splayTwo(X);
			}
			rt=X;
		}
		inline int fnd(int K){
			int P=rt,FP=0;
			while(P){
				FP=P;
				if(tr[tr[P].sn[0]].sz+1<K){
					K-=(tr[tr[P].sn[0]].sz+1);
					P=tr[P].sn[1];
				}else if(tr[tr[P].sn[0]].sz<K){
					return P;
				}else{
					P=tr[P].sn[0];
				}
			}
			return FP;
		}
		inline int fndMn(int X){
			int P=X,FP=tr[X].fa;
			while(P){
				FP=P;
				P=tr[P].sn[0];
			}
			return FP;
		}
		inline int fndMx(int X){
			int P=X,FP=tr[X].fa;
			while(P){
				FP=P;
				P=tr[P].sn[1];
			}
			return FP;
		}
		inline int build(int L,int R,int FA){
			if(L>R){
				return 0;
			}
			tr[MID].fa=FA,tr[MID].sz=1;
			tr[MID].sn[0]=build(L,MID-1,MID);
			tr[MID].sn[1]=build(MID+1,R,MID);
			updt(MID);
			return MID;
		}
		inline void prnt(int X){
			if(!X){
				return;
			}
			prnt(tr[X].sn[0]);
			printf("%d ",X);
			prnt(tr[X].sn[1]);
		}
	public:
		inline void INIT(int N){
			build(1,N,0);
			rt=(1+N)>>1;
		}
		inline void SWAP(int X,int D){
			splayRnw(X);
			int P=D?fndMn(tr[X].sn[1]):fndMx(tr[X].sn[0]);
			int X_2=aloc[X],P_2=aloc[P];
			std::swap(loc[X_2],loc[P_2]);
			std::swap(aloc[X],aloc[P]);
			splayRnw(X);
		}
		inline void LST(int X){
			splayRnw(X);
			int P=fndMn(tr[X].sn[1]);
			tr[tr[X].sn[0]].fa=P,tr[P].sn[0]=tr[X].sn[0],tr[X].sn[0]=0;
			splayRnw(tr[P].sn[0]);
		}
		inline void RST(int X){
			splayRnw(X);
			int P=fndMx(tr[X].sn[0]);
			tr[tr[X].sn[1]].fa=P,tr[P].sn[1]=tr[X].sn[1],tr[X].sn[1]=0;
			splayRnw(tr[P].sn[1]);
		}
		inline int RNK(int X){
			splayRnw(X);
			return tr[tr[X].sn[0]].sz;
		}
		inline int ARNK(int X){
			int P=fnd(X);
			splayRnw(P);
			return P;
		}
		inline void PRINT(){
			printf("%d ->",rt);
			prnt(rt);
			puts("");
		}
};
int n,m;
Splay T;
void init(){
	scanf("%d%d",&n,&m);
	T.INIT(n);
	int x,t;
	for(int i=1;i<=n;++i){
		scanf("%d",&x);
		loc[x]=i,aloc[i]=x;
	}
	char op[10];
	for(int i=1;i<=m;++i){
		std::cin>>op;
		scanf("%d",&x);
		switch(op[0]){
			case 'T':{
				T.LST(loc[x]);
				break;
			}
			case 'B':{
				T.RST(loc[x]);
				break;
			}
			case 'I':{
				scanf("%d",&t);
				t==0?0:(T.SWAP(loc[x],t==-1?0:1),0);
				break;
			}
			case 'A':{
				printf("%d\n",T.RNK(loc[x]));
				break;
			}
			case 'Q':{
				printf("%d\n",aloc[T.ARNK(x)]);
				break;
			}
		}
	} 
}

int main(){
	init();
	return 0;
}

lp3386 二分图最大匹配

一道匈牙利算法的模板题。
对于一张二分图\(G\)(也就是没有奇环的图),我们定义它的「匹配」为一个图\(G'(V’,E’)\),使得:
$$\forall V” \in V’,V”_{u}\in E’,V”_{v}\in E’,|E’|=2|V’|$$
我们称一个匹配是最大匹配,当且仅当它是一个边数最多的匹配。

匈牙利算法是用于求解最大匹配的一类问题。
匈牙利算法使用了一种被称为「增广」的操作。
我们首先定义一条增广路径指的是一张二分图上的路径,使得这条路径的起点和终点都是尚未匹配的点,并且它的路径上经过的所有点都是已经匹配过的点。
那么很容易可以发现,一条增广路径上的边必然是「一条已匹配一条未匹配」的。
于是,我们对增广路径上的所有边的匹配状态取反,就可以增加匹配数量的大小。
增广操作是指,对于一个点,尝试访问它的每一个相邻点,然后从这个相邻点找下去,直到能找到一条增广路径为止。然后将这条增广路径上所有边匹配状态取反。
故而,每一次新加入一个点,我们尝试一次增广。这样就能够找到最大匹配了。

#include<iostream>
#include<cstdio>

int mp[1005][1005];
bool vis[1005];
int n,m,q,usd[1005];
inline bool dfs(int X){
	for(int i=1;i<=m;++i){
		if(!mp[X][i]){
			continue;
		}
		if(!vis[i]){
			vis[i]=1;
			if(!usd[i]||dfs(usd[i])){
				usd[i]=X;
				return 1;
			}
		}
	}
	
	return 0;
}
void init(){
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			mp[i][j]=mp[j][i]=0;
			usd[i]=usd[j]=0;
		}
	}
	int u,v;
	for(int i=1;i<=q;++i){
		scanf("%d%d",&u,&v);
		if(u>n||v>m){
			continue;
		}
		++mp[u][v];
	}
	int ans=0;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			vis[j]=0;
		}
		ans+=dfs(i);
	}
	printf("%d\n",ans);
}

int main(){
	init();
	return 0;
}

lp2042 NOI2005 维护数列

Splay裸题。
具体来说,维护两个延迟标记,翻转标记和改变标记。然后对于每一个标记考虑下传。
对于两种询问各自更新区间和与区间最大子段和。
一个区间的最大子段和有可能有三种情况:左子区间的最大子段和,右子区间的最大子段和,以及跨过两个区间的子段和。
故而我们对每个区间关于子段和维护三个信息,左起最大子段和、右起最大子段和以及总最大子段和。
而对于左起最大子段和的更新,则考虑两种情况:左子区间的最大子段和,以及整个左子区间加上根节点再加上右子区间的左起最大子段和。
右起同理。

注意:

  • 1.updt时应当先updt(tr[X].sn[D^1])再updt(X)
  • 2.添加节点和各种修改之后应当科学地rnw
  • 3.添加节点时应当注意是从posi~posi+1之间的区间。
  • 4.一个节点被删除以后,rnw它的父亲是没有意义的,应当从根开始rnw
  • 5.内存回收机制中,添加入栈应当是++tp,出栈应当是tp–
  • 6.考虑updt和pshd的方式:对于每一次pshd,我们应该统一修改它的子节点的标记,并对它的子节点计算贡献,然后取消它本身的标记;打标记的时候对它本身计算好贡献。
  • 换句话说,不要在统计一个节点的贡献之前,updt它的父亲。
  • 7.加入节点应当加入成一棵二叉树,而不是一条链。根据我根本不懂的势能分析法,加入一棵二叉树带来的势能改变是常数乘大小级的,而一条链则是对数乘大小级的。
  • 8.对于MAX-SUM操作,必须要至少选中一个节点,所以应当额外维护一个最大值。

#include<iostream>
#include<cstdio>
#define R register
#define MAGIC 19260817
#define MID ((L+R_R)>>1)
/*

*/
inline int Max(int A,int B){
    return A>B?A:B;
}
inline int Chck(int X){
    return X>0?X:0;
}
inline void Swap(int &A,int &B){
    A^=B^=A^=B;
}
//表示特殊状态 
class Splay{
    private:
        class Node{
            public:
    			int fa;
    			int sn[2];
    			int sz;
    			int sm;
    			int lmxsm;
    			int rmxsm;
    			int mxsm;
    			int mx;
    			int v;
    			int lzy_flp;
    			int lzy_chng;
    			inline void set(int FA,int V){
    			    fa=FA,sz=1,sm=v=mxsm=mx=V,lmxsm=rmxsm=Chck(V);
    			    sn[0]=sn[1]=lzy_flp=0,lzy_chng=MAGIC;
                }
                inline void init(){
                    fa=sz=sm=lmxsm=rmxsm=v=sn[0]=sn[1]=lzy_flp=0;
                    mxsm=mx=-MAGIC;
                    lzy_chng=MAGIC;
                }
        };
        Node tr[500005];
        int st[500005],tp,cnt,rt;
        inline int fndD(int X){
            return tr[tr[X].fa].sn[0]==X?0:1;
        }
        inline void chng(int X){
            tr[X].sm=tr[X].lzy_chng*tr[X].sz,tr[X].mxsm=Max(tr[X].lzy_chng,tr[X].lzy_chng*tr[X].sz);tr[X].lmxsm=tr[X].rmxsm=Chck(tr[X].lzy_chng*tr[X].sz);
            tr[X].v=tr[X].mx=tr[X].lzy_chng;
        }
        inline void flp(int X){
            Swap(tr[X].sn[0],tr[X].sn[1]);
            Swap(tr[X].lmxsm,tr[X].rmxsm);
        }
        inline void pshd(int X){
            if(!X){
                return;
            }
            if(tr[X].lzy_chng!=MAGIC){
            	tr[tr[X].sn[0]].lzy_chng=tr[tr[X].sn[1]].lzy_chng=tr[X].lzy_chng;
                chng(tr[X].sn[0]),chng(tr[X].sn[1]);
                tr[X].lzy_chng=MAGIC;
            }
            if(tr[X].lzy_flp){
            	tr[tr[X].sn[0]].lzy_flp^=1,tr[tr[X].sn[1]].lzy_flp^=1;
                flp(tr[X].sn[0]),flp(tr[X].sn[1]);
                tr[X].lzy_flp=0;
            }
        }
        inline void updt(int X){
            if(!X){
                return;
            }
            tr[X].sm=tr[tr[X].sn[0]].sm+tr[tr[X].sn[1]].sm+tr[X].v;
            tr[X].mx=Max(Max(tr[tr[X].sn[0]].mx,tr[tr[X].sn[1]].mx),tr[X].v);
            tr[X].sz=tr[tr[X].sn[0]].sz+tr[tr[X].sn[1]].sz+1;
            tr[X].lmxsm=Max(tr[tr[X].sn[0]].sm+tr[X].v+tr[tr[X].sn[1]].lmxsm,tr[tr[X].sn[0]].lmxsm);
            tr[X].rmxsm=Max(tr[tr[X].sn[1]].sm+tr[X].v+tr[tr[X].sn[0]].rmxsm,tr[tr[X].sn[1]].rmxsm);
            tr[X].mxsm=Max(Max(tr[tr[X].sn[0]].mxsm,tr[tr[X].sn[1]].mxsm),tr[tr[X].sn[0]].rmxsm+tr[X].v+tr[tr[X].sn[1]].lmxsm);
        }
        inline void splayOne(int X){
            int D=fndD(X),D2=fndD(tr[X].fa);
            tr[tr[X].sn[D^1]].fa=tr[X].fa,tr[tr[X].fa].sn[D]=tr[X].sn[D^1];
            tr[X].sn[D^1]=tr[X].fa,tr[X].fa=tr[tr[X].fa].fa;
            tr[tr[X].sn[D^1]].fa=X,tr[tr[X].fa].sn[D2]=X;
            updt(tr[X].sn[D^1]),updt(X);
        }
        inline void splayTwo(int X){
            int D=fndD(X),D2=fndD(tr[X].fa);
            tr[X].fa?(tr[tr[X].fa].fa?(D==D2?(splayOne(tr[X].fa),splayOne(X),0):(splayOne(X),splayOne(X),0)):(splayOne(X),0)):0;
        }
        inline void splayRnw(int X){
            if(!X){
                return;
            }
            //printf("%d->",X);
            while(tr[X].fa){
                splayTwo(X);
                //printf("[%d,%d,%d[%d,%d](%d)] ",X,tr[X].fa,tr[tr[X].fa].fa,tr[X].sn[0],tr[X].sn[1],fndD(X));
            }
            //puts("");
            rt=X;
        }
        //注意,权值splay中的fnd函数实质上求的是排名为K的节点。 
        inline int fnd(int K){
            R int P=rt,FP=0;
            while(P){
                pshd(P);
                FP=P;
                if(tr[tr[P].sn[0]].sz+1<K){
                    K-=(tr[tr[P].sn[0]].sz+1);
                    P=tr[P].sn[1];
                }else if(tr[tr[P].sn[0]].sz<K){
                    return P;
                }else{
                    P=tr[P].sn[0];
                }
            }
            return FP;
        }
        inline int nwlc(int FA,int D,int V){
            if(!cnt){
                rt=1;
            }
            int P=tp?st[tp--]:++cnt;
            tr[FA].sn[D]=P;
            tr[P].set(FA,V);
            return P;
        }
        inline int preSplay(int L,int LEN){
            int __L__=fnd(L),__R__=fnd(L+LEN+1);
            splayRnw(tr[__L__].fa),splayRnw(tr[__R__].fa);
            splayRnw(__L__);
            splayRnw(__R__);
            //printf("%d,%d,%d\n",rt,tr[rt].sn[0],tr[rt].sn[1]);
            if(tr[__L__].fa!=__R__&&__L__!=__R__){
                splayOne(__L__);
            }
            pshd(tr[tr[rt].sn[0]].sn[1]);
            return tr[rt].sn[0];
        }
        inline void rmv(int X){
            if(!X){
                return;
            }
            rmv(tr[X].sn[0]);
            rmv(tr[X].sn[1]);
            tr[tr[X].fa].sn[fndD(X)]=0;
            tr[tr[X].sn[0]].fa=tr[tr[X].sn[1]].fa=0;
            st[++tp]=X;
        }
        inline void prnt(int X, int dep=0){
            if(!X){
                return;
            }
            //pshd(X);
            prnt(tr[X].sn[0], dep+1);
            //printf("{%d}[%d](%d,%d)[%d][%d,%d] ",X,tr[X].v,tr[X].sn[0],tr[X].sn[1],tr[X].mxsm,tr[X].lmxsm,tr[X].rmxsm);
            for(int i = 1; i <= dep; ++i) printf("口");
        	//printf("ID:%d    VAL:%d    SM:%d   CHANGE_TAG:%d \n",X,tr[X].v,tr[X].sm,tr[X].lzy_chng);
        	printf("%d %d\n",tr[X].v,tr[X].mxsm);
            prnt(tr[X].sn[1], dep+1);
        }
        inline void build(int L,int R_R,int *IN,int D,int FA){
        	if(L>R_R){
        		return;
			}
        	int P=nwlc(FA,D,IN[MID]);
        	build(L,MID-1,IN,0,P);
        	build(MID+1,R_R,IN,1,P);
        	updt(P);
		}
    public:
        inline void INSERT(int L,int TOT,int *IN){
            int X=preSplay(L+1,0);
            build(1,TOT,IN,1,X);
            updt(X),updt(tr[X].fa),updt(tr[tr[X].fa].fa);
       }
        inline void DELETE(int L,int LEN){
            int X=tr[preSplay(L,LEN)].sn[1];
            rmv(X);
            updt(tr[rt].sn[0]),updt(rt);
        }
        inline void MAKE_SAME(int L,int LEN,int V){
            int X=tr[preSplay(L,LEN)].sn[1];
            tr[X].lzy_chng=V;
            chng(X);
            updt(tr[X].fa),updt(tr[tr[X].fa].fa);
        }
        inline void REVERSE(int L,int LEN){
            int X=tr[preSplay(L,LEN)].sn[1];
            tr[X].lzy_flp^=1;
            if(tr[X].lzy_flp){
            	flp(X);
            }
            updt(tr[X].fa),updt(tr[tr[X].fa].fa);
        }
        inline void GET_SUM(int L,int LEN){
            int X=tr[preSplay(L,LEN)].sn[1];
            printf("%d\n",tr[X].sm);
        }
        inline void MAX_SUM(){
            printf("%d\n",(tr[rt].mxsm)?tr[rt].mxsm:tr[rt].mx);
        }
        inline void INIT(int N,int *IN){
            tr[0].init();
            rt=tp=cnt=0;
            int X=0;
            for(int i=1;i<=N;++i){
                X=nwlc(X,1,IN[i]);
            }
            nwlc(1,0,-MAGIC),nwlc(X,1,-MAGIC);
            splayRnw(N+1),splayRnw(N+2);
        }
        inline void PRINT(){
            printf("%d ->\n",rt);
            prnt(rt);
            puts("");
        }
};
int n,m;
int a[4000005];
Splay T;
void init(){
    scanf("%d%d",&n,&m);
    int posi,tot,c;
    char op[10];
    for(int i=1;i<=n;++i){
        scanf("%d",a+i);
    }
    T.INIT(n,a);
    for(int i=1;i<=m;++i){
        std::cin>>op;
        switch(op[2]){
            case 'S':{
                scanf("%d%d",&posi,&tot);
                for(int j=1;j<=tot;++j){
                    scanf("%d",a+j);
                }
                T.INSERT(posi,tot,a);
                break;
            }
            case 'L':{
                scanf("%d%d",&posi,&tot);
                T.DELETE(posi,tot);
                break;
            }
            case 'K':{
                scanf("%d%d%d",&posi,&tot,&c);
                T.MAKE_SAME(posi,tot,c);
                break;
            }
            case 'V':{
                scanf("%d%d",&posi,&tot);
                T.REVERSE(posi,tot);
                break;
            }
            case 'T':{
                scanf("%d%d",&posi,&tot);
                T.GET_SUM(posi,tot);
                break;
            }
            case 'X':{
                T.MAX_SUM();
                break;
            }
        }
    }
}

int main(){
    init();
    return 0;
}

CF1093

这场比赛打得很糟心,具体来说就是Debug能力不足。勉强涨了一点分。


CF1093 A
一道水题。依照题意模拟即可。

#include<iostream>
#include<cstdio>

int n;
void init(){
	scanf("%d",&n);
	int x,ans;
	for(int i=1;i<=n;++i){
		scanf("%d",&x);
		ans=x/7+1;
		printf("%d\n",ans);
	}
}

int main(){
	init();
	return 0;
}

CF1093 B
将字符串排序之后,如果第一项和最后一项不同,那它肯定不是回文;如果相同,那么中间也都相同,判一下即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

int n,len;
char ch[1005];
void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		std::memset(ch,0,sizeof(ch));
		std::cin>>ch+1;
		len=std::strlen(ch+1);
		std::sort(ch+1,ch+1+len);
		if(ch[1]==ch[len]){
			puts("-1");
			continue;
		}else{
			puts(ch+1);
		}
	}
}

int main(){
	init();
	return 0;
}

CF1093 C
考虑到数列单调不减,则A序列的前半部分也单调不减,那么我们维护一个值表示当前值,然后从\(1\)扫到\(\frac{n}{2}\)即可。该增加的时候就增加。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

int n;
long long a[200005],b[200005];
void init(){
	scanf("%d",&n);
	for(int i=1;i<=(n>>1);++i){
		scanf("%I64d",b+i);
	}
	long long nw=0;
	for(int i=1;i<=(n>>1);++i){
		if(i>1&&b[i]-nw>b[i-1]-a[i-1]){
			nw=b[i]-b[i-1]+a[i-1];
		}
		a[i]=nw,a[n-i+1]=b[i]-nw;
	}
	for(int i=1;i<=n;++i){
		printf("%I64d ",a[i]);
	}
}

int main(){
	init();
	return 0;
}

CF1093 D
考虑每一个连通块各自独立,所以分别计算出值然后乘一起即可。
又,我们发现,本质上题目要求的就是一条线段两端的点的权值的奇偶性不同。
所以我们可以对一个连通块二染色,使得任意两种颜色不相邻。很容易可以证明,要么没有方案,要么方案只有一种。
我们分别考虑用一和三来填充黑色和白色,方案数很显然是\(2^{size_0}+2^{size_1}\)。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm> 
#include<queue>
const long long MOD = 998244353;
struct ee{
	int v;
	int nxt;
}e[600005];
int h[300005],et=0;
inline long long pw(int A,int X){
	long long RT=1,BS=A;
	while(X){
		if(X&1){
			RT*=BS;
			RT%=MOD;
		}
		BS*=BS;
		BS%=MOD;
		X>>=1;
	}
	return RT;
}
inline void add(int u,int v){
	e[++et]=(ee){v,h[u]};
	h[u]=et;
}
bool clr[300005],vis[300005];
std::queue<int> q;
struct data{
	int A;
	int SZ;
}; 
inline data slv(int X){
	int RT=0;
	clr[X]=0,vis[X]=1;
	while(!q.empty()){
		q.pop();
	}
	q.push(X);
	int P,SZ=0;
	while(!q.empty()){
		P=q.front();
		q.pop();
		++SZ;
		if(!clr[P]){
			++RT;
		}
		for(int i=h[P];i;i=e[i].nxt){
			if(vis[e[i].v]){
				if(clr[e[i].v]==clr[P]){
					return (data){-1,-1};
				}
			}else{
				vis[e[i].v]=1;
				clr[e[i].v]=clr[P]^1;
				q.push(e[i].v);
			}
		}
	}
	return (data){RT,SZ};
} 
int n,m;
void init(){
	scanf("%d%d",&n,&m);
	int u,v;
	for(int i=1;i<=m;++i){
		scanf("%d%d",&u,&v);
		add(u,v);
		add(v,u);
	}
	long long ans=1;
	data A;
	for(int i=1;i<=n;++i){
		clr[i]=0;vis[i]=0;
	}	
	for(int i=1;i<=n;++i){
		if(vis[i]){
			continue;
		}else{
			A=slv(i);
			if(A.A==-1){
				puts("0");
				return;
			}
			ans*=(pw(2,A.SZ-A.A)+pw(2,A.A));
			ans%=MOD;
		}
	}
	ans%=MOD;
	printf("%I64d\n",ans);
}
inline void CLEAR(){
	for(int i=1;i<=et;++i){
		e[i].v=e[i].nxt=0;
	}
	for(int i=1;i<=n;++i){
		h[i]=0;
	}
	n=0,m=0,et=0;
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		init();
		CLEAR();
	}
	return 0;
}

AGC029

这一场打得还行,可惜C没有调出来。不过还是暴涨七百多分。摸不透算分机制。

AGC 29 A
给定一个01序列,每一次可以把01变成10,求最大操作次数。
猜结论题(其实证明很显然)。结论是每一个1后面的0的个数之和。

#include<iostream>
#include<cstdio>
#include<cstring>

int n;
char ch[200005];
int sm[200005];
void init(){
	std::cin>>(ch+1);
	n=std::strlen(ch+1);
	for(int i=1;i<=n;++i){
		ch[i]=(ch[i]=='B'?1:0);
	}
	sm[n+1]=0;
	for(int i=n;i>=1;--i){
		sm[i]=sm[i+1]+(ch[i]^1);
	}
	long long ans=0;
	for(int i=1;i<=n;++i){
		if(ch[i]){
			ans+=sm[i+1];
		}
	}
	printf("%lld",ans);
}

int main(){
	init();
	return 0;
}

AGC 29 B
给定一个序列,问从中最多能找出多少个数对使得它们的和是二的次幂。
贪心。考虑从大往小遍历,如果一个大的数能够找到一个比它小的数配成二的次幂,那么不选这个大的数肯定不会更优。
用\(map\)优化一下即可。

#include<iostream>
#include<cstdio>
#include<map>
#include<algorithm>

std::map<int,int> mp;

int n,a[200005];

void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",a+i);
		mp[a[i]]?(++mp[a[i]]):mp[a[i]]=1;
	}
	std::map<int,int>::iterator it=mp.end();
	--it;
	
	int ans=0,nw;
	while(1){
		if(it->second==0){
			goto loop;
		}
		nw=it->first;
		for(int i=30;i>=1;--i){
			while(it->second>=1&&(1<<i)-nw>=0&&mp[(1<<i)-nw]>=1&&(nw!=(1<<(i-1)))){
				--mp[(1<<i)-nw];
				it->second-=1;
				++ans;
			}
			while(it->second>=2&&nw==(1<<(i-1))){
				it->second-=2;
				++ans;
				
			}
		}
		loop:
			if(it==mp.begin()){
				break;
			}
			--it;
	}
	
	printf("%d\n",ans);
} 

int main(){
	init();
	return 0;
}

AGC 29 D
容易知道,每一轮T一定是能走就走。因为如果T不走,那么A就可以通过不走来强迫游戏结束。
并且,如果P经过了一个障碍上方,游戏就结束了。所以A一定会尽可能地让P走到一个障碍上方。
故而,A不往右走,只有两种情况。一,是下方存在一个障碍;二,是右边有障碍挡住。
很显然,如果固定起始点,只有横坐标与纵坐标相同的点才会挡住A。
因此,每一次A被挡住了,就更新起始点,然后向下走即可。

#include<iostream>
#include<cstdio>
#include<algorithm>

struct data{
	int x;int y;
	inline bool operator<(const data &B){
		return x==B.x?y<B.y:x<B.x;
	}
	inline void init(int X,int Y){
		x=X,y=Y;
	}
}a[200005];
int n,h,w;
void init(){
	scanf("%d%d%d",&h,&w,&n);
	int x,y;
	for(int i=1;i<=n;++i){
		scanf("%d%d",&x,&y);
		a[i].init(x,y);
	}
	std::sort(a+1,a+1+n);
	int nw=0;
	for(int i=1;i<=n;++i){
		if(a[i].x-nw==a[i].y){
			++nw;
		}
		if(a[i].x-nw>a[i].y){
			printf("%d\n",a[i].x-1);
			return;
		}
	}
	printf("%d\n",h);
}

int main(){
	init();
	return 0;
}