首页 > 其他分享 >AtCoder Beginner Contest 282 A-F 题解

AtCoder Beginner Contest 282 A-F 题解

时间:2023-02-25 11:34:01浏览次数:52  
标签:AtCoder include return int 题解 ++ 联通 282 ver

比赛链接

A - Generalized ABC

额,对,是的,没错,先这样再那样然后这样

就是这样。

点击查看代码
#include<cstdio>

int n;

int main() {
	scanf("%d", &n);
	for(int i = 0; i < n; i ++) {
		printf("%c", 'A' + i);
	}
	
	return 0;
} 

B - Let's Get a Perfect Score

枚举所有组合,然后暴力判断就好。

点击查看代码
#include<cstdio>
const int N = 35;

char s[N][N];
int n, m, ans;

bool check(int x, int y) {
	for(int i = 1; i <= m; i ++) {
		if(s[x][i] == 'x' && s[y][i] == 'x') return 0;
	}
	return 1;
}

int main() {
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= n; i ++) scanf("%s", s[i] + 1);
	for(int i = 1; i <= n; i ++) {
		for(int j = i + 1; j <= n; j ++) ans += check(i, j);
	}
	printf("%d", ans);
	return 0;
} 

C - String Delimiter

差分,记录一下 封闭区间,然后直接枚举转移就好。

点击查看代码

#include<cstdio>
const int N = 2e5 + 5;

char s[N], ans[N];

int n, tot, v[N];

int main() {
	scanf("%d %s", &n, s + 1);
	for(int i = 1; i <= n; i ++) {
		if(s[i] == '"') {
			tot ++;
			if(tot & 1) v[i] ++;
			else v[i] --;
		}
	}
	for(int i = 1; i <= n; i ++) v[i] += v[i - 1];
	
	for(int i = 1; i <= n; i ++) {
		if(s[i] != ',') ans[i] = s[i];
		else if(!v[i]) ans[i] = '.';
		else ans[i] = ',';
	}
	printf("%s", ans + 1);
	return 0;
} 

D - Make Bipartite 2

是哪个大冤种 return 0 写成了 return 1 导致 RE 还没发现, 开开心心去切下一题,然后痛失 400 pts。

哦,是我呀~

首先,二分图内没有长度为奇数的回路。

所以如果我们将一个图内的点分为两部分,这两部分的点互相连起来的不重复的点都满足是二分图的条件。

于是,我们先判断每个联通块是否是二分图,如果不是,答案为 0,

然后记录一下两种颜色的点数 c1 , c2,计算出他们的贡献就好。

关于贡献,无非就是有一个联通分量,或者多个联通分量。

  • 对于一个联通分量,贡献为 c1 * c2 - m

  • 而多个联通分量,其实就是 每个联通分量的可能的连边 c1 * c2 再加上 各个联通分量之间连边 (c1 + c2) * (n - c1 - c2) 再减去本来的连边 m。

点击查看代码
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 2e5 + 5;
#define int long long
vector<int> G[N];
int n, m, col[N], cnt1, cnt2;

bool dfs(int x, int c) {
	col[x] = c;
	if(c == 1) cnt1 ++;
	else cnt2 ++;
	int ver;
	for(int i = 0; i < G[x].size(); i ++) {
		ver = G[x][i];
		if(col[ver] == c) return 0;
		if(!col[ver] && !dfs(ver, 3 - c)) return 0; 
	}
	return 1;
}
int ans1, ans2;
signed main() {
	scanf("%lld %lld", &n, &m);
	int u, v;
	for(int i = 1; i <= m; i ++) {
		scanf("%lld %lld", &u, &v);
		G[u].push_back(v), G[v].push_back(u);
	}
	for(int i = 1; i <= n; i ++) {
		if(!col[i]) {
			cnt1 = cnt2 = 0;
			if(!dfs(i, 1)) {
				puts("0");
				return 0;
			}
			ans1 += cnt1 * cnt2;
			ans2 += (cnt1 + cnt2) * (n - cnt1 - cnt2); 
		}
	}
	printf("%lld", ans1 + ans2 / 2 - m);
	return 0;
}

E - Choose Two and Eat One

分析可得,一共会执行 n - 1 次操作,

所以我们可以 \(n^2\) 枚举每个分数,

可以直接建图,跑最大生成树,计算答案。

完了。

点击查看代码
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 505;
#define int long long
vector<int> G[N];
bool vis[N];
int n, m, ans, a[N], dis[N], dp[N][N];

int qpow(int a, int b) {
	int res = 1;
	while(b) {
		if(b & 1) res = res * a % m;
		a = a * a % m, b >>= 1;
	}
	return res;
}

void solve() {
	memset(dis, -1, sizeof(dis));
	int tmp;
	for(int i = 0; i < n; i ++) {
		tmp = -1;
		for(int j = 1; j <= n; j ++) {
			if(!vis[j] && (tmp == -1 || dis[tmp] < dis[j])) tmp = j;
		}
		if(i && dis[tmp] == -1) return;
		if(i) ans += dis[tmp];
		vis[tmp] = 1;
		for(int j = 1; j <= n; j ++) dis[j] = max(dis[j], dp[j][tmp]);
	}
}
signed main() {
	
	scanf("%lld %lld", &n, &m);
	for(int i = 1; i <= n; i ++) scanf("%lld", &a[i]);
	
	for(int i = 1; i <= n; i ++) {
		for(int j = 1; j <= n; j ++) {
			if(i == j) dp[i][j] = -1;
			else dp[i][j] = (qpow(a[i], a[j]) + qpow(a[j], a[i])) % m;
		}
	}
	solve();
	
	printf("%lld", ans);
	return 0;
}

F - Union of Two Sets

不会写交互题,

(摆烂姿态)

标签:AtCoder,include,return,int,题解,++,联通,282,ver
From: https://www.cnblogs.com/Spring-Araki/p/17154045.html

相关文章

  • #68. 「NOIP2004」津津的储蓄计划 题解
    #68.「NOIP2004」津津的储蓄计划题解题目传送门题目知识点模拟题目分析非常的“明显”,这是一道模拟题。题意说明有可能在某个月的月初,津津手中的钱加上这个月妈妈......
  • #119. 最大整数 题解
    #119.最大整数题解题目传送门题目知识点字符串+贪心题意说明设有n个正整数(n<=20),将它们连接成一排,组成一个最大的多位整数。(题目简介明了,一看就是出题人懒得写题目背......
  • #160. 「NOIP2004 普及组」不高兴的津津 题解
    #160.「NOIP2004普及组」不高兴的津津题解题目传送门题目知识点枚举题意说明津津如果一天上课超过八个小时就会不高兴,而且上得越久就会越不高兴。假设津津不会因为......
  • #373. 「USACO1.1」Friday the Thirteenth 题解
    #373.「USACO1.1」FridaytheThirteenth题解题目传送门题目知识点模拟+数学闰年知识点题意说明写一个程序来计算在n年里13日落在星期一,星期二......星期日的次数......
  • match 题解
    题面题目描述一个匹配模式是由一些小写字母和问号组成的一个字符串。当一个由小写字母组成的字符串\(s\),长度和匹配模式长度相同,并且在对应的每一位都相等或模式串相应......
  • 题解 Codeforces 1746F Kazaee
    题意给定长度为\(n\)的数组\(a\),和\(q\)次操作,支持:给定\(i,x\),修改\(a_i\)为\(x\)给定\(l,r,k\),查询\([l,r]\)中是否每个数的出现次数都是\(k\)的倍数......
  • 题解 LOJ P2393 「JOISC 2017 Day 2」门票安排
    题意咕咕咕。题解这题太神了,无限膜拜p_b_p_b,搬运一波题解。首先考虑二分。题意等价于选一些区间进行反转。首先注意到反转的区间两两有交,不然不反转一定更优。设反转......
  • P8822 [传智杯#3 初赛] 课程报名 题解
    题目传送门题目大意有一种课程,初始定价为\(v\)元;每报名\(m\)个学员,课程的定价就要提升\(a\)元,一共有\(n\)个学员报名。解题思路因为一共有\(n\)个学员报名,所......
  • P8717 [蓝桥杯 2020 省 AB2] 成绩分析 题解
    题目传送门题目大意计算\(n\)个人考试的最高分、最低分和平均分。解题思路输入\(n\)个人成绩的同时,计算最大值,最小值和总数。再将总数除以\(n\)算出平均值并保......
  • AtCoder Beginner Contest 285 A-F 题解
    比赛链接A-EdgeChecker2判断y==2x||y==2x+1即可。点击查看代码#include<cstdio>#include<algorithm>#include<cstring>usingnamespacestd;inta......