striving & singing
https://www.luogu.com.cn/problem/P3941
常用套路，把一个矩形拆为两个前缀和之差，然后用桶记录$\bmod k$得到的值对应的前缀和有几个即可。
#include<cstdio>
int n, m, d, a[410][410], cnt[1000100], sum[410][410];
long long ans;
int main() {
scanf("%d%d%d", &n, &m, &d);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) scanf("%d", &sum[i][j]), sum[i][j] = (sum[i][j] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + d) % d;
cnt[0] = 1;
for (int i = 1; i <= m; ++i)
for (int j = i; j <= m; ++j) {
for (int k = 1; k <= n; ++k) {
ans += cnt[(sum[k][j] - sum[k][i - 1] + d) % d];
++cnt[(sum[k][j] - sum[k][i - 1] + d) % d];
}
for (int k = 1; k <= n; ++k) --cnt[(sum[k][j] - sum[k][i - 1] + d) % d];
}
printf("%lld\n", ans);
return 0;
}https://www.luogu.com.cn/problem/P3942
经典题，可以树形 DP，不过好像不太好写，贪心要更好写一些。每次取出没被覆盖的点中深度最大的一个，然后以它的 k 级父亲为中心覆盖即可。判断一个点有没有被覆盖可以开一个数组$dis[x]$表示 x 的子树中所有覆盖中心与 x 的距离最短是多少即可。两种做法总复杂度都是$O(nk)$。
#include<cstdio>
#include<cstring>
#include<algorithm>
int n, k, t, depth[100100], p[100100], dis[100100], f[100100], ans;
struct edge { int to, next; };
struct graph {
int ecnt = 1, head[100100];
edge edges[200100];
inline void addedge(int u, int v) {
edges[++ecnt].to = v;
edges[ecnt].next = head[u];
head[u] = ecnt;
}
}g;
void dfs(int x, int lst) {
f[x] = g.edges[lst ^ 1].to;
depth[x] = depth[f[x]] + 1;
for (int i = g.head[x]; i; i = g.edges[i].next) {
if ((i ^ lst) == 1) continue;
dfs(g.edges[i].to, i);
}
}
inline bool cmp(int i, int j) { return depth[i] > depth[j]; }
inline int min(int a, int b) { return a < b ? a : b; }
int main() {
scanf("%d%d%d", &n, &k, &t);
for (int i = 1; i < n; ++i) {
int u, v; scanf("%d%d", &u, &v);
g.addedge(u, v); g.addedge(v, u);
}
dfs(1, 0);
for (int i = 1; i <= n; ++i) p[i] = i;
std::sort(p + 1, p + n + 1, cmp);
memset(dis, 0x3f, sizeof(int) * (n + 1));
for (int i = 1; i <= n; ++i) {
int x = p[i];
bool ok = false;
int d = 0, ca = x;
for (; d <= k && !ok; ++d, ca = f[ca]) if (dis[ca] + d <= k) ok = true;
if (ok) continue;
for (d = k, ca = x; d >= 0; --d, ca = f[ca]) dis[ca] = min(dis[ca], d);
for (d = 1; d <= k; ++d, ca = f[ca]) dis[ca] = min(dis[ca], d);
++ans;
}
printf("%d\n", ans);
return 0;
}https://www.luogu.com.cn/problem/P3943
首先可以把序列差分一下，这样每次操作就转化为把一个长度为$b_i+1$的区间的两个端点取反。目标是把所有的 0 变为 1。把两个 1 取反是没有意义的，而把一个 0 和一个 1 取反相当于把 0 移动到了 1 的位置，把两个 0 取反相当于两个 0 移动到一起时会抵消为 1。
于是可以状压 DP，设$dp[s]$表示状态为 s 时需要的最少操作次数，其中 s 表示所有的 0 的位置上的状态，即是 0 还是 1。枚举把哪两个 0 变为 1 即可。根据愤怒的小鸟那题的 trick 可以固定把第一个 0 变为 1，然后枚举另一个 0 ，这样就把 DP 的复杂度从$O(2^kk^2)$降到了$O(2^kk)$。
另外还要预处理把某两个 0 变为 1 需要的最少操作次数，直接 bfs 即可。看起来好像还能用完全背包，但实际上完全背包是错的，因为在操作时要求操作的区间不能越界，而完全背包只考虑距离之差没有考虑越界的情况，会导致答案错误。
总复杂度$O(nmk+2^kk)$。
#include<cstdio>
#include<cstring>
#include<queue>
int n, k, m, a[20], acnt, b[65], cost[20][40010], dp[66000];
bool flag[40010], vis[40010];
std::queue<int> q;
inline int min(int a, int b) { return a < b ? a : b; }
void bfs(int s) {
memset(vis, 0, sizeof(bool) * (n + 1));
cost[s][a[s]] = 0;
q.push(a[s]);
while (!q.empty()) {
int x = q.front();
q.pop();
if (vis[x]) continue;
vis[x] = true;
for (int i = 1; i <= m; ++i) {
if (x + b[i] - 1 <= n && cost[s][x + b[i] - 1] > cost[s][x] + 1) {
cost[s][x + b[i] - 1] = cost[s][x] + 1;
q.push(x + b[i] - 1);
}
if (x - b[i] + 1 >= 1 && cost[s][x - b[i] + 1] > cost[s][x] + 1) {
cost[s][x - b[i] + 1] = cost[s][x] + 1;
q.push(x - b[i] + 1);
}
}
}
}
int main() {
scanf("%d%d%d", &n, &k, &m);
for (int i = 1; i <= k; ++i) scanf("%d", &a[i]), flag[a[i]] = !flag[a[i]], flag[a[i] + 1] = !flag[a[i] + 1];
++n;
for (int i = 1; i <= n; ++i) if (flag[i]) a[++acnt] = i;
k = acnt;
for (int i = 1; i <= m; ++i) scanf("%d", &b[i]), ++b[i];
memset(cost, 0x3f, sizeof cost);
for (int i = 1; i <= k; ++i) bfs(i);
memset(dp, 0x3f, sizeof dp);
dp[0] = 0;
for (int s = 1; s < (1 << k); ++s) {
int x = 0;
for (int i = 1; i <= k; ++i)
if (s & (1 << i - 1)) {
if (!x) x = i;
else dp[s] = min(dp[s], dp[s ^ (1 << x - 1) ^ (1 << i - 1)] + cost[x][a[i]]);
}
}
printf("%d\n", dp[(1 << k) - 1]);
return 0;
}https://www.luogu.com.cn/problem/P3199
前几天模拟赛的原题。需要注意的是 bfs 式 spfa 会被卡飞，需要写复杂度错误的 dfs 式 spfa 才能通过。
#include<cstdio>
#include<cstring>
#include<queue>
const double eps = 1e-10;
int n, m;
double minw = 0x3fffffff, maxw = -0x3fffffff, dis[3010];
bool vis[3010];
struct edge { int to, next; double w; };
struct graph {
int ecnt = 1, head[3010];
edge edges[10010];
inline void addedge(int u, int v, double w) {
edges[++ecnt].to = v;
edges[ecnt].w = w;
edges[ecnt].next = head[u];
head[u] = ecnt;
}
}g;
std::queue<int> q;
inline double min(double a, double b) { return a < b ? a : b; }
inline double max(double a, double b) { return a > b ? a : b; }
bool dfs(int x, const double mid) {
if (vis[x]) return true;
vis[x] = true;
for (int i = g.head[x]; i; i = g.edges[i].next) {
int &v = g.edges[i].to; double w = g.edges[i].w - mid;
if (dis[v] > dis[x] + w) {
dis[v] = dis[x] + w;
if (dfs(v, mid)) { vis[x] = false; return true; }
}
}
vis[x] = false;
return false;
}
inline bool check(double mid) {
memset(dis, 0, sizeof(double) * (n + 1));
for (int i = 1; i <= n; ++i) if (dfs(i, mid)) return true;
return false;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; ++i) {
int u, v; double w; scanf("%d%d%lf", &u, &v, &w);
g.addedge(u, v, w);
minw = min(minw, w); maxw = max(maxw, w);
}
double l = minw, r = maxw + eps;
while (l + eps < r) {
double mid = l + (r - l) / 2;
if (check(mid)) r = mid;
else l = mid + eps;
}
printf("%.8lf\n", l);
return 0;
}