AtCoder Beginner Contest 333
总结
- 人生第一次掉rating
- 各种降智操作
A
水题
B
逆天操作
WA了3发
第三次交的时候以为过了，等到切完E发现怎么B还没过（
#include<bits/stdc++.h>
using namespace std;
map<string, int> 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)\) 的枚举不写，写半个小时四进制枚举（
#include<bits/stdc++.h>
using 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 << 24; ++ i) {
if(check(i)) ++ cnt;
if(cnt == n) {
int x = i, len = 0, a[15];
while(x) a[++ len] = x % 4, x /= 4;
for(int j = len ;j >= 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\) 所有儿子的集合
#include<bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
vector<int> 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 < n; ++ i) {
int x, y;
cin >> 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
贪心，打每个怪用离其最近的药水
#include<bits/stdc++.h>
using 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.v;
else return p > x.p;
}
};
int main() {
ios :: sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
cin >> n;
set<Node> se;
for(int i = 1; i <= n; ++ i) {
cin >> 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<bits/stdc++.h>
#define ll long long
#define rep(i, j, k) for(int i = j; i <= k; ++ i)
#define per(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;
}