B - Roulette
难度: ⭐
题目大意
有一个猜数字的游戏, 有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 = 2e5 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, idx;
int c[N];
set<int> s[N];
vector<int> v;
bool cmp(int a, int b) {
if (c[a] == c[b]) return a < b;
return c[a] < c[b];
}
signed main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> c[i];
for (int j = 1; j <= c[i]; j++) {
int x;
cin >> x;
s[i].insert(x);
}
}
cin >> idx;
for (int i = 1; i <= n; i++) {
if (s[i].count(idx)) v.push_back(i);
}
if (v.empty()) {
cout << 0 << endl;
return 0;
}
sort(v.begin(), v.end(), cmp);
int minn = c[*v.begin()];
for (int i = 0; i < v.size(); i++) {
if (c[v[i]] == minn) m++;
else break;
}
cout << m << endl;
for (int i = 0; i < m; i++) {
cout << v[i] << " ";
}
return 0;
}
C - Rotate Colored Subsequence
难度: ⭐⭐
题目大意
给定一个长度为你的由小写字母组成的字符串; 每个字符都有一个颜色; 我们让同颜色的字符首尾相连地向右移动一位; eg: abcdef的颜色为111233, 操作完之后变成了cabdfe;
解题思路
开一个数组c, c[i]表示下一个颜色为i的字符要替换为c[i]; 我们把每个颜色中最靠前的字符的下标存一下, 最后更新他们即可; 这样就可以线性地更新完所有字符;
神秘代码
#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, idx;
int f[N], la[N];
char c[N];
signed main(){
cin >> n >> m;
string s;
cin >> s;
for (int i = 0; i < n; i++) cin >> f[i];
for (int i = 0; i < n; i++) {
if (!c[f[i]]) {
c[f[i]] = s[i];
la[f[i]] = i;
}
else {
char x = c[f[i]];
c[f[i]] = s[i];
s[i] = x;
}
}
for (int i = 1; i <= m; i++) {
s[la[i]] = c[i];
}
cout << s;
return 0;
}
D - LOWER
难度: ⭐⭐⭐
题目大意
给定一个由大小写字母组成的字符串; 进行m次操作(t,a,b): 如果t=1, 就把a这个位置的字符换成b; 如果t=2就把所有大写字母变成小写; 如果t=3就把所有小写字母变成大写; 输出最后的字符串;
解题思路
本题的处理难点在于由于数据范围较大, 我们不能每次输入都接着操作, 只能是读取所有操作之后最后进行处理; 这样的难点就是如果我们先t=2, 此时所有字符都是小写字母, 然后在t=1替换一个为一个大写字母; 因为我们最后一直处理一次, 所以这种状态是难以标记的; 所以我们当t=1时, 我们可以记录这次操作是第几个操作, 因为t=2和t=3是相互抵消的, 所以我们只需要记录最后一次last即可; 当t=1的操作顺序在last之后就不需要改变大小写了;
神秘代码
#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 = 5e5 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, idx;
int sp;
int nu[N];
signed main(){
string s;
cin >> n >> s;
s = ' ' + s;
cin >> m;
for(int i=1;i<=m;i++) {
int a, b;
char c;
cin >> a >> b >> c;
if (a == 1) {
s[b] = c;
nu[b] = i;
}
else if (a == 2) {
sp = 1;
idx = i;
}
else {
sp = 2;
idx = i;
}
}
for (int i = 1; i <= n; i++) {
if (nu[i] > idx) continue;
else {
if (sp == 1 && isupper(s[i])) s[i] += 32;
if (sp == 2 && islower(s[i])) s[i] -= 32;
}
}
for (int i = 1; i <= n; i++) cout << s[i];
return 0;
}
E - Roulettes
难度: ⭐⭐⭐⭐
题目大意
现在有n个箱子, 每个箱子都有各自的一个打开费用, 并且每个箱子里都有若干个卡片, 每个卡片都有一个分数; 小莫可以选择花费费用打开一个箱子, 并从中随机选择一个卡片, 然后就可以得到该卡片的分数, 然后把卡片放回箱子里; 问小莫想要得到m分所需要的最小费用期望是多少;
解题思路
初看以为是个概率dp, 然后就一直没找到什么思路, 看完题解后发现思路更像背包dp; 状态表示dp[i]: 表示得到i分数所需要的最小费用期望; 状态转移中我们先遍历分数k, 然后再遍历所有箱子和其里面卡片; 对于当前箱子的卡片, 设某个卡片的分数为x, 那么目前的状态可以用dp[max(0, k-x)]来转移, 我们把所有用于可以转移的dp[max(0, k-x)]求和取平均, 这就是最后用于转移的期望费用sum; 那么什么是可以用于可以转移的dp, 可以想一想, 如果当前箱子里的某张卡片的分数是0, 那么我们就是需要用dp[k-0]也是dp[k]本身, 这是没有意义的; 对于当前这个箱子, 我们拿到有意义卡片(即分数不为0)的概率是num/p[i], num是有意义卡片的数量; 所以我们抽到有意义卡片的期望就是c[i] * p[i] / num, 我们就让sum再加上c[i] * p[i] / num后和dp[k]取min即可;
神秘代码
#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 = 1e2 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, idx;
int s[N][N];
double dp[N];
int p[N], c[N];
signed main(){
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> c[i] >> p[i];
for (int j = 1; j <= p[i]; j++) {
cin >> s[i][j];
}
}
for (int i = 1; i <= m; i++) dp[i] = 1e9;
for (int k = 1; k <= m; k++) {
for (int i = 1; i <= n; i++) {
double x = 0;
double num = 0;
for (int j = 1; j <= p[i]; j++) {
if (s[i][j]) {
x += dp[max(0ll, k - s[i][j])];
num++;
}
}
x /= num;
x += c[i] * p[i] / num;
dp[k] = min(dp[k], x);
}
}
printf("%.30lf",dp[m]);
return 0;
}
F - A Certain Game
难度: ⭐⭐⭐⭐
- Beginner AtCoder Contest 314 abcbeginner atcoder contest 314 beginner atcoder contest abc 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 332 beginner atcoder contest 334