AtCoder Beginner Contest 198 （A ~ F）题解

A. Div

Problem

Solution

签到

第一反应隔板法，把 $n$ 个物品用一个板子隔开，不能为空，答案就是 $C_{n-2+2-1}^{2-1}=C_{n-1}^1=n-1$。

Time

$O(1)$

Code

// Problem: A - Div
// Contest: AtCoder - AtCoder Beginner Contest 198
// URL: https://atcoder.jp/contests/abc198/tasks/abc198_a
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

using namespace std;
#define int long long
const int N = 50007;

int n;

signed main()
{
   
	scanf("%lld", &n);
	printf("%lld\n", n - 1);
	return 0;
}

B. Palindrome with leading zeros

Problem

Solution

签到

只有9位，暴力判断一下是不是回文串即可。

Time

$O(n)$

Code

// Problem: B - Palindrome with leading zeros
// Contest: AtCoder - AtCoder Beginner Contest 198
// URL: https://atcoder.jp/contests/abc198/tasks/abc198_b
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

using namespace std;
#define int long long
const int N = 50007;

string n, s, ans;

signed main()
{
   
	cin >> n;
	s = n;
	ans = "";
	reverse(n.begin(), n.end());
	if(s == n) {
   
		puts("Yes");
		return 0;
	}
	for(int i = s.length() - 1; i >= 0; -- i) {
   
		ans += "0";
		string tmp = ans + s;
		string tmp2 = tmp;
		reverse(tmp.begin(), tmp.end());
		if(tmp == tmp2) {
   
			puts("Yes");
			return 0;
		}
	}
	puts("No");
	return 0;
}

C. Compass Walking

Problem

Solution

签到

显然如果走整数步，差一点到达目的地（差距小于 2p），那么我们就可以少走一步，然后像一个圆规一样地走两步，走一个三角形，就一定能走任意距离到达最后的目的地。所以答案就是 $\text{ceil}(\frac{dist}{p})$。如果距离小于 2p，我们必须走一个三角形走两步到达，但是如果距离等于p，我们只需要走一步就可以到达。

Time

$O(1)$

Code

// Problem: C - Compass Walking
// Contest: AtCoder - AtCoder Beginner Contest 198
// URL: https://atcoder.jp/contests/abc198/tasks/abc198_c
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

using namespace std;
#define int long long
const int N = 50007;
const long double eps = 1e-8;

int n;
int x, y, p;

int sgn(double x)
{
   
	if(fabs(x) <= eps) {
   
		return 0;		
	}
	else if(x < 0) return -1;
	return 1;
}

signed main()
{
   
	scanf("%lld%lld%lld", &p, &x, &y);
	double dist = sqrt(x * x + y * y);
	int ans = ceil(dist / p);
	if(sgn(dist - (double)p) == 0) {
   
		puts("1");
	}
	else if(sgn(dist - 2.0 * p) == -1) {
   
		puts("2");
	}
	else {
   
		printf("%lld\n", ans);
	}
	return 0;
}

D. Send More Money

Problem

Solution

其实就是一个字符向数字的映射，每一字母映射一个 $0\sim 9$ 的数字，不能重复。显然如果出现的字母种类超过10就 $NO$ 。数据保证不超过 $10$ ，所以可以直接全排列每个字母匹配的数字是谁，暴力匹配，找到合法的答案就输出。

Time

$O(10!\times 10)$

Code

// Problem: D - Send More Money
// Contest: AtCoder - AtCoder Beginner Contest 198
// URL: https://atcoder.jp/contests/abc198/tasks/abc198_d
// Memory Limit: 1024 MB
// Time Limit: 5000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

using namespace std;
#define int long long
const int N = 50007;
int mp[N];
int n, m, cnt;
string s[N];
int Ni[N];
bool zero;
int Hash[N];

void init() 
{
   
	for(int i = 1; i <= 10; ++ i) 
		Hash[i] = i - 1;
}

int work(string s)
{
   
	int res = 0;
	if(Hash[mp[s[0] - 'a']] == 0) {
   
		zero = true;
		return -1;
	}
	for(char ch : s) 
		res = res * 10 + Hash[mp[ch - 'a']];
	return res;
}

signed main()
{
   
	init();
	for(int i = 1; i <= 3; ++ i) {
   
		cin >> s[i];
		for(auto ch : s[i]) {
   
			if(mp[ch - 'a'] == 0) {
   
				mp[ch - 'a'] = ++ cnt;
			}
		}
	}
	if(cnt > 10) {
   
		puts("UNSOLVABLE");
		return 0;
	}
	
	do {
   
		zero = false;
		for(int i = 1; i <= 3; ++ i) 
			Ni[i] = work(s[i]);
		if(zero == false && Ni[1] + Ni[2] == Ni[3]) {
   
			for(int i = 1; i <= 3; ++ i) 
				printf("%lld\n", Ni[i]);
			return 0;
		}
	} while(next_permutation(Hash + 1, Hash + 1 + 10));
	puts("UNSOLVABLE");
	return 0;
}

E. Unique Color

Problem

Solution

显然从 1 到结点 $x$ 的路径只有一条，我们直接从 1 开始DFS所有点即可，我们可以统计一下每种颜色的出现次数，如果当前搜到的的颜色只出现了一次，那么他就是一个好点。

Time

$O(n)$

Code

// Problem: E - Unique Color
// Contest: AtCoder - AtCoder Beginner Contest 198
// URL: https://atcoder.jp/contests/abc198/tasks/abc198_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

using namespace std;

const int N = 500007;

int head[N], ver[N], edge[N], nex[N], tot;
int n, m, col[N], cnt[N];
vector <int> ans;

void add(int x, int y)
{
   
	ver[tot] = y;
	nex[tot] = head[x];
	head[x] = tot ++ ;
}

void dfs(int x, int fa) 
{
   
	if(cnt[col[x]] == 1) {
   
		ans.push_back(x);
	}
	for(int i = head[x]; ~i; i = nex[i]) {
   
		int y = ver[i];
		cnt[col[y]] ++ ;
		if(y != fa)
			dfs(y, x);
		cnt[col[y]] -- ;
	}
}

int main()
{
   
	memset(head, -1, sizeof head);
	scanf("%d", &n);
	for(int i = 1; i <= n; ++ i) {
   
		scanf("%d", &col[i]);
	}
	for(int i = 1; i <= n - 1; ++ i) {
   
		int x, y;
		scanf("%d%d", &x, &y);
		add(x, y);
		add(y, x);
	}
	cnt[col[1]] ++ ;
	dfs(1, 0);
	sort(ans.begin(), ans.end());
	for(auto it : ans) 
		printf("%d\n" ,it);
	return 0;
}

F. Cube

Problem

Solution

显然就是一道旋转同构的Polya定理模板题。

Polya定理：

对于一个置换 $f$，$C(f)=k^{m(f)}$，其中 $k$ 为颜色数，$m(f)$ 为 $f$ 的循环节。

在置换群中，等价类个数（方案数）等于所有置换 $f$ 的 $k^{m(f)}$ 的平均数。

骰子只有旋转这一种置换，可以上下旋转或者左右旋转90° / 180°，所以我们只需要处理出来所有和为 $S$ 的数，找到所有置换的循环节个数用Polya定理算一下即可。

对于一个骰子🎲

1对6，2对5，3对4.

我们任意选择两个面的中心轴为转轴顺时针旋转90°，例如我们选择1和6，显然$(2,3,4,5)$ 是一个循环节，即 $2,3,4,5$ 面上的数字相同，1，6面上的数字不一定要相同，所以我们设1面上的数字为 $x$ ，6面上的数字为 $y$，2面上的数字为 $z$ ，则： $x+y+4z=s$。

一共分为24种置换

• 不旋转（一种）
  那么6面的权值可以相同可以不同，问题就变成了将 $s$ 分为 $6$ 份，不能为零的方案数，使用隔板法显然不动点一共有 $C_{s-6+6-1}^{6-1}=C_{s-1}^5$

• 转轴为垂直两个相对的面，顺时针旋转90°，顺时针旋转270°（$2\times 3=6$ 种）

• 转轴为垂直两个相对的面，顺时针旋转180°（$3$ 种）

• 转轴为对角线，顺时针旋转120°，顺时针旋转240°$（2\times 4=8$ 种）

• 转轴为边的中心与立方体中心，顺时针旋转180°（$\frac{12}{2}=6$ 种）

一共为 $1+6+3+8+6=24$ 种置换

分别计算一下每种置换有多少种分配方式（和为 $s$），答案就是平均值，即累加起来除以 $24$ 即可。

（要上课了…写不完了…题解晚上上完课再更…

Time

$O(logs)$

Code

转载：https://blog.csdn.net/weixin_45697774/article/details/115619446