striving & singing
https://www.luogu.com.cn/problem/P1537
设$dp[i]$表示权值和能否凑成$i$，那么问题就是一个有 6 种物品的多重背包问题，使用单调队列优化即可。
注意特判$m$是否能整除$2$。
另外我之前在写单调队列优化时习惯只存下标而不是存下标和对应的值，然后在 DP 时按照拓扑序 DP，保证每个值在被更新前取到，这种写法在写多重背包时十分恶心，需要各种加加减减以及其他一些写起来浑身难受的操作，于是我决定改为同时存下标和对应的值，但每次都要多写个结构体也不太舒服，于是用了 STL 的 pair，还是挺方便的，写起来好受多了。并且我测试了一下，使用 pair 似乎比只存下标要快一些，后者应该是因为计算量更大所以常数更大。
使用 pair 所需的头文件为
#include<cstdio>
#include<cstring>
#include<queue>
#include<utility>
int n[7], m, k;
bool dp[120100];
std::deque<std::pair<int, int> > q;
int main() {
while (~scanf("%d%d%d%d%d%d", &n[1], &n[2], &n[3], &n[4], &n[5], &n[6])) {
k++;
m = n[1] + n[2] * 2 + n[3] * 3 + n[4] * 4 + n[5] * 5 + n[6] * 6;
if (m == 0) break;
memset(dp, 0, sizeof dp); dp[0] = true;
for (int i = 1; i <= 6; i++) {
for (int b = 0; b < i; b++) {
q.clear();
for (int a = 0; a * i + b <= m; a++) {
int x = a * i + b;
while (!q.empty() && (dp[x] || (!dp[x] && !q.back().second))) q.pop_back();
q.push_back(std::make_pair(x, dp[x]));
while (!q.empty() && q.front().first < x - i * n[i]) q.pop_front();
if (!q.empty()) dp[x] = dp[x] || q.front().second;
}
}
}
if (!(m % 2) && dp[m / 2]) printf("Collection #%d:\nCan be divided.\n\n", k);
else printf("Collection #%d:\nCan't be divided.\n\n", k);
}
return 0;
}https://www.luogu.com.cn/problem/P1356
设$dp[i][j]$表示前 i 个位置组成数列能否被 j 整除，那么有
$$dp[i][j]=dp[i-1][j+a[i]]\ ||\ dp[i-1][j-a[i]]$$
边界条件为$dp[1][-a[1]]=dp[1][a[1]]=\text{true}$。
#include<cstdio>
#include<cstring>
int t, n, k;
bool dp[10010][110];
int main() {
scanf("%d", &t);
while (t--) {
scanf("%d%d", &n, &k);
memset(dp, 0, sizeof dp);
for (int i = 1; i <= n; i++) {
int a; scanf("%d", &a);
if (i == 1) dp[1][(a % k + k) % k] = dp[1][(-a % k + k) % k] = true;
else for (int j = 0; j < k; j++) dp[i][j] = dp[i - 1][((j - a) % k + k) % k] || dp[i - 1][((j + a) % k + k) % k];
}
if (dp[n][0]) printf("Divisible\n");
else printf("Not divisible\n");
}
return 0;
}http://csp.ac/contest/37/problem/265
猜结论题，当$n=2$时先手必胜，否则如果$n$是奇数且皮蛋先手则皮蛋胜，否则黑妞胜。
#include<cstdio>
int t;
int main() {
scanf("%d", &t);
while (t--) {
int n, op, bit = 0;
char c = getchar();
while (c != ' ') {
if ('0' <= c && c <= '9') n = c - '0', bit++;
c = getchar();
}
scanf("%d", &op);
if (n == 2 && bit == 1) printf("%d\n", op);
else if (n % 2 && !op) printf("0\n");
else printf("1\n");
}
return 0;
}由于每个位置的颜色只取决于最后一次被染色时的颜色，所以考虑把操作倒序，每次操作都相当于把对应行或列直接删掉，让答案加上当前的列数或行数。
#include<cstdio>
int n, m, k;
long long ans;
bool vis[2][1000100];
struct operation {
int x, y, z;
}opts[1000100];
int main() {
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= k; i++) scanf("%d%d%d", &opts[i].x, &opts[i].y, &opts[i].z);
for (int i = k; i >= 1; i--) {
int x = opts[i].x, y = opts[i].y, z = opts[i].z;
if (!vis[x][y]) {
if (!x) ans += m * z, n--;
else ans += n * z, m--;
}
vis[x][y] = true;
}
printf("%lld\n", ans);
return 0;
}http://csp.ac/contest/37/problem/267
当 t 确定时，选手之间的次序关系也唯一确定，因此每次直接$O(n)$分治找第$k$大元素即可。
离谱的是，我的$O(mnlogn)$暴力排序过了，$O(mn)$分治却只拿了70分。
#include<cstdio>
#include<algorithm>
int n, q, t;
struct player {
int a, v, id;
bool operator < (const player &b) const {
if ((a + (long long)v * t) ^ (b.a + (long long)b.v * t)) return a + (long long)v * t > b.a + (long long)b.v * t;
else return id < b.id;
}
}p[7010];
inline void swap(player &a, player &b) { player t = a; a = b; b = t; }
int kth(int l, int r, int k) {
if (l == r) return p[l].id;
player x = p[l];
int i = l, j = r;
while (i < j) {
while (i < j && x < p[j]) j--;
p[i] = p[j];
while (i < j && p[i] < x) i++;
p[j] = p[i];
}
p[i] = x;
if (k <= i - l + 1) return kth(l, i, k);
else return kth(i + 1, r, k - (i - l + 1));
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d%d", &p[i].v, &p[i].a);
p[i].id = i;
}
scanf("%d", &q);
for (int i = 1; i <= q; i++) {
int k; scanf("%d%d", &t, &k);
printf("%d\n", kth(1, n, k));
}
return 0;
}http://csp.ac/contest/37/problem/268
把每个数 -1，那么分数就由$(s_1-x)(s_2-y)$变为$s_1s_2$，简化了问题。对于一次操作，因为$(a+b)(c+d)\ge ac+bd$，所以显然同时删掉两段长度大于 1 的序列不如最多只删掉一个长度大于 1 的序列优，于是可以$O(n^3)$ DP，设$dp[i][j]$表示 A 的前 i 个位置和 B 的前 j 个位置还没有删掉，那么有
$$dp[i][j]=\max\left(\max_{k=1}^{i-1}{dp[k][j-1]+suma(k+1,i)\times b[j]},\max_{k=1}^{j-1}{dp[i-1][k]+sumb(k+1,j)\times a[i]}\right)$$
因为$suma(k+1,i-1)\times b[j]$已经更新过了$dp[i-1][j]$，$sumb(k+1,j-1)\times a[i]$也已经更新过了$dp[i][j-1]$，所以可以优化为
$$dp[i][j]=\max(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+a[i]\times b[j]$$
需要初始化为$\inf$，并且$dp[0][0]=0$。
另外洛谷有原题(P1846)。
#include<cstdio>
#include<cstring>
int n, m, a[2010], b[2010];
long long dp[2010][2010];
inline long long min(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++) scanf("%d", &a[i]), a[i]--;
for (int i = 1; i <= m; i++) scanf("%d", &b[i]), b[i]--;
memset(dp, 0x3f, sizeof dp);
dp[0][0] = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + a[i] * b[j];
printf("%lld\n", dp[n][m]);
return 0;
}显然是二分，不过 check 函数可能有点细节。二分最大的距离，在 check 函数中需要在满足限制的前提下尽可能得少放置路灯，这类似于区间覆盖，可以记录 lst 表示上一个路灯放置的坐标， p 表示第一个还没被覆盖的路灯坐标，然后分情况讨论即可。注意若上一个路灯和当前路灯的距离大于二分值则需要同时更新 p 。
另外，因为坐标可能是 0 所以不存在的值要表示为 -INF (好像 INF 也行)。
比赛时我看错题了，以为是所有被点亮的路灯与距离最近的路灯的距离的最大值最小，而不是所有路灯，写了个二分对拍没错，但交上去爆零了。
#include<cstdio>
const int INF = 0x3fffffff;
int n, k, a[100100];
bool check(int mid) {
int cnt = 0, lst = -INF, p = a[1];
for (int i = 2; i <= n; i++) {
if (p == -INF && a[i] - lst > mid) p = a[i];
else if (p != -INF && a[i] - p > mid) lst = a[i - 1], cnt++, p = (a[i] - lst > mid ? a[i] : -INF);
}
if (p != -INF) cnt++;
return cnt <= k;
}
int main() {
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
int l = 1, r = a[n] - a[1] + 1;
while (l < r) {
int mid = l + (r - l >> 1);
if (check(mid)) r = mid;
else l = mid + 1;
}
printf("%d\n", l);
return 0;
}可以$O(n^3)$预处理$g[i][j]$表示把$i$和$j$点亮时，$(i,j)$中所有路灯与距离它最近的路灯的距离的和。然后设$f[i][k]$表示前$i$个路灯中点亮了$k$个且点亮了第$i$个路灯时的最小和，那么有：
$$f[i][k]=\begin{cases}g[0][i]&k=1\\\min_{j=1}^{i-1}{dp[j][k-1]+g[j][i]}&k>1\end{cases}$$
其中$g[0][i]$表示前$i-1$个路灯和第$i$个路灯的距离和。同理，$g[i][n+1]$表示$[i+1,n]$中所有路灯和第$i$个路灯的距离和。令$a[0]=-\inf,a[n+1]=\inf$，然后在计算$g$时就可以顺便处理。
最后的答案是$\min_{i=1}^n{dp[i][k]+g[i][n+1]}$。
同样，这题和 t1 一样看错题了，因为一个求最小最大值一个求最小和，其他除了数据范围完全一样。本来就 t1 和 t3 写了正解，结果这两题都看错题了，我好菜。
#include<cstdio>
#include<cstring>
const int INF = 0x3fffffff;
int n, k, a[210], f[210][210], g[210][210], ans = INF;
inline int min(int a, int b) { return a < b ? a : b; }
int main() {
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
a[0] = -INF, a[n + 1] = INF;
for (int i = 0; i <= n; i++)
for (int j = i + 1; j <= n + 1; j++)
for (int k = i + 1; k < j; k++) g[i][j] += min(a[k] - a[i], a[j] - a[k]);
memset(f, 0x3f, sizeof f);
f[1][1] = 0;
for (int i = 2; i <= n; i++) {
f[i][1] = g[0][i];
for (int k = 2; k <= i; k++)
for (int j = 1; j < i; j++) f[i][k] = min(f[i][k], f[j][k - 1] + g[j][i]);
}
for (int i = 1; i <= n; i++) ans = min(ans, f[i][k] + g[i][n + 1]);
printf("%d\n", ans);
return 0;
}通过想象可以得出，三个点能够组成一个组合，当且仅当这三个点中间有个距离他们都是 2 的中转点。那么类似于联合权值那道题，可以枚举中转点，那么这个点对答案的贡献就是所有与它距离为 2 的点的权值中的所有三元组的乘积之和。
设$dp[x]$表示编号为$x$的节点的所有子节点的权值和。考虑当前中转点遍历所有子节点的过程，根据乘法分配律，当前子节点的$dp[v]$对答案的贡献为$dp[v]$乘上其他二元组权值乘积之和。设 s1 表示当前已遍历过的$dp[v]$与其他和 x 距离为 2 但不是 x 的子节点的权值之和，s2 表示当前已遍历过的$dp[v]$与其他和 x 距离为 2 但不是 x 的子节点的二元组权值乘积之和(可以理解为，s1 对应一元组，s2 对应二元组)。那么每遍历到一个子节点，它对答案的贡献就是$dp[v]\times s2$。而 s2 在原有的基础上还要加上$dp[v]\times s1$，$s1$在原有的基础上还要加上$dp[v]$。
#include<cstdio>
int n, a[100100], f[100100];
long long dp[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 dfs1(int x, int lst) {
f[x] = g.edges[lst ^ 1].to;
for (int i = g.head[x]; i; i = g.edges[i].next) {
if ((i ^ lst) == 1) continue;
int &v = g.edges[i].to;
dfs1(v, i);
dp[x] += a[v];
}
}
void dfs2(int x, int lst) {
long long s1 = (f[x] ? dp[f[x]] - a[x] : 0) + a[f[f[x]]], s2 = 0;
for (int i = g.head[x]; i; i = g.edges[i].next) {
if ((i ^ lst) == 1) continue;
int &v = g.edges[i].to;
dfs2(v, i);
ans += s2 * dp[v];
s2 += s1 * dp[v];
s1 += dp[v];
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 1; i < n; i++) {
int u, v; scanf("%d%d", &u, &v);
g.addedge(u, v); g.addedge(v, u);
}
dfs1(1, 0);
dfs2(1, 0);
printf("%lld\n", ans);
return 0;
}http://csp.ac/contest/39/problem/273
显然可以二分 k ，但 n 比较大无法直接计算比较，有个巧妙的做法是取$\log$，因为$a>b\Leftrightarrow \log a>\log b$所以是对的。类似地，也可以取 sqrt 或者其他一些满足上面这个性质的运算，不过阶乘就算取 sqrt 也没法算所以还是不行。
#include<cstdio>
#include<cmath>
int n;
double logn;
bool check(int k) {
double logk = 0;
for (int i = 1; i <= k; i++) logk += log2(i);
return logk * 2 >= logn;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) logn += log2(i);
int l = 1, r = n + 1;
while (l < r) {
int mid = l + (r - l >> 1);
if (check(mid)) r = mid;
else l = mid + 1;
}
printf("%d\n", l);
return 0;
}http://csp.ac/contest/39/problem/274
中规模模拟题。注意任务之间比较的是开始时间，另外正在做的任务 dgtks 在加入新节点时，其结束时间为 lst + t[f.x]，而不是 f.t + t[f.x]。
#include<cstdio>
#include<cstring>
#include<string>
#include<map>
#include<vector>
#include<algorithm>
#include<iostream>
#include<queue>
int cur, l, n, t[1010], thread, deg[1010], ans, lst;
char s[5000100];
bool vis[1010];
struct node {
int x, t; std::string name;
bool operator < (const node &b) const {
if (t ^ b.t) return t > b.t;
return name > b.name;
}
node(int xv = 0, int tv = 0, std::string s = "\0"): x(xv), t(tv), name(s) {}
};
std::priority_queue<node> q, dgtks;
std::vector<node> nodes;
struct edge { int to, next, w; };
struct graph {
int ecnt, head[1010];
edge edges[200100];
inline void addedge(int u, int v) {
edges[++ecnt].to = v;
edges[ecnt].next = head[u];
head[u] = ecnt;
deg[v]++;
}
}g;
std::map<std::string, int> id; std::map<int, std::string> nme;
std::vector<char> ed1, ed2, ed3, ed4, bg, empty;
inline void init() {
cur = 1;
ed1.push_back(':'); ed2.push_back(','); ed2.push_back(']');
ed3.push_back(';'); ed3.push_back('/'); ed4.push_back('\0');
bg.push_back(':'); bg.push_back('[');
}
inline bool exist(std::vector<char> &s, char &c) { return find(s.begin(), s.end(), c) != s.end(); }
inline char read(std::string &name, int &begin, std::vector<char> &bg, std::vector<char> &ed) {
for (; !exist(ed, s[begin]); begin++)
if (!exist(bg, s[begin])) name.push_back(s[begin]);
return s[begin++];
}
inline void newnode(std::string &name) { if (!id.count(name)) id[name] = ++n, nme[n] = name; }
inline int toint(std::string &s) {
int ans = 0;
for (std::string::iterator p = s.begin(); p != s.end(); p++) ans = ans * 10 + *p - '0';
return ans;
}
inline char readtask() {
std::string u_name;
read(u_name, cur, empty, ed1);
newnode(u_name);
std::string v_name;
char c;
do {
c = read(v_name, cur, bg, ed2);
if (v_name.size() == 0) break;
newnode(v_name);
g.addedge(id[v_name], id[u_name]);
v_name.clear();
} while (c != ']');
std::string ts;
c = read(ts, cur, bg, ed3);
t[id[u_name]] = toint(ts);
return c;
}
inline int max(int a, int b) { return a > b ? a : b; }
inline void topo() {
for (int i = 1; i <= n; i++)
if (!deg[i]) nodes.push_back(node(i, 0, nme[i]));
std::sort(nodes.begin(), nodes.end());
for (std::vector<node>::iterator p = --nodes.end(); ; p--) {
if ((int)dgtks.size() < thread) dgtks.push(node(p -> x, t[p -> x], p -> name));
else q.push(*p);
if (p == nodes.begin()) break;
}
while (!dgtks.empty()) {
int lst = -1;
while (!dgtks.empty() && (lst == -1 || dgtks.top().t == lst)) {
node f = dgtks.top();
dgtks.pop();
ans = max(ans, f.t); lst = f.t;
for (int i = g.head[f.x]; i; i = g.edges[i].next) {
int &v = g.edges[i].to;
deg[v]--;
if (!deg[v]) q.push(node(v, f.t, nme[v]));
}
}
while ((int)dgtks.size() < thread && !q.empty()) {
node f = q.top();
dgtks.push(node(f.x, lst + t[f.x], f.name));
q.pop();
}
}
}
int main() {
scanf("%s", s + 1); l = strlen(s + 1);
init();
while (readtask() != '/');
std::string ts; read(ts, cur, empty, ed4);
thread = toint(ts);
topo();
printf("%d\n", ans);
return 0;
}http://csp.ac/contest/39/problem/276
暴力是枚举 V 字的两端，计算中间有多少个小于两端的数，但其实可以枚举中间的数，计算两边分别有多少个大于它的数，再相乘即可。可以直接用值域树状数组维护，因为求的是后缀和所以在树状数组中要把序列反转，也就是x = n - x + 1。
#include<cstdio>
#include<cstring>
const int MOD = 1e9 + 7;
int n, a[100100];
long long f[100100], g[100100], ans;
struct ft {
long long a[100100];
inline int lowbit(int x) { return x & -x; }
inline void add(int x, int v) { for (x = n - x + 1; x <= n; x += lowbit(x)) a[x] += v; }
inline long long query(int x) {
long long ans = 0;
for (x = n - x + 1; x >= 1; x -= lowbit(x)) ans += a[x];
return ans;
}
inline void clear() { memset(a, 0, sizeof(long long) * (n + 1)); }
}ft;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 1; i <= n; i++) {
f[i] = ft.query(a[i] + 1);
ft.add(a[i], i);
}
ft.clear();
for (int i = n; i >= 1; i--) {
g[i] = ft.query(a[i] + 1);
ft.add(a[i], n - i + 1);
}
for (int i = 1; i <= n; i++) ans = (ans + f[i] * g[i] % MOD) % MOD;
printf("%lld\n", ans);
return 0;
}http://csp.ac/contest/40/problem/277
显然可以直接二分油箱容量，然后判断所有边权小于等于油箱容量的边组成的图是否满足任意一个点都能到达其他所有点，等价于图中只有一个强连通分量，直接上 tarjan 即可。另一种思路是等价于节点 1 能够到达所有节点，并且所有节点都能到达节点 1。两种都可以$O(n)$解决，总复杂度$O(n\log w)$。
#include<cstdio>
#include<stack>
#include<cstring>
int n, m, dfn[50100], low[50100], scccnt, cnt, maxw;
bool vis[50100];
struct edge { int to, next, w; };
struct graph {
int ecnt, head[50100];
edge edges[200100];
inline void addedge(int u, int v, int w) {
edges[++ecnt].to = v;
edges[ecnt].w = w;
edges[ecnt].next = head[u];
head[u] = ecnt;
}
}g;
std::stack<int> stk;
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 tarjan(int x, const int mid) {
dfn[x] = low[x] = ++cnt;
vis[x] = true;
stk.push(x);
for (int i = g.head[x]; i; i = g.edges[i].next) {
if (g.edges[i].w > mid) continue;
int &v = g.edges[i].to;
if (!dfn[v]) { tarjan(v, mid); low[x] = min(low[x], low[v]); }
else if (vis[v]) { low[x] = min(low[x], dfn[v]); }
}
if (dfn[x] == low[x]) {
++scccnt;
int t;
do {
t = stk.top();
vis[t] = false;
stk.pop();
} while (t != x);
}
}
bool check(int mid) {
memset(dfn, 0, sizeof(int) * (n + 1)); memset(low, 0, sizeof(int) * (n + 1)); memset(vis, 0, sizeof(bool) * (n + 1));
cnt = scccnt = 0;
for (int i = 1; i <= n; i++)
if (!dfn[i]) tarjan(i, mid);
return scccnt == 1;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int u, v, w; scanf("%d%d%d", &u, &v, &w);
g.addedge(u, v, w);
maxw = max(maxw, w);
}
int l = 1, r = maxw + 1;
while (l < r) {
int mid = l + (r - l >> 1);
if (check(mid)) r = mid;
else l = mid + 1;
}
if (l <= maxw) printf("%d\n", l);
else printf("-1\n");
return 0;
}http://csp.ac/contest/40/problem/278
考虑序列上的情况，可以对区间分治，每次返回左区间 a 的和与右区间 b 的和的乘积，这样显然是对的，而且很巧妙。复杂度$O(n\log n)$。对于树上的情况，直接套上去即可。
http://csp.ac/contest/40/problem/279
可以通过前后缀优化$O(nm)$ DP 出前某个位置和后某个位置不用某种颜色的最小代价，然后枚举相同的颜色，单调队列优化即可。然而考场上没调出来直接爆零了，到现在也没调出来。
http://csp.ac/contest/40/problem/280
考虑每次在末尾添加一个数字。将好数看作点，点之间的边权为一个好数最少要添加几个数字才能得到另一个好数，那么问题求的就是图的最短哈密顿通路，可以直接状压 DP 。求好数之间的距离可以用最短路。
return