striving & singing
ZhengruIOI 普及组五连测 Day1。
http://www.zhengruioi.com/contest/695/problem/1545
看到题目直接打表，然后发现答案是一个斐波那契数列，然后直接矩阵快速幂即可。
原理是设$f(i)$表示$i$的答案，那么第$i$个位置只能填$i$或$i-1$，填$i$时剩余位置的方案数为$f(i-1)$，填$i-1$时第$i-1$个位置只能填$i$，那么剩余位置的方案数为$f(i-2)$。因此$f(i)=f(i-1)+f(i-2)$。
懂了，矩阵快速幂是普及组 T1 难度考点。
#include<cstdio>
#include<cstring>
const int MOD = 998244353;
long long n;
struct matrix {
int l, w, a[3][3];
matrix(int lv = 0, int wv = 0): l(lv), w(wv) { memset(a, 0, sizeof a); }
int* operator [] (const int &idx) { return &a[idx][0]; }
matrix operator * (matrix b) {
matrix ans(l, b.w);
for (int i = 1; i <= ans.l; i++)
for (int j = 1; j <= ans.w; j++)
for (int k = 1; k <= w; k++) ans[i][j] = (ans[i][j] + (long long)a[i][k] * b[k][j] % MOD) % MOD;
return ans;
}
inline void build() { for (int i = 1; i <= l; i++) a[i][i] = 1; }
}f(2, 1), trs(2, 2);
inline matrix pwr(matrix x, long long k) {
matrix ans(x.l, x.w); ans.build();
for (; k; x = x * x, k >>= 1)
if (k & 1) ans = ans * x;
return ans;
}
int main() {
f[1][1] = 1;
trs[1][1] = trs[1][2] = trs[2][1] = 1;
scanf("%lld", &n);
f = pwr(trs, n) * f;
printf("%d\n", f[1][1]);
return 0;
}http://www.zhengruioi.com/contest/695/problem/1546
设一条路径经过了$k$个点，最后在深度为$d$的节点停下，那么最小步数为$2(k-1)-d$。可以考虑在走完某条路径后再回到根节点，那么最小步数为$2(k-1)$，因为显然每条边都最少经过两次。然后因为不用回到根节点所以最小步数为$2(k-1)-d$。然后根据题目条件有$2(k-1)-\min(m,d)\le m$，这里$d$变成了$\min(m,d)$的原因是当$d>m$时无法走到深度为$d$的点，最多只能走到深度为$m$的点。因此$k\le\dfrac{m+\min(m,d)}{2}+1$，所以答案就是$\min(n,\dfrac{m+\min(m,d)}{2}+1)$。
#include<cstdio>
int n, m, d;
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;
inline int min(int a, int b) { return a < b ? a : b; }
inline int max(int a, int b) { return a > b ? a : b; }
void dfs(int x, int lst, int cnt) {
d = max(d, cnt);
for (int i = g.head[x]; i; i = g.edges[i].next) {
if ((i ^ lst) == 1) continue;
int &v = g.edges[i].to;
dfs(v, i, cnt + 1);
}
}
int main() {
scanf("%d%d", &n, &m);
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, 0);
printf("%d\n", min(n, (m + min(m, d)) / 2 + 1));
return 0;
}http://www.zhengruioi.com/contest/695/problem/1547
可以考虑每种颜色对答案的贡献即包含这种颜色的路径条数，那么补集转化一下就是所有路径减去不包含这种颜色的路径条数。所有这种颜色的点把树分成若干连通块，每个连通块的路径条数就是$\binom{size}{2}$，除根节点所在的连通块外，每个连通块都有一个位于顶端的这种颜色的节点，可以在这个节点处计算连通块大小。
有一个巧妙的方法：设$s_i$为以节点$i$为顶端的连通块大小，$f[c[x]]$表示当前所有以第$c[x]$种颜色的节点为顶端的连通块大小$+1$之和，那么在递归遍历完以子节点$v$为根的子树后，可以得到$f[c[x]]$的增量，而$size[v]$减去这个增量就是$v$所在的连通块的大小。之所以要使$f[c[x]]$加一，是因为还要算上这个颜色的节点，这样用$size[v]$减才是对的。
#include<cstdio>
int n, c[200100], size[200100], f[200100], cn;
bool vis[200100];
long long ans;
struct edge { int to, next; };
struct graph {
int ecnt = 1, head[200100];
edge edges[400100];
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) {
size[x] = 1; f[c[x]]++;
for (int i = g.head[x]; i; i = g.edges[i].next) {
if ((i ^ lst) == 1) continue;
int &v = g.edges[i].to, s = f[c[x]];
dfs(v, i);
size[x] += size[v];
s = size[v] - (f[c[x]] - s);
f[c[x]] += s;
ans -= (long long)s * (s - 1) / 2;
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &c[i]), vis[c[i]] = true;
for (int i = 1; i <= n; i++) if (vis[i]) cn++;
for (int i = 1; i < n; i++) {
int u, v; scanf("%d%d", &u, &v);
g.addedge(u, v); g.addedge(v, u);
}
ans = (long long)cn * n * (n - 1) / 2;
dfs(1, 0);
for (int i = 1; i <= n; i++) if (vis[i]) ans -= (long long)(n - f[i]) * (n - f[i] - 1) / 2;
printf("%lld\n", ans);
return 0;
}http://www.zhengruioi.com/contest/695/problem/1548
是个 DP，然后题解其他部分我就看不懂了，垃圾题解写了跟没写一样，连转移方程都没有，状态含义也是含糊不清。等我 DP 水平提高点再来补。
https://www.luogu.com.cn/problem/P1776
多重背包模板题。设$dp[j]$表示所选重量之和为$j$时的最大价值和，那么$dp[j]=\max\limits_{i=1}^c (dp[j-wi]+vi)$，可以用把$j$按照$j\bmod w$的值分组，然后直接对每组 DP，从而可以用单调队列优化。不用推式子，但其他题解上都推了一堆式子，不是很懂。
#include<cstdio>
#include<queue>
int n, m;
long long dp[40100], ans;
std::deque<int> q;
inline long long max(long long a, long long b) { return a > b ? a : b; }
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
int v, w, c; scanf("%d%d%d", &v, &w, &c);
for (int b = 0; b < w; b++) {
int cur = (m - b) / w - 1;
q.clear();
for (int a = (m - b) / w; a >= 0; a--) {
while (!q.empty() && q.front() >= a) q.pop_front();
while (cur >= 0 && cur >= a - c) {
while (!q.empty() && dp[q.back() * w + b] + v * (a - q.back()) <= dp[cur * w + b] + v * (a - cur)) q.pop_back();
q.push_back(cur);
cur--;
}
if (!q.empty()) dp[a * w + b] = max(dp[a * w + b], dp[q.front() * w + b] + v * (a - q.front()));
}
}
}
for (int i = 1; i <= m; i++) ans = max(ans, dp[i]);
printf("%lld\n", ans);
return 0;
}https://www.luogu.com.cn/problem/P1833
混合背包模板题，直接写即可。
#include<cstdio>
#include<queue>
int n, m, tshh, tsmm, tehh, temm;
long long dp[1010], ans;
std::deque<int> q;
inline long long max(long long a, long long b) { return a > b ? a : b; }
int main() {
scanf("%d:%d %d:%d %d", &tshh, &tsmm, &tehh, &temm, &n);
m = tehh * 60 + temm - (tshh * 60 + tsmm);
for (int i = 1; i <= n; i++) {
int w, v, c; scanf("%d%d%d", &w, &v, &c);
if (c == 0) for (int j = w; j <= m; j++) dp[j] = max(dp[j], dp[j - w] + v);
else if (c == 1) for (int j = m; j >= w; j--) dp[j] = max(dp[j], dp[j - w] + v);
else {
for (int b = 0; b < w; b++) {
int cur = (m - b) / w - 1;
for (int a = (m - b) / w; a >= 0; a--) {
while (!q.empty() && q.front() >= a) q.pop_front();
while (cur >= 0 && cur >= a - c) {
while (!q.empty() && dp[q.back() * w + b] + v * (a - q.back()) <= dp[cur * w + b] + v * (a - cur)) q.pop_back();
q.push_back(cur);
cur--;
}
if (!q.empty()) dp[a * w + b] = max(dp[a * w + b], dp[q.front() * w + b] + v * (a - q.front()));
}
}
}
}
for (int i = 1; i <= m; i++) ans = max(ans, dp[i]);
printf("%lld\n", ans);
return 0;
}