2012 Asia Chengdu Regional Contest

D Graph

lbn187

按度数讨论即可,比赛时没有考虑到重边的情况狂T不止

#include<bits/stdc++.h>
#define N 100005
#define LL long long
#define fr(i,n) for(int i=1;i<=n;i++)
#define CL(a) memset(a,0,sizeof a)
using namespace std;
int ca,n,m,i,x,y,z,v0,v1,Lim,Q,du[N],c[N];
LL AN,an1[N][2],an2[2][2];char s[9];
map<int,LL>mp[N];map<int,LL>::iterator it;
struct P{int y;LL z;};
bool operator <(P a,P b){return du[a.y]>du[b.y];}
vector<P>V[N];vector<int>Big;
void ins(int x,int y,int z){mp[x][y]+=z;}
void add_new(int x,int y,LL z){
	if(du[x]<Lim&&du[y]>=Lim)swap(x,y);
	if(du[x]>=Lim)an1[x][c[y]]+=z;
	else an2[c[x]][c[y]]+=z;
}
void rd(int&x){
	char ch;
	for(ch=getchar();ch<'0'||ch>'9';ch=getchar());
	for(x=0;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
}
int main(){
	for(;~scanf("%d%d",&n,&m);){
		printf("Case %d:\n",++ca);
		Big.clear();CL(an2);Lim=(int)sqrt(m);
		fr(i,n)rd(c[i]),V[i].clear(),mp[i].clear();
		fr(i,m)rd(x),rd(y),rd(z),ins(x,y,z),ins(y,x,z);
		for(int i=1;i<=n;i++)for(it=mp[i].begin();it!=mp[i].end();it++)V[i].push_back(P{(*it).first,(*it).second}),du[i]++;
		fr(i,n)sort(V[i].begin(),V[i].end());
		fr(i,n)if(du[i]>=Lim)Big.push_back(i);
		fr(i,n)for(int j=0;j<V[i].size();j++)add_new(i,V[i][j].y,V[i][j].z);
		rd(Q);
		for(;Q--;){
			scanf("%s",s);
			if(s[0]=='A'){
				rd(v0);rd(v1);AN=0;
				for(int i=0;i<Big.size();i++){
					x=Big[i];
					if(c[x]==v0)AN+=an1[x][v1];
					else if(c[x]==v1)AN+=an1[x][v0];
				}
				if(v0!=v1)AN+=an2[v0][v1]*2;else AN+=an2[v0][v1];
				printf("%lld\n",AN/2);
			}else{
				rd(x);
				int SZ=V[x].size(),xx;
					for(int i=0;i<SZ&&du[xx=V[x][i].y]>=Lim;i++){
						LL zz=V[x][i].z;
						if(du[x]<Lim)zz*=2;
						an1[xx][c[x]]-=zz;
						an1[xx][c[x]^1]+=zz;

					}
				if(du[x]<Lim){
					for(int i=0;i<SZ;i++)if(du[xx=V[x][i].y]<Lim){
						LL zz=V[x][i].z;
						an2[c[x]][c[xx]]-=zz;
						an2[c[xx]][c[x]]-=zz;
						an2[c[x]^1][c[xx]]+=zz;
						an2[c[xx]][c[x]^1]+=zz;
//						printf("%d %d %d %d\n",x,xx
					}
				}
				c[x]^=1;
			//	printf("%lld %lld %lld\n",an2[0][0],an2[0][1],an2[1][1]);
			}
		}
		for(i=1;i<=n;i++)an1[i][0]=an1[i][1]=0,du[i]=0;
	}
}

G Blackjack

lbn187

暴力枚举两个端点然后大模拟,交晚了几秒钟。。

#include<bits/stdc++.h>
#define N 2222
#define CL(a) memset(a,0,sizeof a)
#define fr(i,n) for(int i=1;i<=n;i++)
using namespace std;
int n,k,an,ca,ne[N][12],e[N][12],V[N],to[N][12];
char s[9];
int cal(char ch){
	if(ch>='1'&&ch<='9')return ch-'0';
	if(ch=='A')return 1;
	if(ch=='T')return 10;
	if(ch=='J')return 10;
	if(ch=='Q')return 10;
	if(ch=='K')return 10;
}
int main(){
	for(;~scanf("%d%d",&n,&k);){
		k--;
		CL(ne);CL(e);an=0;
		fr(i,n)scanf("%s",s),V[i]=cal(s[0]),to[i][0]=i;
		fr(i,n){
			bool ff=0;int CA=0,CB=0,SA=0,SB=0,j;
			if(i+3>n){
				ne[i][0]=n+1;
				e[i][0]=0;
				continue;
			}
			CA=2;CB=2;SA=V[i]+V[i+2];SB=V[i+1]+V[i+3];
			if(SA>15)ff=1;
			if(ff&&SB>15){
				ne[i][0]=i+4;
				if(SA>SB)e[i][0]=1;else e[i][0]=0;
			}else {
			for(j=i+4;j<=n;j++){
				if(!ff){
					CA++;
					SA+=V[j];
				}else{
					CB++;
					SB+=V[j];
				}
				if(SA>21){
					ne[i][0]=j+1;
					e[i][0]=0;
					break;
				}
				if(CA==5){
					ne[i][0]=j+1;
					e[i][0]=1;
					break;
				}
				if(SB>21){
					ne[i][0]=j+1;
					e[i][0]=1;
					break;
				}
				if(CB==5){
					ne[i][0]=j+1;
					e[i][0]=0;
					break;
				}
				if(SA>15)ff=1;
				if(ff&&SB>15){
					ne[i][0]=j+1;
					if(SA>SB)e[i][0]=1;else e[i][0]=0;
					break;
				}
			}
			if(j>n)ne[i][0]=n+1,e[i][0]=0;
			}
		}
//		printf("%d %d\n",ne[1][0],e[1][0]);
		ne[n+1][0]=n+1;e[n+1][0]=0;to[n+1][0]=n+1;
		fr(j,10)fr(i,n+1){
			ne[i][j]=ne[ne[i][j-1]][j-1];
			e[i][j]=e[i][j-1]+e[ne[i][j-1]][j-1];
			to[i][j]=to[ne[i][j-1]][j-1];
		}
		for(int l=2;l<n;l++)for(int r=l;r<n;r++){
			int x=l,S=0,CA,CB,SA,SB,i,j,o,vo;bool ff=0;
			for(i=10;~i;i--){
				if(ne[x][i]<=r+1&&r-to[x][i]+1+l-1+n-r>k){
					S+=e[x][i];
					x=ne[x][i];
				}
			}
			ff=0;CA=CB=SA=SB=0;
			if(l-1+n-r+r-x+1<=k){
				an=max(an,S);
				continue;
			}
			for(i=x;i<=r;i++){
				if(CA<2||CB<2){
					if(CA<=CB){
						CA++;
						SA+=V[i];
					}else{
						CB++;
						SB+=V[i];
					}
				}else
				if(!ff){
					CA++;
					SA+=V[i];
				}else{
					CB++;
					SB+=V[i];
				}
				if(SA>15)ff=1;
			}
			/*if(l-1+n-r+r-i+1<=k){
				an=max(an,S);
				continue;
			}*/
			o=0;
			if(ff&&SB>15){
				o=1;
				if(SA>SB)S++;
			}else
			for(i=1;i<l;i++){

				if(CA<2||CB<2){
					if(CA<=CB){
						CA++;
						SA+=V[i];
					}else{
						CB++;
						SB+=V[i];
					}
				}else
				if(!ff){
					CA++;
					SA+=V[i];
				}else{
					CB++;
					SB+=V[i];
				}
				if(CA>=2&&CB>=2){
				if(SA>21){
					o=i+1;
					break;
				}
				if(CA==5){
					o=i+1;
					S++;
					break;
				}
				if(SB>21){
					o=i+1;
					S++;
					break;
				}
				if(CB==5){
					o=i+1;
					break;
				}
				
				if(SA>15)ff=1;
				if(ff&&SB>15){
					o=i+1;
					if(SA>SB)S++;
					break;
				}
				}
			}
			if(o&&l-o+n-r<=k){an=max(an,S);continue;}
			if(o){
				x=o;
				for(i=10;~i;i--){
					if(ne[x][i]<=l&&l-to[x][i]+n-r>k){
						S+=e[x][i];
						x=ne[x][i];
					}
				}
				CA=CB=SA=SB=0;ff=0;
				if(l-x+n-r<=k){
					an=max(an,S);
					continue;
				}
				for(i=x;i<l;i++){
					if(CA<2||CB<2){
						if(CA<=CB){
							CA++;
							SA+=V[i];
						}else{
							CB++;
							SB+=V[i];
						}
					}else
					if(!ff){
						CA++;
						SA+=V[i];
					}else{
						CB++;
						SB+=V[i];
					}
					if(SA>15)ff=1;
				}
				/*if(l-i+n-r<=k){
					an=max(an,S);
					continue;
				}*/
			}
			o=0;
			if(ff&&SB>15){
				o=r+1;
				if(SA>SB)S++;
			}else
			for(i=r+1;i<=n;i++){
				if(CA<2||CB<2){
					if(CA<=CB){
						CA++;
						SA+=V[i];
					}else{
						CB++;
						SB+=V[i];
					}
				}else
				if(!ff){
					CA++;
					SA+=V[i];
				}else{
					CB++;
					SB+=V[i];
				}
				if(CA>=2&&CB>=2){
				if(SA>21){
					o=i+1;
					break;
				}
				if(CA==5){
					o=i+1;
					S++;
					break;
				}
				if(SB>21){
					o=i+1;
					S++;
					break;
				}
				if(CB==5){
					o=i+1;
					break;
				}
				if(SA>15)ff=1;
				if(ff&&SB>15){
					o=i+1;
					if(SA>SB)S++;
					break;
				}
				}
			}
			if(n-o+1<=k){
				an=max(an,S);
				continue;
			}
			if(o){
				x=o;
				for(i=10;~i;i--){
					if(ne[x][i]<=n+1&&n-to[x][i]+1>k){
						S+=e[x][i];
						x=ne[x][i];
					}
				}
			}
			an=max(an,S);
		}
		printf("Case %d: %d\n",++ca,an);
	}
}

J Exam

lbn187

将题意转化为求\(a*b*c\leq N\)的个数,那么枚举较小的两个数,即可求出第三个数的取值范围得到答案,时间复杂度\(O(n^{0.67})\)。太菜了没想到杜教筛了半天。。

#include<bits/stdc++.h>
#define LL long long
using namespace std;
LL n,a,b,c,an;int ca;
int main(){
	for(;~scanf("%lld",&n);){
		an=0;
		for(a=1;a*a*a<=n;a++)
			for(b=a;a*b*b<=n;b++){
				c=n/(a*b);
				if(a==b)an+=3*(c-b)+1;
				else an+=6*(c-b)+3;
			}
		printf("Case %d: %lld\n",++ca,an);
	}
}