最近几周打了很多多场训练赛，都没有更新博客 实际上还是有做题的
周五
D.Artifacts（细节）
是一道挺简单的模拟题
注意一个细节
atoi和atof可以把char数组转化为int和double 很方便
但是注意这个函数是遇到‘\0’停止
有时候要自己加上
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;double ATK, ATKr, Cridr = 50, Crir = 5;int main()
{_for(i, 1, 25){string s, op, num;getline(cin, s);int pos = s.find('+');op = s.substr(0, pos);num = s.substr(pos + 1);if(num.back() == '%') num.pop_back();int len = num.size();char *str = new char[len + 1];rep(i, 0, len) str[i] = num[i];str[len] = '\0';double t = atof(str);if(op == "ATK") ATK += t;if(op == "ATK Rate") ATKr += t;if(op == "Crit Rate") Crir += t;if(op == "Crit DMG Rate") Cridr += t;}Crir = min(Crir, 100.0);ATKr /= 100;Cridr /= 100;Crir /= 100;ATK = 1500 * (1 + ATKr) + ATK;double E = ATK * (1 - (Crir)) + ATK * (1 + (Cridr)) * (Crir);printf("%.9lf\n", E);return 0;
}A - Girls Band Party （分组背包 + 细节）
这题比赛时是一个爆搜的做法，思路是对的，但是一直过不了
赛后发现有人就是爆搜过的，更多人是用dp过的
一个名字只能选一个，那就是分组背包了
与一般的背包不同，除了值还有一个加成
那就把这个加成到dp的维度中，这是常见的套路了
可以用滚动数组，我有点遗忘了
写的时候注意
（1） i j k这些位置不要写错，写完第一遍肉眼查错要查出来
（2）dp的统计答案最后不要写在dp的循环里面 另外写循环统计答案。这样比较稳 不要漏
（3）这题有很多状态是不合法的，所以要一开始全部设为负无穷
（4）注意一些细节
cnt = 0;_for(i, 1, cnt) ve[i].clear(), v[i] = 0;这种错误我已经犯了几次了 特别小心
到第二行的时候，cnt已经改变了
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 1e5 + 10;
int n, num[N], v[N], dp[6][20], cnt;
struct node { string s; int val; };
unordered_map<string, int> col, id;
vector<node> ve[N];int main()
{int T; scanf("%d", &T);while (T--) {cin >> n;_for(i, 1, n) {string name, co; int num;cin >> name >> co >> num;if(!id[name]) id[name] = ++cnt;ve[id[name]].push_back(node{co, num});}_for(i, 1, 5){string s; cin >> s;v[id[s]] = 1;}string s; cin >> s;col[s] = 2;_for(j, 0, 5)_for(k, 0, 15)dp[j][k] = -1e9;dp[0][0] = 0;_for(i, 1, cnt)for(int j = 5; j >= 1; j--)for(auto x: ve[i]){int add = v[i] + col[x.s];_for(k, add, 15)dp[j][k] = max(dp[j][k], dp[j - 1][k - add] + x.val); }int ans = 0;_for(i, 0, 15) if(dp[5][i] > 0)ans = max(ans, dp[5][i] * (10 + i) / 10);printf("%d\n", ans);col.clear();id.clear(); _for(i, 1, cnt) ve[i].clear(), v[i] = 0;cnt = 0;}return 0;
}E. Buy and Delete （最小环）
当时很快就推出了找最小环
然而我写了个错误的爆搜，一开始是错误的爆搜，后来写对了又T了
后来想到用dijstkra就行了
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;typedef long long ll;
const int N = 2e3 + 10;
struct node
{ int v; ll w; bool operator < (const node& rhs) const{return w > rhs.w;}
};
vector<node> g[N];
int vis[N], k[N], n, m, c, mi = 1e9;
ll dis[N][N], ans;void work(int s, ll d[])
{_for(i, 1, n) d[i] = 1e18;d[s] = 0;priority_queue<node> q;q.push(node{s, d[s]});while(!q.empty()){node x = q.top(); q.pop();int u = x.v;if(x.w != d[u]) continue;for(auto t: g[u]){int v = t.v; ll w = t.w;if(d[v] > d[u] + w){d[v] = d[u] + w;q.push(node{v, d[v]});}}}
}int main()
{scanf("%d%d%d", &n, &m, &c);while(m--){int u, v, w;scanf("%d%d%d", &u, &v, &w);g[u].push_back(node{v, w});mi = min(mi, w);}if(c < mi){puts("0");return 0;}_for(i, 1, n) work(i, dis[i]);ans = 1e18;_for(i, 1, n)_for(j, 1, n)if(i != j && dis[i][j] + dis[j][i] < ans)ans = dis[i][j] + dis[j][i];puts(c >= ans ? "2" : "1");return 0;
}G. Occupy the Cities（dp）
很容易看出来就是每一个1第一次往左还是往右
这个可以用dp来解决
dp[i][0] 表示第i个1选择往左，前缀实际最小值
dp[i][1]表示向右
dp就完事
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 1e6 + 10;
int a[N], dp[N][2], n;
vector<int> p;int main()
{int T; scanf("%d", &T);while(T--){p.clear(); p.push_back(0);scanf("%d", &n);bool ok = true;_for(i, 1, n) {scanf("%1d", &a[i]);if(a[i]) p.push_back(i);else ok = false;}if(ok) { puts("0"); continue; } //全是1要特判一下dp[1][0] = p[1] - 1;dp[1][1] = p[1];int cnt = p.size() - 1; //存一下方便一些_for(i, 2, cnt){int d = p[i] - p[i - 1] - 1; //中间0的数量还要减去一个1dp[i][0] = min(max(dp[i - 1][0], 1 + d / 2), max(dp[i - 1][1], 1 + (d - 1) / 2));dp[i][1] = min(max(dp[i - 1][0], 1 + (d + 1) / 2), max(dp[i - 1][1], 1 + d / 2));}int d = n - p[cnt];int ans = min(max(dp[cnt][0], d + 1), max(dp[cnt][1], d));printf("%d\n", ans);}return 0;
}周六
CF768D Jon and Orbs（dp解决概率问题）
一般想到概率都会想推公式
其实dp也是一种解决概率问题的一种方式
这道题就可以用dp来解决
dp[i][j]表示i天取了j个不同类型物品的概率
那么只有看当前第i天取的这件是不是在j件里面就行了
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 1e3 + 10;
double dp[N * 10][N];
int n, q;int main()
{scanf("%d%d", &n, &q);dp[1][1] = 1; dp[1][0] = 0;_for(i, 2, 1e4)_for(j, 1, min(i, n))dp[i][j] = dp[i - 1][j] * j / n + dp[i - 1][j - 1] * (n - j + 1) / n;while(q--){int p; scanf("%d", &p);_for(i, n, 1e4)if(dp[i][n] * 2000 >= p){printf("%d\n", i);break;}}return 0;
}CF1265E Beautiful Mirrors（期望dp）
很少做期望dp 这次算是加深对期望dp的理解
dp[i]表示进行到第i天的期望天数
那么方程就是
dpi = pi * (1 + dpi - 1) + (1 - pi) * (1 + dpi - 1 + dpi)
注意这个方程又出现了自己，要化简以下
可以得到
dpi = (dpi + 1) / pi
其中dp0 = 0 或者dp1 = 1 / p
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 2e5 + 10;
const int mod = 998244353;
int p[N], dp[N], n;int add(int a, int b) { return (a + b) % mod; }
int mul(int a, int b) { return 1LL * a * b % mod; }int binpow(int a, int b)
{int res = 1;for(; b; b >>= 1){if(b & 1) res = mul(res, a);a = mul(a, a);}return res;
}int inv(int x) { return binpow(x, mod - 2); }int main()
{scanf("%d", &n);_for(i, 1, n){int x; scanf("%d", &x);p[i] = mul(x, inv(100));}dp[1] = 1 * inv(p[1]);_for(i, 2, n) dp[i] = mul(dp[i - 1] + 1, inv(p[i]));printf("%d\n", dp[n]);return 0;
}L. Random Permutation（高精度）
推个公式然后高精度即可
#include <bits/stdc++.h>
#define num(i) a[i + 20]
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 1e4;
int a[N], len, n;int main()
{scanf("%d", &n);len = 1; num(0) = 1;_for(k, 2, n){rep(i, 0, len) num(i) *= k * k;rep(i, 0, len){num(i + 1) += num(i) / 10;num(i) %= 10;}while(num(len)){num(len + 1) += num(len) / 10;num(len) %= 10;len++;}}_for(i, 1, n) //高精除低精{for(int j = len - 1; j >= -15; j--){num(j - 1) += num(j) % n * 10;num(j) /= n;}while(!num(len - 1) && len > 1) len--;}for(int i = len - 1; i >= -15; i--){printf("%d", num(i));if(i == 0) putchar('.');}return 0;
}CF235B Let's Play Osu!（期望dp）
对期望的理解加深了
之前算过的期望就看作普通的值，处理完乘上概率
这道题的思路是考虑每一位的贡献加起来
假设当前第i位
以i为结尾向左有多少个O的期望为qi
如果第i位为O，那么平方相减贡献就为2 * qi-1 + 1
乘上概率就是pi(2 * qi-1 + 1)
那么怎么求qi呢
qi = (qi-1 + 1) * pi
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 1e5 + 10;
double len[N], ans;
int n;int main()
{scanf("%d", &n);_for(i, 1, n){double p; scanf("%lf", &p);ans += p * (2 * len[i - 1] + 1);len[i] = (len[i - 1] + 1) * p;}printf("%.10f\n", ans);return 0;
}