B - Dentist Aoki
难度: ⭐
题目大意
现在有数列1 ~ n, 现在有m次操作, 每次给出一个x, 如果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, inf = 131;
typedef pair<int, int> PII;
int n, m;
int p[N], f[N];
signed main(){
IOS;
cin >> n >> m;
for(int i = 1; i <= m; i++){
int x;
cin >> x;
if(f[x]) n++;
else n--;
f[x] = !f[x];
}
cout << n;
return 0;
}
C - Sort
难度: ⭐⭐
题目大意
现在有一个乱序的数列A, A由1 ~ n组成; 我可以选择两个位置并把这两个位置上的数字互换, 请问最少进行多少次这种操作可以把A变成有序的;
解题思路
也是打暴力, 用数组p[i] = x表示第i个位置上的数字是x, f[x] = i表示数字x的位置是i; 我们从1 ~ n遍历, 依序调整数字位置即可;
神秘代码
#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, inf = 131;
typedef pair<int, int> PII;
int n, m;
int p[N], f[N];
vector<PII> v;
signed main(){
IOS;
cin >> n;
for(int i = 1; i <= n; i++){
int x;
cin >> x;
p[i] = x;
f[x] = i;
}
int num = 0;
for(int i = 1; i <= n; i++){
if(p[i] != i){
v.push_back({i, f[i]});
num++;
int u = p[i];
p[f[i]] = u;
p[i] = i;
f[u] = f[i];
f[i] = i;
}
}
cout << num << endl;
for(auto x : v){
cout << x.first << ' ' << x.second << endl;
}
return 0;
}
D - New Friends
难度: ⭐⭐⭐
题目大意
现在有n个人, 其中有m对朋友; 如果A和B是朋友, B和C是朋友, 但是A和C不是朋友, 那么我们就可以介绍A和C成为朋友; 并且此后就把A和C视为朋友关系; 请问我们最多可以介绍多少对人成为朋友;
解题思路
如果朋友之间用边相连的话, 题目问的就是我们可以在基础上多连多少条边; 根据题意我们发现一个连通块的里的点都可以相互成为朋友; 一个n个点的连通块最多有n * (n - 1) / 2条边, 减去原本存在的边就是我们可以连的边了; 用并查集标记连通块;
神秘代码
#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, inf = 131;
typedef pair<int, int> PII;
int n, m;
int p[N];
bool st[N];
map<int, int> mp1, mp2;
vector<int> v[N];
int find(int x){
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
signed main(){
IOS;
cin >> n >> m;
for(int i = 1; i <= n; i++) p[i] = i;
for(int i = 1; i <= m; i++){
int a, b;
cin >> a >> b;
v[a].push_back(b);
if(find(a) != find(b)){
p[find(b)] = find(a);
}
}
for(int i = 1; i <= n; i++){
int a = find(i);
mp1[a]++;
mp2[a] += v[i].size();
}
int res = 0;
for(auto x : mp1){
int a = x.first, b = x.second;
int sum = b * (b - 1) / 2 - mp2[a];
res += sum;
}
cout << res;
return 0;
}
E - Toward 0
难度: ⭐⭐⭐
题目大意
给定一个值n, 我们有两种选择
一是花费X元, 让n变成n / A(向下取整);
二是花费Y元, 扔一个骰子, 设B是骰子的点数结果, 让n变成n / B(向下取整);
请问让n变成0的最少期望花费;
解题思路
概率dp, 设dp[i]表示让i变成0的最少期望花费;
根据选择一, dp[i] = dp[i / A] + X;
然后看选择二的期望: dp[i] = dp[i] / 6 + dp[i / 2] / 6 + dp[i / 3] / 6 + dp[i / 4] / 6 + dp[i / 5] / 6 + dp[i / 6] / 6 + Y; 移项化简得dp[i] = 5 * dp[i / 2] + 5 * dp[i / 3] + 5 * dp[i / 4] + 5 * dp[i / 5] + 5 * dp[i / 6] + 6 * Y / 5;
两者取最小即可; 本题的另一难点在于n的范围在1e18; 所以要挑选出所有可能遇到的i的值拿来状态转移, 可以用dfs加记忆化搜索;
神秘代码
#include<bits/stdc++.h>
#define int unsigned 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, inf = 131;
typedef pair<int, int> PII;
int n, m, A, B, res;
int p[N];
map<int, double> dp;
map<int, int> mp;
set<int> s;
void dfs(int u){
s.insert(u);
mp[u] = 1;
for(int i = 2; i <= 6; i++){
if(u / i != 0&& mp[u / i] == 0) dfs(u / i);
}
}
signed main(){
cin >> n >> m >> A >> B;
dfs(n);
dp[0] = 0;
while(s.size()){
int x = *s.begin();
if(x > n) break;
s.erase(x);
dp[x] = dp[x / m] + A;
double sum = 0;
for(int i = 2; i <= 6; i++){
sum += dp[x / i] / 5;
}
sum += (6.0 * B) / 5;
dp[x] = min(dp[x], sum);
}
printf("%.9lf", dp[n]);
return 0;
}