A - Repression 6
B - Hydrate 98
初始有a个蓝球，每次增加b个蓝球和c个红球，问至少几次后蓝球与红球的数量比不超过d
化一下式子，\((a+bk)/(ck)\le d\iff k\ge a/(dc-b)\)。那么分母小于等于0时无解，否则上取整
C - Many Segments 397
根据左右开闭分为四种区间，问有多少对相交区间。保证输入的左端点小于右端点
首先想到开区间转为闭区间，把开的端点+1或-1。这样有两个问题：
- 转化后左端点可能大于右端点（其实这应该没影响）
- 相交的 \(,3),(2,\) 区间被错误地转化为不相交的 \(,2],[3\)
一个神奇的解决方法：输入后马上把两个端点 \(\times 2\)！正确性应该可以分类讨论两个区间的边界情况来证明
官方题解做法：把开区间端点 +0.5 或者 -0.5，区间 \([a,b],[c,d]\) 相交当且仅当 \(\max(a,c)\le\min(b,d)\)
网上一些 ±0.3 的做法应该也类似
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n;
cin >> n;
vector<pair<int, int>> a(n);
for (auto &[l, r] : a) {
int t;
cin >> t >> l >> r;
l *= 2, r *= 2;
if (t > 2) l++;
if (t % 2 == 0) r--;
}
int ans = 0;
for (auto [l, r] : a) {
for (auto [x, y] : a) {
ans += x <= r && y >= l;
}
}
cout << (ans - n) / 2;
return 0;
}
/*
[1,2]
[2,3) [2,2] [4,5]
(2,4] [3,4] [5,8]
*/
D - Congruence Points 2074
平面上有两个点集 \(S,T\)，问能否通过旋转和平移使 \(S,T\) 重合。这里操作是对整个点集的，不能单独对某个点旋转或平移。
先通过平移把两个点集的重心都移到原点（注意不能仅把 \(S\) 的重心移到 \(T\) 的重心处，一定要都移到原点），接下来就只需要旋转了
然后 \(O(n^4)\) 大力枚举旋转的角度、旋转每个点、检查是否匹配
但是我对double过敏，WA了两发。。在题解里看到一个很妙的不需要浮点数的做法：
分别对两个点集极角排序，然后把每个点到原点的距离、相邻点的点积和叉积塞进数组，比较两个数组在某固定偏移量下是不是完全相等就行了。这里的比较可以 \(O(n^2)\) 实现，题解写了个Z算法（扩展KMP）让我大为震撼，其实用普通的KMP是不是也行？
细节还蛮多的，注意 \((0,0)\) 不参与排序。极角排序我写了个自认为比较天衣无缝的比较函数
#include <bits/stdc++.h>
using namespace std;
int operator* (pair<int, int> a, pair<int, int> b) {
return a.first * b.first + a.second * b.second;
}
int operator^ (pair<int, int> a, pair<int, int> b) {
return a.first * b.second - a.second * b.first;
}
bool below(pair<int, int> a) { //下半平面(-pi,pi]
return a.second < 0 || a.second == 0 && a.first > 0;
}
bool cmp(pair<int, int> a, pair<int, int> b) {
if (a * a == 0 || b * b == 0) return b * b == 0; //(0,0)放末尾
if (below(a) != below(b)) return below(a);
if ((a ^ b) != 0) return (a ^ b) > 0;
return a * a < b * b;
}
int main() {
int n;
cin >> n;
vector<pair<int, int>> a(n), b(n);
int x1 = 0, y1 = 0, x2 = 0, y2 = 0;
for (auto &[x, y] : a) {
cin >> x >> y;
x1 += x; y1 += y;
x *= n; y *= n;
}
for (auto &[x, y] : b) {
cin >> x >> y;
x2 += x; y2 += y;
x *= n; y *= n;
}
for (auto &[x, y] : a) x -= x1, y -= y1;
for (auto &[x, y] : b) x -= x2, y -= y2;
sort(a.begin(), a.end(), cmp);
sort(b.begin(), b.end(), cmp);
if (a.back() * a.back() == 0) a.pop_back();
if (b.back() * b.back() == 0) b.pop_back();
if (a.size() != b.size()) return cout << "No", 0;
n = a.size();
if (!n) return cout << "Yes", 0;
vector<array<int, 3>> A(n), B(n);
for (int i = 0; i < n; i++) {
A[i] = {a[i] * a[i], a[i] * a[(i + 1) % n], a[i] ^ a[(i + 1) % n]};
B[i] = {b[i] * b[i], b[i] * b[(i + 1) % n], b[i] ^ b[(i + 1) % n]};
}
for (int i = 0; i < n; i++) {
bool ok = true;
for (int j = 0; j < n; j++)
if (A[(i + j) % n] != B[j]) ok = false;
if (ok) return cout << "Yes", 0;
}
cout << "No";
return 0;
}
E - Mod i 1820
给定长为 \(3000\) 的数组，问有多少种方式把数组切成子段，第 \(i\) 个子段的和能被 \(i\) 整除。
要想到 区间和能整除 就是 两端点处前缀和同余
\(f(i,j)\) 表示 \(a[1..i]\) 被分成 \(j\) 段的方案数。那么
其中 \(g(i,j)\) 是个类似前缀和的东西，表示分成 \(i\) 段，右端点前缀和 \(\% (i+1)=j\) 的方案数
然后用 \(f\) 更新 \(g\)，\(f(i,j)\to g(j,s_i\%(j+1))\)
或许 \(f\) 数组可以不开，但我不太懂怎么搞
这题挺艺术的，推导优雅、代码简短
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll P = 1e9 + 7;
const int N = 3005;
ll n, s, f[N][N], g[N][N];
int main() {
cin >> n;
f[0][0] = g[0][0] = 1;
for (int i = 1; i <= n; i++) {
ll x; cin >> x; s += x;
for (int j = 1; j <= i; j++)
f[i][j] = g[j - 1][s % j];
for (int j = 1; j <= i; j++)
(g[j][s % (j + 1)] += f[i][j]) %= P;
}
ll ans = 0;
for (int i = 1; i <= n; i++)
(ans += f[n][i]) %= P;
cout << ans;
return 0;
}
F - Tree Patrolling 2398
给定一棵树。在一个结点设置一个警卫可以保护此结点和它的所有邻点。现在你可以任选任意个结点设置警卫，问恰好有 \(0,1,\cdots,n\) 个结点被保护的方案数。
\(f(i,j,0/1/2)\) 表示以结点 \(i\) 为根的子树中恰有 \(j\) 个结点被保护，且 \(i\) 未被保护/被 \(i\) 的某个儿子保护/有警卫的方案数。注意转移时被保护结点数量的变化，有时候会多一个
这题思路简单，代码也简单。最酷的是复杂度为什么是 \(n^2\)：
每次转移相当于从 \(v\) 子树的每个点向 \(v\) 左边的所有兄弟的子树中的每个点连一条边，最后形成一个完全图，边数 \(n^2\) 级别
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll P = 1e9 + 7;
const int N = 2005;
ll n, f[N][N][3], g[N][3]; // backup
vector<int> G[N];
int dfs(int u, int fa) {
int su = 1; //返回size
f[u][0][0] = f[u][1][2] = 1;
for (int v : G[u]) if (v != fa) {
int sv = dfs(v, u);
for (int i = 0; i <= su; i++) {
for (int j = 0; j <= sv; j++) {
g[i + j][0] += f[u][i][0] * f[v][j][0] % P;
g[i + j][0] += f[u][i][0] * f[v][j][1] % P;
g[i + j + 1][1] += f[u][i][0] * f[v][j][2] % P;
g[i + j][1] += f[u][i][1] * f[v][j][0] % P;
g[i + j][1] += f[u][i][1] * f[v][j][1] % P;
g[i + j][1] += f[u][i][1] * f[v][j][2] % P;
g[i + j + 1][2] += f[u][i][2] * f[v][j][0] % P;
g[i + j][2] += f[u][i][2] * f[v][j][1] % P;
g[i + j][2] += f[u][i][2] * f[v][j][2] % P;
}
}
su += sv;
for (int i = 0; i <= su; i++) {
for (int k = 0; k < 3; k++) {
f[u][i][k] = g[i][k] % P;
g[i][k] = 0;
}
}
}
return su;
}
int main() {
cin >> n;
for (int i = 1; i < n; i++) {
int x, y;
cin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
dfs(1, 0);
for (int i = 0; i <= n; i++) {
cout << (f[1][i][0] + f[1][i][1] + f[1][i][2]) % P << '\n';
}
return 0;
}