目录
写在前面
比赛地址：https://codeforces.com/gym/103428。
以下按个人向难度排序。
最杂鱼的一集，vp 时 1h 过了三题就开始坐牢了。
妈的怎么这么多数学题，不会数学的飞舞被杀死了、、、
A
签到。
有度数大于等于 4 的点则不合法，否则任选度数不大于 2 的点为根即可。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 1e6 + 10;
//=============================================================
int n, into[kN], cnt[kN];
//=============================================================
//=============================================================
int main() {
//freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
std::cin >> n;
for (int i = 1; i < n; ++ i) {
int u, v; std::cin >> u >> v;
cnt[into[u]] --, cnt[into[v]] --;
into[u] ++, into[v] ++;
cnt[into[u]] ++, cnt[into[v]] ++;
}
for (int i = 4; i <= n; ++ i) {
if (cnt[i]) {
std::cout << 0 << "\n";
return 0;
}
}
std::cout << n - cnt[3] << "\n";
return 0;
}
J
签到，数学。
你上过初中吗？我觉得我上过。
可求得每次弹射转过的圆心角是 \(2\times \beta\)，考虑第一次转过 360 度的倍数，则答案即 \(\frac{180\times b}{\gcd(a, b)} - 1\)。
记得开 LL。
#include<bits/stdc++.h>
using namespace std;
#define int long long
int T;
int a,b;
signed main(){
cin>>T;
while(T--){
cin>>a>>b;
b*=180;
int gg=__gcd(a,b);
b/=gg;
cout<<b-1<<endl;
}
return 0;
}
D
KMP，二分。
首先 KMP 求得原字符串的所有周期，手玩下发现修改位置 \(p\) 后的字符串的周期 \(l\) 需要满足：
- \(l\) 是原串的周期。
- \(\frac{n}{2} < l\)。
- \(n-l < p\le l\)。
将满足前两条件的周期排序后，对于每次询问，二分求满足第三个条件的周期数量即可。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 1e6 + 10;
//=============================================================
char s[kN];
int n, fail[kN];
std::vector <int> v, v1;
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
void KMP() {
n = strlen(s + 1);
fail[1] = 0;
for (int i = 2, j = 0; i <= n; ++ i) {
while (j && s[i] != s[j + 1]) j = fail[j];
if (s[i] == s[j + 1]) ++ j;
fail[i] = j;
}
int f = fail[n];
while (n - f <= n / 2) f = fail[f];
while (f) {
if (n - f > f) v.push_back(n - f);
f = fail[f];
}
std::sort(v.begin(), v.end());
for (auto x: v) v1.push_back(n - x);
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
scanf("%s", s + 1);
KMP();
int q = read(), len = v.size();
while (q --) {
int p = read(), posl = len, posr = len;
for (int l = 0, r = len - 1; l <= r; ) {
int mid = (l + r) >> 1;
if (p <= v[mid]) {
posr = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
for (int l = 0, r = len - 1; l <= r; ) {
int mid = (l + r) >> 1;
if (v1[mid] < p) {
posl = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
printf("%d\n", std::min(len - posl, len - posr));
}
return 0;
}
/*
aaaaa
1
3
*/
G
枚举，数学，结论
对于确定的 \(k\)，答案即为 \(\prod_{i=1}^{n} {k\choose a_i}\)，但是显然不能直接求，\(O(nm)\) 怎么也卡不过去啊呃呃。
发现有 \(\sum a_i\le 10^5\) 的限制，则不同的 \(a_i\) 仅有 \(\sqrt{10^5} \approx 316\) 种，则可以预处理各种 \(a_i\) 再枚举 \(k = 1, 2, \cdots, m\)，枚举所有种类的 \(a_i\) 快速幂即可。
总时间复杂度 \(O(m\sqrt{v}\log v)\) 级别。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 1e5 + 10;
const LL p = 998244353;
//=============================================================
int n, m, maxa, a[kN], cnt[kN];
LL fac[kN], ifac[kN], inv[kN];
std::vector <int> v;
//=============================================================
LL C(LL n_, LL m_) {
if (m_ > n_) return 0;
return fac[n_] * ifac[m_] % p * ifac[n_ - m_] % p;
}
LL qpow(LL x_, LL y_) {
LL ret = 1;
while (y_) {
if (y_ & 1ll) ret = ret * x_ % p;
x_ = x_ * x_ % p, y_ >>= 1ll;
}
return ret;
}
void Init() {
std::cin >> n >> m;
for (int i = 1; i <= n; ++ i) {
std::cin >> a[i];
maxa = std::max(maxa, a[i]);
if (!cnt[a[i]]) v.push_back(a[i]);
++ cnt[a[i]];
}
inv[1] = fac[1] = ifac[1] = ifac[0] = 1;
for (int i = 2; i <= std::max(maxa, m); ++ i) {
inv[i]= 1ll * (p - p / i + p) % p * inv[p % i] % p;
fac[i] = 1ll * fac[i - 1] * i % p;
ifac[i] = 1ll * ifac[i - 1] * inv[i] % p;
}
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
Init();
for (int i = 1; i < std::min(maxa, m); ++ i) {
std::cout << 0 << "\n";
}
for (int i = maxa; i <= m; ++ i) {
LL ans = 1;
for (auto x: v) ans = ans * qpow(C(i, x), cnt[x]) % p;
std::cout << ans << "\n";
}
return 0;
}
E
期望，双指针
妈的怎么又是一道数学题
套路地记 \(E(x)(0\le x\le k)\) 表示可进行 \(x\) 次重抽操作的期望得分，显然有 \(E(0) = \frac{\sum_{i\not= j} a_i + a_j}{{n\choose 2}} = \frac{\sum_i (n-1)\times a_i}{{n\choose 2}}\)，第一问答案即为 \(E(k)\)。
当 \(x>0\) 时，显然当重抽结果大于 \(E(x-1)\) 时才会选择重抽，考虑枚举重抽结果 \(a_i + a_j\)，则有：
\[E(x) = \dfrac{\left(\sum\limits_{i\not= j, a_i + a_j \le E(x - 1)} E(x-1)\right)+ \left(\sum\limits_{i\not= j, a_i + a_j > E(x - 1)} a_i + a_j\right)}{{n\choose 2}} \]双指针枚举所有满足 \(a_i+a_j>E(x-1)\) 的数对即可在 \(O(n)\) 复杂度内求得 \(E(x)\)，发现 \(k\) 很小，直接 \(O(nk)\) 地求 \(E(k)\) 即可。
第二问判断最优策略，基于上述思路，仅需 \(O(1)\) 地比较 \(a_x + a_y\) 与重抽 \(c-1\) 次的期望得分 \(E(c-1)\) 的大小即可。注意特判 \(c=0\) 的情况，此时只能接受。
总时间复杂度 \(O(nk + q)\) 级别。
注意使用 cout 输出一定位数的小数时注意：std::fixed << std::setprecision()，不加 fixed 会变科学计数法。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
#define LD long double
const int kN = 1e6 + 10;
const int kK = 110;
const LD eps = 1e-4;
//=============================================================
int n, q, k, a[kN], b[kN];
LL all, sum[kN];
LD E[kK];
//=============================================================
void Init() {
std::cin >> n >> k >> q;
all = 1ll * n * (n - 1) / 2ll;
for (int i = 1; i <= n; ++ i) {
std::cin >> a[i];
b[i] = a[i];
}
std::sort(b + 1, b + n + 1, std::greater<int>());
for (int i = 1; i <= n; ++ i) {
sum[i] = sum[i - 1] + b[i];
E[0] += 1.0l * (n - 1) * b[i];
}
E[0] = 1.0 * E[0] / all;
}
void DP() {
for (int i = 1; i <= k; ++ i) {
LL cnt = 0, s = 0;
for (int p = 1, q = n; p < q; ++ p) {
while (p < q && b[p] + b[q] < E[i - 1]) -- q;
if (p < q) cnt += q - p, s += 1ll * (q - p) * b[p] + sum[q] - sum[p];
}
E[i] = (1.0l * (all - cnt) * E[i - 1] + s) / all;
}
}
//=============================================================
int main() {
//freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
Init();
DP();
std::cout << std::fixed << std::setprecision(10) << E[k] << "\n"; //输出小数必备格式
while (q --) {
int x, y, c; std::cin >> x >> y >> c;
if (c == 0) std::cout << "accept" << "\n";
else if (a[x] + a[y] - E[c - 1] > eps) std::cout << "accept" << "\n";
else if (a[x] + a[y] - E[c - 1] < -eps) std::cout << "reselect" << "\n";
else std::cout << "both" << "\n";
}
return 0;
}
/*
85.555555556
*/
M
组合数学，容斥
看到这个输入这么简略可以猜到大概又是一道数学题。
首先把限制 \(k\) 搞掉，记 \(f(x)\) 为仅允许有长度不大于 \(x\) 的全 1 段的方案数，则限定最长段为 \(k\) 的方案数即为 \(f(k) - f(k-1)\)。
然后考虑如何求 \(f(k)\)。限定串中有 \(m\) 个 1，即有 \(n-m\) 个 0，则构造字符串等价于在 \(n-m\) 个 0 之间和两端共 \(n-m+1\) 个空中填入总共 \(m\) 个 1，每个空可填入 \(0\sim k\) 个 1。这是个经典问题，参考 hdu6397，考虑容斥消去填入上限的限制。
设 \(g(i)\) 表示总共填入了 \(m\) 个 1 且没有填入上限，有至少 \(i\) 个空至少填入了 \(k+1\) 的方案数：
- 显然有 \(0\le i\le \min\left( n - m + 1, \frac{m}{(k_ + 1)}\right)\)。
- 对于 \(i=0\)，即每个空没有填数上限，则直接插板法，方案数为 \({{(n-m+1) + m - 1} \choose {n-m-1 + 1}} = {n\choose {n-m}}\)。
- 对于 \(i>0\)，考虑先选出 \(i\) 个空为它们预分配 \(k+1\)，然后转化为了 \(i=0\) 的情况，方案数为 \({{n-m+1}\choose i}\times {{n - (k+1)\times i} \choose {n-m}}\)。
则有 \(f(k) = \sum\limits_{i} (-1)^i\times g(i)\)，注意特判 \(f(-1) = 0\)。
预处理下阶乘和逆元，总时间复杂度 \(O(n)\) 级别。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 1e5 + 10;
const LL p = 998244353;
//=============================================================
int n, m, k;
LL inv[kN], fac[kN], ifac[kN];
//=============================================================
LL C(LL n_, LL m_) {
if (m_ > n_) return 0;
return fac[n_] * ifac[m_] % p * ifac[n_ - m_] % p;
}
void Init() {
inv[1] = fac[0] = fac[1] = ifac[0] = ifac[1] = 1;
for (int i = 2; i < kN; ++ i) {
inv[i]= 1ll * (p - p / i + p) % p * inv[p % i] % p;
fac[i] = fac[i - 1] * i % p;
ifac[i] = ifac[i - 1] * inv[i] % p;
}
}
LL f(LL k_) {
if (k_ == -1) return 0;
LL ans = 0, f = 1;
for (int i = 0; i <= std::min(n - m + 1ll, m / (k_ + 1)); ++ i, f = -f) {
LL d1 = C(n - m + 1, i), d2 = C(n - (k_ + 1) * i, n - m);
ans = (ans + f * d1 * d2 % p + p) % p;
}
return ans;
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
Init();
std::cin >> n >> m >> k;
std::cout << (f(k) - f(k - 1) + p) % p << "\n";
return 0;
}
H
最小割（最大权闭合子图）
一眼想到最大权闭合子图，但是因为选择距离不大于 \(p\) 的点需要先选择距离不大于 \(p-1\) 这个有依赖性的限制，建图还有点技巧。
对于所有原图中节点 \(i(1\le i\le n)\) 建立 \(n\) 个虚拟节点 \(v_{i, j}(0\le j<n)\) 代表距离节点 \(i\) 为 \(j\) 的点集，然后按下述规则连边：
- 原图中节点 \(i\) 向汇点连边，容量为 \(w_i\)。
- 所有 \(v_{i, j}\) 向与 \(i\) 距离 \(j\) 的所有点连边，容量无限。
- \(v_{i, j}\) 向 \(v_{i, j - 1}\) 连边，容量无限，对于每个 \(i\) 限制了割去从源点连向 \(v_{i, j}(0\le j<n)\) 的边时只能按照 \(j\) 降序割，即放弃贡献只能按照 \(j\) 降序放弃，从而满足了一开始提到的限制。
- 源点向所有 \(v_{i, j}\) 连边，容量为 \(v_j - v_{j-1}\)，表示割去该边后的价值减量。
答案即为 \(n\times v_{n-1}\) 减去最小割。
虽然点数边数都是 \(O(n^2)\) 级别的但是就是能跑出来，很神奇吧，网络流！
然而用自己的 Dinic T 翻了，上网抄了大神的就不 T 了妈的，我写的是什么构式板子赶紧全删了算了我草
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 210;
const int kM = kN << 1;
const int kN1 = 1e5 + 10;
const int kM1 = 2e7 + 10;
const LL kInf = 1e12 + 2077;
//=============================================================
int n, weight[kN], value[kN];
int edgenum, v[kM], ne[kM], head[kN];
int nodenum, S, T, id[kN][kN];
int edgenum1 = 1, v1[kM1], ne1[kM1], head1[kN1];
int cur[kN1], dep[kN1];
LL w1[kM1];
//=============================================================
void Add(int u_, int v_) {
v[++ edgenum] = v_;
ne[edgenum] = head[u_];
head[u_] = edgenum;
}
void Add1(int u_, int v_, LL w_) {
v1[++ edgenum1] = v_;
w1[edgenum1] = w_;
ne1[edgenum1] = head1[u_];
head1[u_] = edgenum1;
}
void DFS(int u_, int fa_, int top_, int dep_) {
Add1(id[top_][dep_], u_, kInf);
Add1(u_, id[top_][dep_], 0);
for (int i = head[u_]; i; i = ne[i]) {
int v_ = v[i];
if (v_ == fa_) continue;
DFS(v_, u_, top_, dep_ + 1);
}
}
void Init() {
std::cin >> n;
for (int i = 1; i <= n; ++ i) std::cin >> weight[i];
for (int i = 0; i < n; ++ i) std::cin >> value[i];
for (int i = 1; i < n; ++ i) {
int u_, v_; std::cin >> u_ >> v_;
Add(u_, v_), Add(v_, u_);
}
nodenum = n + 2, S = n + 1, T = n + 2;
for (int i = 1; i <= n; ++ i) Add1(i, T, weight[i]), Add1(T, i, 0);
for (int i = 1; i <= n; ++ i) {
for (int j = 0; j < n; ++ j) {
id[i][j] = ++ nodenum;
Add1(S, id[i][j], value[j] - (j > 0 ? value[j - 1] : 0));
Add1(id[i][j], S, 0);
if (j > 0) {
Add1(id[i][j], id[i][j - 1], kInf);
Add1(id[i][j - 1], id[i][j], 0);
}
}
DFS(i, 0, i, 0);
}
}
bool BFS() {
std::queue <int> q;
memset(dep, 0, (nodenum + 1) * sizeof (int));
dep[S] = 1; //注意初始化
q.push(S);
while (!q.empty()) {
int u_ = q.front(); q.pop();
for (int i = head1[u_]; i; i = ne1[i]) {
int v_ = v1[i];
LL w_ = w1[i];
if (w_ > 0 && !dep[v_]) {
dep[v_] = dep[u_] + 1;
q.push(v_);
}
}
}
return dep[T];
}
LL DFS1(int u_, LL into_) {
if (u_ == T) return into_;
LL ret = 0;
for (int i = cur[u_]; i && into_; i = ne1[i]) {
int v_ = v1[i];
LL w_ = w1[i];
if (w_ && dep[v_] == dep[u_] + 1) {
LL dist = DFS1(v_, std::min(into_, w_));
if (!dist) dep[v_] = kN1;
into_ -= dist;
ret += dist;
w1[i] -= dist, w1[i ^ 1] += dist;
if (!into_) return ret;
}
}
if (!ret) dep[u_] = 0;
return ret;
}
LL Dinic() {
LL ret = 0;
while (BFS()) {
memcpy(cur, head1, (nodenum + 1) * sizeof (int));
ret += DFS1(S, kInf);
}
return ret;
}
//=============================================================
int main() {
//freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
Init();
// for (int i = 1; i <= nodenum; ++ i) {
// for (int j = head1[i]; j; j = ne1[j]) {
// if (w1[j] == 0) continue;
// std::cout << i << " " << v1[j] << " " << w1[j] << "\n";
// }
// }
std::cout << 1ll * n * value[n - 1] - Dinic();
return 0;
}
写在最后
参考：
学到了什么：
- G：看全所有限定条件，注意 \(\sum a_i \le x\) 这种条件。
- E：使用
cout输出一定位数的小数时注意：std::fixed << std::setprecision()，不加 fixed 会变科学计数法。 - H：把你那你那 b 网络流垃圾板子扔了吧求你了哥