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;
}