POI2011

orz hhw posted @ 2017年11月22日 22:45 in 做题记录 with tags 解题报告 POI , 653 阅读

T1 Tree Rotations 写了个暴力归并然后T了,我只能想到Splay啊,可别人代码都这么短。。

还是乖乖地写了下Splay,代码也不长,不过是在搞不懂最短的不到1K是怎么做到的,写Splay这道题就比较直观了,只要暴力把小的合到大的上面然后统计答案就可以了

#include<cstdio>
#include<cstdio>
#include<algorithm>
#define N 222222
using namespace std;
typedef long long LL;
int n,x,top,a[N],b[N];LL ans;
void get(){
	int i,j,k,l,r,mid;LL now=0;
	scanf("%d",&x);
	if(!x){
		l=top+1;get();mid=top;get();r=top;
		for(k=l,j=mid+1,i=l;i<=mid;b[k++]=a[i],i++)
			for(;j<=r&&a[j]<a[i];b[k++]=a[j++])now+=(LL)(mid-i+1);
		for(;j<=r;b[k++]=a[j++]);
		for(k=l;k<=r;k++)a[k]=b[k];
		ans+=min(now,(LL)(mid-l+1)*(LL)(r-mid)-now);
	}else a[++top]=x;
}
int main(){
	scanf("%d",&n);get();
	printf("%lld",ans);
}
#include<cstdio>
#include<algorithm>
#define N 2222222
using namespace std;
typedef long long LL;
int n,x,y,tot,top,fa[N],sz[N],q[N],c[N][2],val[N];LL ans,now;
void ps(int x){sz[x]=sz[c[x][0]]+sz[c[x][1]]+1;}
void R(int x){
	int y=fa[x],k=(c[y][0]==x);
	c[y][!k]=c[x][k];fa[c[x][k]]=y;
	fa[x]=fa[y];c[fa[y]][c[fa[y]][1]==y]=x;
	c[x][k]=y;fa[y]=x;ps(y);
}
void sy(int x,int &rt){for(;y=fa[x];R(x))if(fa[y])R((x==c[y][0])==(y==c[fa[y]][0])?y:x);ps(x);rt=x;}
void Nw(int &x,int la,int key){x=++tot;fa[x]=la;val[x]=key;sz[x]=1;}
void ins(int key,int &rt){
	int x=rt;for(;c[x][key<val[x]];x=c[x][key<val[x]]);
	Nw(c[x][key<val[x]],x,key);sy(c[x][key<val[x]],rt);now+=sz[c[rt][0]];
}
void tr(int x){if(!x)return;q[++top]=val[x];tr(c[x][0]);tr(c[x][1]);}
int get(){
	scanf("%d",&x);
	if(!x){
		int l=get(),r=get();LL sum=(LL)sz[l]*(LL)sz[r];if(sz[l]<sz[r])swap(l,r);now=0;top=0;
		tr(r);sort(q+1,q+top+1);for(int i=1;i<=top;i++)ins(q[i],l);ans+=min(now,sum-now);return l;
	}else{val[++tot]=x;sz[tot]=1;return tot;}
}
int main(){scanf("%d",&n);get();printf("%lld",ans);}

T2 Difference 每次维护出$cnt[i]-cnt[j]-(cnt[i2]-cnt[j2])$,可以维护出$cnt[i]-cnt[j]$的最小值,就可以快速转移了

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,i,j,c,ans,f[27][27],g[27][27];char s[1001000];
int main(){
	scanf("%d%s",&n,s+1);
	for(i=1;i<=n;i++){
		c=s[i]-'a';
		for(j=0;j<26;j++){
			f[c][j]++;f[j][c]--;
			if(!g[j][c])g[j][c]=1;
			if(g[j][c]==2){g[j][c]--;f[j][c]++;}
			if(f[j][c]<=-1){f[j][c]=-1;g[j][c]=2;}
            if(g[j][c])ans=max(ans,f[j][c]);
            if(g[c][j])ans=max(ans,f[c][j]);
		}
	}
	printf("%d",ans);
}

T3 Shift 先把$1~n-2$暴力调整到相应位置,如果符合则直接输出,否则如果是奇数不合法,偶数把$n$不断往前跳得到正确答案,WA了好久,后来发现步数>n要取模,而且模为0还要删去。。

#include<cstdio>
#define N 2222
int n,i,u,x,y,t,tp,pt,a[N*N],b[N*N];
int abs(int x){return x>0?x:-x;}
void add(int x){x*b[tp]>0?b[tp]+=x:b[++tp]=x;}
void c1(){u=(u-1+n)%n;add(1);}
void c2(){
	x=(u+1)%n;y=(u+2)%n;t=a[u];
	a[u]=a[y];a[y]=a[x];a[x]=t;
	add(-1);
}
void c3(){u=(u+1)%n;add(n-1);}
int main(){
	for(scanf("%d",&n);i<n;i++)scanf("%d",&a[i]);
	for(i=2;i<n-1;i++){
		for(;a[u]!=i;c1());
		for(;a[(u-1+n)%n]!=i-1;){
			c1();
			if(a[(u-1+n)%n]!=i-1)c1(),c2();else c2(),c2();
		}
	}
	for(;a[u]!=1;c1());
	if(a[(u+n-1)%n]!=n){
		if(n&1)return puts("NIE DA SIE"),0;
		for(c1();a[(u+1)%n]!=n;)c2(),c2(),c3(),c3();
		for(;a[u]!=1;)c1();
	}
	for(i=1;i<=tp;i++)if(abs(b[i])%n!=0)a[++pt]=abs(b[i])%n,b[pt]=b[i]>0?1:0;
	for(printf("%d\n",pt),i=1;i<=pt;i++)printf("%d",a[i]),printf("%c ",b[i]?'a':'b');
}

T4 Conspiracy 先2-SAT构造一组方案,然后要调整的话肯定最多只能调整一对,可以求出每个调整影响到的人,如果>1则不合法,如果没有影响到人则把答案加上,影响到则把两个人一起改的答案加上,不过要注意一个块只有1个人的时候要特判

#include<cstdio>
#define N 5050
int n,m,i,j,t,x,ans,c0,c1,g[N][N],q[N<<1],a[N],b[N];bool v[N<<1];
int dfs(int x){
	if(v[x>n?x-n:x+n])return 0;
	if(v[x])return 1;v[q[++t]=x]=1;
	if(x>n){for(int i=1;i<=n;i++)if(i!=x-n&&g[x-n][i])if(!dfs(i))return 0;}
	else for(int i=1;i<=n;i++)if(i!=x&&!g[x][i])if(!dfs(i+n))return 0;
	return 1;
}
int main(){
	for(scanf("%d",&n),i=1;i<=n;i++)for(scanf("%d",&m);m--;g[i][x]=1)scanf("%d",&x);
	for(i=1;i<=n;i++)if(!v[i]&&!v[i+n])
		if(t=0,!dfs(i)){
			for(;t;v[q[t--]]=0);
			if(!dfs(i+n))return puts("0"),0;
		}
	for(i=1;i<=n;i++)if(v[i])c0++;else c1++;
	for(i=1;i<=n;i++)if(v[i])for(j=1;j<=n;j++)if(!v[j]&&g[i][j])if(!a[i])a[i]=j;else a[i]=-1;
	for(i=1;i<=n;i++)if(!v[i])for(j=1;j<=n;j++)if(v[j]&&!g[i][j])if(!b[i])b[i]=j;else b[i]=-1;
	for(i=1;i<=n;i++)if(v[i])ans+=!a[i]&&c0>1;else ans+=!b[i]&&c1>1;
	for(i=1;i<=n;i++)if(v[i])for(j=1;j<=n;j++)if(!v[j]&&(!a[i]||a[i]==j)&&(!b[j]||b[j]==i))ans++;
	printf("%d",ans+(c0&&c1));
}

T5 Lightning Conductor 一开始化出了式子$max(a[j]+\sqrt{abs(i-j)})-a[i]$,但感觉无从下手,试了下斜率优化发现不可行,又回去想了一天多,还是没想出来,只好去看题解。这原来是一道不用斜率优化的1D1D单调性优化,和NOI2009的诗人小G差不多。。单调性DP优化几乎都忘光了。。差不多就是对于区间$[l,r]$都用值$p$来更新答案。。

对于这道题$\sqrt{x}-\sqrt{x-1}$单调递减,如果$k<j<i$且对于$i$而言$j$比$k$优,$k$就是无用的。。

维护很多个区间三元组${p,l,r}$,对于每个插入的$i$,他能管得区间一定是$[x,n]$

如果对于$n$,当前$i$比队尾更优,就把队尾弹出,最后的队尾$(p,l,r)$满足在$l$上$p$比$i$优,在$r$上$i$比$p$优,可以二分查找这个分界点$x$

然后将队尾变成$(p,l,x-1)$,然后将$(i,x+1,n)$加入,这样就完成了单调性DP优化,这也差不多是单调性DP的基本步骤。。斜率优化如果想不出不妨想想单调性优化。。

#include<cstdio>
#include<cmath>
#include<algorithm>
#define N 500500
using namespace std;
double f[N],g[N];
int n,i,l,r,mid,a[N];
struct data{int p,l,r;}q[N];
double cal(int j,int i){return a[j]+sqrt(abs(i-j))-a[i];}
void dp(double *f){
	for(int h=1,t=0,i=1;i<=n;i++){
		q[h].l++;if(h<=t&&q[h].l>q[h].r)h++;
		if(h>t||cal(i,n)>cal(q[t].p,n)){
			for(;h<=t&&cal(i,q[t].l)>cal(q[t].p,q[t].l);t--);
			if(h>t)q[++t]=(data){i,i,n};else{
				l=q[t].l;r=q[t].r;
				while(l<r){
					mid=l+r>>1;
					if(cal(q[t].p,mid)>cal(i,mid))l=mid+1;else r=mid;
				}
				q[t].r=l-1;q[++t]=(data){i,l,n};
			}
		}
		f[i]=cal(q[h].p,i);
	}
}
int main(){
	scanf("%d",&n);for(i=1;i<=n;i++)scanf("%d",&a[i]);
	dp(f);reverse(a+1,a+n+1);dp(g);
	for(i=1;i<=n;i++)printf("%d\n",(int)ceil(max(f[i],g[n-i+1])));
}

T6 Lollipop 首先所有前缀和都是可行的,然后对于每个数找到他右边最多有几个2,然后对每个2进行如下判定,如果1位置后面的2数量比i后面的2少,就向右移动$ex[1]$位,否则就向右移$ex[i]$位,但如果超过$n$就是不合法的

#include<cstdio>
#define N 2001000
int n,m,i,sum,x,l[N],r[N],ex[N];char s[N];
int main(){
	scanf("%d%d%s",&n,&m,s+1);
	for(i=n;i;i--)s[i]=='W'?ex[i]=0:ex[i]=ex[i+1]+1;
	for(i=1;i<=n;i++){
		sum+=s[i]=='W'?1:2;
		l[sum]=1;r[sum]=i;
		if(s[i]=='T'){
			if(ex[1]<ex[i])l[sum-1]=ex[1]+2,r[sum-1]=i+ex[1];else
			if(i+ex[i]!=n+1)l[sum-1]=ex[i]+1,r[sum-1]=i+ex[i];
		}
	}
	while(m--){
		scanf("%d",&x);
		if(x>sum||!l[x])puts("NIE");else printf("%d %d\n",l[x],r[x]);
	}
}

T7 Temperature 一开始写个贪心WA了,后来发现贪心有点不对,要改成单调队列,维护单调上升的l[]值来得到答案

#include<cstdio>
#define N 1111111
int n,i,ans=1,h=1,t,la=1,now,l[N],r[N],q[N];char ch;
int main(){
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d%d",&l[i],&r[i]);
		for(;l[q[t]]<=l[i]&&h<=t;t--);
		q[++t]=i;now=la;
		for(;l[q[h]]>r[i];)now=q[h++]+1;
		ans=ans>i-now+1?ans:i-now+1;la=now;
	}
	printf("%d",ans);
}

T8 Strongbox 很神的题,弄出所有gcd去重后判断。。

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
LL m,ans,a[251000];int n,i,tot;
LL gcd(LL a,LL b){return !b?a:gcd(b,a%b);}
void check(LL x){
	for(int i=1;i<=tot;i++)if(a[i]%x==0)return;
	ans=min(ans,x);
}
int main(){
	scanf("%lld%d",&m,&n);ans=m;
	for(i=1;i<=n;i++)scanf("%lld",&a[i]),a[i]=gcd(a[i],m);
	sort(a+1,a+n);for(i=1;i<n;i++)if(a[i]!=a[i+1])a[++tot]=a[i];
	for(i=1;(LL)i*i<=a[n];i++)if(a[n]%i==0){
		check(i);check(a[n]/i);
	}
	printf("%lld",m/ans);
}

T9 Garbage 就是有一些需要改变的边,每次可以改变一个环的状态,求可行解

如果需要改的边的点的度数为奇数则无解,因为每次改变的是一个环

首先如果两个环相交,则多出来的是不必要的,所以每个环一定不相交,可以每次找出一个环然后删掉

于是可以对每个点暴力扩展找环,加一个对走边条件的小优化,时间复杂度就是$O(n+m)$的了

#include<cstdio>
#define M 2001000
int n,m,x,y,p,q,i,t,tot,cnt,scc,fir[M],st[M],pos[M],du[M],a[M],ne[M],la[M];bool is[M],v[M];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;du[x]++;}
int main(){
	for(scanf("%d%d",&n,&m),tot=1;m--;){scanf("%d%d%d%d",&x,&y,&p,&q);if(p^q)ins(x,y),ins(y,x);}
	for(i=1;i<=n;i++)if(du[i]&1)return puts("NIE"),0;
	for(x=1;x<=n;x++)for(st[t=1]=y=x;y;y=q){
		for(is[y]=1,q=0,i=fir[y];i;i=ne[i])if(!v[i]){
			v[i]=v[i^1]=1;fir[y]=ne[i];
			if(is[p=la[i]]){
				for(a[++cnt]=q=p;st[t]!=p;is[st[t--]]=0)a[++cnt]=st[t];
				pos[++scc]=cnt;
			}else q=st[++t]=p;
			break;
		}
		if(!q&&t)q=st[t--];
	}
	for(printf("%d\n",scc),x=1;x<=scc;printf("%d\n",a[pos[x-1]+1]),x++)for(printf("%d ",pos[x]-pos[x-1]),i=pos[x-1]+1;i<=pos[x];i++)printf("%d ",a[i]);
}

T10 Plot 可以二分每个覆盖圆半径的最大值然后进行判断,进行判断的时候当然不能在没有随机的情况下直接暴力判,要先倍增找到一个合适的范围,然后二分查找这个范围中该半径控制的范围,这样时间复杂度是$O(nlog^2n)$?虽然我觉得是$O(nlg^3n)$,而如果不倍增复杂度是$n^2lgn$的。。反正这题有5分钟的时限,去爆爆OJ的感觉挺好的

#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#define eps 1e-9
#define N 100010
using namespace std;
int n,m,i,cnt,ans[N][2];
double l,r,mid,R;
struct P{double x,y;}a[N],b[N],O;
double dis(P x,P y){return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));}
P get(P a,P b,P c){
	double a1=b.x-a.x,b1=b.y-a.y,c1=(a1*a1+b1*b1)/2,a2=c.x-a.x,b2=c.y-a.y,c2=(a2*a2+b2*b2)/2,d=a1*b2-a2*b1;
	return (P){a.x+(c1*b2-c2*b1)/d,a.y+(a1*c2-a2*c1)/d};
}
void cal(int l,int r){
	int i,j,k,n=0;
	for(i=l;i<=r;i++)a[++n]=b[i];
	for(i=2;i<=n;i++)swap(a[1+(rand()%n)],a[i]);
	for(O=a[1],R=0,i=2;i<=n;i++)if(R+eps<dis(O,a[i]))
		for(O=a[i],R=0,j=1;j<i;j++)if(R+eps<dis(O,a[j]))
			for(O=(P){(a[i].x+a[j].x)/2,(a[i].y+a[j].y)/2},R=dis(O,a[i]),k=1;k<j;k++)
				if(R+eps<dis(O,a[k]))O=get(a[i],a[j],a[k]),R=dis(O,a[k]);
}
bool ok(double x){
	int i,j,l,r,mid,t,sum=0;
	for(i=1;i<=n;i=t+1){
		for(j=1;i+(1<<j)-1<=n;j++){
			cal(i,i+(1<<j)-1);
			if(R>x+eps)break;
		}
		t=i,l=i+(1<<(j-1))-1;r=i+(1<<j)-1;if(r>n)r=n;
		while(l<=r){
			cal(i,mid=(l+r)>>1);
			if(R<x+eps)l=(t=mid)+1;else r=mid-1;
		}
		if(++sum>m)return 0;
		ans[++cnt][0]=i;ans[cnt][1]=t;
	}
	return 1;
}
int main(){
	scanf("%d%d",&n,&m);for(i=1;i<=n;i++)scanf("%lf%lf",&b[i].x,&b[i].y);
	cal(1,n);r=R;
	if(m>1)for(;r-l>eps;cnt=0)if(ok(mid=(l+r)/2))r=mid;else l=mid;
	ok(r);printf("%.8lf\n%d\n",r,cnt);
	for(i=1;i<=cnt;i++)cal(ans[i][0],ans[i][1]),printf("%.8lf %.8lf\n",O.x,O.y);
}

T11 Dynamite 先二分爆破的时间,然后贪心,对于每个点,有三种情况,一种是子树中有选择的点还有对上面的贡献,一种是子树中还有未覆盖到的关键点,还有一种是既没有贡献点也没有关键点,贪心进行三种情况的转移,如果能利用贡献尽量利用贡献,不能了再选该点为关键点

#include<cstdio>
#include<algorithm>
#define N 300030
using namespace std;
int n,m,x,y,tot,cnt,ans,l,r,mid,i,a[N],fir[N],ne[N<<1],la[N<<1],f[N],st[N];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void dfs(int x,int fa,int lim){
	int i,y,n1=-1,n2=a[x]-1;
	for(i=fir[x];i;i=ne[i]){
		y=la[i];
		if(y!=fa){
			dfs(y,x,lim);
			if(st[y]==0)n1=max(n1,f[y]-1);else
			if(st[y]==1)n2=max(n2,f[y]+1);
		}
	}
	if(n1<n2)if(n2==lim)cnt++,f[x]=lim,st[x]=0;else f[x]=n2,st[x]=1;
	else if(n1!=-1)f[x]=n1,st[x]=0;else f[x]=0,st[x]=2;
}
bool ok(int x){cnt=0;dfs(1,0,x);if(st[1]==1)cnt++;return cnt<=m;}
int main(){
	scanf("%d%d",&n,&m);for(i=1;i<=n;i++)scanf("%d",&a[i]);
	for(i=1;i<n;i++)scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
	for(l=0,r=n;l<=r;){
		mid=l+r>>1;
		if(ok(mid))ans=mid,r=mid-1;else l=mid+1;
	}
	printf("%d",ans);
}

T12 Inspection 坚挺了15S WA了,本地数据都过的,真是搞不懂。。大概就是求出每个点到其他点的距离和-到最远点的距离,但是最大子树$*2=n$时要特判一下,只能从最大子树中找最大直径。。原来是$n=1$的情况没有忒判

#include<cstdio>
#include<algorithm>
#define N 1001000
using namespace std;
typedef long long LL;LL go[N],ans,now;bool flag;
int n,i,tot,x,y,up[N],ma[N],fa[N],to[N],ne[N<<1],la[N<<1],fir[N],size[N];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void dfs(int x){
	size[x]=1;to[x]=0;
	for(int i=fir[x];i;i=ne[i]){
		int y=la[i];
		if(fa[x]!=y){
			fa[y]=x;
			dfs(y);
			to[x]=max(to[y]+1,to[x]);
			if(size[y]>ma[x])ma[x]=size[y];
			size[x]+=size[y];
			go[x]+=go[y]+(LL)size[y];
		}
	}
	if(n-size[x]>ma[x])ma[x]=n-size[x];
}
void dfs2(int x){
	if(x!=1)go[x]=go[fa[x]]+(LL)n-(LL)size[x]*2;
	int mx1=-1,mx2=-1,now;
	for(int i=fir[x];i;i=ne[i]){
		int y=la[i];
		if(fa[x]!=y){
			if(to[y]>mx1)mx2=mx1,mx1=to[y];
			else if(to[y]>mx2)mx2=to[y];
		}
	}
	for(int i=fir[x];i;i=ne[i]){
		int y=la[i];
		if(fa[x]!=y){
			if(to[y]==mx1)now=mx2;else now=mx1;
			up[y]=max(up[x]+1,max(1,now+2));
			dfs2(y);
		}
	}
}
int main(){
	scanf("%d",&n);if(n==1)return puts("0"),0;
	for(i=1;i<n;i++)scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
	dfs(1);dfs2(1);
	for(x=1;x<=n;x++)if(ma[x]*2<=n){
		flag=0;now=1e18;
		for(i=fir[x];i;i=ne[i]){
			int y=la[i];
			if(fa[x]==y){
				now=min(now,go[x]*2-(LL)up[x]);
				if(size[x]*2==n){
					flag=1;
					printf("%lld\n",go[x]*2-(LL)up[x]);
					break;
				}
			}else{
				now=min(now,go[x]*2-(LL)to[y]-1);
				if(size[y]*2==n){
					flag=1;
					printf("%lld\n",go[x]*2-(LL)to[y]-1);
					break;
				}
			}
		}
		if(!flag)printf("%lld\n",now);
	}else puts("-1");
}

T13 Meteors 很容易想到二分时间,但是如果二分时间后对每个国家暴力判显然是不可行的,于是需要CDQ分治

以时间为单位分治,每次把mid时间内完成收集的国家放到一边,剩下的放到另一边,用链表存储每个国家的信息,就可以在$O(mlgmlgk)$之内出解

#include<cstdio>
#define inf 1e9
#define N 333333
typedef long long LL;
int n,m,i,x,k,tot,la[N],ne[N],fir[N],e[N],id[N],L[N],R[N],a[N],ans[N],q1[N],q2[N];
LL sum,cur[N],now[N],c[N];
void add(int x,int z){for(;x<=m;x+=x&-x)c[x]+=z;}
LL que(int x){for(sum=0;x;x-=x&-x)sum+=c[x];return sum;}
void get(int x,int y,int z){add(x,z);add(y+1,-z);}
void solve(int l,int r,int h,int t){
	if(l==r){for(int i=h;i<=t;i++)ans[id[i]]=l;return;}
	int i,j,w,mid=(l+r)>>1,ln=0,rn=0;
	for(i=l;i<=mid;i++)if(L[i]<=R[i])get(L[i],R[i],a[i]);else get(L[i],m,a[i]),get(1,R[i],a[i]);
	for(i=h;i<=t;i++){
		cur[w=id[i]]=0;
		for(j=fir[w];j;j=ne[j]){
			cur[w]+=que(la[j]);
			if(cur[w]+now[w]>e[w])break;
		}
		if(cur[w]+now[w]>=e[w])q1[++ln]=w;else q2[++rn]=w,now[w]+=cur[w];
	}
	for(i=l;i<=mid;i++)if(L[i]<=R[i])get(L[i],R[i],-a[i]);else get(L[i],m,-a[i]),get(1,R[i],-a[i]);
	for(i=1;i<=ln;i++)id[h+i-1]=q1[i];
	for(i=1;i<=rn;i++)id[h+i+ln-1]=q2[i];
	solve(l,mid,h,h+ln-1);solve(mid+1,r,h+ln,t);
}
int main(){
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)scanf("%d",&x),la[++tot]=i,ne[tot]=fir[x],fir[x]=tot;
	for(i=1;i<=n;i++)scanf("%d",&e[i]),id[i]=i;
	scanf("%d",&k);
	for(i=1;i<=k;i++)scanf("%d%d%d",&L[i],&R[i],&a[i]);
	k++;L[i]=1;R[i]=m;a[i]=inf;
	solve(1,k,1,n);
	for(i=1;i<=n;i++)ans[i]==k?puts("NIE"):printf("%d\n",ans[i]);
}

T14 黄主力做了%%%

T15 Sticks 写了个贪心2100MS被鏼死,把贪心改一下,只要从大到小选就A啦哈哈,虽然跑得超慢,但主要原因是写了个set+堆,想不通为什么这道题没有1K以内的。。

#include<cstdio>
#include<set>
#include<algorithm>
using namespace std;
set<int>st[52];
int n,i,x,p,rt,sz,a,b,c,val[52],ch[52][2];
int merge(int x,int y){
	if(!x||!y)return x+y;
	if(val[x]<val[y])swap(x,y);
	ch[x][1]=merge(ch[x][1],y);
	swap(ch[x][0],ch[x][1]);
	return x;
}
int main(){
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d",&x);
		while(x--){
			scanf("%d",&p);
			st[i].insert(p);
		}
		val[i]=*--st[i].end();
		rt=merge(rt,i);sz++;
	}
	while(sz>=3){
		a=rt;rt=merge(ch[rt][0],ch[rt][1]);ch[a][0]=ch[a][1]=0;
		b=rt;rt=merge(ch[rt][0],ch[rt][1]);ch[b][0]=ch[b][1]=0;
		c=rt;rt=merge(ch[rt][0],ch[rt][1]);ch[c][0]=ch[c][1]=0;
		if(val[b]+val[c]>val[a])return printf("%d %d %d %d %d %d",a,val[a],b,val[b],c,val[c]),0;
		rt=merge(rt,c);rt=merge(rt,b);
		st[a].erase(val[a]);
		if(st[a].size())val[a]=*--st[a].end(),rt=merge(rt,a);else sz--;
	}
	puts("NIE");
}

T16 Party 乱写个按度数排序贪心选点的贪心,竟然1A了哈哈。。看了下正解,应该是对不合法点对进行去除就可以了

#include<cstdio>
#include<algorithm>
#define N 3030
#define M 9000200
using namespace std;
int n,m,i,j,x,y,tot,h,fir[N],du[N],a[N],q[N],v[N],ne[M],la[M];
bool flag;bool cmp(int x,int y){return du[x]>du[y];}
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;du[x]++;}
int main(){
	scanf("%d%d",&n,&m);for(i=1;i<=n;i++)a[i]=i;
	for(i=1;i<=m;i++)scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
	sort(a+1,a+n+1,cmp);q[1]=a[1];h=1;
	for(i=2;i<=n;i++){
		if(h>=(n/3))break;
		for(j=fir[a[i]];j;j=ne[j])v[la[j]]=i;
		flag=1;
		for(j=1;j<=h;j++)if(v[q[j]]!=i){flag=0;break;}
		if(flag)q[++h]=a[i];
	}
	for(i=1;i<=h;i++)printf("%d ",a[i]);
}

T17 Programming Contest 写了个费用流动态加边,但正好T了。。本地的数据都能过。。难道歪果仁都会ZKW费用流吗。。难道我vector作死?

#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#define inf 1e9
#define N 222222
#define M 2222222
using namespace std;
int n,m,i,he,ta,s,t,R,T,k,x,y,sz,ns,ans,flow,sum,tot,p,to[N],o[510],fir[N],dis[N],pre[N],q[M],la[M],ne[M],cos[M],va[M];
bool v[N];vector<int>a[510];vector<int>::iterator it;char ch;
void read(int &x){
	for(ch=getchar();ch<'0'||ch>'9';ch=getchar());
	for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';
}
void ins(int x,int y,int fl,int co){
	la[tot]=y;ne[tot]=fir[x];cos[tot]=co;va[tot]=fl;fir[x]=tot++;
	la[tot]=x;ne[tot]=fir[y];cos[tot]=-co;va[tot]=0;fir[y]=tot++;
}
bool spfa(){
	memset(v,0,sizeof(v));
	for(i=1;i<=ns;i++)dis[i]=inf;
	he=0;ta=1;dis[s]=0;v[s]=1;q[1]=s;
	while(he!=ta)
		for(i=fir[x=q[he=he%ns+1]],v[x]=0;i;i=ne[i])
			 if(dis[x]+cos[i]<dis[y=la[i]]&&va[i]){
				dis[y]=dis[x]+cos[pre[y]=i];
				if(!v[y])v[q[ta=ta%ns+1]=y]=1;
			}
	if(dis[t]==inf)return 0;return 1;
}
void end(){
	sum=inf;
	for(i=t;i!=s;i=la[pre[i]^1])if(va[pre[i]]<sum)sum=va[pre[i]];
	for(i=t;i!=s;i=la[pre[i]^1]){
		va[p=pre[i]]-=sum;
		va[p^1]+=sum;
		ans+=sum*cos[p];
	}
	p=to[la[pre[t]^1]];o[p]++;to[++ns]=p;
	if(o[p]<=sz){
		ins(ns,t,1,o[p]);
		for(it=a[p].begin();it!=a[p].end();it++)ins(*it,ns,1,0);
	}
	flow+=sum;
}
int main(){
	read(n);read(m);read(R);read(T);read(k);sz=T/R;s=m+1;ns=t=s+1;tot=2;
	for(i=1;i<=m;i++)ins(s,i,1,0);
	for(i=1;i<=n;i++)to[++ns]=i,o[i]=1,ins(ns,t,1,1);
	for(i=1;i<=k;i++)read(x),read(y),a[x].push_back(y),ins(y,x+m+2,1,0);
	for(;spfa();end());
	printf("%d %d",flow,ans*R);
}