20191214 Codeforces Round #606 (Div. 2, based on Technocup 2020 Elimination Round 4)

概述

切了 ABCE，Room83 第一

还行吧

A - Happy Birthday, Polycarp!

题解

显然这样的数不会很多。

于是可以通过构造法，直接求出 \([1,10^9]\) 内所有符合要求的数。

\(\mathrm{Code}\)

#include<bits/stdc++.h>

using namespace std;

int a[]={1,2,3,4,5,6,7,8,9,11,22,33,44,55,66,77,88,99,111,222,333,444,555,666,777,888,999,1111,2222,3333,4444,5555,6666,7777,8888,9999,11111,22222,33333,44444,55555,66666,77777,88888,99999,111111,222222,333333,444444,555555,666666,777777,888888,999999,1111111,2222222,3333333,4444444,5555555,6666666,7777777,8888888,9999999,11111111,22222222,33333333,44444444,55555555,66666666,77777777,88888888,99999999,111111111,222222222,333333333,444444444,555555555,666666666,777777777,888888888,999999999,1000000001};

int T,n;

int main(){

	cin>>T;

	while(T--){

		cin>>n;int ans=0;

		for(int i=1;a[i]<=n;i++) ++ans;

		cout<<ans+1<<endl;

	}

	return 0;

}

B - Make Them Odd

题解

显然每次从最大的数进行处理最划算。

于是用个优先队列存储所有的数，用 map 记录这个数是否还要付出代价即可。

\(\mathrm{Code}\)

#include<bits/stdc++.h>

using namespace std;

const int maxn=2000007;

int T,n;

int a[maxn];

int b[maxn],t[maxn];

int m;

map<int,bool>mp;

#define pii(x,y) make_pair(x,y)

priority_queue < int>q;

int main(){

	scanf("%d",&T);

	while(T--){

		scanf("%d",&n);mp.clear();

		int ans=0;

		for(int i=1;i<=n;i++){

			scanf("%d",&a[i]);

			q.push(a[i]);

		}

		while(q.size()){

			int x=q.top();//x=-x;

			q.pop();

			if(x&1) continue;

			if(mp[x]) continue;

			++ans;mp[x]=1;

			q.push(x/2);

		}

		printf("%d\n",ans);

	}

}

C - As Simple as One and Two

题解

这种题目 WA 了一次 pretest ，说明我水平低下。

two 和 one 放在一起是非常美妙的字符串。

如果有子串 twone ，显然删去中间的 o 最优。

再处理 two 和 one ，为了不造成新的这样的串，删掉中间的 w 或 n 。

\(\mathrm{Code}\)

#include<bits/stdc++.h>

using namespace std;

const int maxn=150007;

int T,val[maxn];

char s[maxn];

int ans[maxn],cnt;

int main(){

	scanf("%d",&T);

	while(T--){

		scanf("%s",s+1);

		int len=strlen(s+1);cnt=0;

		memset(val,0,sizeof(val));

		for(int i=1;i+4<=len;i++){

			if(s[i]=='t'&&s[i+1]=='w'&&s[i+2]=='o'&&s[i+3]=='n'&&s[i+4]=='e'){

				ans[++cnt]=i+2;

				s[i+2]=' ';

			}

		}

		for(int i=1;i+2<=len;i++){

			if(s[i]=='o'&&s[i+1]=='n'&&s[i+2]=='e'){

				ans[++cnt]=i+1;s[i+1]=' ';

			}

			if(s[i]=='t'&&s[i+1]=='w'&&s[i+2]=='o'){

				ans[++cnt]=i+1;s[i+1]=' ';

			}

		}

		printf("%d\n",cnt);

		for(int i=1;i<=cnt;i++){

			printf("%d ",ans[i]);

		}

		puts("");

	}

}

E - Two Fairs

题解

这种傻逼题花了一个小时还 WA 了一次 pretest，说明我水平低下。

扫一遍，并查集一下就行了。

神仙 zzk 有两次 bfs 的做法？

\(\mathrm{Code}\)

#include<bits/stdc++.h>

using namespace std;

const int maxn=200007;

const int maxm=1000007;

int T;

int n,m,a,b;

#define pii(x,y) make_pair(x,y)

vector <pair<int,int> >e;

int cnt;

int f[maxn];

set<int>A,B;

void clear(void){

	e.clear();

	memset(f,0,sizeof(f));

	for(int i=1;i<=n;i++) f[i]=i;

	A.clear();B.clear();

}

int find(int x){

	return f[x]==x?x:f[x]=find(f[x]);

}

void merge(int x,int y){

	int xx=find(x),yy=find(y);

	if(xx!=yy) f[xx]=yy;

}

void Init(void){

//	for(int i=1;i<=n;i++){

//		cout<<f[i]<<" ";

//	}

	for(int i=1,x,y;i<=m;i++){

		scanf("%d%d",&x,&y);

		if(a!=x&&a!=y&&b!=x&&b!=y) merge(x,y);

		else e.push_back(pii(x,y));

	}

//	for(int i=1;i<=n;i++){

//		cout<<f[i]<<" ";

//	}

}

void Work(void){

	for(auto it:e){

		int x=it.first,y=it.second;

		if(y<x) swap(x,y);

		if(a==x) A.insert(find(y));

		if(a==y) A.insert(find(x));

		if(b==x) B.insert(find(y));

		if(b==y) B.insert(find(x));

	}

	int aa=0,bb=0;

	for(int i=1;i<=n;i++){

//		if(i==a||i==b) continue;

		if(i!=a&&i!=b&&A.count(find(i))&&B.count(find(i))==0) ++aa;

		if(i!=a&&i!=b&&B.count(find(i))&&A.count(find(i))==0) ++bb;

	}

	for(auto it:e) merge(it.first,it.second);

	if(find(a)==find(b)) printf("%d\n",aa*bb);

	else puts("0");

}

int main(){

	scanf("%d",&T);

	while(T--){

		scanf("%d%d%d%d",&n,&m,&a,&b);

		clear();

		Init();

		Work();

	}

}

巴特西

20191214 Codeforces Round #606 (Div. 2, based on Technocup 2020 Elimination Round 4)

概述

A - Happy Birthday, Polycarp!

题解

\(\mathrm{Code}\)

B - Make Them Odd

题解

\(\mathrm{Code}\)

C - As Simple as One and Two

题解

\(\mathrm{Code}\)

E - Two Fairs

题解

\(\mathrm{Code}\)

最新文章

热门文章