T1.zzy的金牌
比较妙的计数 \(dp\)。一个显然的定义 \(dp[i][j]\) 表示给前 \(i\) 个盒子分配了 \(j\) 个金牌的情况。但是发现会有重复情况出现，按照常人的思路，对于一个集合肯定是有序状态才容易判断，因为无序肉眼很难观察。所以不妨将 \(a\) 排序，并且强制让操作完之后的数组也是有序的。
定义 \(dp[i][j][k]\) 为前 \(i\) 个盒子，分配了 \(j\) 个金牌，给第 \(i\) 个盒子分配了 \(k\) 个金牌。
转移就比较显然了\(dp[i][j][k] += dp[i-1][j-k][t]\ [a_{i-1}+t \le a_i+k]\)
用前缀和优化一下即可。
代码
#define sandom signed
#define fre(x, y) freopen(#x ".in", "r", stdin), freopen(#y ".out", "w", stdout);
#include <iostream>
#include <algorithm>
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
using namespace std; typedef long long ll;
namespace IO
{
const int bif = 1 << 18; char buf[bif], *p1, *p2;
inline char getc() { if (p1 == p2) { p2 = (p1 = buf) + fread(buf, 1, bif, stdin); if (p1 == p2) return EOF; } return *p1++; }
inline int read() { int x = 0, f = 0; char c = getc(); while (!isdigit(c)) f |= c == '-', c = getc(); while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getc(); return f ? -x : x; }
}; using namespace IO;
const int Z = 310; const int mod = 998244353;
inline int min(int a, int b) { return a < b ? a : b; }
int n, m, k, ans;
int a[Z], dp[Z][Z], sum[Z][Z];
sandom main()
{
fre(orzzy, orzzy);
n = read(), k = read();
rep(i, 1, n) a[i] = read();
sort(a + 1, a + 1 + n);
sum[0][0] = 1;
rep(i, 1, n)
{
rep(j, 0, k) rep(s, 0, j)
(dp[j][s] += sum[j - s][min(a[i] - a[i - 1] + s, j - s)]) %= mod;
rep(j, 0, k)
{
sum[j][0] = dp[j][0], dp[j][0] = 0;
rep(s, 1, j) sum[j][s] = (sum[j][s - 1] + dp[j][s]) % mod, dp[j][s] = 0;
}
}
cout << sum[k][k];
return 0;
}
T2.口粮输送
转换：从一个点把物资运送到另一个点，等价于两个点同时往\(LCA\)处靠拢，在\(LCA\)处交接。
看到树的部分分，先考虑\(dp\)一下。如果子树缺少物资，那就向上传递需要的数量，如果多余，那就向上传递给出的数量，如果给出还不如不给，那肯定选择不给。
观察发现，如果这条边没有给出去物资，同时也不会有物资运进来，那么这条边完全可以删去，树分割成两个树。并且，如果没有了这种边，树形\(dp\)就会非常简洁\(ans=\sum\limits(a-b)-\sum\limits w_i\)，发现前半部分贡献固定，后半部分显然是一个最小生成树的形式。因为删去了一些边，那么也就是最后需要构成的是最小生成树森林。
发现\(n\le 15\)那就状压枚举那些点构成最小生成树，然后再由多个连通块拼成一个最小生成树森林。
代码
#define sandom signed
#define fre(x, y) freopen(#x ".in", "r", stdin), freopen(#y ".out", "w", stdout);
#include <iostream>
#include <algorithm>
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
using namespace std; typedef long long ll;
namespace IO
{
const int bif = 1 << 18; char buf[bif], *p1, *p2;
inline char getc() { if (p1 == p2) { p2 = (p1 = buf) + fread(buf, 1, bif, stdin); if (p1 == p2) return EOF; } return *p1++; }
inline int read() { int x = 0, f = 0; char c = getc(); while (!isdigit(c)) f |= c == '-', c = getc(); while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getc(); return f ? -x : x; }
}; using namespace IO;
const int Z = 16;
int n, m, k, ans;
int fa[Z];
inline int find(int x) { return x == fa[x] ? x : find(fa[x]); }
int w[Z], dp[1 << Z];
struct edge
{
int u, v, w;
friend bool operator <(edge A, edge B) { return A.w < B.w; }
}; edge e[Z * Z];
bool MST(int s)
{
int tot = 0, sum = 0;
rep(i, 1, n) fa[i] = i;
rep(i, 1, n) if (s & (1 << i - 1)) sum += w[i], tot++;
rep(i, 1, m)
{
if (tot == 1) return sum >= 0;//生成树完成
if (!(s & (1 << e[i].u - 1)) || !(s & (1 << e[i].v - 1))) continue;//不在子集中
int u = find(e[i].u), v = find(e[i].v);
if (u != v) fa[u] = v, sum -= e[i].w, tot--;
if (tot == 1) return sum >= 0;//生成树完成
}
return false;//甚至不连通
}
sandom main()
{
fre(trans, trans);
int T = read();
while (T--)
{
n = read(), m = read(); k = (1 << n) - 1;
rep(i, 1, m) e[i].u = read(), e[i].v = read(), e[i].w = read();
rep(i, 1, n) { int a = read(), b = read(); w[i] = a - b; }
sort(e + 1, e + 1 + m);
rep(s, 1, k)
{
dp[s] = MST(s);
for (int t = s; t; t = s & (t - 1))
dp[s] |= (dp[t] & dp[s ^ t]);//能够拼成最小生成森林
}
dp[k] ? puts("Yes") : puts("No");
}
return 0;
}
T3.作弊
作弊区间不相交相当于简化了问题。
直接暴力 \(dp\)。
定义 \(dp[i]\) 为前 \(i\) 个小朋友的最大收益。\(dp[i] = \max\limits_{0\le j < i }\{dp[j] + sum(j + 1, i)\}\)
对于\(sum(l, r)\)考虑扫描线动态维护。直接维护不太方便，考虑单独一个人对\(sum\)贡献当且仅当：\(max_{l, r}\in[l_i, r_i]，i\in [l, r]\)。把 \(max_{l, r}\) 拆分成 \(max\{max_{l, i}, max_{i, r}\}\)，利用\(max\)的单调性，分别找到贡献范围，使得 \(l\in [Ll,Rl]\) 时，有 \(max_{l, i}\in[l_i,r_i]\)，\(r\in [Lr, Rr]\)，有 \(max_{i, r}\in[l_i, r_i]\)。当右端点处于 \([i, Lr]\) 时，左端点需要处于 \([Ll, Rl]\) 才有贡献；当右端点处于 \([Lr, Rr]\) 时，左端点处于 \([Ll, i]\) 都有贡献；此外无贡献。扫描线维护 \(dp\) 最大值即可。
代码
#define sandom signed
#define fre(x, y) freopen(#x ".in", "r", stdin), freopen(#y ".out", "w", stdout);
#include <iostream>
#include <cmath>
#include <vector>
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
using namespace std; typedef long long ll;
namespace IO
{
const int bif = 1 << 18; char buf[bif], *p1, *p2;
inline char getc() { if (p1 == p2) { p2 = (p1 = buf) + fread(buf, 1, bif, stdin); if (p1 == p2) return EOF; } return *p1++; }
inline int read() { int x = 0, f = 0; char c = getc(); while (!isdigit(c)) f |= c == '-', c = getc(); while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getc(); return f ? -x : x; }
}; using namespace IO;
const int Z = 1e5 + 10;
inline int max(int a, int b) { return a > b ? a : b; } inline int min(int a, int b) { return a < b ? a : b; }
int n, m, k, ans;
int a[Z], l[Z], r[Z];
#define mid (L + R >> 1)
#define lk (rt << 1)
#define rk (rt << 1 | 1)
struct tree { int max, lz; } tr[Z << 2];
inline void change(int rt, int v) { tr[rt].lz += v, tr[rt].max += v; }
inline void pushup(int rt) { tr[rt].max = max(tr[lk].max, tr[rk].max); }
inline void pushdown(int rt) { if (tr[rt].lz) change(lk, tr[rt].lz), change(rk, tr[rt].lz), tr[rt].lz = 0; }
void update(int rt, int L, int R, int l, int r, int v)
{
if (l > r) return;
if (l <= L && r >= R) { change(rt, v); return; }
pushdown(rt);
if (l <= mid) update(lk, L, mid, l, r, v);
if (r > mid) update(rk, mid + 1, R, l, r, v);
pushup(rt);
}
struct ST
{
int mx[20][Z];
inline void init()
{
rep(i, 1, n) mx[0][i] = a[i];
int t = log2(n);
rep(j, 1, t) for (int i = 1; (i + (1 << j) - 1) <= n; ++i)
mx[j][i] = max(mx[j - 1][i], mx[j - 1][i + (1 << j - 1)]);
}
inline int RMQ(int l, int r)
{
if (l > r) swap(l, r);
int t = log2(r - l + 1);
return max(mx[t][l], mx[t][r - (1 << t) + 1]);
}
}; ST st;
inline int work1(int L, int R, int i)//第一个<=
{
int ans = i + 1;
while (L <= R)
{
if (st.RMQ(i, mid) <= r[i]) ans = mid, R = mid - 1;
else L = mid + 1;
}
return ans;
}
inline int work2(int L, int R, int i)//最后一个>=
{
int ans = 0;
while (L <= R)
{
if (st.RMQ(i, mid) >= l[i]) ans = mid, L = mid + 1;
else R = mid - 1;
}
return ans;
}
inline int work3(int L, int R, int i)//第一个>=
{
int ans = n + 1;
while (L <= R)
{
if (st.RMQ(i, mid) >= l[i]) ans = mid, R = mid - 1;
else L = mid + 1;
}
return ans;
}
inline int work4(int L, int R, int i)//最后一个<=
{
int ans = i - 1;
while (L <= R)
{
if (st.RMQ(i, mid) <= r[i]) ans = mid, L = mid + 1;
else R = mid - 1;
}
return ans;
}
struct nod { int l, r, k; }; vector <nod> opt[Z];
sandom main()
{
fre(cheat, cheat);
n = read(); m = n + 1;
rep(i, 1, n) a[i] = read();
st.init();
rep(i, 1, n) l[i] = read(), r[i] = read();
rep(i, 1, n)
{
int ll = work1(1, i, i), lr = work2(1, i, i);
int rl = work3(i, n, i), rr = work4(i, n, i);
opt[i].push_back(nod{ll, lr, 1});
opt[rl].push_back(nod{lr + 1, i, 1});
opt[rr + 1].push_back(nod{ll, i, -1});
}
rep(i, 1, n)
{
update(1, 1, m, i, i, tr[1].max);
for (auto j : opt[i]) update(1, 1, m, j.l, j.r, j.k);
}
cout << tr[1].max;
return 0;
}