Petrozavodsk Summer-2017. Warsaw U Contest

时间：2021-10-13 13:31:26

A. Connectivity

设$f[i][j]$为第$i$张图中$j$点所在连通块的编号，加边时可以通过启发式合并在$O(dn\log n)$的时间内维护出来。

对于每个点，设$h[i]$为$f[j][i]$的hash值，若两个点hash值相等，则它们在$d$张图中均连通。

#include<cstdio>

typedef unsigned long long ll;

const int D=200,N=5002,M=262143;

int d,n,m,i,j,x,y,z,ans;

int f[D][N],s[D][N],g[D][N],v[D*N*2],nxt[D*N*2],ed;

ll po[D],h[N];

struct E{ll v;int w,nxt;}e[N];

int G[M+1],res[N],cur;

inline void add(int z,int x,int y){v[++ed]=y;nxt[ed]=g[z][x];g[z][x]=ed;}

inline void ins(ll v){

	int u=v&M,i=G[u];

	for(;i;i=e[i].nxt)if(e[i].v==v){ans+=e[i].w*2+1;e[i].w++;return;}

	ans++,e[i=res[cur--]].v=v,e[i].w=1,e[i].nxt=G[u];G[u]=i;

}

inline void del(ll v){

	int u=v&M,i=G[u],j=i;

	if(e[i].v==v){

		ans-=e[i].w*2-1;

		if(!(--e[i].w))G[u]=e[res[++cur]=i].nxt;

		return;

	}

	for(i=e[i].nxt;i;j=i,i=e[i].nxt)if(e[i].v==v){

		ans-=e[i].w*2-1;

		if(!(--e[i].w))e[j].nxt=e[res[++cur]=i].nxt;

		return;

	}

}

void dfs(int z,int x,int y,int t){

	del(h[x]);

	h[x]-=po[z]*f[z][x];

	f[z][x]=t;

	ins(h[x]+=po[z]*t);

	for(int i=g[z][x];i;i=nxt[i])if(v[i]!=y)dfs(z,v[i],x,t);

}

inline void merge(int z,int x,int y){

	if(f[z][x]==f[z][y])return;

	if(s[z][f[z][x]]>s[z][f[z][y]]){int t=x;x=y;y=t;}

	s[z][f[z][y]]+=s[z][f[z][x]];

	add(z,x,y);

	add(z,y,x);

	dfs(z,x,y,f[z][y]);

}

int main(){

	scanf("%d%d%d",&d,&n,&m);

	for(po[0]=i=1;i<d;i++)po[i]=po[i-1]*10007;

	for(i=1;i<=n;i++)res[++cur]=i;

	for(i=1;i<=n;ins(h[i++]))for(j=0;j<d;j++)f[j][i]=i,s[j][i]=1,h[i]+=po[j]*i;

	while(m--)scanf("%d%d%d",&x,&y,&z),merge(--z,x,y),printf("%d\n",ans);

}

　　

B. Hotter-colder

留坑。

C. Painting

将每种颜色用最左和最右位置$[l,r]$表示，对于连续的区间，需要决定顺序。

设$f[l][r]$表示考虑第$l$到第$r$个区间的最大操作代价，通过观察可以发现最优决策中第一步一定操作$l$或者$r$。

时间复杂度$O(n+m^2)$。

#include<cstdio>

#include<algorithm>

using namespace std;

typedef long long ll;

const int N=100010,M=5005;

int n,m,i,j,cnt,x,y,l[M],r[M],a[N],pos[N];ll s[M],f[M][M],ans;

ll fast(){

	int i,j;

	for(i=1;i<=cnt;i++)s[i]+=s[i-1];

	for(i=cnt;i;i--)for(j=i;j<=cnt;j++)

		f[i][j]=max(f[i][j-1],f[i+1][j])+s[j]-s[i-1];

	return f[1][cnt];

}

int main(){

	scanf("%d%d",&n,&m);

	for(i=1;i<=n;i++)scanf("%d",&a[i]);

	for(i=1;i<=n;i++)r[a[i]]=i;

	for(i=n;i;i--)l[a[i]]=i;

	for(i=1;i<=m;i++)pos[l[i]]=i;

	for(i=1;i<=n;i++)if(pos[i]){

		cnt=0;

		x=i;

		while(pos[x]){

			y=pos[x];

			pos[x]=0;

			s[++cnt]=r[y]-l[y]+1;

			x=r[y]+1;

		}

		ans+=fast();

	}

	printf("%lld",ans);

}

　　

D. Ones

倍增构造即可。

#include<cstdio>

#include<iostream>

#include<string>

using namespace std;

int T,n;

string gao(int n){

	if(n==1)return "1";

	if(n==2)return "1+1";

	if(n==3)return "1+1+1";

	int t=n/2;

	string o=gao(t);

	string oo="("+o+")*(1+1)";

	if(t+t==n)return oo;

	return "("+oo+")+1";

}

int main(){

	cin>>T;

	while(T--){

		cin>>n;

		cout<<gao(n)<<endl;

	}

}

　　

E. Seats

留坑。

F. Ants

留坑。

G. Permutation

设$f[i][j][k]$表示考虑前$i$个数，最后一个与$i$不在一起的数为$j$，$i$位于第$k$个数列是否可行。

转移可以用set实现，时间复杂度$O(n\log n)$。

#include<cstdio>

#include<set>

using namespace std;

const int N=100010;

int Case,n,i,o,x,y,a[N],b[N],c[N],g[N][2],ca,cb,qa[N],qb[N];

set<int>f0,f1;

void solve(){

	scanf("%d",&n);

	for(i=1;i<=n;i++)scanf("%d",&a[i]),b[a[i]]=i;

	f0.clear();

	f1.clear();

	f0.insert(N);

	f1.insert(0);

	for(i=1;i<n;i++){

		bool A=0,B=0;

		set<int>::iterator it=f1.lower_bound(a[i+1]);

		if(it!=f1.begin())it--;

		if(it!=f1.end())if((*it)<a[i+1])A=1;

		it=f0.lower_bound(a[i+1]);

		if(it!=f0.end())if((*it)>a[i+1])B=1;

		if(a[i+1]>a[i])f1.clear();else f0.clear();

		if(A)f0.insert(a[i]);

		if(B)f1.insert(a[i]);

		g[i+1][0]=g[i+1][1]=0;

		if(f0.size())g[i+1][0]=*f0.rbegin();

		if(f1.size())g[i+1][1]=*f1.begin();

		//printf("%d:\n",i+1);

		//for(it=f0.begin();it!=f0.end();it++)printf("%d ",*it);puts("");

		//for(it=f1.begin();it!=f1.end();it++)printf("%d ",*it);puts("");

	}

	//for(i=2;i<=n;i++)printf("%d %d %d\n",i,g[i][0],g[i][1]);

	if(!f0.size()&&!f1.size()){

		puts("NO");

		return;

	}

	x=n;

	if(f0.size())o=0;

	if(f1.size())o=1;

	while(x){

		y=g[x][o];

		if(y>=1&&y<=n)y=b[y];else y=0;

		for(i=y+1;i<=x;i++)c[i]=o^1;

		x=y,o^=1;

	}

	ca=cb=0;

	for(i=1;i<=n;i++)if(c[i])qa[++ca]=a[i];else qb[++cb]=a[i];

	puts("YES");

	printf("%d",ca);

	for(i=1;i<=ca;i++)printf(" %d",qa[i]);puts("");

	printf("%d",cb);

	for(i=1;i<=cb;i++)printf(" %d",qb[i]);puts("");

}

int main(){

	scanf("%d",&Case);

	while(Case--){

		solve();

	}

}

　　

H. Primes

莫比乌斯反演，分段计算。

时间复杂度$O(n+q\sqrt{n})$。

#include<cstdio>

#include<algorithm>

using namespace std;

typedef long long ll;

const int N=1000010;

int i,j,v[N],mu[N],f[N],tot,p[N],g[N];

ll sg[N],sf[N],ans;

ll w[N];

int T,n,m;

inline ll cal(int n,int m){

	if(!n||!m)return 0;

	if(n==m)return w[n];

	ll ret=0;

	for(int i=1,j;i<=n&&i<=m;i=j+1){

		j=min(n/(n/i),m/(m/i));

		ret+=(sg[j]-sg[i-1])*(n/i)*(m/i);

	}

	return ret;

}

int main(){

	for(mu[1]=1,i=2;i<N;i++){

		if(!v[i]){

			p[tot++]=i;

			mu[i]=-1;

			for(j=i;j<N;j+=i)f[j]++;

		}

		for(j=0;j<tot&&i*p[j]<N;j++){

			v[i*p[j]]=1;

			if(i%p[j])mu[i*p[j]]=-mu[i];else break;

		}

	}

	for(i=1;i<N;i++)for(j=i;j<N;j+=i)g[j]+=f[i]*mu[j/i];

	for(i=1;i<N;i++)sf[i]=sf[i-1]+f[i],sg[i]=sg[i-1]+g[i];

	for(i=1;i<N;i++)for(j=i;j<N;j+=i)w[j]+=1LL*(j/i)*g[i];

	for(i=1;i<N;i++)w[i]=w[i-1]+w[i]*2-f[i];

	scanf("%d",&T);

	while(T--){

		scanf("%d%d",&n,&m);

		ans=cal(m,m)-cal(n-1,m)*2+cal(n-1,n-1);

		ans-=sf[m]-sf[n-1];

		ans/=2;

		printf("%lld\n",ans);

		fflush(stdout);

	}

}

　　

I. Vertex covers

留坑。

J. Scheduling

将时间离散化后网络流。

#include<cstdio>

#include<algorithm>

using namespace std;

const int N=510,inf=~0U>>2;

struct E{int t,f;E*nxt,*pair;}*g[N],*d[N],pool[N*N*2],*cur=pool;

int n,m,i,j,cnt,a[110][3],b[N],ans,S,T,h[N],gap[N];

inline void add(int s,int t,int f){

	E*p=cur++;p->t=t;p->f=f;p->nxt=g[s];g[s]=p;

	p=cur++;p->t=s;p->f=0;p->nxt=g[t];g[t]=p;

	g[s]->pair=g[t];g[t]->pair=g[s];

}

int sap(int v,int flow){

	if(v==T)return flow;

	int rec=0;

	for(E*p=d[v];p;p=p->nxt)if(h[v]==h[p->t]+1&&p->f){

		int ret=sap(p->t,min(flow-rec,p->f));

		p->f-=ret;p->pair->f+=ret;d[v]=p;

		if((rec+=ret)==flow)return flow;

	}

	if(!(--gap[h[v]]))h[S]=T;

	gap[++h[v]]++;d[v]=g[v];

	return rec;

}

int main(){

	scanf("%d%d",&n,&m);

	for(i=1;i<=n;i++){

		scanf("%d%d",&a[i][1],&a[i][2]);

		scanf("%d",&a[i][0]);

		a[i][2]--;

		b[++cnt]=a[i][1];

		b[++cnt]=a[i][1]+1;

		b[++cnt]=a[i][2];

		b[++cnt]=a[i][2]+1;

	}

	sort(b+1,b+cnt+1);

	for(j=0,i=1;i<=cnt;i++)if(i==1||b[i]!=b[i-1])b[++j]=b[i];

	cnt=j;

	b[cnt+1]=b[cnt]+1;

	S=n+cnt+1;

	T=S+1;

	for(i=1;i<=cnt;i++)add(n+i,T,(b[i+1]-b[i])*m);

	for(ans=0,i=1;i<=n;i++){

		add(S,i,a[i][0]);ans+=a[i][0];

		for(j=1;j<=cnt;j++)if(a[i][1]<=b[j]&&b[j+1]-1<=a[i][2])add(i,n+j,b[j+1]-b[j]);

	}

	for(gap[0]=T,i=1;i<=T;i++)d[i]=g[i];

	while(h[S]<T)ans-=sap(S,inf);

	puts(ans?"NO":"YES");

}

　　

K. Shuffle

不难发现操作两次等于没操作，故将操作次数模$2$即可。

#include<cstdio>

#include<algorithm>

using namespace std;

int n,T,i,a[2222222];

//[l,r)

void solve(int l,int r){

	if(r-l<=1)return;

	if(r-l==2){

		swap(a[l],a[l+1]);

		return;

	}

	int mid=(l+r)>>1;

	solve(l,mid);

	solve(mid,r);

	for(int i=l,j=mid;i<mid;i++,j++)swap(a[i],a[j]);

}

int main(){

	scanf("%d%d",&n,&T);

	T%=2;

	for(i=0;i<1<<n;i++)scanf("%d",&a[i]);

	while(T--){

		solve(0,1<<n);

	}

	for(i=0;i<1<<n;i++)printf("%d ",a[i]);

}

　　

相关文章