https://codeforces.com/contest/1925
恶心round,从C题开始每题都是一眼看出做法但是细节挺多的题,烦的一比。
A. We Got Everything Covered! *800
给定 \(n,k\),若所有长度为 \(n\) 且仅由字母表中前 \(k\) 个小写字母组成的串都是 \(s\) 的子序列,则称 \(s\) 是 "Everything Covered" 的。请构造串 \(s\)。
这样构造:abcdabcdabcd
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void sol() {
int n, k;
cin >> n >> k;
while (n--) {
for (int i = 0; i < k; i++)
cout << char('a' + i);
}
cout << '\n';
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int T; cin >> T; while (T--)
sol();
}
B. A Balanced Problemset? *1200
把 \(x\) 分成 \(n\) 个大于零的数之和,这些数的 \(gcd\) 最大是多少?
\(x\le 10^{8}\)
这些数都能表示成它们的 \(gcd\) 的倍数,\(gcd\) 必是 \(x\) 的因子,枚举因子即可。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void sol() {
int x, n;
cin >> x >> n;
vector<int> d;
for (int i = 1; i <= x / i; i++) {
if (x % i) continue;
d.push_back(i);
if (i != x / i) d.push_back(x / i);
}
sort(d.begin(), d.end());
for (int di : d) {
if (di >= n) return cout << x / di << '\n', void();
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int T; cin >> T; while (T--)
sol();
}
C. Did We Get Everything Covered? *1500
判断给定串是不是 "Everything Covered" 的。如果不是,构造反例。
这样构造反例:每次选“最晚出现的字符”
感觉这个人的方法比我帅多了 https://zhuanlan.zhihu.com/p/680178758
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void sol() {
int n, k, m;
string s;
cin >> n >> k >> m >> s;
vector<int> p(k, m), f(m); //后缀中首次出现位置最晚的字符出现的位置
for (int i = m - 1; ~i; i--) {
p[s[i] - 'a'] = i;
for (int j : p) f[i] = max(f[i], j);
}
string ans;
for (int i = 0; i < m; i++) {
if (f[i] < m) {
ans += s[f[i]];
i = f[i];
if (ans.size() == n)
return cout << "YES\n", void();
} else {
vector<bool> occ(k);
for (int j = i; j < m; j++)
occ[s[j] - 'a'] = true;
int c = 0; while (occ[c]) c++;
while (ans.size() < n) ans += char(c + 'a');
cout << "NO\n" << ans << '\n';
return;
}
}
while (ans.size() < n) ans += 'a';
cout << "NO\n" << ans << '\n';
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int T; cin >> T; while (T--)
sol();
}
D. Good Trip *1900
有 \(n\) 个同学,其中有 \(m\) 对朋友,第 \(i\) 对朋友有友谊值 \(f_i\)。老师每次随机(从所有 \(C_n^2\) 对中)选一对人,共选 \(k\) 次。一对朋友被选中后,答案加上他们当前的友谊值,然后他们的友谊值增加 \(1\)。问答案的期望。
\(n,m\le 1e5, k\le 2e5\)
考虑第 \(i\) 对朋友对答案的贡献。\(f_i\) 被加入答案的概率为 \(P(1)\),\(f_i+1\) 被加入答案的概率为 \(P(2)\),以此类推。
\(P(x)\) 为第 \(i\) 对朋友被选择的次数 \(\ge x\) 的概率,\(P(x)=\sum_{j=x}^k C_k^j p^j(1-p)^{k-j}\),其中 \(p=1/C_n^2\)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int P = 1e9 + 7;
const int N = 2e5 + 5;
ll fac[N], ifac[N];
ll qmi(ll a, ll b) {
ll s = 1;
for (; b; b >>= 1) {
if (b & 1) s = s * a % P;
a = a * a % P;
}
return s;
}
ll C(ll n, ll k) {
if (n < k) return 0;
return fac[n] * ifac[k] % P * ifac[n - k] % P;
}
void sol() {
ll n, m, k;
cin >> n >> m >> k;
ll sp = 0, sip = 0, ans = 0;
ll p = qmi(n * (n - 1) / 2 % P, P - 2), q = (1 - p + P) % P;
for (ll i = k, s = 0; i; i--) {
(s += C(k, i) * qmi(p, i) % P * qmi(q, k - i) % P) %= P;
(sp += s) %= P;
(sip += i * s % P) %= P;
}
for (int i = 0; i < m; i++) {
ll a, b, f;
cin >> a >> b >> f;
ans += (f - 1) * sp % P + sip;
}
cout << (ans % P + P) % P << '\n';
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
fac[0] = 1;
for (int i = 1; i < N; i++)
fac[i] = fac[i - 1] * i % P;
ifac[N - 1] = qmi(fac[N - 1], P - 2);
for (int i = N - 1; i; i--)
ifac[i - 1] = ifac[i] * i % P;
int T; cin >> T; while (T--)
sol();
}
E. Space Harbour *2100
树状数组或者线段树 区间加差分数组、区间求和,把模板题代码拉过来微调一下就行
我写的是树状数组维护二阶差分
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct BIT {
int n; vector<ll> tr;
BIT(int n): n(n), tr(n + 1) {}
int lowbit(int x) { return x & -x; }
void add(int p, ll x) { for (; p <= n; p += lowbit(p)) tr[p] += x; }
ll ask(int p) { ll s = 0; for (; p > 0; p -= lowbit(p)) s += tr[p]; return s; }
};
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m, q;
cin >> n >> m >> q;
BIT c(n), kc(n), kkc(n);
auto add = [&](int p, ll x) { //对c数组的单点加
c.add(p, x); kc.add(p, x * p); kkc.add(p, x * p * p);
};
auto upd = [&](int l, int r, ll a, ll d) { //a数组区间加等差数列
add(l, a);
add(l + 1, d - a);
add(r + 1, -(a + d * (r - l + 1)));
add(r + 2, (a + d * (r - l)));
};
auto ask = [&](int n) {
ll s = c.ask(n) * (n + 1) * (n + 2);
s -= (2 * n + 3) * kc.ask(n);
s += kkc.ask(n);
return s / 2;
};
vector<pair<int, int>> harbour(m);
for (int i = 0; i < m; i++) cin >> harbour[i].first;
for (int i = 0; i < m; i++) cin >> harbour[i].second;
sort(harbour.begin(), harbour.end()); //题目没说港口是有序的...
auto modify = [&](int x1, int v1, int x2, ll ty = 1) { //del=-1表示删除序列
upd(x1 + 1, x2, ty * v1 * (x2 - x1 - 1), -ty * v1);
};
set<pair<int, int>> S;
for (int i = 0; i < m; i++) {
if (i > 0)
modify(harbour[i - 1].first, harbour[i - 1].second, harbour[i].first);
S.insert(harbour[i]);
}
while (q--) {
int t; cin >> t;
if (t == 1) {
int x, v; cin >> x >> v;
auto it = S.lower_bound({x, v});
auto [x2, v2] = *it;
auto [x1, v1] = *prev(it);
modify(x1, v1, x2, -1);
modify(x1, v1, x);
modify(x, v, x2);
S.insert({x, v});
} else {
int l, r; cin >> l >> r;
cout << ask(r) - ask(l - 1) << '\n';
}
}
return 0;
}
F. Fractal Origami *2400 分母有理化
折纸,正方形的纸边长为 \(1\),每次把四个角往内折,得到新的更小的正方形。最后展开,折痕分为峰和谷两类,峰与谷的长度之比 \(M/V\) 一定是 \(A+B\sqrt2\) 的形式,\(A,B\) 均为有理数。请输出 \(B\)。
找规律,列式子,分母有理化
拿张纸巾折了几次,发现第 \(2\) 次 \(M,V\) 均增加 \(2\),第 \(3\) 次 \(M,V\) 均增加 \(2\sqrt2\)。大胆猜测每次 \(M,V\) 均增加上次增加长度的 \(\sqrt2\) 倍。然后就是臭不可闻的列式子+疯狂有理化
\[M = \frac{2(\sqrt 2 ^{n-1}-1)}{\sqrt2-1} = 2(\sqrt 2 ^{n-1}-1)(\sqrt2 + 1) = 2(\sqrt2^n-1+\sqrt2^{n-1}-\sqrt2) \\V = M + 2\sqrt2 = 2(\sqrt2^n-1+\sqrt2^{n-1}) \\ \frac{M}{V} = \frac{\sqrt2^n-1+\sqrt2^{n-1}-\sqrt2}{\sqrt2^n-1+\sqrt2^{n-1}} \]当 \(n\) 为奇数时,
\[\frac{M}{V} = \frac{2^{(n-1)/2}\sqrt2-1+2^{(n-1)/2}-\sqrt2}{2^{(n-1)/2}\sqrt2-1+2^{(n-1)/2}} \]当 \(n\) 为偶数时,
\[\frac{M}{V} = \frac{2^{n/2}-1+2^{(n-2)/2}\sqrt2-\sqrt2}{2^{n/2}-1+2^{(n-2)/2}\sqrt2} \]太丑了,设一下继续算
\[\frac{M}{V} = \frac{(x-1)\sqrt2+y}{x\sqrt2+y} = \frac{y}{2x^2-y^2}\sqrt2+一个有理数 \]#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int P = 999999893;
const int N = 2e5 + 5;
ll fac[N], ifac[N];
ll qmi(ll a, ll b) {
ll s = 1;
for (; b; b >>= 1) {
if (b & 1) s = s * a % P;
a = a * a % P;
}
return s;
}
void sol() {
ll n;
cin >> n;
ll x = qmi(2, n / 2 - !(n & 1)), y = qmi(2, n / 2) - 1;
cout << (y * qmi((2 * x * x % P - y * y % P) % P, P - 2) % P + P) % P << '\n';
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int T; cin >> T; while (T--)
sol();
}
标签:int,sqrt2,ll,Codeforces,long,cin,using,921,Div
From: https://www.cnblogs.com/wushansinger/p/18011426