T1
NFLSOJ 服装
考虑逐次确定每个人。从前往后枚举，维护一个栈表示当前前缀里所有颜色不同的人。加入一个人的时候和栈里的东西并起来查，查出来是栈大小说明这个颜色出现过，在栈里二分找到那个颜色相同的人。否则当前颜色没出现过，将其加入栈。
代码
#include <iostream>
using namespace std;
int n;
int stk[155], sz;
int Ask(int l, int r, int x) {
cout << r - l + 2 << " ";
for (int i = l; i <= r; i++) cout << stk[i] << " ";
cout << x << endl;
cin >> x;
return x;
}
int clr[155], ccnt;
int main() {
cin >> n;
stk[++sz] = 1;
clr[1] = 1;
for (int i = 2; i <= n; i++) {
if (Ask(1, sz, i) == sz) {
int l = 1, r = sz, mid;
while (l < r) {
mid = (l + r) >> 1;
if (Ask(l, mid, i) == mid - l + 1)
r = mid;
else
l = mid + 1;
}
clr[i] = clr[stk[l]];
} else {
stk[++sz] = i;
clr[i] = sz;
}
}
cout << 0 << " ";
for (int i = 1; i <= n; i++) cout << clr[i] << " ";
cout << endl;
return 0;
}
T2
NFLSOJ 跑步
考虑图确定的 dp 就是 \(dp[i]\) 表示从 \(i\) 出发的合法路径条数的奇偶性。这 dp 只有 \(0 / 1\)，考虑 dp 套 dp。设 \(dp[i][x][y][z][w]\) 表示从后往前处理到 \(i\)，后面有 \(x\) 个黑点使得从它出发的路径条数为奇数，有 \(y\) 个黑点使得出发的条数是偶数，后两维同理。发现如果一个点出发的路径条数是偶数，那这个点就不会有贡献，因为任何一条路径如果走到他，往后的方案数就是偶数条，因此就相当于没贡献。于是只需要记三维，转移考虑当前点能否为某颜色点，然后考虑当前点是否作为有贡献点。设在 \(n\) 个数中选出偶 / 奇数个的方案数为 \(c(n, 0 / 1)\)。设当前点为黑点，则之后所有黑点和偶数白点都没有贡献，向它们的边可连可不连，转移即为 \(dp[i][x][y] = dp[x - 1][y] \times c(x - 1, 0) \times 2^{n - i - x + 1} + dp[i + 1][x][y] \times c(x - 1, 1) \times 2^{n - i - x + 1}\)。根据二项式定理，\(n \ne 0\) 时，\(c(n, 0) = c(n, 1) = 2^{n - 1}\)，发现 \(x\) 刚好抵消，则不需要记录 \(x\) 的值，只需要其是否为 \(0\) 及其奇偶性（用来判定答案），于是就没了。
代码
#include <iostream>
#define int long long
using namespace std;
const int P = 998244353;
inline void Madd(int& x, int y) { (x += y) >= P ? (x -= P) : 0; }
int n;
int a[200005];
int dp[200005][3][3];
int pw[200005];
signed main() {
freopen("life.in", "r", stdin);
freopen("life.out", "w", stdout);
cin >> n;
pw[0] = 1;
for (int i = 1; i <= n; i++) cin >> a[i], pw[i] = (pw[i - 1] << 1) % P;
dp[n + 1][2][2] = 1;
for (int i = n; i; i--) {
for (int x : { 0, 1, 2 }) {
for (int y : { 0, 1, 2 }) {
// this vertex white
if (a[i] != 1) {
if (y != 2) {
Madd(dp[i][x][y], dp[i + 1][x][y] * pw[n - i - 1] % P);
Madd(dp[i][(x + 1) & 1][y], dp[i + 1][x][y] * pw[n - i - 1] % P);
} else
Madd(dp[i][(x + 1) & 1][y], dp[i + 1][x][y] * pw[n - i] % P);
}
// this vertex black
if (a[i] != 0) {
if (x != 2) {
Madd(dp[i][x][y], dp[i + 1][x][y] * pw[n - i - 1] % P);
Madd(dp[i][x][(y + 1) & 1], dp[i + 1][x][y] * pw[n - i - 1] % P);
} else
Madd(dp[i][x][(y + 1) & 1], dp[i + 1][x][y] * pw[n - i] % P);
}
}
}
}
cout << (dp[1][0][1] + dp[1][1][0] + dp[1][1][2] + dp[1][2][1]) % P << "\n";
return 0;
}
T3
NFLSOJ 排列计数机
权值即为最大值个数。\(f[i][j][k]\) 表示到 \(i\)，最大值为 \(j\)，所有方案权值的 \(k\) 次方和。对于 \(i\)，只有 \(f[i][a[i]]\) 需要特殊转移，其他位置转移平凡。考虑维护给所有方案的权值 \(+1\) 后的 \(k\) 次方和。二项式定理展开一下，发现只需要组合数和在较小的 \(k\) 时的 dp 值。手推一下 dp 式子，发现只需要线段树支持区间乘以 \(2\) 和区间求和以及单点加即可。对每个 \(k \le m\) 都开一棵线段树维护。由于转移还需要方案数，再开一棵线段树维护方案数即可。
代码
#include <iostream>
#define int long long
using namespace std;
const int P = 1000000007;
inline void Madd(int& x, int y) { (x += y) >= P ? (x -= P) : 0; }
int fac[200005], inv[200005], ifac[200005];
void Cpre(int x) {
fac[0] = fac[1] = inv[0] = inv[1] = ifac[0] = ifac[1] = 1;
for (int i = 2; i <= x; i++) {
fac[i] = fac[i - 1] * i % P;
inv[i] = (P - P / i) * inv[P % i] % P;
ifac[i] = ifac[i - 1] * inv[i] % P;
}
}
int C(int n, int m) { return (n < 0 || m < 0 || n < m) ? 0 : fac[n] * ifac[m] % P * ifac[n - m] % P; }
int n, m;
int a[100005];
struct Segment_Tree {
int tgm[400005];
int s[400005];
void tag(int o, int v) {
s[o] = s[o] * v % P;
tgm[o] = tgm[o] * v % P;
}
void pushdown(int o) {
if (tgm[o] == 1)
return;
tag(o << 1, tgm[o]);
tag(o << 1 | 1, tgm[o]);
tgm[o] = 1;
}
void pushup(int o) { s[o] = (s[o << 1] + s[o << 1 | 1]) % P; }
void Build(int o, int l, int r) {
tgm[o] = 1;
if (l == r)
return;
int mid = (l + r) >> 1;
Build(o << 1, l, mid);
Build(o << 1 | 1, mid + 1, r);
}
void Multi(int o, int l, int r, int L, int R, int v) {
if (L <= l && r <= R) {
tag(o, v);
return;
}
pushdown(o);
int mid = (l + r) >> 1;
if (L <= mid)
Multi(o << 1, l, mid, L, R, v);
if (R > mid)
Multi(o << 1 | 1, mid + 1, r, L, R, v);
pushup(o);
}
void Add(int o, int l, int r, int x, int v) {
if (l == r) {
s[o] = (s[o] + v) % P;
return;
}
pushdown(o);
int mid = (l + r) >> 1;
if (x <= mid)
Add(o << 1, l, mid, x, v);
else
Add(o << 1 | 1, mid + 1, r, x, v);
pushup(o);
}
int Query(int o, int l, int r, int L, int R) {
if (L <= l && r <= R)
return s[o];
pushdown(o);
int mid = (l + r) >> 1;
if (R <= mid)
return Query(o << 1, l, mid, L, R);
if (L > mid)
return Query(o << 1 | 1, mid + 1, r, L, R);
return (Query(o << 1, l, mid, L, R) + Query(o << 1 | 1, mid + 1, r, L, R)) % P;
}
} f[25], g;
int tmp[25];
signed main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
Cpre(m);
for (int i = 1; i <= m; i++) f[i].Build(1, 0, n);
g.Build(1, 0, n);
g.Add(1, 0, n, 0, 1);
for (int i = 1; i <= n; i++) {
for (int k = 1; k <= m; k++) f[k].Multi(1, 0, n, a[i] + 1, n, 2);
for (int k = 1; k <= m; k++) tmp[k] = f[k].Query(1, 0, n, 0, a[i] - 1);
for (int k = 1; k <= m; k++) {
int t = 0;
for (int x = 1; x <= k; x++)
t = (t + C(k, x) * tmp[x] % P);
f[k].Add(1, 0, n, a[i], t);
f[k].Add(1, 0, n, a[i], g.Query(1, 0, n, 0, a[i] - 1));
}
g.Multi(1, 0, n, a[i] + 1, n, 2);
g.Add(1, 0, n, a[i], g.Query(1, 0, n, 0, a[i] - 1));
}
cout << f[m].Query(1, 0, n, 0, n) << "\n";
return 0;
}
T4
NFLSOJ 安装软件包
线性规划，转对偶，变网络流，即为给定 DAG，要选出若干路径，每个点被覆盖一次有收益，每选出一条路径有代价。一个点有覆盖次数上限，若超过上限则不再有收益。拆点，求一个最大费用可行流即可。
代码
#include <iostream>
#include <string.h>
#include <queue>
#include <map>
#define int long long
using namespace std;
const int inf = 0x7ffffffffff;
const int N = 500, M = 2000000;
struct Flow {
int n, S, T, c;
int head[N + 5], nxt[M + 5], to[M + 5], res[M + 5], cst[M + 5], ecnt = 1;
int cur[N + 5], dist[N + 5];
bool inq[N + 5], vis[N + 5];
queue<int> q;
void add(int u, int v, int x, int y) {
to[++ecnt] = v, nxt[ecnt] = head[u], head[u] = ecnt, res[ecnt] = x, cst[ecnt] = y;
to[++ecnt] = u, nxt[ecnt] = head[v], head[v] = ecnt, res[ecnt] = 0, cst[ecnt] = -y;
}
bool spfa() {
for (int i = 1; i <= n; i++) dist[i] = inf;
dist[S] = 0;
q.push(S);
while (!q.empty()) {
int x = q.front();
q.pop();
inq[x] = 0;
for (int i = head[x]; i; i = nxt[i]) {
int v = to[i];
if (dist[v] > dist[x] + cst[i] && res[i]) {
dist[v] = dist[x] + cst[i];
if (!inq[v]) {
q.push(v);
inq[v] = 1;
}
}
}
}
return (dist[T] < 0);
}
int dfs(int x, int flow) {
if (x == T)
return flow;
int ret = 0;
vis[x] = 1;
for (int i = cur[x]; i && flow; i = nxt[i]) {
cur[x]= i;
int v = to[i];
if (!vis[v] && dist[v] == dist[x] + cst[i] && res[i]) {
int tmp = dfs(v, min(flow, res[i]));
if (tmp) {
res[i] -= tmp;
res[i ^ 1] += tmp;
flow -= tmp;
ret += tmp;
c += tmp * cst[i];
}
}
}
if (!ret)
dist[x] = inf;
vis[x] = 0;
return ret;
}
int MinCost() {
c = 0;
while (spfa()) {
for (int i = 1; i <= n; i++) cur[i] = head[i];
dfs(S, inf);
}
return c;
}
void clear() {
memset(head, 0, sizeof head);
ecnt = 1;
}
} g;
int n, m, w;
int t[60], c[60];
int eu[405], ev[405];
bool chk(int K) {
g.clear();
g.S = n * 2 + 1, g.n = g.T = n * 2 + 2;
for (int i = 1; i <= n; i++) {
g.add(g.S, i, inf, K);
g.add(i + n, g.T, inf, 0);
g.add(i, i + n, c[i], -t[i]);
g.add(i, i + n, inf, 0);
}
for (int i = 1; i <= m; i++) g.add(eu[i] + n, ev[i], inf, 0);
return -g.MinCost() <= w;
}
signed main() {
freopen("soft.in", "r", stdin);
freopen("soft.out", "w", stdout);
cin >> n >> m >> w;
for (int i = 1; i <= n; i++) cin >> t[i];
for (int i = 1; i <= n; i++) cin >> c[i];
for (int i = 1; i <= m; i++) cin >> eu[i] >> ev[i];
int l = 0, r = 100000, mid, ans = 0;
while (l <= r) {
mid= (l + r) >> 1;
if (chk(mid))
ans = mid, r = mid - 1;
else
l = mid + 1;
}
cout << ans << "\n";
return 0;
}