Codeforces Round 928 (Div. 4)

Codeforces Round 928 (Div. 4) (A~E)-CSDN博客

Codeforces Round 928 (Div. 4) (A~E)

目录：A B C D E

A题：Vlad and the Best of Five

标签: 实现问题，编程技巧，模拟（implementation）

题目大意

• 有一个长度为 5的字符串，每个字符都是 A或 B 。
• 问：哪个字母出现的频率最高？ A 还是 B ？

思路

• 暴力即可

AC代码

#include<bits/stdc++.h>
using namespace std;
void solve(){
	string s; 
	cin >> s;
    int cnt = 0;
    for(int i = 0; i < 5; i++)
		if(s[i] == 'A') cnt++;
    puts(cnt >= 3 ? "A" : "B");
} 
int main(){
	int T; cin >> T;
	while(T--) 
		solve();
}

B题：Vlad and Shapes

标签: 实现问题，编程技巧，模拟（implementation）

题目大意

• 有一个由 n×n正方形网格。网格上画有三角形或正方形，符号为 1 。
• 问：网格上画的是哪个形状。

思路

• 判断是否有连续两行有不同数量的1，有就是三角形

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N = 20;
int a[N];
void solve(){
    int n; cin >> n;
    for(int i = 0; i < n; i++)
		cin >> a[i];
	int t = 0;
	for(int i = 0; i < n; i++)
	{
		if(a[i] != 0 && t != 0 && a[i] != t)
		{
			cout << "TRIANGLE\n";
			return;
		}
		t = a[i];
	}
	cout << "SQUARE\n";
} 
int main(){
	int T; cin >> T;
	while(T--) 
		solve();
}

C题：Vlad and a Sum of Sum of Digits

标签: 前缀和，动态规划（dp）实现问题，编程技巧，模拟（implementation）

题目大意

• 将1~n每个整数替换为其数位之和。(1≤n≤2⋅10^5^)
• 多次求前n项和

思路

• 暴力将前2⋅10^5^内的数替换为其数位之和
• 求前缀和保存在 ans数组中，每次求前n项和直接输出 ans[n] 即可

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N = 200010;
int ans[N];
void solve(){
    int n; cin >> n;
    cout << ans[n] << "\n";
} 
int main(){
	for(int i = 1; i <= 200000; i++){
    	int t = 0;
	    for(int j = i; j ; j /= 10)
			t += j % 10;
	    ans[i] = ans[i-1] + t;
  	}
	int T; cin >> T;
	while(T--) 
		solve();
}

D题：Vlad and Division

标签: 位掩码（bitmasks）贪心（greedy）

题目大意

• 有n个非负整数，对这n个数分组，分组规则如下：
• 对于同一组中的任意两个数 x 和 y ，条件 x2(i) ≠ y2(i) 必须对所有的 1≤i<32成立，其中x2(i) 表示x转化为二进制数的第 i 位

思路

• 转化为二进制每位是1或0，两种情况，两个数二进制每位(31位)都不同，那么这两个数之和一定为
• 1111111111111111111111111111111(二进制) = 2147483647
• 即：对于同一组中的任意两个数 x 和 y，满足x + y == 2147483647
• 由于2147483647是奇数所以同一组中也不可能出现两个相同数字

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N = 200010;
int a[N], cnt[N];
void solve(){
    int n; cin >> n;
    map<int, int> cnt;
    for(int i = 1; i <= n; i++)
		cin >> a[i], cnt[a[i]]++;
    int ans = 0;
    for(int i = 1; i <= n; i++)
    { 
		ans += max(cnt[a[i]], cnt[2147483647 - a[i]]);
		cnt[a[i]] = cnt[2147483647 - a[i]] = 0;
	}
    cout << ans << '\n';
} 
int main(){
	int T; cin >> T;
	while(T--) 
		solve();
}

E题：Vlad and an Odd Ordering

标签: 二分搜索（binary search）位掩码（bitmasks）数据结构（data structures）动态规划（dp）实现问题，编程技巧，模拟（implementation）数学（math）

题目大意

• 有编号为 1,2,…,n的n 张牌，把这些牌按如下方式排成一排
• 1. 首先，他把所有奇数牌从小到大依次铺开。
• 2. 接着，放下所有从小到大是奇数i倍的牌(即 2 乘以一个奇数)。
• 3. 接着，放下所有从小到大是奇数的 3 倍(即 3 乘以奇数)的牌。
• 4. 接着，放下所有从小到大 4 乘以一个奇数(即 4 乘以一个奇数)的牌。
• 5. 依此类推，直到所有的牌都放下为止。
• 问：放下的第 k张牌是什么？

思路

• 手动模拟一下

• 

• 可以看出只有第1 2 4 16 32…轮才可能放下牌，并且放下的牌构成等差数列公差为2 * cnt

AC代码

#include <bits/stdc++.h>
using namespace std;
void solve()
{
	int n, k;
	cin >> n >> k;
    //第cnt轮
	int cnt = 1;
	while(true) 
	{
        // 第cnt轮放下的牌数
        int now = (n / cnt + 1) / 2;
		if(now >= k)
		{
            //等差数列首项为cnt，公差为cnt * 2
            //输出第k项
			cout << cnt + (k-1) * cnt * 2 << endl;
			return;
		}
		k -= now;
        //下一轮放牌为第cnt * 2轮
		cnt *= 2;
	}
} 
int main()
{
	int T; cin >> T;
	while(T--)
		solve();
	return 0;
}

logo

//へ　　　　　／|
//　　/＼7　　　 ∠＿/
//　 /　│　　 ／　／
//　│　Z ＿,＜　／　　 /`ヽ
//　│　　　　　ヽ　　 /　　〉
//　 Y　　　　　`　 /　　/
//　ｲ●　､　●　　⊂⊃〈　　/
//　()　 へ　　　　|　＼〈
//　　>ｰ ､_　 ィ　 │ ／／
//　 / へ　　 /　ﾉ＜| ＼＼
//　 ヽ_ﾉ　　(_／　 │／／
//	　　7　　　　　　　|／
//

/*
          __   _,--="=--,_   __
         /  \."    .-.    "./  \
        /  ,/  _   : :   _  \/` \
        \  `| /o\  :_:  /o\ |\__/
         `-'| :="~` _ `~"=: |
            \`     (_)     `/
     .-"-.   \      |      /   .-"-.
.---{     }--|  /,.-'-.,\  |--{     }---.
 )  (_)_)_)  \_/`~-===-~`\_/  (_(_(_)  (
(                         				)
 )                                     (
'---------------------------------------'
*/