B - Pentagon
难度: ⭐
题目大意
给定一个正五边形, 其顶点为ABCDE; 给定端点a, b, c, d; 问a, b之间的距离和c, d之间的距离是否相等;
解题思路
两个端点之间的距离就看两个端点之间隔了几条边就行; 并且因为是五边形, 隔x条边和隔5-x条边是等价的;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
using namespace std;
const int N = 1e6 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, k;
signed main() {
char a, b, c, d;
cin >> a >> b >> c >> d;
int d1 = abs(a - b);
int d2 = abs(c - d);
if(d1 == d2 || d1 + d2 == 5) cout << "Yes";
else cout << "No";
return 0;
}
C - Repunit Trio
难度: ⭐
题目大意
定义一个数列是由{1, 11, 111, 1111...}组成, 从中选择3个数相加(可以重复), 可以再得到一个数列; 问这个数列中第n小的数是多少;
解题思路
因为n最大为333, 由样例可得是一个12位的数; 那么我们可以之间三重循环暴力即可;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
using namespace std;
const int N = 1e6 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, k;
set<int> s;
int idx = 111111111111;
signed main() {
cin >> n;
for(int i = 1; i <= idx; i = i * 10 + 1){
for(int j = i; j <= idx; j = j * 10 + 1){
for(int h = j; h <= idx; h = h * 10 + 1){
s.insert(i + j + h);
}
}
}
auto p = s.begin();
for(int i = 1; i < n; i++) p++;
cout << *p;
return 0;
}
D - Erase Leaves
难度: ⭐⭐⭐
题目大意
给定一个无向树, 我们可以进行如下操作: 选择其中一个叶子节点并且删除它, 也就是把与该叶子节点的边删除; 问我们最少进行多少次操作后可以删除节点1;
解题思路
这题就是问需要进行多少次操作后可以让节点1变成叶子节点; 我们可以把1看作根节点, 设它有n个子树, 那么我们需要删除其中(n-1)个子树才可以让其变成叶子节点, 所以我们可以找出节点数最多的一个子树, 删除除了它之外的所有子树即可; 因为有3e5个节点, 我担心dfs会爆栈, 所以就没用递归, 而是采用kruskal的思想, 用边来遍历每个节点; 每个子树都可以看作一个连通块, 用并查集来维护每个连通块的节点数量即可;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
using namespace std;
const int N = 3e5 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, k;
vector<int> v;
int p[N];
map<int,int> mp;
int find(int x){
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
signed main() {
cin >> n;
for(int i = 1; i <= n; i++) p[i] = i;
for(int i = 1; i < n; i++){
int a, b;
cin >> a >> b;
if(a != 1 && b != 1){
if(find(a) != find(b)){
p[find(b)] = find(a);
}
}
}
int maxn = 0;
for(int i = 2; i <= n; i++){
mp[find(i)]++;
maxn = max(maxn, mp[find(i)]);
}
cout << n - maxn;
return 0;
}
E - Takahashi Quest
难度: ⭐⭐⭐
题目大意
现在有一个长度为n的走廊, 每个格子都随机产生一个武器或者怪兽, 注意小莫同时拥有多种武器; 其属性为(x, y); 如果x为1, 则是武器, 为2, 则是怪兽; 只有y类的武器才能击败y类的怪兽; 设k是整个过程中某个时刻小莫拥有武器的最大数量; 请问在通关的前提下, k的最小值是多少, 并且给出所有武器的拾取情况, 1是拾取, 2是不拾取;
解题思路
既然要求小莫要尽量少地积累武器, 所以我们拾取武器后要尽快的用出去, 尽量不要累计; 所以基础策略就是对于一个怪兽, 我们要拾取距离其最近的武器来对付; 我们可以用一个数组p[y]表示当前最靠前的y类武器在第几个格子; 设第i个格子上的武器种类是y, 那么pre[i]表示距离i最近的武器种类为y的位置在第几个格子; 这样我们就可以用p[y]和pre[i]来实现对应武器位置的定位;
当第i个位置的武器种类为b, 那么更新方式为pre[i] = p[b]; p[b] = i;
当第i个位置的怪兽种类为b, 那么更新方式为p[b] = pre[p[b]];
而对于k的数量, 我们直接遍历这n个格子, 如果拾取该武器就+1, 如果遇到怪兽就-1, 每次都更新一下最大值即可;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
using namespace std;
const int N = 2e5 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, k;
int p[N], mk[N], pre[N];
bool st[N];
signed main() {
cin >> n;
for(int i = 1; i <= n; i++){
int a, b;
cin >> a >> b;
mk[i] = a;
if(a == 1){
pre[i] = p[b];
p[b] = i;
}
else {
if(p[b]) {
st[p[b]] = true;
p[b] = pre[p[b]];
}
else {
cout << -1;
return 0;
}
}
}
int maxn = 0, x = 0;
for(int i = 1; i <= n; i++){
if(mk[i] == 1 && st[i]) x++;
else if(mk[i] == 2) x--;
maxn = max(maxn, x);
}
cout << maxn << endl;
for(int i = 1; i <= n; i++){
if(mk[i] == 1){
if(st[i]) cout << 1 << ' ';
else cout << 0 << ' ';
}
}
return 0;
}
F - Bomb Game 2
难度: ⭐⭐⭐⭐
- Beginner AtCoder Contest 333beginner atcoder contest 333 contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 328 beginner atcoder contest 334 beginner atcoder contest 332 beginner atcoder contest 327