Codeforces Round #606 Div. 2 比赛总结

比赛情况

bq. A题 Wrong Answer on test 2 , E题sb题没切。bqbqbq.

比赛总结

bq.

那就直接上题解吧！^-

A

数位dp，分类讨论，注意细节。

Talk is cheap.Show me the code.

#include<bits/stdc++.h>

using namespace std;

inline int read() {

	int x=0,f=1; char ch=getchar();

	while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }

	while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }

	return x * f;

}

int n,m,ans,L;

void work() {

	n = read(), ans = 0;

	L = 0, m = n;

	while(m/10) ++L, m /= 10;

	ans += L * 9;

	L = 1, m = n;

	while(m/10) L = (L*10)+1, m /= 10;

	ans += n/L;

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

}

int main()

{

	int T = read();

	while(T--) work();

	return 0;

}

B

我们把数值一样的数放在一起，扔进堆里。按数值从大到小处理就OK了。

注意值域比较大，用一下 \(STL\) 里面的 map。

Talk is cheap.Show me the code.

#include<bits/stdc++.h>

using namespace std;

inline int read() {

	int x=0,f=1; char ch=getchar();

	while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }

	while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }

	return x * f;

}

const int N = 2e5+7;

int n;

int a[N];

void work() {

	map<int,int> s;

	priority_queue<int> q;

	n = read(); int ans = 0;

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

		a[i] = read();

		if(s[a[i]]==0) {

			q.push(a[i]);

		}

		++s[a[i]];

	}

	while(!q.empty()) {

		int now = q.top(); q.pop();

		if(now&1) continue;

		if(s[now/2]==0) q.push(now/2);

		s[now/2] += s[now]; ans++;

		//printf("ans += s[%d], s[now]=%d\n",now,s[now]);

	}

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

}

int main()

{

	//freopen("a.out","w",stdout);

	int T = read();

	while(T--) work();

	return 0;

}

C

贪心题。

如果有 twone 则删去 'o'，否则删去中间这个，比如 one 删去 'n'。这样是对的。

然后模拟即可。

Talk is cheap.Show me the code.

#include<bits/stdc++.h>

using namespace std;

inline int read() {

	int x=0,f=1; char ch=getchar();

	while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }

	while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }

	return x * f;

}

void work() {

	string s; cin>>s; vector<int> Ans;

	for(int i=1;i<s.length();++i) {

		char a = s[i-1], b = s[i], c = s[i+1];

		if(a=='t' && b=='w' && c=='o') {

			if(s[i+2]=='n' && s[i+3]=='e') s[i+1] = '-', Ans.push_back(i+1)/*, i = i+3+1*/;

			else s[i] = '-', Ans.push_back(i)/*, i = i+1+1*/;

		} else if(a=='o' && b=='n' && c=='e') {

			Ans.push_back(i);

		}

	}

	printf("%d\n",(int)Ans.size());

	for(int i=0;i<Ans.size();++i) printf("%d ",Ans[i]+1);

	puts("");

}

int main()

{

	//freopen("a.out","w",stdout);

	int T = read();

	while(T--) work();

	return 0;

}

D

待补坑。

E

炒鸡简单

考虑一张下面这样的图：

答案不就是两个蓝色部分的大小相乘吗？（题目不考虑A，B两点）

这不就是Dfs的事吗qwq

（其实如果这两块蓝色的有边将他们连起来了就是 puts("0")）

Talk is cheap.Show me the code.

#include<bits/stdc++.h>

using namespace std;

inline int read() {

	int x=0,f=1; char ch=getchar();

	while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }

	while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }

	return x * f;

}

const int N = 2e5+7, M = 5e5+7;

int n,m,a,b,cnt,flag,tot;

int head[N],vis[N];

struct Edge {

	int next,to;

}edge[M<<1];

inline void add(int u,int v) {

	edge[++cnt] = (Edge)<%head[u],v%>;

	head[u] = cnt;

}

void Dfs(int u,int F) {

	flag |= (u==F); vis[u] = 1; ++tot;

	for(int i=head[u];i;i=edge[i].next) {

		int v = edge[i].to;

		if(!vis[v]) Dfs(v,F);

	}

}

void work() {

	memset(head, 0, sizeof(head)); cnt = flag = 0;

	n = read(), m = read(), a = read(), b = read();

	for(int i=1,u,v;i<=m;++i) {

		u = read(), v = read();

		add(u,v), add(v,u);

	}

	memset(vis, 0, sizeof(vis));

	vis[a] = 1; int n1 = 0, n2 = 0, nxt = 0;

	for(int i=head[a];i;i=edge[i].next) {

		int v = edge[i].to; tot = 0; Dfs(v,b);

		if(flag) {

			n1 = n - tot - 1; break;

		}

	}

	memset(vis, 0, sizeof(vis));

	vis[b] = 1; flag = 0;

	for(int i=head[b];i;i=edge[i].next) {

		int v = edge[i].to; tot = 0; Dfs(v,a);

		if(flag) {

			n2 = n - tot - 1; break;

		}

	}

	printf("%lld\n",(long long)(1ll*n1*n2));

}

int main()

{

	int T = read();

	while(T--) work();

	return 0;

}

F

待补坑。

巴特西

Codeforces Round #606 Div. 2 比赛总结

比赛情况

比赛总结

A

B

C

D

E

F

最新文章

热门文章