Codeforces Round 937 (Div. 4) A - F 题解

2024-03-29 09:14:04
开发
16

A. Stair, Peak, or Neither?

题解：直接比较输出即可。

代码：

#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
const int maxn = 2e5 + 7 ;
const int mod = 1e9 + 7 ;
inline ll read() {
	ll x = 0, f = 1 ;
	char c = getchar() ;
	while (c > '9' || c < '0') {
		if (c == '-')
			f = -1 ;
		c = getchar() ;
	}
	while (c >= '0' && c <= '9') {
		x = x * 10 + c - '0' ;
		c = getchar() ;
	}
	return x * f ;
}
char s[maxn] ;
ll t , n , d , k , a[maxn] , ans[maxn] ;
struct Node{
	ll val , id ;
	bool friend operator < (const Node a , const Node b){
		return a.val < b.val ;
	}
}b[maxn];
ll sum[maxn] ;
void solve(){
	n = read() ;
	d = read() ;
	k = read() ;
	if(n < d && d < k){
		cout <<"STAIR" << endl ;
		return ;
	}
	if(n < d && d > k){
		cout << "PEAK" << endl ;
		return ;
	}
	cout << "NONE" << endl ;
}
int main(){
	t = read() ;
	while(t --){
		solve() ;
	}
	return 0 ;
}

B. Upscaling

题解：直接模拟输出即可。

代码：

#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
const int maxn = 2e5 + 7 ;
const int mod = 1e9 + 7 ;
inline ll read() {
	ll x = 0, f = 1 ;
	char c = getchar() ;
	while (c > '9' || c < '0') {
		if (c == '-')
			f = -1 ;
		c = getchar() ;
	}
	while (c >= '0' && c <= '9') {
		x = x * 10 + c - '0' ;
		c = getchar() ;
	}
	return x * f ;
}
char s[maxn] ;
ll t , n , d , k , a[maxn] , ans[maxn] ;
struct Node{
	ll val , id ;
	bool friend operator < (const Node a , const Node b){
		return a.val < b.val ;
	}
}b[maxn];
ll sum[maxn] ;
void solve(){
	n = read() ;
	for(int i = 1 ; i <= n ; i ++){
		if(i % 2 == 1){
			bool f = 1 ;
			for(int j = 1 ; j <= n ; j ++){
				if(f == 1){
					cout << "##" ;
					f = 0 ;
				}
				else{
					cout << ".." ;
					f = 1 ;
				}
			}
			cout << endl ;
			f = 1 ;
			for(int j = 1 ; j <= n ; j ++){
				if(f == 1){
					cout << "##" ;
					f = 0 ;
				}
				else{
					cout << ".." ;
					f = 1 ;
				}
			}
			cout << endl ;
		}
		else{
			bool f = 0 ;
			for(int j = 1 ; j <= n ; j ++){
				if(f == 1){
					cout << "##" ;
					f = 0 ;
				}
				else{
					cout << ".." ;
					f = 1 ;
				}
			}
			cout << endl ;
			f = 0 ;
			for(int j = 1 ; j <= n ; j ++){
				if(f == 1){
					cout << "##" ;
					f = 0 ;
				}
				else{
					cout << ".." ;
					f = 1 ;
				}
			}
			cout << endl ;
		}
	}
}
int main(){
	t = read() ;
	while(t --){
		solve() ;
	}
	return 0 ;
}

C. Clock Conversion

题意：让你将二十四小时制转成十二小时制。

题解：多注意细节，判断输出即可。

代码：

#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
const int maxn = 2e5 + 7 ;
const int mod = 1e9 + 7 ;
inline ll read() {
	ll x = 0, f = 1 ;
	char c = getchar() ;
	while (c > '9' || c < '0') {
		if (c == '-')
			f = -1 ;
		c = getchar() ;
	}
	while (c >= '0' && c <= '9') {
		x = x * 10 + c - '0' ;
		c = getchar() ;
	}
	return x * f ;
}
ll t , n , d , k , a[maxn] , ans[maxn] ;
struct Node{
	ll val , id ;
	bool friend operator < (const Node a , const Node b){
		return a.val < b.val ;
	}
}b[maxn];
ll sum[maxn] ;
char s[maxn] ;
void solve(){
	scanf("%s" , s + 1) ;
	if(s[1] == '0'){
		if(s[2] == '0'){
			cout << "12" << ":" << s[4] << s[5] << " " ;
			cout << "AM" << endl ;
		}
		else{
			cout << s[1] << s[2] << ":" << s[4] << s[5] << " " ;
			cout << "AM" << endl ;
		}
	}
	else{
		ll sum = s[1] - '0' ;
		sum = sum * 10 + (s[2] - '0') ;
		if(sum < 12){
			cout << s[1] << s[2] << ":" << s[4] << s[5] << " " << "AM" << endl ;
			return ;
		}
		if(sum == 12){
			cout << s[1] << s[2] << ":" << s[4] << s[5] << " " ;
			cout << "PM" << endl ;
		}
		if(sum > 12){
			if(sum - 12 < 10){
				cout << 0 ;
			}
			cout << sum - 12 << ":" << s[4] << s[5] << " " ;
			cout << "PM" << endl ;
		}
	}
}
int main(){
	t = read() ;
	while(t --){
		solve() ;
	}
	return 0 ;
}

D. Product of Binary Decimals

**题意：问给你一个数字，看能否将数字变成 $a_1 * a_2 * ... * a_n == x$ 的形式，a数组必须保证是二进制数字。**

题解：看起来很复杂，但是你会发现， $n <= 200000$ 的数字，最多就有6位数字，那么很简单，直接枚举数字从n - 1 到 2，看看数字是否符合二进制数字的限制，如果符合并且能够整除n，那么就除尽为止，最后判断一下数字是否为二进制数字即可。复杂度 $O(6 * n)$

代码：

#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
const int maxn = 2e5 + 7 ;
const int mod = 1e9 + 7 ;
inline ll read() {
	ll x = 0, f = 1 ;
	char c = getchar() ;
	while (c > '9' || c < '0') {
		if (c == '-')
			f = -1 ;
		c = getchar() ;
	}
	while (c >= '0' && c <= '9') {
		x = x * 10 + c - '0' ;
		c = getchar() ;
	}
	return x * f ;
}
ll t , n , d , k , a[maxn] , ans[maxn] ;
struct Node{
	ll val , id ;
	bool friend operator < (const Node a , const Node b){
		return a.val < b.val ;
	}
}b[maxn];
ll sum[maxn] ;
char s[maxn] ;
bool check(ll x){
	while(x){
		ll res = x % 10 ;
		if(res == 0 || res == 1){
			x /= 10 ;
		}
		else{
			return 0 ;
		}
	}
	return 1 ;
}
vector < ll > q ;
void solve(){
	n = read() ;
	ll N = n ;
	if(check(n)){
		cout << "YES\n" ;
		return ;
	}
	for(auto it : q){
		if(it < N){
			while(N % it == 0){
				N /= it ;
			}
		}
	}
	if(check(N)){
		cout << "YES\n" ;
	}
	else{
		cout << "NO\n" ;
	}
}
int main(){
	t = read() ;
	for(ll i = 100000 ; i >= 2 ; i --){
		if(check(i)){
			q.push_back(i) ;
		}
	}
	while(t --){
		solve() ;
	}
	return 0 ;
}

E. Nearly Shortest Repeating Substring

题意：给你一个字符串n，能否找到最小的字符串k，将字符串k粘贴x遍，使长度和n相同，并且满足做多只有一个字符不同的最小字符串是什么？

题解：很明显，枚举因数存在set中，然后判断能否找到最多只有一个不同的字符串即可。

代码：

#include<bits/stdc++.h>
using namespace std ;
#define int long long
const int maxn = 2e5 + 7 ;
inline int read() {
	int x = 0, f = 1 ;
	char c = getchar() ;
	while (c > '9' || c < '0') {
		if (c == '-')
			f = -1 ;
		c = getchar() ;
	}
	while (c >= '0' && c <= '9') {
		x = x * 10 + c - '0' ;
		c = getchar() ;
	}
	return x * f ;
}
int n , t ;
string s ;
void solve(){
	n = read() ;
	cin >> s ;
	set < int > st ;
	for(int i = 1 ; i <= (int)sqrt(n) ; i ++){
		if(n % i == 0){
			st.insert(i) ;
			st.insert(n / i) ;
		}
	}
	int ans = n ;
	for(auto it : st){
		map < string , int > mp ;
		for(int i = 0 ; i <= n - it ; i += it){
			string x ;
			for(int j = i ; j < i + it ; j ++){
				x.push_back(s[j]) ;
			}
			mp[x]++ ;
		}
		if(mp.size() == 1){
			ans = min(ans , it) ;
			break ;
		}
		if(mp.size() == 2){
			vector < string > zz ;
			bool ok = 0 ;
			for(auto [a , b] : mp){
				zz.push_back(a) ;
				if(b == 1)
					ok = 1 ;
			}
			if(!ok)
				continue ;
			int cnt = 0 ; 
			for(int i = 0 ; i < it ; i++){
				if(zz[0][i] != zz[1][i])
					cnt ++ ;
			}
			if(cnt <= 1){
				ans = min(ans , it) ;
				break ;
			}
		}
	}
	cout << ans << endl ;
}
int main()
{
	t = read() ;
	while(t --){
		solve() ;
	}
}

F. 0, 1, 2, Tree!

题意：给你三个数字a,b,c，a表示有a个点有两个孩子，b表示有b个点有一个孩子，c表示有c个点有0个孩子，问能否构建符合条件的有根树（有根树是一个没有循环的连通图，有一个称为根的特殊顶点。在有根树中，在由一条边连接的任意两个顶点中，一个顶点是父顶点（靠近根的顶点），另一个顶点是子顶点。）。

题解：我们分情况讨论，首先先看为-1的情况，如果说一个树的根总数不等于c，那么一定无解。如果a为0，那么很明显如果c不等于1，那么一定无解。如果c等于1，那么答案显然就是b。那么如果a不为0，我们可以累加2的次方，看看加到2的第多少次幂会超出a，假设加到第i次幂大于等于a，如果是正好等于a,那么层数为i，否则层数为i + 1。然后再看最后一层一共有多少个孩子，说正好等于a，那么孩子的数量就是2的i次方，如果不等于a，那么答案就是2的i + 1次方减去前面的总和加上2的i次方减去n，最后看b，如果前面累加不等于a，那么就先把上一层填满，再往下填即可。

注：整道题思维量比较大，代码很简单。希望大家能耐心读完！

代码：

#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
const int maxn = 2e5 + 7 ;
const int mod = 1e9 + 7 ;
inline ll read() {
	ll x = 0, f = 1 ;
	char c = getchar() ;
	while (c > '9' || c < '0') {
		if (c == '-')
			f = -1 ;
		c = getchar() ;
	}
	while (c >= '0' && c <= '9') {
		x = x * 10 + c - '0' ;
		c = getchar() ;
	}
	return x * f ;
}
char s[maxn] ;
ll t , n , d , k , a[maxn] , ans[maxn] ;
struct Node{
	ll val , id ;
	bool friend operator < (const Node a , const Node b){
		return a.val < b.val ;
	}
}b[maxn];
ll Pow(ll x , ll y){
	ll cnt = 1 ;
	while(y){
		if(y % 2)
			cnt = cnt * x ;
		x = x * x ;
		y >>= 1 ;
	}
	return cnt ;
}
ll sum[maxn] ;
void solve(){
	n = read() ;
	d = read() ;
	k = read() ;
	if(n == 0){
		if(k != 1){
			cout << -1 << endl ;
			return ;
		}
		else{
			cout << d << endl ;
			return ;
		}
	}
	ll ans = 0 , sum = 0 , ceng = 1 , ress , rt ;
	for(int i = 0 ; i <= 32 ; i ++){
		ll xx = Pow(2 , (ll)i) ;
		if(ans + xx <= n){
			ans += xx ;
		}
		else{
			if(ans == n){
				sum = Pow(2 , (ll)i) ;
				rt = 0 ;
				ceng = i ;
			}
			else{
				sum = Pow(2 , (ll)(i + 1)) - (ans + Pow(2 , (ll)i) - n) ;	
				rt = Pow(2 , (ll)(i)) - (n - ans) ;
				ceng = i + 1 ;
			}
			break ;
		}
	}
//	cout << rt << endl ;
	if(sum != k){
		cout << -1 << endl ;
		return ;
	}
	else{
		ll B = d ;
		if(B - rt <= 0){
			cout << ceng << endl ;
			return ;
		}
		else{
			B -= rt ;
			while(B > 0){
				B -= sum ;
				ceng ++ ;
			}
			cout << ceng << endl ;
		}
	}
	
}
int main(){
	t = read() ;
	while(t --){
		solve() ;
	}
	return 0 ;
}

如果喜欢作者的记得点赞收藏加关注哦~

原文地址:https://blog.csdn.net/m0_63322121/article/details/137128986 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：https://www.suanlizi.com/kf/1773518954397044736.html 如若内容造成侵权/违法违规/事实不符，请联系《酸梨子》网邮箱：1419361763@qq.com进行投诉反馈，一经查实，立即删除！

阅读全部