Codeforces Round #664 (Div. 2)

Problems

#	Name
A	Boboniu Likes to Color Ballsstandard input/output1 s, 256 MB		x9516
B	Boboniu Plays Chessstandard input/output1 s, 512 MB		x8169
C	Boboniu and Bit Operationsstandard input/output1 s, 256 MB		x3799
D	Boboniu Chats with Dustandard input/output1 s, 256 MB		x937
E	Boboniu Walks on Graphstandard input/output1 s, 256 MB		x26
F	Boboniu and Stringstandard input/output3 s, 256 MB		x3

Solution

A

#include<set>
#include<map>
#include<ctime>
#include<queue>
#include<stack>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define rint register int
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int INF=0x7fffffff;
int T;
int a,b,c,d;
int main()
{
//	freopen("1.in","r",stdin);
	int cnt,cmin;
	scanf("%d",&T);
	while(T--) {
		scanf("%d%d%d%d",&a,&b,&c,&d);
		cnt=0;
		if(a&1) cnt++;
		if(b&1) cnt++;
		if(c&1) cnt++;
		if(d&1) cnt++;
		cmin=min(min(a,b),c);
		if(cmin>0) {
			if(cnt>=3||cnt<=1) 
				printf("Yes\n");
			else printf("No\n");
		}
		else {
			if(cnt<=1) printf("Yes\n");
			else printf("No\n");
		}
	}
	return 0;
}

B

#include<set>
#include<map>
#include<ctime>
#include<queue>
#include<stack>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define rint register int
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int N=100+5;
int n,m;
int sx,sy;
bool vis[N][N];
int p[N*N][2];
void dfs(int x,int y,int step)
{
	int i;
	p[step][0]=x; p[step][1]=y;
	for(i=1;i<=n;i++) {
		if(vis[i][y]) continue;
		vis[i][y]=true;
		dfs(i,y,step+1);
		vis[i][y]=false; 
	}
	for(i=1;i<=m;i++) {
		if(vis[x][i]) continue;
		vis[x][i]=true;
		dfs(x,i,step+1);
		vis[x][i]=false;
	}
	if(step==n*m) {
		for(i=1;i<=n*m;i++) 
			printf("%d %d\n",p[i][0],p[i][1]);
		exit(0);
	}
	p[step][0]=0; p[step][1]=0;
	return;
}
int main()
{
//	freopen("1.in","r",stdin);
	scanf("%d%d%d%d",&n,&m,&sx,&sy);
	vis[sx][sy]=true;
	dfs(sx,sy,1);
	return 0;
}

C

#include<set>
#include<map>
#include<ctime>
#include<queue>
#include<stack>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define rint register int
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int N=256;
int a[N],b[N];
int n,m;
int c[N][N],t[N];
bool vis[N][N];
int main()
{
//	freopen("1.in","r",stdin);
	int i,j,k;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++) scanf("%d",&a[i]);
	for(i=1;i<=m;i++) scanf("%d",&b[i]);
	for(i=1;i<=n;i++) 
		for(j=1;j<=m;j++) {
			c[i][j]=(a[i]&b[j]);
		}
	int ans=0;
	for(k=11;k>=1;k--) {
		bool flag=false;
		memset(t,0,sizeof t);
		for(i=1;i<=n;i++)
			for(j=1;j<=m;j++) 
				if((!vis[i][j])&&(c[i][j]>>(k-1)&1)==0) 
					t[i]=true;
		for(i=1;i<=n;i++) 
			if(t[i]==false) 
				flag=true;
		if(flag) ans=ans|(1<<(k-1));
		else {
			for(i=1;i<=n;i++)
				for(j=1;j<=m;j++) 
					if((!vis[i][j])&&(c[i][j]>>(k-1)&1)) 
						vis[i][j]=true;
		}	
	}
	cout<<ans;
	return 0;
}

D

#pragma GCC optimize(2)
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define rint register int
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int N=2e5+5;
LL a[N],f[N];
int n,d,k;
LL m;
int p[N];
int main()
{
//	freopen("1.in","r",stdin);
	rint i,j;
	scanf("%d%d%lld",&n,&d,&m);
	for(i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	sort(a+1,a+n+1);
	k=(int)(upper_bound(a+1,a+n+1,m)-a)-1;
	sort(a+1,a+k+1,greater<LL>());
	for(i=1;i<=k;i++) f[i]=f[i-1]+a[i]; 
	for(i=k+1;i<=n;i++) f[i]=f[i-1];
	sort(a+k+1,a+n+1,greater<LL>());
	int pp=(n+d)/(d+1);
	p[k]=d+1;
	for(i=k+1;i<=min(k+pp,n);i++) {
		for(j=n+d;j>=p[i-1]+1;j--) {
			if(f[j-d-1]+a[i]>f[j]) {
				f[j]=f[j-d-1]+a[i];
				p[i]=j;
			}
		}
	}
//	for(i=1;i<=n;i++) 
//		cout<<p[i]<<" ";
//	cout<<endl;		
	LL ans=0;
	for(i=n;i<=n+d;i++) 
		ans=max(ans,f[i]);
	cout<<ans;
	return 0;
}

玄学方法，慎用。

E

#include<set>
#include<map>
#include<ctime>
#include<queue>
#include<stack>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define rint register int
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int N=2e5+5;
vector< pair<int,int> > v[N];
vector<int> p[19];
int dep[N];
int n,m,k;
int c[N];
LL ans=0;
void dfs(int step)
{
	if(step==k+1) {
		ans++; 
		return;
	}		
	rint i,j,x;
	for(i=0;i<=step-1;i++) {
		for(j=0;j<(int)p[step].size();j++) {
			x=p[step][j];
			if(dep[v[x][i].second]) break;
			dep[v[x][i].second]++;
		}
		if(j==(int)p[step].size()) 	dfs(step+1);
		for(j=j-1;j>=0;j--) {
			x=p[step][j];
			dep[v[x][i].second]--;
		}
	}
}
int main()
{
//	freopen("1.in","r",stdin);
	int i;
	int x,y,z;
	scanf("%d%d%d",&n,&m,&k);
	for(i=1;i<=m;i++) {
		scanf("%d%d%d",&x,&y,&z);
		v[x].push_back(make_pair(z,y));
	}
	for(x=1;x<=n;x++) {
		sort(v[x].begin(),v[x].end());
		p[v[x].size()].push_back(x);
	}
	dfs(1);
	cout<<ans<<endl;
	return 0;
}

F

(^&^)

Codeforces Round #664 (Div. 2)

原文：https://www.cnblogs.com/cjl-world/p/13494003.html