总结
- 人生第一次掉rating
- 各种降智操作
A
水题
B
逆天操作
WA了3发
第三次交的时候以为过了,等到切完E发现怎么B还没过(
#include
using 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)) 的枚举不写,写半个小时四进制枚举(
#include
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; -- j) {
cout
D
以 (1) 为根,(ans=n – max(size[y]hspace{0.4cm} |hspace{0.4cm} y in H[1]))
(H[x]) 为 (x) 所有儿子的集合
#include
using 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
E
贪心,打每个怪用离其最近的药水
#include
using namespace std;
const int N = 2e5 + 5;
int n, op[N], a[N];
bool used[N];
struct Node {
int p, v;
bool operator 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
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
机房租用,北京机房托管,大带宽租用,IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net