CCPC-Final2016
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");
}
}
评论 (0)
