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