CCPC-Final2016

orz hhw posted @ 2017年11月30日 00:51 in 做题记录 with tags 解题报告 acm , 273 阅读

A - The Third Cup is Free

排序,每次取三个加到答案中即可

#include<bits/stdc++.h>
using namespace std;
int T,n,i,V,ca,a[111111];
int main(){
for(scanf("%d",&T);T--;){
scanf("%d",&n);V=0;
for(i=1;i<=n;i++)scanf("%d",&a[i]),V+=a[i];
sort(a+1,a+n+1);
for(i=n-2;i>=1;i-=3)V-=a[i];
printf("Case #%d: %d\n",++ca,V);
}
}

B - Wash

有$N$台洗衣机和$M$台吹风机,第$i$台洗衣机需要$a_i$的时间洗一件衣服,第$i$台吹风机需要$b_i$的时间吹一件衣服,现在要洗+吹$L$件衣服,问什么时候可以全部完成。$N,M\leq100000,L\leq1000000$。

如果只有洗衣机或者只有吹风机,那么用堆可以轻松维护出第$i$件衣服完成的时间$T_i$。我们令洗衣机完成第$i$件衣服的时间为$A_i$,吹风机完成第$i$件衣服的时间为$B_i$,那么$max\{A_i+B_{n-i+1}\}$即为所求。时间复杂度$O(L(lgN+lgM))$。

#include<bits/stdc++.h>
#define N 111111
#define LL long long
#define fr(i,n) for(int i=1;i<=n;i++)
using namespace std;
int T,L,n,m,x,ca,a[N],b[N];LL z,an,V[N*10];
struct P{int x;LL z;bool operator<(P a)const{return a.z<z;}};
priority_queue<P>Q;
int main(){
	for(scanf("%d",&T);T--;){
		an=0;
	    scanf("%d%d%d",&L,&n,&m);
	    fr(i,n)scanf("%d",&a[i]),Q.push(P{i,a[i]});
	    fr(i,L){
	        x=Q.top().x;z=Q.top().z;
	        V[i]=z;Q.pop();
	        Q.push(P{x,z+a[x]});
	    }
	    for(;!Q.empty();Q.pop());
	    fr(i,m)scanf("%d",&b[i]),Q.push(P{i,b[i]});
	    fr(i,L){
	        x=Q.top().x;z=Q.top().z;
	        an=max(an,z+V[L-i+1]);Q.pop();
	        Q.push(P{x,z+b[x]});
	    }
	    for(;!Q.empty();Q.pop());
	    printf("Case #%d: %lld\n",++ca,an);
	}
}

C - Mr.Panda and Survey

给$N$个人做调查,共有$M$个问题,每个人对每个问题都有回答YES或NO,一个问题是有意义的当且仅当有人回答YES有人回答NO。现在对问题的所有$2^M$个子集$\{S\},求$AN_{\{S\}}$的异或和。$AN_{\{S\}}$为对于每个人参与/不参与调查的$2^N$种情况里,所有问题都有意义的方案数。$N\leq100000,M\leq15$。不会做

D - Game Leader

汤姆有$N$个朋友,他们的影响力顺次排列,汤姆的影响力在他的朋友中排名为$R$。朋友关系是双向的,对于每个人,他的所有朋友中影响力最大的人$i$将获得一个星星,现在有若干对已知的朋友关系,并知道汤姆每个朋友的星星。求至少有多少个汤姆的陌生人,对其影响力最大的人是汤姆的朋友。$N\leq100000,R\leq N$。

贪心,先求出对第$i$个人影响力最大的人的标号至少是多少,令这个值为$f_i$,那么可以求出前$i$个人中最多有多少个星星来源于汤姆的朋友,剩下的人只能是陌生人,取一个最大的就好了。

#include<bits/stdc++.h>
#define N 101010
#define CL(a) memset(a,0,sizeof a)
using namespace std;
int T,n,m,k,i,x,y,ca,rk,a[N],f[N],cnt[N],c[N];long long an;
int main(){
	for(scanf("%d",&T);T--;){
		CL(cnt);an=0;
		scanf("%d%d%d",&n,&m,&rk);
		for(i=1;i<=n;i++)scanf("%d",&a[i]),f[i]=min(i,rk);
		for(f[rk]=1;m--;)scanf("%d%d",&x,&y),f[x]=min(f[x],y),f[y]=min(f[y],x);
		for(i=1;i<=n;i++)cnt[f[i]]++;
		for(i=1;i<=n;i++)an=max(an+a[i]-cnt[i],0ll);
		printf("Case #%d: %lld\n",++ca,an);
	}
}

E - Problem Buyer

有$N$道题目,他们的难度系数为$[A_i,B_i]$,现在考卷要出$M$道题目,第$i$道试题的难度是$C_i$,一道题目$i$合法当且仅当$A_i\leq c\leq B_i$。现在找到一个最小的$K$,使得在$N$道题目中随意选$K$道都可以组出满足条件的试卷。$N,M\leq100000$。

将$N$道题目按$A_i$排序,考卷难度$C_i$也升序排列,如果$A_i\leq C_i$就将$B_i$插入到set中,每次将set中不超过当前难度$C_i$的值弹出,并选出一个set中最小的元素来作为对应的题目。在这个过程中,只要维护$max\{n-size(set)+1\}$的值即可,因为在set中的元素至少取一个,所以必须取这么多个才能保证合法。

#include<bits/stdc++.h>
#define N 101010
using namespace std;
multiset<int>S;
int T,n,m,i,j,ca,an,ff,a[N];
struct P{int x,y;}p[N];
bool cmp(P a,P b){return a.x<b.x;}
int main(){
	for(scanf("%d",&T);T--;){
		S.clear();
		scanf("%d%d",&n,&m);
		for(i=1;i<=n;i++)scanf("%d%d",&p[i].x,&p[i].y);
		sort(p+1,p+n+1,cmp);
		for(i=1;i<=m;i++)scanf("%d",&a[i]);
		sort(a+1,a+m+1);ff=0;an=0;
		for(i=j=1;i<=m;i++){
			for(;p[j].x<=a[i]&&j<=n;j++)S.insert(p[j].y);
			for(;S.size()&&*S.begin()<a[i];)S.erase(S.begin());
			if(!S.size()){ff=1;break;}
			an=max(an,n-(int)S.size()+1);
			S.erase(S.begin());
		}
		printf("Case #%d: ",++ca);
		if(ff)puts("IMPOSSIBLE!");else printf("%d\n",an);
	}
}

F - Periodical Cicadas

有两个$N*M$的矩阵$a_{i,j}$和$m_{i,j}$,$0\leq a_{i,j}<m_{i,j}\leq40$。现在有$Q$次询问,每次询问$[X1,X2][Y1,Y2]$中元素进行中国剩余定理后的结果。$N,M\leq200,Q\leq500000$。

先预处理$aa_{i,j,k}$和$mm_{i,j,k}$表示第$i~j$行,第$k$列合并后的答案,然后对于每次询问只要合并列即可,合并的过程中答案会爆long long,慢速乘和O(1)快速乘都会超时,要用int128。时间复杂度$O((N^2+Q)MlgW)$。正规点的做法应该是用二维RMQ维护,时间复杂度$O((NMlgNlgM+Q)lgW)$,不过很麻烦。

#include<bits/stdc++.h>
#define fr(i,n) for(int i=1;i<=n;i++)
#define LL long long
#define N 202
#define __ __attribute__ ((optimize("-O3")))
#define _ __ __inline __attribute__ ((__gnu_inline__,__always_inline__,__artificial__))
using namespace std;
int T,n,m,Q,ca,X1,Y1,X2,Y2,x;
char ch;
LL AA,MM,AAA,MMM,_a[N][N][N],_m[N][N][N];
__ LL mul(LL a,LL b,LL p){
	LL t=(a*b-(LL)((long double)a/p*b+1e-3)*p)%p;
	return t<0?t+p:t;
}
__ LL exgcd(LL a,LL b,LL&x,LL&y,LL&d){
	if(!b)x=1,y=0,d=a;else exgcd(b,a%b,y,x,d),y-=a/b*x;
}
__ void merge(LL a1,LL m1,LL a2,LL m2,LL&A,LL&M){
	if(a1==-1||m1==-1){A=-1;return;}
	LL c=a2-a1,x,y,d;
	exgcd(m1,m2,x,y,d);
	if(c%d){A=-1;return;}
	c/=d;M=m1/d*m2;
	A=((__int128)m1*x*c%M+M+a1)%M;
}
__ void rd(int &x){
    for(ch=getchar();ch<'0'||ch>'9';ch=getchar());
    for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';
}
__ int main(){
	for(rd(T);T--;){
		rd(n);rd(m);
		fr(i,n)fr(j,m)rd(x),_a[i][i][j]=x;
		fr(i,n)fr(j,m)rd(x),_m[i][i][j]=x;
		fr(i,n)fr(j,m){
			for(int k=i+1;k<=n;k++)
				merge(_a[i][k-1][j],_m[i][k-1][j],_a[k][k][j],_m[k][k][j],_a[i][k][j],_m[i][k][j]);
		}
		printf("Case #%d:\n",++ca);
		for(rd(Q);Q--;){
			rd(X1);rd(Y1);rd(X2);rd(Y2);
			AA=0;MM=1;
			for(int i=Y1;i<=Y2&&AA!=-1;i++){
				merge(_a[X1][X2][i],_m[X1][X2][i],AA,MM,AAA,MMM);
				AA=AAA;MM=MMM;
			}
			printf("%lld\n",AA);
		}
	}
}

G - Pandaland

给定一张$m$条边的平面图,找到平面图上最小环。$m\leq4000$。

枚举每条边,对剩下的边跑SPFA即可。

#include<bits/stdc++.h>
#define N 4444
using namespace std;
int T,n,m,i,j,x,y,z,ca,an,tot,d[N],la[N*2],ne[N*2],va[N*2],fir[N],q[N],X[N],Y[N],Z[N];
bool v[N];
map<pair<int,int>,int>mp;
int rd(){
	int x,y;
	scanf("%d%d",&x,&y);
	if(!mp[make_pair(x,y)])mp[make_pair(x,y)]=++n;
	return mp[make_pair(x,y)];
}
void ins(int x,int y,int z){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;va[tot]=z;}
int spfa(int S,int T){
	int h=0,t=1,i,x,y;
	for(d[q[t]=S]=0;h^t;){
		x=q[h=h%n+1];
		if(d[x]>an)continue;
		for(i=fir[x],v[x]=0;i;i=ne[i])
			if(d[x]+va[i]<d[y=la[i]])if(d[y]=d[x]+va[i],!v[y])v[q[t=t%n+1]=y]=1;
	}
	return d[T];
}
int main(){
	for(scanf("%d",&T);T--;){
		mp.clear();n=0;an=1e9;
		scanf("%d",&m);
		for(i=1;i<=m;i++){
			X[i]=rd();Y[i]=rd();
			scanf("%d",&Z[i]);
		}
		for(i=1;i<=m;i++){
			tot=0;
			for(j=1;j<=n;j++)fir[j]=0,d[j]=1e9,v[j]=0;
			for(j=1;j<=m;j++)if(i!=j)ins(X[j],Y[j],Z[j]),ins(Y[j],X[j],Z[j]);	
			an=min(an,spfa(X[i],Y[i])+Z[i]);
		}
		printf("Case #%d: %d\n",++ca,an==1e9?0:an);
	}
}

H - Engineer Assignment

有$N$个项目,每个项目需要$C_i$个方向的人员各至少一个。有$M$个员工,每个员工有$D_i$个研究方向。现在每个员工最多在一个项目里工作,问最多完成几个项目。$N,M\leq10,C_i\leq 3,D_i\leq 2$。

先预处理出第$i$个项目由员工集合$\{S\}$是否能完成,然后进行DP,用$f_{i,S}$表示前$i$个项目,使用员工状态是$S$时,最多完成的项目。枚举子集转移,时间复杂度$O(3^MN)$。

#include<bits/stdc++.h>
#define N 111
#define inf 1e9
#define CL(a) memset(a,0,sizeof a)
using namespace std;
int Te,ca,n,m,i,j,k,w,ff,an,c[N],d[N],a[N][4],b[N][4],num[N],f[1111];
bool ok[12][1111];
int main(){
	for(scanf("%d",&Te);Te--;){
		scanf("%d%d",&n,&m);
		for(i=1;i<=n;i++){
			scanf("%d",&c[i]);
			for(j=1;j<=c[i];j++)scanf("%d",&a[i][j]);
		}
		for(i=1;i<=m;i++){
			scanf("%d",&d[i]);
			for(j=1;j<=d[i];j++)scanf("%d",&b[i][j]);
		}
		for(i=0;i<1<<m;i++){
			for(j=1;j<=100;j++)num[j]=0;
			for(j=1;j<=m;j++)if(i>>(j-1)&1)
				for(k=1;k<=d[j];k++)num[b[j][k]]++;
			for(j=1;j<=n;j++){
				ff=0;
				for(k=1;k<=c[j];k++)
					if(!num[a[j][k]])ff=1;
				if(!ff)ok[j][i]=1;else ok[j][i]=0;
			}
		}
		for(i=0;i<1<<m;i++)f[i]=0;
		for(i=1;i<=n;i++){
			for(j=(1<<m)-1;j;j--)
				for(k=j;k;k=(k-1)&j)
					if(ok[i][k])f[j]=max(f[j],f[j-k]+1);
		}
		printf("Case #%d: %d\n",++ca,f[(1<<m)-1]);
	}
}

I - Mr.Panda and Crystal

有$N$件物品,每件物品需要$a_i$的法力值创造,有$b_i$的价值。物品之间可以进行转化,可以将若干件物品转化为一件物品,转化关系有$K$条。你有$M$的法力值,问最多能创造多少价值的物品。$N,K\leq200,M\leq10000$。

先通过最短路求出创造第$i$件物品需要的最小法力值$V_i$,可以用Dijkstra开个Vector拓扑实现,然后跑一遍背包就好了。时间复杂度$O(N^2lgN+NM)$。

#include<bits/stdc++.h>
#define N 222
using namespace std;
int T,m,n,k,i,j,lx,x,y,xx,yy,ca,c[N],d[N],V[N],to[N],sz[N],f[11111];
bool v[N];
struct P{int x,z;bool operator<(P a)const{return a.z<z;}};
priority_queue<P>Q;vector<P>G[N];
int main(){
	for(scanf("%d",&T);T--;){
		scanf("%d%d%d",&m,&n,&k);
		for(i=1;i<=n;i++)v[i]=0,G[i].clear();
		for(i=1;i<=n;i++){
			scanf("%d",&lx);
			if(lx==0)d[i]=m+1;else scanf("%d",&d[i]),Q.push(P{i,d[i]});
			scanf("%d",&c[i]);
		}
		for(i=1;i<=k;i++){
			scanf("%d%d",&to[i],&sz[i]);V[i]=0;
			for(j=1;j<=sz[i];j++){
				scanf("%d%d",&x,&y);
				G[x].push_back(P{y,i});
			}
		}
		for(;!Q.empty();){
			x=Q.top().x;Q.pop();
			if(!v[x])for(v[x]=1,i=0;i<G[x].size();i++){
				xx=G[x][i].x;yy=G[x][i].z;
				V[yy]+=xx*d[x];if(V[yy]>m)V[yy]=m+1;
				if(!--sz[yy])if(V[yy]<d[to[yy]])d[to[yy]]=V[yy],Q.push(P{to[yy],V[yy]});
			}
		}
		for(i=0;i<=m;i++)f[i]=0;
		for(i=1;i<=n;i++)
			for(j=d[i];j<=m;j++)
				f[j]=max(f[j],f[j-d[i]]+c[i]);
		printf("Case #%d: %d\n",++ca,f[m]);
	}
}

J - Worried School

暴力枚举判断

#include<bits/stdc++.h>
using namespace std;
string s;
int T,n,i,j,id,an,ca,X,Y,YY,q[7][22];
map<string,int>mp;
bool vs[122];
int main(){
	for(scanf("%d",&T);T--;){
		mp.clear();id=0;
		scanf("%d",&n);cin>>s;
		mp[s]=++id;
		for(i=1;i<=6;i++)
			for(j=1;j<=20;j++){
				cin>>s;
				if(!mp[s])mp[s]=++id;
				q[i][j]=mp[s];
			}
		an=-1;
		for(YY=0;YY<=n;YY++){
			Y=YY;X=n-Y;
			for(i=1;i<=id;i++)vs[i]=0;
			for(j=1;j<=20&&X;j++)
				for(i=1;i<=5&&X;i++)
					if(!vs[q[i][j]])vs[q[i][j]]=1,X--;
			for(j=1;j<=20&&Y;j++)
				if(!vs[q[6][j]])vs[q[6][j]]=1,Y--;
			if(!vs[1]){
				an=YY;
				break;
			}
		}
		printf("Case #%d: ",++ca);
		if(an==-1)puts("ADVANCED!");else printf("%d\n",an);
	}
}

L - Daylight Saving Time

 大力分类讨论,抄日期模板

#include<bits/stdc++.h>
using namespace std;
int ca;
int G(int d,int m,int y){
	int ans;
	if(m==1||m==2)m+=12,y--;
	if((y<1752)||(y==1752&&m<9)||(y==1752&&m==9&&d<3))ans=(d+2*m+3*(m+1)/5+y+y/4+5)%7;
	else ans=(d+2*m+3*(m+1)/5+y+y/4-y/100+y/400)%7;
	return (ans+1)%7;
}
int cal(int yy,int mm,int dd,int h,int m,int s){
	if(mm<3||mm>11)return 1;
	if(mm>3&&mm<11)return 2;
	if(mm==3){
		int w=0;
		for(int i=1;i<=dd;i++)
			if(!G(i,mm,yy))w++;
		if(w<2)return 1;
		if(w>2)return 2;
		if(G(dd,mm,yy))return 2;
		if(h==2)return 4;
		return (h<2)?1:2;
	}else{
		int w=0;
		for(int i=1;i<=dd;i++)
			if(!G(i,mm,yy))w++;
		if(w<1)return 2;
		if(w>1)return 1;
		if(G(dd,mm,yy))return 1;
		if(h==1)return 3;
		return (h<1)?2:1;
	}
}
char s[19];
int main(){
	int T,day,month,year,hour,minite,second,an;
	for(scanf("%d",&T);T--;){
		scanf("%s",s);
		day=(s[8]-'0')*10+s[9]-'0';
		month=(s[5]-'0')*10+s[6]-'0';
		year=(s[0]-'0')*1000+(s[1]-'0')*100+(s[2]-'0')*10+s[3]-'0';
		scanf("%s",s);
		hour=(s[0]-'0')*10+s[1]-'0';
		minite=(s[3]-'0')*10+s[4]-'0';
		second=(s[6]-'0')*10+s[7]-'0';
		an=cal(year,month,day,hour,minite,second);
		printf("Case #%d: ",++ca);
		if(an==1)puts("PST");
		if(an==2)puts("PDT");
		if(an==3)puts("Both");
		if(an==4)puts("Neither");
	}
}