4
17
2016
0

codeforces 347 div2

rank3应该是有的吧。。。来不及写E了。。。现在是2:12分

A:求两个超大数的之间的所有数的gcd

显然gcd(a,a+1)=1所以判一下a是不是和b相等就行了

#include<cstdio>
#include<cstring>
using namespace std;
char a[205],b[205];
int main(){
	scanf("%s%s",a,b);
	if(strlen(a)!=strlen(b)){
		printf("1");
		return 0;
	}
	for(int i=0;i<strlen(a);i++)if(a[i]!=b[i]){
		printf("1");
		return 0;
	}
	printf("%s",a);
}

B:

给你一个 ?很多个+?还有很多个-?=n形式的等式,问你找到一组解使得每一个?的位置都放一个1到n之间的正整数使得等式成立。无解输出-1

因为n很小所以暴力弄就可以辣。

 

#include<cstdio>
using namespace std;
int v[1005];
int a[1005];
int n,sa,sb,m,p;
char c[2];
int main(){
	scanf("%s",c);
	v[1]=sa=1;
	m=1;
	scanf("%s",c);
	while(c[0]!='='){
		if(c[0]=='+'){v[++m]=1;sa++;}
		else{v[++m]=-1;sb++;}
		scanf("%s",c);
		scanf("%s",c);
	}
	scanf("%d",&n);
	p=sa-sb;
	for(int i=1;i<=m;i++)a[i]=1;
	for(int i=1;i<=m;i++){
		while((p<n)&&(v[i]==1)&&(a[i]<n))a[i]++,p++;
		while((p>n)&&(v[i]==-1)&&(a[i]<n))a[i]++,p--;	
	}
	if(p!=n){printf("Impossible");return 0;}
	printf("Possible\n");
	printf("%d ",a[1]);
	for(int i=2;i<=m;i++){
		if(v[i]==1)printf("+ ");
		else printf("- ");
		printf("%d ",a[i]);
	}
	printf("= %d",n);
}

c:

从1989开始写年份,能用后缀表示而且和之前的年份没有重复的就这样表示,给出表示方法问你是几几年,比如1989的表示方法是9

1999的表示方法是99,因为9的后缀1989已经用过了

没啥意思,判一下所有的n位后缀中哪些后缀在n位中已经用过了,剩下的都是1....形式的。代码写丑了

#include<cstdio>
#include<cstring>
using namespace std;
int test,n;
char s[100];
int main(){
	scanf("%d",&test);
	while(test--){
		scanf("%s",s);
		if(strlen(s)==5){
			if(s[4]!='9')printf("199%c",s[4]);
			else printf("1989");
		}
		if(strlen(s)==6){
			if((s[4]=='9')&&(s[5]=='9'))printf("1999");
			else printf("20%c%c",s[4],s[5]);
		}
		if(strlen(s)==7){
			if((s[4]=='0')&&((s[5]!='9')||(s[6]!='9')))printf("3%c%c%c",s[4],s[5],s[6]);
			else printf("2%c%c%c",s[4],s[5],s[6]);
		}
		if(strlen(s)==8){
			n=(s[4]-'0')*1000+(s[5]-'0')*100+(s[6]-'0')*10+s[7]-'0';
			if(n<=3098)printf("1%d",n);
			else printf("%d",n);
		}
		if(strlen(s)==9){
			n=(s[4]-'0')*10000+(s[5]-'0')*1000+(s[6]-'0')*100+(s[7]-'0')*10+s[8]-'0';
			if(n<=13098)printf("1%d",n);
			else printf("%d",n);
		}
		if(strlen(s)==10){
			n=(s[4]-'0')*100000+(s[5]-'0')*10000+(s[6]-'0')*1000+(s[7]-'0')*100+(s[8]-'0')*10+s[9]-'0';
			if(n<=113098)printf("1%d",n);
			else printf("%d",n);
		}
		if(strlen(s)==11){
			n=(s[4]-'0')*1000000+(s[5]-'0')*100000+(s[6]-'0')*10000+(s[7]-'0')*1000+(s[8]-'0')*100+(s[9]-'0')*10+s[10]-'0';
			if(n<=1113098)printf("1%d",n);
			else printf("%d",n);
		}
		if(strlen(s)==12){
			n=(s[4]-'0')*10000000+(s[5]-'0')*1000000+(s[6]-'0')*100000+(s[7]-'0')*10000+(s[8]-'0')*1000+(s[9]-'0')*100+(s[10]-'0')*10+s[11]-'0';
			if(n<=11113098)printf("1%d",n);
			else printf("%d",n);
		}
		if(strlen(s)==13){
			n=(s[4]-'0')*100000000+(s[5]-'0')*10000000+(s[6]-'0')*1000000+(s[7]-'0')*100000+(s[8]-'0')*10000+(s[9]-'0')*1000+(s[10]-'0')*100+(s[11]-'0')+s[12]-'0';
			if(n<=111113098)printf("1%d",n);
			else printf("%d",n);
		}
		puts("");
	}
}

d:

一个无向图,每条边有两个颜色,你可以操作一个点使得它连出的所有边颜色取反,问把所有边变成颜色相同的最小操作次数,无解输出-1

这个题是我拿的一血主要是因为当时B、C都没想法

显然一个点最多操作一次

显然边最后要么都是黑色要么都是白色

那么我们按黑白两色都做一次,每一次假如边颜色不符合要求,那么显然p[u]^p[v]=1否则p[u]^p[v]=0。

带权并查集乱搞搞就没了。

关于最小操作次数的问题,对于每个联通块最后统计一下和根p相同的和不同的有几个,取比较少的那个就可以了

 

#include<cstdio>
using namespace std;
int fa[100005],re[100005],r[100005],sam[100005],dif[100005],Re[100005];
int n,m,ans,s;
char c[2];
struct edge{
	int u,v,p;
}e[100005];
inline int find(int k){
	if(fa[k]==k)return k;
	int tmp=fa[k];
	fa[k]=find(fa[k]);
	r[k]=r[tmp]^r[k];
	return fa[k];
}
void check(int p){
	for(int i=1;i<=n;i++)fa[i]=i,r[i]=0,sam[i]=dif[i]=0;
	for(int i=1;i<=m;i++){
		int u=find(e[i].u),v=find(e[i].v);
		if(u==v){
			if((e[i].p==p)&&(r[e[i].u]==r[e[i].v]))return;
			if((e[i].p!=p)&&(r[e[i].u]!=r[e[i].v]))return;
		}else{
			if(e[i].p==p)fa[u]=v,r[u]=r[e[i].v]^r[e[i].u]^1;
			else fa[u]=v,r[u]=r[e[i].v]^r[e[i].u];
		}
	}
	for(int i=1;i<=n;i++){
		find(i);
		if(r[i])dif[fa[i]]++;
		else sam[fa[i]]++;
	}
	s=0;
	for(int i=1;i<=n;i++)
		if(dif[fa[i]]>sam[fa[i]]){if(r[i]==0)Re[++s]=i;}
		else{if(r[i]==1)Re[++s]=i;}
	if((ans==-1)||(s<ans)){
		ans=s;
		for(int i=1;i<=ans;i++)re[i]=Re[i];
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d%s",&e[i].u,&e[i].v,c);
		if(c[0]=='B')e[i].p=1;
		else e[i].p=0;
	}
	for(int i=1;i<=n;i++)fa[i]=i,sam[i]=1,dif[i]=0;
	ans=-1;
	check(1);check(0);
	printf("%d\n",ans);
	for(int i=1;i<=ans;i++)printf("%d ",re[i]);
}

e

你是一个CF选手。现在有3道题,每个人做出题的时间每道题有一个参数ai、bi、ci。以ai为例,ai的绝对值表示这个选手做出题的时间,假如ai是负的,那么表示你可以插他使他挂题,也就意味着他这题会无法通过。一个选手一道题得分计算公式如下:

我懒就直接贴了,k表示这道题过题人数,t表示这个选手过题的时间,s表示the maximum possible score

If n < 2k ≤ 2n, then the maximum possible score is 500;

If n < 4k ≤ 2n, then the maximum possible score is 1000;

If n < 8k ≤ 2n, then the maximum possible score is 1500;

If n < 16k ≤ 2n, then the maximum possible score is 2000;

If n < 32k ≤ 2n, then the maximum possible score is 2500;

If 32k ≤ n, then the maximum possible score is 3000.

现在这个选手这道题得分就是s*(250-t}/250(取整),一个选手的分数就是他三道题分数之和

你的任务是决定插掉哪些人,使得你最后的排名最高。排名的定义是分数严格大于你的人数+1,输出这个值。

我想到了一个应该是对的网络流做法,然而来不及写了_(:зゝ∠)_

做一下嘴巴选手吧。

首先三道题的s一共也只有63种情况,我们暴力枚举的话时间复杂度是允许的。

然后我们按照枚举出的情况的s计算出当前的排名,我们的任务就变成了我们有若干次机会让排名在自己前面的人一道题爆0,最后使得自己排名最高。

一个人显然最多只有8种插法,23插不插十分显然,那么一个人8种插法能否比我的当前分数低可以表示成为28,也就是说,其实不同的人只有28.

那么这个东西有什么用呢?我们可以建图了,源点向三个点连边,表示我这道题能插几次,这三个点向那8个点连边,表示8种插的方法是否要消耗这道题的次数。

然后8种插法再向256种人连边,每种人向汇点连排名比我高而且是这种情况的人数的流量,就可以了。

然而我并没有写

Category: codeforces | Tags: codeforces contests | Read Count: 574

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com