总结

  • 人生第一次掉rating
  • 各种降智操作

A

水题

B

逆天操作
WA了3发
第三次交的时候以为过了，等到切完E发现怎么B还没过（

#includeusing namespace std;map f;int main() {f["AB"] = f["BC"] = f["CD"] = f["DE"] = f["EA"] = 1;f["AC"] = f["BD"] = f["CE"] = f["DA"] = f["EB"] = 2;string s1, s2;cin >> s1 >> s2;if(!f[s1]) swap(s1[0], s1[1]);if(!f[s2]) swap(s2[0], s2[1]);puts(f[s1] == f[s2] ? "Yes" : "No");return 0;}

C

人家题把上限都告诉你了
然后我\(O(12^3)\) 的枚举不写，写半个小时四进制枚举（

#includeusing namespace std;bool check(int x) {int a[15], len = 0;while(x) a[++ len] = x % 4, x /= 4;for(int i = len ;i >= 1; -- i) {if(!a[i]) return 0;}for(int i = len; i > 1; -- i) {if(a[i] > a[i - 1]) return 0;}return a[1] == 3;}int main() {int n, cnt = 0;cin >> n;for(int i = 0; i < 1 <= 1; -- j) {cout << a[j];}return 0;}}return 0;}

D

以 \(1\) 为根，\(ans=n – max(size[y]\hspace{0.4cm} |\hspace{0.4cm} y \in H[1])\)

\(H[x]\) 为 \(x\) 所有儿子的集合

#includeusing namespace std;const int N = 3e5 + 5;vector H[N];int fa[N], sz[N];int dfs(int x) {sz[x] = 1;for(int y : H[x]) {if(y != fa[x]) {fa[y] = x;sz[x] += dfs(y);}}return sz[x];}int main() {ios :: sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);int n;cin >> n;for(int i = 1; i > x >> y;H[x].push_back(y);H[y].push_back(x);}dfs(1);int ans = n;for(int y : H[1]) ans = min(ans, n - sz[y]);cout << ans;return 0;}

E

贪心，打每个怪用离其最近的药水

#includeusing namespace std;const int N = 2e5 + 5;int n, op[N], a[N];bool used[N];struct Node {int p, v;bool operator < (const Node &x) const {if(v != x.v) return v  x.p;}};int main() {ios :: sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);cin >> n;set se;for(int i = 1; i > op[i] >> a[i];if(op[i] == 1) se.insert({i, a[i]});}for(int i = 1; i <= n; ++ i) {if(op[i] == 2) {auto it = se.lower_bound({i, a[i]});auto x = *it;if(x.v == a[i]) {se.erase(it);used[x.p] = 1;}else return cout << -1, int();}}int cur = 0, ans = 0;for(int i = 1; i <= n; ++ i) {if(used[i]) ++ cur;if(op[i] == 2) -- cur;ans = max(ans, cur);}cout << ans << '\n';for(int i = 1; i <= n; ++ i) if(op[i] == 1) cout << used[i] << ' ';return 0;}

F

一道比较有意思的概率dp
我们令 \(f[i][j]\) 表示当前一共\(i\)个人，其中第\(j\)个人留到最后的概率
不难得到

\[f[i][j] = \frac{1}{2} \times f[i][j – 1] + \frac{1}{2} \times f[i – 1][j – 1]\]

现在就是看边界\(f[i][1]\)怎么求，也就是要用\(f[i – 1]\)里的东西来表示\(f[i][1]\)
手动模拟一下\(n = 3\)或\(n = 4\)的情况
可以得到

\[f[i][1] = ( \sum_{j = 2}^{i} \frac{1}{2^j} \times f[i – 1][i – j + 1]) + \frac{1}{2^i} \times f[i][1]\]

注意这里的式子是有后效性的，简单解一下方程就好了
具体实现看代码

#include#define ll long long#define rep(i, j, k) for(int i = j; i = k; -- i)using namespace std;const ll P = 998244353, N = 3005;ll f[N][N], inv[N];ll qp(ll a, ll b) {ll ret = 1;while(b) {if(b & 1) ret = ret * a % P;b >>= 1;a = a * a % P;}return ret;}ll calc(ll x) {return qp(2, x) * qp(qp(2, x) - 1, P - 2) % P;}void init() {inv[N - 1] = qp(qp(2, N - 1), P - 2);per(i, N - 2, 0) inv[i] = inv[i + 1] * 2 % P;f[1][1] = 1;}int main() {int n; cin >> n;init();rep(i, 2, n) {rep(j, 2, i) f[i][1] = (f[i][1] + inv[j] * f[i - 1][i - j + 1]) % P;f[i][1] = f[i][1] * calc(i) % P;rep(j, 2, i) f[i][j] = inv[1] * (f[i - 1][j - 1] + f[i][j - 1]) % P;}rep(i, 1, n) cout << f[n][i] << ' ';return 0;}