striving & singing
https://www.luogu.com.cn/problem/AT2021
直接推一下式子：
$$\sum_{x_1=l_1}^{r_1}\sum_{x_2=l_2}^{r_2}...\sum_{x_n=l_n}^{r_n}\sum_{a_1+a_2+...+a_n=c}\prod_{i=1}^n x_i^{a_i}$$
$$=\sum_{a_1+a_2+...+a_n=c}\sum_{x_1=l_1}^{r_1}x_1^{a_1}\sum_{x_2=l_2}^{r_2}x_2^{a_2}...\sum_{x_n=l_n}^{r_n}x_n^{a_n}$$
对于这种若干变量之和为定值的求值，可以用背包解决。设$dp[i][j]$表示前 i 个变量之和等于 j 时的这个式子的值，有：
$$dp[i][j]=\sum_{k=0}^{j}dp[i-1][j-k]\sum_{x=l_i}^{r_i}x^{k}$$
直接预处理 k 次幂然后递推即可。
#include<cstdio>
const int MOD = 1e9 + 7;
int n, c, dp[410][410], pwrsum[410][410], l[410], r[410], maxr;
inline int max(int a, int b) { return a > b ? a : b; }
int main() {
scanf("%d%d", &n, &c);
for (int i = 1; i <= n; ++i) scanf("%d", &l[i]);
for (int i = 1; i <= n; ++i) scanf("%d", &r[i]), maxr = max(maxr, r[i]);
for (int i = 1; i <= maxr; ++i) pwrsum[0][i] = 1;
for (int i = 1; i <= c; ++i)
for (int j = 1; j <= maxr; ++j) pwrsum[i][j] = (long long)pwrsum[i - 1][j] * j % MOD;
for (int i = 0; i <= c; ++i)
for (int j = 1; j <= maxr; ++j) pwrsum[i][j] = (pwrsum[i][j - 1] + pwrsum[i][j]) % MOD;
dp[0][0] = 1;
for (int i = 1; i <= n; ++i)
for (int j = 0; j <= c; ++j)
for (int k = 0; k <= j; ++k) dp[i][j] = (dp[i][j] + (long long)dp[i - 1][j - k] * (pwrsum[k][r[i]] - pwrsum[k][l[i] - 1] + MOD) % MOD) % MOD;
printf("%d\n", dp[n][c]);
return 0;
}https://www.luogu.com.cn/problem/AT2022
只要两个字符串的长度相同，那么得到这两个字符串的方案数就是相同的。于是可以设$dp[i][j]$表示操作了 i 次后字符串的长度为 j 的方案数，因为长度为 j 的字符串有$2^j$种所以递推完后把答案除以$2^j$即可。
#include<cstdio>
#include<cstring>
const int MOD = 1e9 + 7;
int n, m, dp[5010][5010];
char s[5010];
inline int pwr(int x, int k) {
int ans = 1;
for (; k; x = (long long)x * x % MOD, k >>= 1)
if (k & 1) ans = (long long)ans * x % MOD;
return ans;
}
inline int inv(int a) { return pwr(a, MOD - 2); }
int main() {
scanf("%d%s", &n, s + 1);
m = strlen(s + 1);
dp[0][0] = 1;
for (int i = 1; i <= n; ++i) {
dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) % MOD;
for (int j = 1; j <= n; ++j) dp[i][j] = (dp[i - 1][j - 1] * 2 % MOD + dp[i - 1][j + 1]) % MOD;
}
printf("%lld\n", (long long)dp[n][m] * inv(pwr(2, m)) % MOD);
return 0;
}https://www.luogu.com.cn/problem/AT2038
对于这个数据范围，复杂度只能是$O(\log n)$，$O(\sqrt n)$之类的。于是不难想到当$b>\sqrt n$时，n 在 b 进制下是一个两位数。两位数好像只是算得快一些，似乎没什么性质。然后我就想不出来了。
可以把这个两位数设出来。设它是$n=pb+q$，那么显然$s=p+q$。两式相减可以得出$n-s=p(b-1)$，即$b=\dfrac{n-s}{p}+1$。因为 b 是整数，所以可以枚举$n-s$的所有因子 p ，然后验证是否可行即可，复杂度$O(\sqrt n)$。
当$b\le \sqrt n$时，可以直接暴力验证。总复杂度$O(\sqrt n\log n)$。
#include<cstdio>
const long long INF = 0x7fffffffffffffff;
long long n, s, ans = INF;
bool ok;
inline bool check(int b) {
long long x = n, sum = 0;
while (x) sum += x % b, x /= b;
return sum == s;
}
inline long long min(long long a, long long b) { return a < b ? a : b; }
int main() {
scanf("%lld%lld", &n, &s);
for (int i = 2; (long long)i * i <= n; ++i)
if (check(i)) ans = min(ans, i);
for (long long p = 1; p * p <= n - s; ++p) {
if ((n - s) % p) continue;
long long b = (n - s) / p + 1, q = n - p * b;
if (b > (double)n / b && p >= 0 && p < b && q >= 0 && q < b && p + q == s) ans = min(ans, b);
b = p + 1, q = n - p * b;
if (b > (double)n / b && p >= 0 && p < b && q >= 0 && q < b && p + q == s) ans = min(ans, b);
}
if (n == s) ans = min(ans, n + 1);
if (ans != INF) printf("%lld\n", ans);
else printf("-1\n");
return 0;
}https://www.luogu.com.cn/problem/AT2039
一次行程等价于把序列分为尽量少的段，使得每段的和都大于等于 l，所以从左到右和从右到左是等价的。倍增预处理向右走 2 的幂天后到达的位置即可。
#include<cstdio>
#include<algorithm>
int n, l, q, pos[100100], nxt[100100][18];
inline void swap(int &a, int &b) { int t = a; a = b; b = t; }
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &pos[i]);
scanf("%d", &l);
for (int i = n; i >= 1; --i) {
nxt[i][0] = std::upper_bound(pos + 1, pos + n + 1, pos[i] + l) - 1 - pos;
for (int j = 1; j < 18; ++j) nxt[i][j] = nxt[nxt[i][j - 1]][j - 1];
}
scanf("%d", &q);
while (q--) {
int a, b, ans = 0; scanf("%d%d", &a, &b);
if (a > b) swap(a, b);
for (int j = 17; j >= 0; --j)
if (nxt[a][j] < b) a = nxt[a][j], ans += (1 << j);
printf("%d\n", ans + 1);
}
return 0;
}https://www.luogu.com.cn/problem/P3916
考虑把过程反过来，让编号最大的点反过来遍历这个点。于是可以建一个反图，然后倒序枚举所有点为起点，把能到达的所有没被标记过的点标记一下即可。
#include<cstdio>
int n, m, ans[100100];
struct edge { int to, next; };
struct graph {
int ecnt, 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 s) {
if (ans[x]) return;
ans[x] = s;
for (int i = g.head[x]; i; i = g.edges[i].next) dfs(g.edges[i].to, s);
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; ++i) {
int u, v; scanf("%d%d", &u, &v);
g.addedge(v, u);
}
for (int x = n; x >= 1; --x) dfs(x, x);
for (int i = 1; i <= n; ++i) printf("%d ", ans[i]);
return 0;
}下面是今天校内模拟赛的题。
设$f[i][j][k][l]$表示两个数组分别取到$[i,j],[k,l]$时当前手的最高分，$g[i][j][k][l]$表示最优决策，枚举当前手和对手的决策并分情况讨论即可。
其实可以像在矩阵上搜索一样开几个常量数组来简化代码，不过考场上没想到。
#include<cstdio>
#include<cstring>
int t, n, a[23], b[23], df[23][23][23][23];
long long f[23][23][23][23];
inline long long max(long long a, long long b) { return a > b ? a : b; }
int main() {
freopen("game.in", "r", stdin);
freopen("game.out", "w", stdout);
scanf("%d", &t);
while (t--) {
memset(f, 0, sizeof f); memset(df, 0, sizeof df);
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
for (int i = 1; i <= n; ++i) scanf("%d", &b[i]);
for (int i = 1; i <= n; ++i)
for (int k = 1; k <= n; ++k) {
f[i][i][k][k - 1] = a[i], df[i][i][k][k - 1] = 1;
f[i][i - 1][k][k] = b[k], df[i][i - 1][k][k] = 3;
}
for (int la = 0; la <= n; ++la)
for (int lb = 0; lb <= n; ++lb) {
if (!la && !lb) continue;
for (int i = 1; i + la - 1 <= n; ++i)
for (int k = 1; k + lb - 1 <= n; ++k) {
int j = i + la - 1, l = k + lb - 1;
//a[i+1,j] b[k,l]
if (df[i + 1][j][k][l] == 1) {
if (f[i][j][k][l] < f[i + 2][j][k][l] + a[i])
f[i][j][k][l] = f[i + 2][j][k][l] + a[i], df[i][j][k][l] = 1;
}
else if (df[i + 1][j][k][l] == 2) {
if (f[i][j][k][l] < f[i + 1][j - 1][k][l] + a[i])
f[i][j][k][l] = f[i + 1][j - 1][k][l] + a[i], df[i][j][k][l] = 1;
}
else if (df[i + 1][j][k][l] == 3) {
if (f[i][j][k][l] < f[i + 1][j][k + 1][l] + a[i])
f[i][j][k][l] = f[i + 1][j][k + 1][l] + a[i], df[i][j][k][l] = 1;
}
else if (df[i + 1][j][k][l] == 4) {
if (f[i][j][k][l] < f[i + 1][j][k][l - 1] + a[i])
f[i][j][k][l] = f[i + 1][j][k][l - 1] + a[i], df[i][j][k][l] = 1;
}
//a[i,j-1] b[k,l]
if (df[i][j - 1][k][l] == 1) {
if (f[i][j][k][l] < f[i + 1][j - 1][k][l] + a[j])
f[i][j][k][l] = f[i + 1][j - 1][k][l] + a[j], df[i][j][k][l] = 2;
}
else if (df[i][j - 1][k][l] == 2) {
if (f[i][j][k][l] < f[i][j - 2][k][l] + a[j])
f[i][j][k][l] = f[i][j - 2][k][l] + a[j], df[i][j][k][l] = 2;
}
else if (df[i][j - 1][k][l] == 3) {
if (f[i][j][k][l] < f[i][j - 1][k + 1][l] + a[j])
f[i][j][k][l] = f[i][j - 1][k + 1][l] + a[j], df[i][j][k][l] = 2;
}
else if (df[i][j - 1][k][l] == 4) {
if (f[i][j][k][l] < f[i][j - 1][k][l - 1] + a[j])
f[i][j][k][l] = f[i][j - 1][k][l - 1] + a[j], df[i][j][k][l] = 2;
}
//a[i,j] b[k+1,l]
if (df[i][j][k + 1][l] == 1) {
if (f[i][j][k][l] < f[i + 1][j][k + 1][l] + b[k])
f[i][j][k][l] = f[i + 1][j][k + 1][l] + b[k], df[i][j][k][l] = 3;
}
else if (df[i][j][k + 1][l] == 2) {
if (f[i][j][k][l] < f[i][j - 1][k + 1][l] + b[k])
f[i][j][k][l] = f[i][j - 1][k + 1][l] + b[k], df[i][j][k][l] = 3;
}
else if (df[i][j][k + 1][l] == 3) {
if (f[i][j][k][l] < f[i][j][k + 2][l] + b[k])
f[i][j][k][l] = f[i][j][k + 2][l] + b[k], df[i][j][k][l] = 3;
}
else if (df[i][j][k + 1][l] == 4) {
if (f[i][j][k][l] < f[i][j][k + 1][l - 1] + b[k])
f[i][j][k][l] = f[i][j][k + 1][l - 1] + b[k], df[i][j][k][l] = 3;
}
//a[i,j] b[k,l-1]
if (df[i][j][k][l - 1] == 1) {
if (f[i][j][k][l] < f[i + 1][j][k][l - 1] + b[l])
f[i][j][k][l] = f[i + 1][j][k][l - 1] + b[l], df[i][j][k][l] = 4;
}
else if (df[i][j][k][l - 1] == 2) {
if (f[i][j][k][l] < f[i][j - 1][k][l - 1] + b[l])
f[i][j][k][l] = f[i][j - 1][k][l - 1] + b[l], df[i][j][k][l] = 4;
}
else if (df[i][j][k][l - 1] == 3) {
if (f[i][j][k][l] < f[i][j][k + 1][l - 1] + b[l])
f[i][j][k][l] = f[i][j][k + 1][l - 1] + b[l], df[i][j][k][l] = 4;
}
else if (df[i][j][k][l - 1] == 4) {
if (f[i][j][k][l] < f[i][j][k][l - 2] + b[l])
f[i][j][k][l] = f[i][j][k][l - 2] + b[l], df[i][j][k][l] = 4;
}
}
}
printf("%lld\n", f[1][n][1][n]);
}
return 0;
}可以对每个位置算一下对答案的贡献，推完式子后直接二进制高精算一下即可，不过在做高精加减法时要把加减的位置标记一下然后在最后统一处理，这样复杂度才是$O(n)$的。
#include<cstdio>
#include<cstring>
int t, n, ans[2000100], len;
char s[1000100];
inline int max(int a, int b) { return a > b ? a : b; }
int main() {
freopen("binary.in", "r", stdin);
freopen("binary.out", "w", stdout);
scanf("%d", &t);
while (t--) {
memset(ans, 0, sizeof(int) * (len + 1)); len = 0;
scanf("%s", s + 1);
n = strlen(s + 1);
for (int i = 1; i <= n; ++i) {
if (s[i] == '1') for (int j = 0; (1 << j) <= i; ++j)
if (i & (1 << j))
ans[n - i + 1 + j]++, ans[j]--, len = max(len, n - i + 1 + j);
}
for (int i = 0; i <= len; ++i) {
if (ans[i] < 0) {
int d = (-ans[i] >> 1) + (-ans[i] & 1);
ans[i] += d << 1; ans[i + 1] -= d;
if (ans[i + 1] == 0 && i + 1 == len) len--;
}
else if (ans[i] > 1) {
int d = (ans[i] >> 1);
ans[i] -= d << 1; ans[i + 1] += d;
if (ans[i + 1] != 0 && i == len) len++;
}
}
for (int i = len; i >= 0; --i) printf("%d", ans[i]);
printf("\n");
}
return 0;
}用 manacher 或二分+哈希预处理出所有极长回文串，然后$O(n)$ DP 即可。
树上启发式合并，然而我不会。
下面又是今天校内模拟赛的题。
直接算一下前缀和然后输出答案即可。
#include<cstdio>
int n, m;
long long sum[100100];
int main() {
freopen("a.in", "r", stdin);
freopen("a.out", "w", stdout);
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) scanf("%lld", &sum[i]), sum[i] += sum[i - 1];
for (int i = 1; i <= n; ++i) printf("%lld ", sum[i] / m - sum[i - 1] / m);
return 0;
}把每个物品和商人的组合预处理出来，把价值作为位置，物品编号作为颜色，然后问题转化为求数轴上包含所有颜色的点的最小区间长度，直接双指针即可。
#include<cstdio>
#include<utility>
#include<algorithm>
int n, p[7], vcnt, cnt[100100], ccnt, ans = 2e9;
std::pair<int, int> v[600100];
inline int min(int a, int b) { return a < b ? a : b; }
int main() {
freopen("b.in", "r", stdin);
freopen("b.out", "w", stdout);
scanf("%d", &n);
scanf("%d%d%d%d%d%d", &p[1], &p[2], &p[3], &p[4], &p[5], &p[6]);
for (int i = 1; i <= n; ++i) {
int x; scanf("%d", &x);
for (int j = 1; j <= 6; ++j) v[++vcnt] = std::make_pair(x - p[j], i);
}
std::sort(v + 1, v + vcnt + 1);
int cur = 0;
for (int i = 1; i <= vcnt; ++i) {
while (ccnt < n && cur < vcnt) {
++cnt[v[++cur].second];
if (cnt[v[cur].second] == 1) ccnt++;
}
if (ccnt == n) ans = min(ans, v[cur].first - v[i].first);
--cnt[v[i].second];
if (cnt[v[i].second] == 0) ccnt--;
}
printf("%d\n", ans);
return 0;
}https://www.luogu.com.cn/problem/AT1999
把序列从大到小排序，然后画成一个柱状图，然后两种操作就相当于把最下面一行或者最左边一列切掉，等价于以左下角为起点每次向上或向右走，边界的点是必败点。然后有个规律是$y=x$这条对角线上的所有状态相同(边界点除外)，可以用反证法证明：
假设一个点是 0，它的右上角是 1，那么情况是：
? ? ?
1 1 ?
0 1 ?因为 1 的后继状态中一定存在一个 0，所以左上角和右下角都是 0。因为 0 的后继状态一定都是 1，所以可以推出这个矩阵是这样的：
0 1 ?
1 1 1
0 1 0正中间的 1 的两个后继状态都是 1，显然不合法。
还有另一种情况，即一个点是 1，它的右上角是 0：
? 1 ?
? 0 1
1 ? ?由于 0 的前驱状态一定都是 1，所以可以推出：
? 1 ?
1 0 1
1 1 ?这种情况显然也不合法。因此得证。
对于每个子树，求出所有点的编号有几个连续段。
据说可以树上启发式合并，不过我不会。不难想到维护有几个连续段可以用线段树，于是直接写个线段树合并即可。
#include<cstdio>
#include<cstring>
int t, n, root, ans[100100], rt[100100];
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;
}
inline void clear() { memset(head, 0, sizeof(int) * (n + 1)); memset(edges, 0, sizeof(edge) * (ecnt + 1)); ecnt = 1; }
}g;
struct segtreenode { int ans, ls, rs; bool lext, rext; };
struct segtree {
int cnt;
segtreenode nds[8000100];
inline void pushup(int x) {
nds[x].lext = nds[nds[x].ls].lext; nds[x].rext = nds[nds[x].rs].rext;
nds[x].ans = nds[nds[x].ls].ans + nds[nds[x].rs].ans;
if (nds[nds[x].ls].rext && nds[nds[x].rs].lext) nds[x].ans--;
}
inline int insert(int x, int l, int r, int q) {
if (!x) x = ++cnt;
if (l == r) { nds[x].lext = nds[x].rext = true; nds[x].ans = 1; return x; }
int mid = l + (r - l >> 1);
if (q <= mid) nds[x].ls = insert(nds[x].ls, l, mid, q);
if (mid + 1 <= q) nds[x].rs = insert(nds[x].rs, mid + 1, r, q);
pushup(x);
return x;
}
inline int query(int x, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) return nds[x].ans;
int mid = l + (r - l >> 1), ans = 0;
if (ql <= mid) ans = query(nds[x].ls, l, mid, ql, qr);
if (mid + 1 <= qr) ans += query(nds[x].rs, mid + 1, r, ql, qr);
if (ql <= mid && mid + 1 <= qr && nds[nds[x].ls].rext && nds[nds[x].rs].lext) ans--;
return ans;
}
inline int merge(int x, int y, int l, int r) {
if (!x || !y) return x ^ y;
if (l == r) {
nds[x].lext = nds[x].rext = (nds[x].lext || nds[y].lext);
if (nds[x].lext) nds[x].ans = 1;
return x;
}
int mid = l + (r - l >> 1);
nds[x].ls = merge(nds[x].ls, nds[y].ls, l, mid);
nds[x].rs = merge(nds[x].rs, nds[y].rs, mid + 1, r);
pushup(x);
return x;
}
inline void clear() { memset(nds, 0, sizeof(segtreenode) * (cnt + 1)); cnt = 0; }
}seg;
void dfs(int x, int lst) {
rt[x] = seg.insert(rt[x], 1, n, x);
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);
rt[x] = seg.merge(rt[x], rt[v], 1, n);
}
ans[x] = seg.query(rt[x], 1, n, 1, n);
}
int main() {
freopen("d.in", "r", stdin);
freopen("d.out", "w", stdout);
scanf("%d", &t);
while (t--) {
scanf("%d%d", &n, &root);
g.clear(); seg.clear();
memset(ans, 0, sizeof(int) * (n + 1)); memset(rt, 0, sizeof(int) * (n + 1));
for (int i = 1; i < n; ++i) {
int u, v; scanf("%d%d", &u, &v);
g.addedge(u, v); g.addedge(v, u);
}
dfs(root, 0);
for (int x = 1; x <= n; ++x) printf("%d ", ans[x]);
printf("\n");
}
return 0;
}下面又是今天校内模拟赛的题。
打表发现答案就是$n+1$，直接输出即可。
https://www.luogu.com.cn/problem/P3199
对于 01 分数规划问题，可以用二分求解，即二分平均数是几，然后问题变为判断是否存在环使得
$$\dfrac{\sum w}{s}\ge mid$$
稍微变一下式子，可以得到：
$$\sum(w-mid)\ge0$$
于是直接二分+spfa判负环即可。
根据常规套路把操作都倒过来，于是删除操作就变为了合并操作，直接线段树合并+并查集维护单点修改以及连通块第 k 大即可，不过我太菜了写挂了。
return