ZROI Day11-Day20 笔记

比利♂海灵顿 · 2021-10-23 10:16:17 · 个人记录

[TOC]

ZROI

Day11: SA

倍增

过水已隐藏

SA 做 SAM 板子

求字符串本质不同的子串个数.

所有字串都可以唯一地表示为第 i 个后缀的第 j 个前缀, 共 \frac {n(n + 1)}2 个. 所以我们只要排序后缀, 然后求出 LCP_{i, i + 1}, 就可以知道一个后缀和相邻后缀有多少前缀相同, 总数减去重复的数量就是不同的数量.

例题

求所有无序后缀对两两 lcp 之和.

定义 h_i = lcp_{i, i + 1}. 有一个引理: lcp_{i, j} = min(h_k) k\in[i, j).

单调栈求出 h_i 左边的连续大于等于它的数量 l_i, 右边连续大于它的数量 r_i, 这时统计 \displaystyle\sum_{i = 1}^{n}(r_i + l_i + 1) \times h_i.

CF1073G

给一个字符串, 每次询问给两个数集 A, B, 求 A 中每个后缀和 B 中每个后缀的 LCP 长度之和.

所有询问 A 或 B 大小之和不超过 2 * 10^5.

首先想到暴力, 可以每次枚举所有数对, 在后缀树上两两求 LCA, 将 Len 统计入答案.

然后用树链剖分优化, 因为一个 LCA 的 Len 是它到根上的所有点的 Len 和父亲的 Len 的差的总和. 可以用树链剖分维护这个差加权的区间和. 对于每个 A 集合的点, 将它到根的所有点的权值加 1. 然后查询每个 B 集合的点到根的加权的差的和, 即可在 O(n + \log^2 n (\sum |A| + \sum |B|)) 的时间内求出答案.

也可以用虚树, 这样可以在 O(n + \log n (\sum |A| + \sum |B|)) 内求出答案.

还有后缀数组的做法, 先求后缀数组, 然后求出 Height, 数组, 存入 ST 表中.

对于朴素的做法, 枚举所有 A, B 中的元素, 查询其区间 Height 最小值, 复杂度 O(n\log n + |A|*|B|), 尝试将 A, B, 按 RK 排序, 这样可以先处理 RK_{A_i} \leq RK_{B_j} 的情况, 然后处理 RK_{B_i} < RK_{A_j} 的情况.

对于 RK_{A_i} \leq RK_{B_j}, 双指针扫描两个数组, 对于一个 B_j, 将所有可能对它有贡献的 A_i 的 \displaystyle{\min_{k = RK_{A_i} + 1}^{RK_{B_j}} Height_{k}} 插入权值线段树中, 统计答案.

特殊地, 对于 A_i = B_j, 将 n - A_i + 1 插入线段树.

考虑由 B_j 到 B_{j + 1} 变化后, 线段树中的值对答案的贡献变化, 发现

所以只要每次移动 j 的时候把线段树中比 \displaystyle{\min_{k = RK_{B_j} + 1}^{RK_{B_{j + 1}}} Height_{k}} 大的值都变成 \displaystyle{\min_{k = RK_{B_j} + 1}^{RK_{B_{j + 1}}} Height_{k}} 就可以了.

首先有个性质: 只要 N \geq A + C 或 M \geq B + D, 一定把多出来的苹果或骨头换成另一种.

然后是 N + C \leq A 或 M + D \leq B, 这时如果生产 C 个苹果比 D 个骨头时间短, 则生产 C 个苹果换成 D 个骨头代替直接生产骨头, 反之亦然.

对于整段之后的零头, 仍然要讨论, 比如现在 N + C > A, 但是 A - N 个苹果生产仍然不如生产 D 个骨头, 那就选择 D 个骨头换出 C 个苹果.

还要讨论一开始形如 A < N < A + C 的情况, 因为有时候, 拿 C 个苹果换到 D 个骨头, 然后生产 C + A - N 个苹果的方案更优.

unsigned a[10005], N, M, X, Y, m, n, Cnt(0), A, B, C, D, t, TmpB, TmpA, Ans(0), Tmp1(0), Tmp2(0), Tmp(0);
char b[10005];
int main() {
  N = RD(), M = RD(), X = RD(), Y = RD(), A = RD(), B = RD(), C = RD(), D = RD();
  if((N >= A) && (M >= B)) {
    printf("0\n");
    return 0;
  }
  if(N >= A) {
    M += ((N - A) / C) * D;
    if(M >= B) {
      printf("0\n");
      return 0;
    }
    Tmp = (N - A + C - 1) / C;
    TmpB = M + Tmp * D;
    if(TmpB >= B) Tmp1 = X * (A + Tmp * C - N);
    else Tmp1 = X * (A + Tmp * C - N) + min(((B - TmpB + D - 1) / D) * C * X, Y * (B - TmpB));
    Tmp2 = min(((B - M + D - 1) / D) * C * X, Y * (B - M));
    Ans += min(Tmp1, Tmp2);
    printf("%u\n", Ans);
    return 0;
  }
  if(M >= B) {
    N += ((M - B) / D) * C;
    if(N >= A) {
      printf("0\n");
      return 0;
    }
    Tmp = (M - B + D - 1) / D;
    TmpA = N + Tmp * C;
    if(TmpA >= A) Tmp1 = Y * (B + Tmp * D - M);
    else Tmp1 = Y * (B + Tmp * D - M) + min(((A - TmpA + C - 1) / C) * D * Y, X * (A - TmpA));
    Tmp2 = min(((A - N + C - 1) / C) * D * Y, X * (A - N));
    Ans += min(Tmp1, Tmp2);
    printf("%u\n", Ans);
    return 0;
  }
  TmpA = ((A - N) / C) * D * Y + X * (A - (((A - N) / C) * C) - N);
  TmpB = ((B - M) / D) * C * X + Y * (B - (((B - M) / D) * D) - M);
  Ans += min(min(((A - N + C - 1) / C) * D * Y, X * (A - N)), TmpA);
  Ans += min(min(((B - M + D - 1) / D) * C * X, Y * (B - M)), TmpB);
  printf("%u\n", Ans);
  return Wild_Donkey;
}

B

给一个 1, 2, 3,...,n 的序列, 可以随意选择几位, 将它变成 x - 1, 然后求异或和.

一共有 2^n 种情况, 求这 2^n 种情况得到的异或和中, \geq m 的情况数.

打表题, 打表发现, 无论 n 是多少, 最后前缀和中, [0, 2^{\lfloor \log n \rfloor + 1}) 每种数字出现次数相同.

所以对于 m, 求 \frac{2^n(m + 1)}{2^{\lfloor \log n \rfloor + 1}} = 2^{n - \lfloor \log n \rfloor - 1}(m + 1) 即可, 快速幂解决.

const unsigned long long MOD(1000000007);
unsigned long long m, n, Cnt(0), N, Ans(0), Tmp(0), a[1005];
unsigned long long Power(unsigned long long y) {
  register unsigned long long Tmpx(2), Final(1);
  while (y) {
    if(y & 1) {
      Final = Final * Tmpx % MOD;
    }
    Tmpx = Tmpx * Tmpx % MOD;
    y >>= 1;
  }
  return Final;
}
int main() {
  Tmp = n = RD(), m = RD();
  while (Tmp) {
    ++Cnt;
    Tmp >>= 1;
  }
  N = ((unsigned long long)1 << Cnt) - 1;
  m = min(N, m);
  printf("%llu\n", ((1 + m) % MOD) * Power(n - Cnt) % MOD);
  return Wild_Donkey;
}

D

构造数据卡贪心.

有 n 个数, 要求分成两个集合使得它们的和的差尽可能小.

需要 Hack 的算法: 降序排序, 将数字插入和较小的那个集合.

给定 n, m, 输出 n 个数, 分成两个集合差值最小是 m.

发现原算法可以在 n \leq 5 的时候给出正确答案.

原算法一定会使得最大的和二大的数字分到两个不同的集合中, 所以我们只要构造数据使得答案中最大的和二大的数字分到一个集合中即可.

G

一棵树, 两点之间连的是双向边, 也就是一共 2(n - 1) 条有向边.

一条边可以被删除, 当且仅当它的终点不存在到达不是它的起点的点的出边.

发现一开始所有连向叶子的边都可以被删除, 删除连向叶子的边之后, 连向这些删除了的边的起点的边也可以删除, 所以 DFS 回溯过程中删除之前走的每一条边即可. 这样就删掉了所有父亲连向儿子的边.

然后发现这时连向根的边可以被删除, 删除这些边之后, 每一颗子树又变成了同样的子问题, 所以仍然是 DFS, 在搜索一个子树之前, 删除这个子树连向根的边即可.

unsigned a[10005], m, n, Cnt(0), C, D, t, Ans(0), Tmp(0);
struct Edge;
struct Node {
  Edge *Fst;
  Node *Fa;
}N[100005], *A, *B;
struct Edge {
  Node *To;
  Edge *Nxt;
}E[200005], *CntE(E);
void Link(Node *x, Node *y) {
  (++CntE)->Nxt = x->Fst;
  x->Fst = CntE;
  CntE->To = y;
}
void DFS(Node *x) {
  Edge *Sid(x->Fst);
  while (Sid) {
    if(Sid->To != x->Fa) {
      Sid->To->Fa = x;
      DFS(Sid->To);
      printf("%u %u\n", x - N, Sid->To - N);
    }
    Sid = Sid->Nxt;
  }
}
void DFS2 (Node *x) {
  Edge *Sid(x->Fst);
  while (Sid) {
    if(Sid->To != x->Fa) {
      printf("%u %u\n", Sid->To - N, x - N);
      DFS2(Sid->To);
    }
    Sid = Sid->Nxt;
  }
}
int main() {
  n = RD();
  for (register unsigned i(1); i < n; ++i) {
    A = N + RD(), B = N + RD();
    Link(A, B);
    Link(B, A);
  }
  DFS(N + 1);
  DFS2(N + 1);
  return Wild_Donkey;
}

J

对一个序列执行一次操作, 使得前 k 个数接到第 n 个数后面.

然后对序列进行合并, 规则是两个相邻的数字 x, y 合成一个数 x - y, 每轮之后对新的数组重复操作, 直到数组只剩一个元素.

求合并到只剩一个元素的最大值.

使用倍增, a_{i, j} 表示从 i 开始合并到 i + 2^i - 1 的结果.

所以这个是类似 ST 表的思想, 需要 O(n\log n) 的空间预处理.

破环为链, 枚举每个起始位置, 这样就可以每次二进制分组, 暴力合并得到的长度为 \log n 的序列即可.

遗憾的是, 虽然场切了核心思想, 但是下面这个细节却没有调出来, 否则就是场上唯一一个切 8 题的学生队伍了.

暴力合并时, 要注意不能使用直接合并的规则, 因为每个元素不是同时得到的, 所以一定是原序列较小的元素先合并, 所以答案应该是得到的序列从左到右交替加减得到的结果.

long long a[200005][20], m, n, Cnt(0), A, B, C, D, t, Ans(-0x3f3f3f3f3f3f3f3f), Tmp[100005], Bin[200005], Log[200005];
long long Force() {
  register long long All(0);
  for (register unsigned i(1); i <= Cnt; ++i) {
    if(i & 1) {
      All += Tmp[i]; 
    } else {
      All -= Tmp[i];
    }
  }
  return All;
}
int main() {
  m = RD(), n = m << 1;
  for (register unsigned i(1), j(0); i <= n; i <<= 1, ++j) {
    Bin[j] = i, Log[i] = j; 
  }
  for (register unsigned i(1); i <= n; ++i) {
    Log[i] = max(Log[i - 1], Log[i]);
  }
  for (register unsigned i(1); i <= m; ++i) {
    a[i + m][0] = a[i][0] = RD();
  }
  for (register unsigned j(1); j <= Log[m]; ++j) {
    for (register unsigned i(1); i + Bin[j] <= n; ++i) {
      a[i][j] = a[i][j - 1] - a[i + Bin[j - 1]][j - 1];
    }
  }
  for (register unsigned i(1); i <= m; ++i) {
    Cnt = 0;
    register unsigned Len(0);
    for (register unsigned j(Log[m]); j < 0x3f3f3f3f; --j) {
      if(Len + Bin[j] <= m) {
        Tmp[++Cnt] = a[i + Len][j];
        Len += Bin[j];
      }
    }
    Ans = max(Force(), Ans);
  }
  printf("%lld\n", Ans);
  return Wild_Donkey;
}

L

给一个六边形网格, 每次将一个连通块涂成红色或蓝色, 求整个变成蓝色的最少涂色数量.

搜索, 得到每个连通块的相邻关系, 每个连通块作为一个点, 和与它相邻的点连边, 得到一个二分图, 这时二分图一定是一棵树, 这是因为六边形网格的特殊性不存在环.

发现每次做染色操作相当于以某个连通块所在的点为根, 将树从上面减少一层, 所以整个图变成统一颜色的操作数是树高, 所以我们要求出树高最小的根.

这个最小的树高即为直径的二分之一向上取整. (直径定义为最长链的边数)

特别地, 有可能最后整个图变成红色, 在直径为奇数的时候可以通过选择合适的直径中点作为根来控制最终颜色, 操作次数也不会改变.

特判直径为偶数的时候, 这时如果直径中点是蓝色, 直径的一半是偶数, 答案不变, 直径一半是奇数, 答案增加 1; 如果中点是红色, 直径一半是偶数, 答案增加 1, 否则答案不变.

M

一条长 L 的路, 路上有 n 个消防局, 可以在没有消防局的整点上修建筑. 修 m 个建筑, 使得所有建筑到最近的消防局的距离的最大值最小.

显然是二分答案题, 二分最大距离 x, 在每个消防局周围 x 范围内放满建筑, 看是否放够了 m 个即可.

unsigned a[100005], m, n, Cnt(0), A, B, C, D, L, t, Ans(0), Tmp(0);
char Judge (unsigned x) {
  register unsigned Now(0);
  a[n + 1] = L + x + 1;
  for (register unsigned i(1); i <= n; ++i) {
    Now += min(a[i] - a[i - 1] - 1, x);
    if(a[i + 1] - a[i] - 1 > x) {
      Now += min(a[i + 1] - a[i] - 1 - x, x);
    }
  }
  return Now >= m;
}
int main() {
  n = RD(), m = RD(), L = RD();
  for (register unsigned i(1); i <= n; ++i) {
    a[i] = RD();
  }
  a[0] = 0;
  sort(a + 1, a + n + 1);
  register l(1), r(L), Mid;
  while (l < r) {
    Mid = ((l + r) >> 1);
    if(Judge(Mid)) {
      r = Mid;
    } else {
      l = Mid + 1;
    }
  }
  printf("%u\n", l);
  return Wild_Donkey;
}

N

轮廓线长度, 直接从左到右扫描即可.

unsigned a[10005], m, n, Cnt(0), A, B, C, D, t, Ans(0), Tmp(0);
char b[10005];
inline void Clr() {}
int main() {
  Ans = n = RD();
  for (register unsigned i(1); i <= n; ++i) {
    a[i] = RD();
  }
  ++n;
  for (register unsigned i(1); i <= n; ++i) {
    if(a[i] > a[i - 1]) {
      Ans += a[i] - a[i - 1];
    } else {
      Ans += a[i - 1] - a[i];
    }
  }
  printf("%u\n", Ans);
  return Wild_Donkey;
}

O

构造一个长度为 m 的数, 各位和为 n.

不能有前导零, n = 0 时只有 m = 1 时有解, 为 0.

总和除以长度向下取整得到每一位的数, 然后将余数从高到低补上即可.

unsigned m, n, Base, Cnt(0), A, B, C, D, t, Ans(0), Tmp(0);
inline void Clr() {}
int main() {
  n = RD(), m = RD();
  if(!n) {
    if(m > 1) {
      printf("-1\n");
      return 0;
    } else {
      printf("0\n");
      return 0;
    }
  }
  Base = n / m;
  if(Base > 9) {
    printf("-1\n");
    return 0;
  }
  if((Base == 9) && (Base * m < n)) {
    printf("-1\n");
    return 0;
  }
  for (register unsigned i(1); i <= n - (Base * m); ++i) {
    printf("%u", Base + 1);
  }
  for (register unsigned i(n - (Base * m) + 1); i <= m; ++i) {
    printf("%u", Base);
  }
  putchar('\n');
  return Wild_Donkey;
}

P

翻转字符串, 如果首字母大写, 则反转后的首字母大写, 也就是原串末字符大写.

按空格分割每个字符串输入, 判断首字符, 打 Tag, 将所有字符转化为小写, 翻转, 然后输出时判断 Tag 将首字符大写即可.

unsigned Pos[3005], n(3000), Cnt(0), A, B, C, D, t, Ans(0), Tmp(0);
char a[3005], b[3005], Tag[3005];
int main() {
  fread(a + 1, 1, 3002, stdin);
  while (a[n] < 'A') {
    --n;
  }
  Pos[0] = 0;
  for (register unsigned i(1); i <= n; ++i) {
    if(a[i] < 'A') {
      Pos[++Cnt] = i;
    }
    if(a[i] >= 'A' && a[i] < 'a') {
      Tag[Cnt] = 1;
      a[i] += 'a' - 'A';
    }
  }
  Pos[++Cnt] = n + 1;
  for (register unsigned i(0); i < Cnt; ++i) {
    if(Tag[i]) {
      a[Pos[i + 1] - 1] -= 'a' - 'A';
    }
  }
  for (register unsigned i(n); i; --i) {
    putchar(a[i]);
  }
  putchar('\n');
  return Wild_Donkey;
}

Day15: 连通性

强连通分量

过水已隐藏

Tip: Tarjan 找到强连通分量的顺序反转后是得到的 DAG 的拓扑序, 原因是一个点被弹出时, 它连向的点一定也被弹出了, 所以一个强连通分量被弹出时, 所有拓扑序应该比它大的点都被弹出了.

NOIp2009

枚举拓扑序, 对于每个拓扑序, 累加可行的连边情况.

对节点状压, f_i 表示包含集合 i 中的所有拓扑序, 符合条件的连边情况总和. 对于一个点集, 只考虑这些点之间的边.

那么 i 只包含一个点的时候, 是边界情况, f_i = 1, 对于转移来说, 枚举一个点加入点集, 放到集合最后.

这时我们会得出 x_1, y_0 的答案, 不合法.

但是当我们重新审视这组数据, 发现不会存在仅从 x 的点往 y 的点连边的情况, 所以不会出现这种数据.

unsigned m, n, n2, Top(0), SCC(0);
unsigned A, B, C, D, t;
unsigned Cnt(0), Tmp(0);
unsigned Fa[2000005], SetStack[2000005], STop(0);
char Ans[1000005];
struct Node;
struct Edge {
  Node* To;
  Edge* Nxt;
}E[2000005], * CntE(E);
struct Node {
  Edge* Fst;
  unsigned Low, DFSr, Bel;
  char InS;
}N[2000005], * Stack[2000005];
inline unsigned Find(unsigned x) {
  while (x ^ Fa[x]) SetStack[++STop] = x, x = Fa[x];
  while (STop) Fa[SetStack[STop--]] = x;
  return x;
}
inline void Link(Node* x, Node* y) {
  (++CntE)->Nxt = x->Fst, x->Fst = CntE, CntE->To = y;
  Fa[Find(x - N)] = Find(y - N);
}
inline void Tarjan(Node* x) {
  x->Low = x->DFSr = ++Cnt, Stack[++Top] = x, x->InS = 1;
  Edge* Sid(x->Fst);
  while (Sid) {
    if(Sid->To->DFSr) {
      if(Sid->To->InS) x->Low = min(x->Low, Sid->To->Low);
    } else {
      Tarjan(Sid->To), x->Low = min(x->Low, Sid->To->Low);
    }
    Sid = Sid->Nxt;
  }
  if(x->Low == x->DFSr) {
    ++SCC;
    do Stack[Top]->Bel = SCC, Stack[Top]->InS = 0; while (Stack[Top--] != x);
  }
}
signed main() {
  n2 = ((n = RD()) << 1), m = RD();
  for (unsigned i(1); i <= m; ++i) {
    A = (RD() << 1), B = RD(), C = (RD() << 1), D = RD();
    Link(N + (A ^ B ^ 1), N + (C ^ D));
    Link(N + (C ^ D ^ 1), N + (A ^ B));
  }
  for (unsigned i(1); i <= n2; ++i) if(!N[i + 1].DFSr) Tarjan(N + i + 1);
  for (unsigned i(2); i <= n2; i += 2) {
    if(N[i ^ 1].Bel == N[i].Bel) {printf("IMPOSSIBLE\n");return 0;}
    Ans[i >> 1] = (N[i ^ 1].Bel < N[i].Bel) ? 1 : 0;
  }
  printf("POSSIBLE\n");
  for (unsigned i(1); i <= n; ++i) printf("%u ", Ans[i]);
  return Wild_Donkey;
}

P6965 + LOJ6036

树链剖分优化建图, 复杂度 O(n\log^2n), 开了 -O2 跑得真不慢.

有 n 个二进制串，每个串最多有一位是 ?。

你要给 ? 填上 0/1, 使得不存在 i, j 使 s_i 是 s_j 的前缀.

洛谷上要输出方案, 而 LOJ 只需要判断可行性, 相当于弱化版, 所以这里只放 P6965 的做法.

将每个字符串 ? 取 0 和 1 的情况都存到 Trie 里.

我们发现, 如果选了一个节点, 那么它子树上的节点都不能选, 它到根的路径上的节点也不能选, 所以我们要往这些点的对应点上连边.

我们知道有线段树优化建边, 当线段树从序列上放到 Trie 上, 就需要树链剖分了, (显然我没有想到可以只连父子)

树链剖分建边是 O(n\log^2n), 对于常数极大的线性算法, 这个算法增加的 \log^2n 的复杂度没有明显地比别的算法慢, 只是不开 -O2 会超时, 但是开了 -O2 便跑到了最优解第一页的前半部分.

建边之后跑 2-SAT 即可.

我觉得这份代码最妙的地方莫过于在递归过程中计算线段树区间长度, 然后用 vector 存图, 实现了线段树和有向图的无缝衔接, 这虽然对数组来说是很正常的事, 但是对于指针来说, 少定义两个结构体 (存边和存线段树) 确实大大减少了代码难度.

unsigned m, n, n2;
unsigned A, B, C, D, t;
unsigned Tmp(0);
unsigned DFSCnt(1), STop(0), SCC(0);
char TmpI[500005], UnSur[500005], Cr(0), Flg(0);
vector<char> Ans[500005];
struct Trie;
struct Node {
  vector<Node*> To;
  Trie* Tr;
  unsigned Bel, Low, DFSr;
  char InS;
}N[2000005], * List[2000005], * CntN, * Frm, * Root;
struct Trie {
  Trie* Son[2], * Top, * Fa;
  unsigned RL, RR, Size, Cnt;
  char Heavy;
  inline void PreDFS() {
    unsigned Mx(0);
    if (Son[0]) Son[0]->Fa = this, Son[0]->PreDFS(), Heavy = 0, Mx = Son[0]->Size;
    if (Son[1]) {
      Son[1]->Fa = this, Son[1]->PreDFS();
      if (Son[1]->Size > Mx) Heavy = 1;
    }
  }
  inline void DFS() {
    RL = DFSCnt, RR = RL + Cnt - 1, DFSCnt += Cnt;
    if (!Son[Heavy]) return;
    Son[Heavy]->Top = Top, Son[Heavy]->DFS();
    Trie* Cur(Son[Heavy ^ 1]);
    if (Cur) Cur->Top = Cur, Cur->DFS();
  }
}T[1000005], * CntT(T), * Lst1, * Lst2;
inline void Link(Node* x, unsigned L, unsigned R) {
  if ((A <= L) && (R <= B)) { Frm->To.emplace_back(x);return; }
  unsigned Mid((L + R) >> 1);
  if (A <= Mid) Link(x->To[0], L, Mid);
  if (B > Mid) Link(x->To[1], Mid + 1, R);
}
inline Node* Build(unsigned L, unsigned R) {
  if (L == R) { return N + ((List[L] - N) ^ 1); }
  unsigned Mid((L + R) >> 1);
  Node* Cur(++CntN);
  Cur->To.emplace_back(Build(L, Mid));
  Cur->To.emplace_back(Build(Mid + 1, R));
  return Cur;
}
inline void Tarjan(Node* x) {
  x->DFSr = x->Low = ++DFSCnt, List[++STop] = x, x->InS = 1;
  for (auto Cur : x->To) {
    if (Cur->DFSr) { if (Cur->InS) x->Low = min(x->Low, Cur->Low); }
    else Tarjan(Cur), x->Low = min(x->Low, Cur->Low);
  }
  if (x->DFSr == x->Low) {
    ++SCC;
    do List[STop]->Bel = SCC, List[STop]->InS = 0;
    while (List[STop--] != x);
  }
}
signed main() {
  CntN = N + (n2 = ((n = RD()) << 1)) - 1;
  for (unsigned i(0), j(1); i < n; ++i) {
    scanf("%s", TmpI + 1), Lst1 = Lst2 = T, j = 1;
    while (TmpI[j] >= '0') {
      ++(Lst1->Size), ++(Lst2->Size);
      Ans[i].push_back(TmpI[j]);
      if (TmpI[j] == '?') {
        UnSur[i] = 1;
        if (!(Lst1->Son[0])) Lst1->Son[0] = ++CntT;
        if (!(Lst2->Son[1])) Lst2->Son[1] = ++CntT;
        Lst1 = Lst1->Son[0];
        Lst2 = Lst2->Son[1];
      }
      else {
        Cr = TmpI[j] - '0';
        if (!(Lst1->Son[Cr])) Lst1->Son[Cr] = ++CntT;
        if (!(Lst2->Son[Cr])) Lst2->Son[Cr] = ++CntT;
        Lst1 = Lst1->Son[Cr];
        Lst2 = Lst2->Son[Cr];
      }
      ++j;
    }
    ++(Lst1->Cnt), ++(Lst1->Size), N[i << 1].Tr = Lst1;
    ++(Lst2->Cnt), ++(Lst2->Size), N[(i << 1) ^ 1].Tr = Lst2;
  }
  T->PreDFS(), T->Top = T, T->DFS();
  for (unsigned i(0); i < n2; ++i) List[(N[i].Tr)->RL + (--((N[i].Tr)->Cnt))] = N + i;
  for (unsigned i(1); i <= n2; ++i) List[i]->DFSr = i;
  Root = Build(1, n2);
  for (Frm = N + n2 - 1; Frm >= N; --Frm) {
    Trie* Cur(Frm->Tr);
    A = Frm->DFSr + 1, B = Cur->RL + Cur->Size - 1;
    if (A <= B) Link(Root, 1, n2);
    A = Cur->Top->RL, B = Frm->DFSr - 1;
    if (A <= B) Link(Root, 1, n2);
    Cur = Cur->Top->Fa;
    while (Cur) {
      A = Cur->Top->RL, B = Cur->RR;
      if (A <= B) Link(Root, 1, n2);
      Cur = Cur->Top->Fa;
    }
  }
  for (unsigned i(1); i <= n2; ++i) List[i]->DFSr = 0;
  DFSCnt = 0, Tarjan(Root);
  for (unsigned i(0); i < n; ++i)
    if (N[i << 1].Bel == N[(i << 1) ^ 1].Bel) { Flg = 1;break; }
    else UnSur[i] = (N[i << 1].Bel > N[(i << 1) ^ 1].Bel ? 1 : 0);
  if (Flg) { printf("NO\n"); return 0; }
  printf("YES\n");
  for (unsigned i(0); i < n; ++i) {
    for (auto j : Ans[i]) {
      if (j == '?') putchar(UnSur[i] + '0');
      else putchar(j);
    }
    putchar('\n');
  }
  return Wild_Donkey;
}

AT2336

数轴上插 n 面旗, 第 i 面要么插 x_i, 要么插 y_i. 使相邻旗子最小间隔最大.

设计每个旗子两个点分别表示选 x_i 和 y_i, 然后二分答案 Ans, 这样每个点 x_i 左后各 Ans 位区间内的点的对应点都应该和 y_i 连边, 跑 2-SAT 判断可行性.

用线段树优化建边, 线段树优化 Tarjan, 可以在 O(n\log n) 的时间内, 跑 O(n^2) 条边的 Tarjan.

AC 之后才发现, 我写的根本就不是什么线段树优化建边, 如果非要起个名字, 我愿称之为 "无边Tarjan", 虽然常数效率不高, 但是实现非常精彩, 再次给线段树长脸了.

unsigned m, n, n2, SCC, Top(0);
unsigned A, B, C, D, t;
unsigned BinL(0), BinR(1000000000), BinMid; 
unsigned Cnt(0), Ans(0), Tmp(0);
char Flg(0);
struct Node;
struct Seg;
struct Node {
  Node* Bro;
  unsigned RL, RR, Low, DFSr, Pos, Num, Bel;
  inline const char operator < (const Node &x) const {return Pos < x.Pos; }
}N[20005], ForFind, * Tlag[10005], *Stack[20005], * To;
struct Seg {
  Seg* LS, * RS;
  Node* Ava;
  unsigned Mn;
  inline void Chg(unsigned L, unsigned R) {
    if(L == R) {Mn = B;return;}
    unsigned Mid((L + R) >> 1);
    if(A <= Mid) LS->Chg(L, Mid);
    else RS->Chg(Mid + 1, R);
    Mn = min(LS->Mn, RS->Mn);
  }
  inline void Vis(unsigned L, unsigned R) {
    if(L == R) {Ava = NULL;return;}
    unsigned Mid((L + R) >> 1);
    if(A <= Mid) LS->Vis(L, Mid);
    else RS->Vis(Mid + 1, R);
    Ava = (LS->Ava) ? (LS->Ava) : (RS->Ava);
  }
  inline void Qry(unsigned L, unsigned R) {
    if((A <= L) && (R <= B)) {Ans = min(Ans, Mn);return;}
    unsigned Mid((L + R) >> 1);
    if(A <= Mid) LS->Qry(L, Mid);
    if(B > Mid) RS->Qry(Mid + 1, R);
  }
  inline void Find(unsigned L, unsigned R) {
    if((A <= L) && (R <= B)) {To = Ava;return;}
    unsigned Mid((L + R) >> 1);
    if(A <= Mid) LS->Find(L, Mid);
    if(To) return;
    if(B > Mid) RS->Find(Mid + 1, R);
  }
}S[40005], * CntS(0);
inline void Build(Seg* x, unsigned L, unsigned R) {
  x->Mn = 0x3f3f3f3f;
  if (L == R) {x->Ava = N[L].Bro;return;}
  unsigned Mid((L + R) >> 1);
  Build(x->LS = ++CntS, L, Mid);
  Build(x->RS = ++CntS, Mid + 1, R);
  x->Ava = (x->LS->Ava) ? (x->LS->Ava) : (x->RS->Ava);
}
inline void Tarjan(Node* x) {
  x->Low = x->DFSr = ++Cnt, Stack[++Top] = x;
  Ans = 0x3f3f3f3f, A = x->RL, B = x - N - 1;
  if((B < 0x3f3f3f3f) && (A <= B)) S->Qry(0, n2 - 1);
  A = x + 1 - N, B = x->RR;
  if(A <= B) S->Qry(0, n2 - 1);
  x->Low = min(x->Low, Ans);
  A = x->Bro - N, B = x->Low, S->Chg(0, n2 - 1), S->Vis(0, n2 - 1);
  To = NULL, A = x->RL, B = x - N - 1; 
  if((B < 0x3f3f3f3f) && (A <= B)) S->Find(0, n2 - 1);
  A = x + 1 - N, B = x->RR;
  if(A <= B) S->Find(0, n2 - 1);
  Node* Cur(To);
  while(Cur) {
    Tarjan(Cur), x->Low = min(x->Low, Cur->Low);
    To = NULL, A = x->RL, B = x - N - 1;
    if((B < 0x3f3f3f3f) && (A <= B)) S->Find(0, n2 - 1);
    A = x + 1 - N, B = x->RR;
    if(A <= B) S->Find(0, n2 - 1);
    Cur = To;
  }
  A = x->Bro - N, B = x->Low, S->Chg(0, n2 - 1);
  if(x->Low == x->DFSr) {
    ++SCC, B = 0x3f3f3f3f;
    do{
      A = Stack[Top]->Bro - N, S->Chg(0, n2 - 1), Stack[Top]->Bel = SCC;
    }while(Stack[Top--] != x);
  }
}
inline char Judge(unsigned x) {
  SCC = 0, Flg = 0, CntS = S, Cnt = 0;
  Build(S, 0, n2 - 1);
  for (unsigned i(0); i < n2; ++i) {
    if(N[i].Pos >= x) ForFind.Pos = N[i].Pos - x + 1, N[i].RL = lower_bound(N, N + n2, ForFind) - N;
    else N[i].RL = 0;
    ForFind.Pos = N[i].Pos + x, N[i].RR = lower_bound(N, N + n2, ForFind) - N;
    if(N[i].RR >= n2) N[i].RR = n2 - 1; else --(N[i].RR);
  }
  for (unsigned i(0); i < n2; ++i) N[i].Low = N[i].DFSr = N[i].Bel = 0;
  for (unsigned i(0); i < n2; ++i) if(!N[i].DFSr) Tarjan(N + i);
  for (unsigned i(0); i < n2; ++i) if(N[i].Bel == N[i].Bro->Bel) {Flg = 1;break;}
  return Flg;
}
signed main() {
  n2 = ((n = RD()) << 1);
  for (unsigned i(0); i < n2; i += 2) {
    N[i].Pos = RD(), N[i ^ 1].Pos = RD();
    N[i].Num = N[i ^ 1].Num = i >> 1;
  }
  sort(N, N + n2);
  for (unsigned i(0); i < n2; ++i) {
    if(Tlag[N[i].Num]) Tlag[N[i].Num]->Bro = N + i, N[i].Bro = Tlag[N[i].Num];
    else Tlag[N[i].Num] = N + i;
  }
  while (BinL ^ BinR) {
    BinMid = (BinL + BinR + 1) >> 1;
    if(Judge(BinMid)) BinR = BinMid - 1;
    else BinL = BinMid;
  }
  printf("%u\n", BinL);
  return Wild_Donkey;
}

P6898

给定 n 个点的无向带权图, 将点集剖分成 L, R, 最小化 L 内部最大边权与 R 内部最大边权的和.

假设 L 的最大边权更大, 枚举 L 的最大边权 x, 二分 R 的最大边权 y. 对于一个二分到的 (x, y), 对所有大于 x 的边 (u_i, v_i), 连接 {u_i}_L 和 {v_i}_R, 对于大于 y 的边, 连接 {u_i}_R 和 {v_i}_L. 每次判断 x, y 是否可行可以直接跑 2-SAT, 单次 O(1).

但是这样的 2-SAT 判断次数达到了 O(n^2 \log Max), 总复杂度 O(n^4 \log Max), n \leq 200 是必然过不去的.

从大到小枚举边, 对于每条枚举的边, 假设它是 L 内部的最大边, 也就是 x. 然后讨论原图只选取 \geq x 的边, 得到的环的情况.

由于是从大到小枚举, 所以是不断向当前的图里加边, 而一条一条加边判断环的这种操作很经典的方法是并查集.

这里先定义一条边加入是否成环: 一条边加入后成环, 当且仅当它的两端本来就在一个连通块内.

接下来分类讨论按顺序枚举的边加入后成环情况:

• 不成环

  这种情况直接二分 y, 统计答案即可.

• 成偶环

  这时当前枚举的边的两端都应该在 L 中, 而如果这两个点都在 L 中, 剩下的点无论如何分配, 都会出现大于等于 x 的边连接同一集合内的两点, 所以这条边是不能做最大边的, 但是不排除更小的边做最大边的情况, 所以什么都不做直接 continue.

• 成奇环

  已经成奇环了, 奇环内无论怎么分配, 至少存在一条边会出现在集合内部, 我们设这条边是当前枚举的边, 这时 L 的最大边权是 x, 二分 y 得到这种情况的答案. 但是这时如果继续枚举边, 则这个奇环中的边都不能出现在集合内部了, 但是奇环永远不会消失, 所以以后就不会有解了, 所以二分完以后就结束枚举.

复杂度证明, 第一种情况的出现次数取决于两个端点不在一个集合中的边数, 容易发现, 第一种情况每次出现一次, 集合数就会少 1, 所以这种情况的出现次数是 O(n) 的. 每次出现花费 O(n^2 \log Max) 的复杂度, 所以总复杂度 O(n^3 \log Max).

第二种情况出现最多是 O(n^2) 次, 这种情况可以通过二分图的形式连边来构造, 每次出现消耗 O(\log n) 的复杂度, 总复杂度 O(n^2 \log n).

第三种情况最多出现一次, 复杂度 O(n^2 \log Max).

三种情况的总复杂度 O(n^3 \log Max).

代码部分, 需要查询环的奇偶, 所以使用边带权并查集, 维护每条边成环情况. 对于二分判断, 直接常规 2-SAT 即可.

unsigned E[205][205], Stack[405];
unsigned DFSr[405], Low[405], Bel[405], Col[405];
unsigned Fa[205], Setak[205], STop(0);
unsigned m, n, n2;
unsigned A, B, C, D, Mx(0);
unsigned Cnt(0), SCC(0), Ans(0x3f3f3f3f), Tmp(0), Top(0);
unsigned char ToFa[205];
char InS[405], Flg(0);
struct Edge {
  unsigned Frm, To, Val;
  const inline char operator <(const Edge& x) const {return Val < x.Val;}
}List[20005];
inline void Tarjan(unsigned x) {
  Low[x] = DFSr[x] = ++Cnt, Stack[++Top] = x, InS[x] = 1;
  if(x & 1) {
    for (unsigned i(0); i < n; ++i) {
      if(E[x >> 1][i] > D) {
        unsigned Cur(i << 1);
        if (DFSr[Cur]) {if(InS[Cur]) Low[x] = min(Low[x], Low[Cur]);}
        else Tarjan(Cur), Low[x] = min(Low[x], Low[Cur]);
      }
    }
  }else {
    for (unsigned i(0); i < n; ++i) {
      if(E[x >> 1][i] > C) {
        unsigned Cur((i << 1) ^ 1);
        if (DFSr[Cur]) {if(InS[Cur]) Low[x] = min(Low[x], Low[Cur]);}
        else Tarjan(Cur), Low[x] = min(Low[x], Low[Cur]);
      }
    }
  }
  if(Low[x] == DFSr[x]) {
    ++SCC;
    do Bel[Stack[Top]] = SCC, InS[Stack[Top]] = 0;
    while(Stack[Top--] ^ x);
  }
}
inline char Judge () {
  memset(Low, 0, ((n + 1) << 3));
  memset(DFSr, 0, ((n + 1) << 3));
  Cnt = 0, SCC = 0;
  for (unsigned i(0); i < n2; ++i) if(!DFSr[i]) Tarjan(i);
  for (unsigned i(0); i < n; ++i) if(Bel[i << 1] == Bel[(i << 1) ^ 1]) return 0;
  return 1;
}
inline unsigned Find(unsigned x) {
  unsigned char AddUp(0);
  while (Fa[x] ^ x) Setak[++STop] = x, x = Fa[x];
  while (STop) AddUp += ToFa[Setak[STop]], Fa[Setak[STop]] = x, ToFa[Setak[STop--]] = AddUp & 1;
  return x;
}
inline void Binary() {
  A = 0, B = D + 1;
  while (A ^ B) {
    C = (A + B) >> 1;
    if(Judge()) B = C;
    else A = C + 1;
  }
  if(A ^ (D + 1)) Ans = min(Ans, D + A);
}
signed main() {
  n2 = ((n = RD()) << 1), m = (n * (n + 1)) >> 1;
  for (unsigned i(0); i < n; ++i) Fa[i] = i;
  for (unsigned i(0); i < n; ++i) {
    E[i][i] = 0;
    for (unsigned j(i + 1); j < n; ++j)
      Mx = max(Mx, List[++Cnt].Val = E[i][j] = E[j][i] = RD()),
      List[Cnt].Frm = i, List[Cnt].To = j;
    List[++Cnt].Val = 0, List[Cnt].Frm = List[Cnt].To = i;
  }
  sort(List + 1, List + m + 1);
  for (unsigned i(m); i; --i) {
    D = List[i].Val, A = Find(List[i].Frm), B = Find(List[i].To);
    if(A ^ B) {
      Fa[A] = B, ToFa[A] = ToFa[List[i].Frm] ^ ToFa[List[i].To] ^ 1, Binary();
    } else {
      if(ToFa[List[i].Frm] ^ ToFa[List[i].To]) continue;
      else {Binary();break;}
    }
  }
  printf("%u\n", Ans);
  return Wild_Donkey;
}

CF1215F

有 n 个电台, 频段在 [l(i), r(i)] 之间.

由你在 [1, m] 中选频段 f. 区间不包含 f 的电台不能被启用.

给 k 条限制, 有两种:

• 电台 u 和 v 至少选一个

• 电台 u 和 v 不能同时选

输出 f 和选择方案.

其实频段就是增加了一些不能同时选的限制, 所以理论上我们应该给区间不交的点连边, 但是这样显然是 O(n^2) 的, 发现可以, 前缀和 + 后缀和优化建边, 优化到 O(n\log n).

得到的图跑 2-SAT.

得到一组可行解后, 将所有选定的区间取交 (其实就是求这些区间左端点最大值), 输出方案即可.

unsigned m, n, p, M;
unsigned A, B, C, D, t;
unsigned a[400005];
unsigned Cnt(0), Ans(0), Tmp(0), SCC(0), Top(0);
char Choice[400005], Flg(0);
struct Node;
struct Node {
  vector<Node*> To;
  unsigned DFSr, Low, Bel;
  char InS;
}N[1600005], * Stack[1600005], * Suf, * Pref;
struct Station {
  unsigned Le, Ri, Num;
  inline const char operator<(const Station& x) const{ return Num < x.Num;}
}S[400005];
inline char Cmpl(const Station &x, const Station &y) {return x.Le < y.Le;}
inline char Cmpr(const Station &x, const Station &y) {return x.Ri < y.Ri;}
inline void Tarjan(Node* x) {
  x->DFSr = x->Low = ++Cnt, Stack[++Top] = x, x->InS = 1; 
  for (auto i:x->To) {
    if(i->DFSr) { if(i->InS) x->Low = min(x->Low, i->Low); }
    else Tarjan(i), x->Low = min(x->Low, i->Low);
  }
  if(x->Low == x->DFSr) {
    ++SCC;
    do Stack[Top]->Bel = SCC, Stack[Top]->InS = 0;
    while (Stack[Top--] != x);
  }
}
signed main() {
  n = RD(), p = RD(), M = RD(), m = RD();
  Suf = N + (p << 1) + 1, Pref = Suf + p;
  for (unsigned i(1); i <= n; ++i)
    A = RD() << 1, B = RD() << 1, N[A ^ 1].To.push_back(N + B), N[B ^ 1].To.push_back(N + A);
  for (unsigned i(1); i <= p; ++i) S[i].Le = RD(), S[i].Ri = RD(), S[i].Num = i;
  for (unsigned i(1); i <= m; ++i)
    A = RD() << 1, B = RD() << 1, N[A].To.push_back(N + (B ^ 1)), N[B].To.push_back(N + (A ^ 1));
  sort(S + 1, S + p + 1, Cmpl);
  for (unsigned i(1); i <= p; ++i) Suf[i].To.push_back(N + ((S[i].Num << 1) ^ 1));
  for (unsigned i(1); i < p; ++i) Suf[i].To.push_back(Suf + i + 1);
  for (unsigned i(1); i <= p; ++i) a[i] = S[i].Le;
  for (unsigned i(1); i <= p; ++i) {
    A = upper_bound(a + 1, a + p + 1, S[i].Ri) - a;
    if(A <= p) N[S[i].Num << 1].To.push_back(Suf + A);
  }
  sort(S + 1, S + p + 1, Cmpr);
  for (unsigned i(1); i <= p; ++i) Pref[i].To.push_back(N + ((S[i].Num << 1) ^ 1));
  for (unsigned i(2); i <= p; ++i) Pref[i].To.push_back(Pref + i - 1);
  for (unsigned i(1); i <= p; ++i) a[i] = S[i].Ri;
  for (unsigned i(1); i <= p; ++i) {
    A = lower_bound(a + 1, a + p + 1, S[i].Le) - a - 1;
    if(A) N[S[i].Num << 1].To.push_back(Pref + A);
  }
  for (Node* i(N + ((p << 1) ^ 1)); i > N + 1; --i) if(!(i->DFSr)) Tarjan(i);
  for (unsigned i(1); i <= p; ++i)
    if(N[i << 1].Bel ^ N[(i << 1) ^ 1].Bel) Choice[i] = N[i << 1].Bel < N[(i << 1) ^ 1].Bel;
    else {Flg = 1; break;}
  if(Flg) {printf("-1\n"); return 0;}
  A = 0, B = 0x3f3f3f3f;
  sort(S + 1, S + p + 1);
  for (unsigned i(1); i <= p; ++i) if(Choice[i])
    A = max(A, S[i].Le), ++Ans;
  printf("%u %u\n", Ans, A);
  for (unsigned i(1); i <= p; ++i) if(Choice[i]) printf("%u ", i);
  return Wild_Donkey;
}

Day17: 网络流

Ford_Fulkerson

每次从源点 DFS 找增广路, 因为 DFS 可能会每次只找 1 个流量, 而且可能会遍历整个边集, 可能会被卡到 O(mMax).

Edmond_Karp

将 DFS 改成 BFS, 每次找边数最少的增广路来增广.

Dinic

BFS 将图分层, DFS 找增广路, 一次 DFS 走多条增广路. 为了避免走得太远, 选择只能从一个点走到它下一层的点. 复杂度 O(n^2m)

其它算法

但是仅仅是 Dinic 还远远不够, Dinic 的常用优化 ISAP 综合常数和复杂度考虑往往是常规数据中最有效率的算法. 对于正解是网络流的题目, 95\% 的题目可以用 Dinic 通过, 99.5\% 的题目可以用 ISAP 通过.

但是因为 HLPP 的复杂度非常优秀, 所以在一些较大的数据中, HLPP 是竞赛中会用到的最高效的算法. 但是由于代码复杂度, 常数还有网络流算法一般不会跑到复杂度上界等原因, Dinic 仍是算法竞赛的首选, 而且不会被卡.

最小割

最小割大小即为最大流大小, 这便是最小割最大流定理.

最大权闭合子图

一个有向图, 选择一个点就必须选择其后继点. 求选择的总点权最大值.

假设初始全选所有正权点, 设这个总和为 Sum, 建 S 连向所有正权点, 负权点连向 T, 容量都是对应点权的绝对值, 求出最大流也就是最小割.

• 求最多同时取出多少长度为 s 的不下降子序列

• 如果第一个和最后一个元素可以随意无限使用, 求最多同时取出多少长度为 s 的不同的不下降子序列

对于第一个问题, 直接 DP 即可.

设 DP 时每个点为结尾的最长不下降子序列为 f_i.

第二个问题, 每个点拆成两个, 中间连一条容量为 1 的边, 自己的第二个点往自己后面不比自己小的数 j 并且 f_j = f_i + 1 的第一个点连边, 这样就得到了一个分层图.

新建源点 S, 向每个深度为 1 的点连边, 新建汇点 T, 每个深度为 s 的点向汇点连边.

为了防止一个点两次被用, 我们将一个点拆成两个点, 中间用容量为 1 的边连接, 这样再跑最大流即可.

第三个问题, 为了复用第一个和最后一个元素, 我们只要将这两个元素的点之间的边, S 到 1 的第一个点, n 的第二个点到 T 的边的容量都设为无限.

别忘了特判序列长度为 1 的情况.

const unsigned maxn(1010);
unsigned Q[1005], Hd(0), Tl(0);
unsigned n, x[maxn], en(1), fst[maxn], S, T;
unsigned long long dep[maxn], Flow, Tmp1, Tmpn, Tmp, f[maxn], s;
struct Edge {
  ll c;
  unsigned to, nxt;
  char Type;
}ed[maxn * maxn + maxn * 2];
void add(int u, int v, ll w) {
  ed[++en].to = v, ed[en].c = w, ed[en].nxt = fst[u], fst[u] = en;
  ed[++en].to = u, ed[en].nxt = fst[v], fst[v] = en;
}
bool BFS() {
  memset(dep, 0, sizeof(dep));//重置深度
  dep[S] = 1;//重新来过
  Hd = Tl = 0, Q[++Tl] = S;
  while (Tl ^ Hd) {//手写队列可不可以/kk
    unsigned u(Q[++Hd]);
    for (unsigned e(fst[u]), v(ed[e].to); e; e = ed[e].nxt, v = ed[e].to)
      if ((!(dep[v])) && (ed[e].c > 0)) dep[v] = dep[u] + 1, Q[++Tl] = v;
  }
  return dep[T];
}
ll DFS(int u, ll flow) {//DFS 大成功 √
  if (u == T) return flow;//汇点, 来多少要多少
  if (!flow) return 0;//没有流量, 拉倒
  ll res = flow;//分配
  for (int e(fst[u]), v(ed[e].to); e; e = ed[e].nxt, v = ed[e].to) {
    if (!res) break;
    if ((dep[v] == dep[u] + 1) && (ed[e].c)) {//加个括号吧姐姐
      ll k(DFS(v, min(res, ed[e].c)));//实际上的流量
      if (!k) dep[v] = 0;//一点都流不得了
      res -= k;
      ed[e].c -= k, ed[e ^ 1].c += k;
    }
  }
  return flow - res;//这时剩余的和进来的差就是实际流量
}
int main() {
  n = rd(); S = n * 2 + 3, T = n * 2 + 4;
  if (n == 1) { printf("1\n1\n1\n");return 0; }
  for (int i(1); i <= n; ++i) x[i] = rd(), f[i] = 1;//2 ~ 2 * n + 1 // 自边 每一个点拆成两个点 二者连边? 用于限制每个数的使用次数
  for (int i(1); i <= n; ++i) for (int j(1); j < i; ++j)
    if (x[j] <= x[i]) f[i] = max(f[i], f[j] + 1);//DP 求最长
  for (int i(1); i <= n; ++i) s = max(s, f[i]);
  printf("%lld\n", s);
  for (int i(1); i <= n; ++i) if (f[i] == 1) add(S, i, 1);
  for (int i(1); i <= n; ++i) if (f[i] == s) add(i + n, T, 1);
  for (int i(1); i <= n; ++i) for (int j(1); j < i; ++j)
    if ((x[j] <= x[i]) && (f[j] + 1 == f[i])) add(j + n, i, 1);
  for (int i(1); i <= n; ++i) add(i, i + n, 1);//自边
  while (BFS()) Flow += DFS(S, inf); // 最大流
  printf("%lld\n", Flow);
  for (unsigned i(1); i <= en; ++i) ed[i].c = ((i & 1) ^ 1);
  for (unsigned e(fst[S]); e; e = ed[e].nxt) if (ed[e].to == 1) ed[e].c = inf;
  for (unsigned e(fst[n << 1]); e; e = ed[e].nxt) if (ed[e].to == T) ed[e].c = inf;
  ed[fst[1]].c = inf, ed[fst[n]].c = inf, Flow = 0;
  while (BFS()) Flow += DFS(S, inf); // 最大流
  printf("%lld\n", Flow);
  return 0;
}

P2774

给一个方格图, 每个格子有权值, 要求选出互不相邻的格子使得权值和最大, 求权值.

先在每对相邻的点之间连边, 得到一个二分图, 建立源点 S 连向二分图每个左部点一条容量为点权的边, 左部点到右部点的边容量无穷, 右部点向汇点 T 连容量为点权的边.

求这个网络的最小割后, 发现一定是 S 到左部点和右部点到 T 的边被割掉.

假设一开始选择所有点, 把每条边被割掉看成是对应的点被删除, 则最小割割掉后, 相当于不存在一条左右部之间的边两端的点都没有删掉的情况, 也就是点的选择合法了.

接下来分析其点权和最大, 因为是从所有点中, 删除一些点使得方案合法, 所以只要保证删除点权和最小, 而这个值等于网络的割, 因为求的是最小割, 所以这个值最小, 保证了答案正确性.

unsigned m, n, mn;
unsigned A, B, C, D, t;
unsigned Cnt(0), Ans(0), Tmp(0);
struct Node;
struct Edge {
  Node* To;
  unsigned Cap, Inv;
};
struct Node {
  vector<Edge> E;
  unsigned Dep;
}N[10005], * Q[10005];
inline char BFS() {
  for (Node* i(N + mn); i > N; --i) i->Dep = 0x3f3f3f3f;
  unsigned Hd(0), Tl(0);
  (Q[++Tl] = N)->Dep = 1;
  while (Hd ^ Tl) {
    Node* Cur(Q[++Hd]);
    for (auto i:Cur->E) if((i.Cap) && (i.To->Dep >= 0x3f3f3f3f))
      i.To->Dep = Cur->Dep + 1, Q[++Tl] = i.To;
  }
  return N[1].Dep < 0x3f3f3f3f;
}
inline unsigned DFS(Node* x, unsigned Come) {
  if(x == N + 1) {Ans -= Come; return Come;}
  unsigned Res(Come);
  for (unsigned i(x->E.size() - 1); ~i; --i) 
    if((x->E[i].Cap) && (x->E[i].To->Dep == x->Dep + 1)) {
      unsigned Go(min(x->E[i].Cap, Res)), Push(DFS(x->E[i].To, Go));
      if(Push < Go) {x->E[i].To->Dep = 0x3f3f3f3f;}
      Res -= Push, x->E[i].Cap -= Push, x->E[i].To->E[x->E[i].Inv].Cap += Push;
    }
  return Come - Res;
}
inline void Link(Node* x, Node* y) {
  x->E.push_back((Edge){y, 0x3f3f3f3f, 0});
  y->E.push_back((Edge){x, 0, 0});
  x->E.back().Inv = y->E.size() - 1;
  y->E.back().Inv = x->E.size() - 1;
  return;
}
signed main() {
  n = RD(), m = RD(), mn = (n * m) + 1;
  for (unsigned i(1), k(2); i <= n; ++i) {
    for (unsigned j(1); j <= m; ++j, ++k) {
      Ans += (A = RD());
      if((i ^ j) & 1) {
        N->E.push_back((Edge){N + k, A, 0});
        N[k].E.push_back((Edge){N, 0, 0});
        N[k].E[0].Inv = (k >> 1) - 1;
      } else {
        N[1].E.push_back((Edge){N + k, 0, 0});
        N[k].E.push_back((Edge){N + 1, A, 0});
        N[k].E[0].Inv = (k >> 1) - 1;
      }
    }
  }
  for (unsigned i(2), j; i <= mn; ++i)
    if (((((i - 2) / m) + 1) ^ (((i - 2) % m) + 1)) & 1) {
      if ((i - 2) % m) Link(N + i, N + i - 1);
      if ((i - 1) % m) Link(N + i, N + i + 1);
      if (i > m + 1) Link(N + i, N + i - m);
      if (i + m <= mn) Link(N + i, N + i + m);
    }
  while (BFS()) DFS(N, 0x3f3f3f3f);
  printf("%u\n", Ans);
  return Wild_Donkey;
}

由于在 vector 里只有 0 号元素的时候访问 1 号元素, 所以调了很久, 但是非常感谢小黄鸭的支持, 让我意识到这个问题, 获得了 AC.

P1251

有 n 天, 每天需要 r_i 块餐巾, 每天可以送去快/慢洗部一些餐巾, 花费一定 m or n 天是间和 f or s 金钱洗完, 也可以新买一批餐巾, 花费金钱 p 立刻得到餐巾.

求保证每天有足够干净餐巾的情况下的最小花费.

每天建两个点, 分别是臭抹布点和新抹布点.

源点 S 向每天的新抹布点连一条费用为 p, 容量无限的边, 这些边代表着新抹布收费不限量供应.

源点 S 向每天的臭抹布点连一条免费的, 容量为 r_i 的边, 表示臭抹布免费限量供应, 数量取决于当天用多少.

每天的新抹布点向汇点 T 连一条免费的, 容量为 r_i 的边, 表示新抹布用完后扔到一个高维空间, 这里面的臭抹布会通过源点提供给当天的臭抹布点.

每天的臭抹布点下一天的臭抹布点连一条免费的, 容量无限的边, 表示可以把臭抹布放着不洗.

臭抹布点还可以向 n 或 m 天之后的新抹布点连费用为 s 或 f, 容量无限的边, 表示可以洗抹布.

容易发现, 这个网络最大流是所有天的抹布总和, 而它的最小费用最大流就是最小的花费.

#define INF 20000000000
long long a[4005]; 
long long QC, New, SC, Ans(0);
unsigned QD, SD, n, n2;
unsigned A, B, C, D, t;
unsigned Cnt(0);
struct Node;
struct Edge {
  Node* To;
  long long Val, Cap;
  unsigned Inv;
};
struct Node {
  vector<Edge> E;
  long long Dis;
  char InQ;
}N[4005], * Q[100005];
inline void Link(Node* x, Node* y, long long V) {
  x->E.push_back((Edge){y, V, INF, 0});
  y->E.push_back((Edge){x, -V, 0, 0});
  x->E.back().Inv = y->E.size() - 1;
  y->E.back().Inv = x->E.size() - 1;
}
inline char SPFA () {
  for (Node* i(N + n2); i > N; --i) i->Dis = INF, i->InQ = 0; 
  unsigned Hd(0), Tl(0);
  (Q[++Tl] = N)->Dis = 0, N->InQ = 1;
  while (Hd ^ Tl) {
    Node* Cur(Q[++Hd]);
    Cur->InQ = 0;
    for (auto i:Cur->E) if((i.Cap) && (i.To->Dis > Cur->Dis + i.Val)) {
      i.To->Dis = Cur->Dis + i.Val;
      if(!(i.To->InQ)) Q[++Tl] = i.To, i.To->InQ = 1;
    }
  }
  return N[1].Dis < INF;
}
inline long long DFS (Node* x, long long Come) {
  x->InQ = 1;
  if(x == N + 1) {Ans += Come * x->Dis;return Come;}
  long long Res(Come);
  for (unsigned i(x->E.size() - 1); ~i; --i) 
    if((x->E[i].Cap) && (x->E[i].To->Dis == x->Dis + x->E[i].Val) && (!(x->E[i].To->InQ))) {
      long long Go(min(x->E[i].Cap, Res)), Push(DFS(x->E[i].To, Go));
      x->E[i].To->InQ = 0;
      if(Go > Push) x->E[i].To->Dis = INF;
      Res -= Push, x->E[i].Cap -= Push, x->E[i].To->E[x->E[i].Inv].Cap += Push;
      if(!Res) break; 
    }
  return Come - Res;
}
signed main() {
  n2 = ((n = RD()) << 1) + 1;
  for (unsigned i(1); i <= n; ++i) a[i] = RD();
  New = RD(), QD = RD(), QC = RD(), SD = RD(), SC = RD();
  for (unsigned i(2); i <= n2; i += 2) {
    N->E.push_back((Edge){N + i, 0, a[i >> 1], 0});
    N[i].E.push_back((Edge){N, 0, 0, (i >> 1) - 1});
  }
  for (unsigned i(3); i <= n2; i += 2) {
    N->E.push_back((Edge){N + i, New, INF, 0});
    N[i].E.push_back((Edge){N, -New, 0, n + (i >> 1) - 1});
  }
  for (unsigned i(3); i <= n2; i += 2) {
    N[1].E.push_back((Edge){N + i, 0, 0, 1});
    N[i].E.push_back((Edge){N + 1, 0, a[i >> 1], (i >> 1) - 1});
  }
  for (unsigned i(4); i <= n2; i += 2) Link(N + i - 2, N + i, 0);
  if(QD < n) for (unsigned i(n2 - ((QD) << 1) ^ 1); i >= 2; i -= 2) Link(N + i, N + i + (QD << 1) + 1, QC);
  if(SD < n) for (unsigned i(n2 - ((SD) << 1) ^ 1); i >= 2; i -= 2) Link(N + i, N + i + (SD << 1) + 1, SC);
  while (SPFA()) DFS(N, INF);
  printf("%lld\n", Ans);
  return Wild_Donkey;
}

NOI2008

这个题可以不用管放椅子的问题, 因为既然往实数点放了, 就一定可以想让谁坐, 就找到一个位置放下椅子让他坐, 所以我们只要求原来整点上的椅子和人的最大匹配就可以了.

但是这个题如果用二分图匹配, 每个人连出 O(m) 条边, 则总边数就是 O(nm) 的, 这样跑二分图匹配就是 O(nm\sqrt n), 是绝对不行的.

因为建边的特殊性, 考虑前后缀和优化建边, 这样用 3m + n 个点, 4m + 2n 条边将图建出来, 然后跑二分图.

下面这份 Dinic 跑二分图, 在 48 个点中过了 31 个.

unsigned a[10005], m, n;
unsigned A, B, C, D, t;
unsigned Cnt(0), Ans(0), Tmp(0);
struct Node;
struct Edge {
  Node* To;
  unsigned Cap, Inv;
};
struct Node {
  vector<Edge> E;
  unsigned Dep;
}N[800005], * Q[800005], * Peo, * Suf, * Pre, * Cha(N + 1);
inline void Link(Node* x, Node* y) {
  x->E.push_back((Edge){y, INFi, 0});
  y->E.push_back((Edge){x, 0, 0});
  x->E.back().Inv = y->E.size() - 1;
  y->E.back().Inv = x->E.size() - 1;
}
inline char BFS() {
  for (Node* i(Peo + n + 1); i > N; --i) i->Dep = 0x3f3f3f3f;
  unsigned Hd(0), Tl(0);
  (Q[++Tl] = N)->Dep = 1;
  while (Hd ^ Tl) {
    Node* Cur(Q[++Hd]);
    for (auto i:Cur->E) if((i.Cap) && (i.To->Dep >= 0x3f3f3f3f)) 
      i.To->Dep = Cur->Dep + 1, Q[++Tl] = i.To;
  }
  return N[1].Dep < 0x3f3f3f3f;
}
inline unsigned DFS(Node* x, unsigned Come) {
  if(x == N + 1) {--Ans; return 1;}
  unsigned Res(Come);
  for (unsigned i(x->E.size() - 1); ~i; --i) 
    if((x->E[i].Cap) && (x->E[i].To->Dep == x->Dep + 1)) {
      unsigned Go(min(Res, x->E[i].Cap)), Push(DFS(x->E[i].To, Go));
      if(Go ^ Push) x->E[i].To->Dep = 0x3f3f3f3f;
      Res -= Push, x->E[i].Cap -= Push, x->E[i].To->E[x->E[i].Inv].Cap += Push;
      if(!Res) break;
    }
  return Come - Res;
}
signed main() {
  Ans = n = RD(), Pre = N + (m = RD()) + 1, Suf = Pre + m, Peo = Suf + m;
  for (unsigned i(1); i <= m; ++i) {
    Cha[i].E.push_back((Edge){N + 1, 1, i - 1});
    N[1].E.push_back((Edge){Cha + i, 0, 0});
    Cha[i].E.push_back((Edge){Pre + i, 0, 0});
    Pre[i].E.push_back((Edge){Cha + i, 1, 1});
    Cha[i].E.push_back((Edge){Suf + i, 0, 0});
    Suf[i].E.push_back((Edge){Cha + i, 1, 2});
  }
  for (unsigned i(1); i <= n; ++i) {
    Peo[i].E.push_back((Edge){N, 0, i - 1});
    N->E.push_back((Edge){Peo + i, 1, 0});
  }
  for (unsigned i(2); i <= m; ++i) Link(Pre + i, Pre + i - 1);
  for (unsigned i(1); i < m; ++i) Link(Suf + i, Suf + i + 1);
  for (unsigned i(1); i <= n; ++i) {
    A = RD(), B = RD();
    if(A) Link(Peo + i, Pre + A);
    if(B <= m) Link(Peo + i, Suf + B);
  }
  while (BFS()) DFS(N, INFi);
  printf("%u\n", Ans);
  return Wild_Donkey;
}

但是我怎么能只会写 Dinic 呢, ISAP 赶紧安排上, 结果发现只过了 24 个点.

unsigned m, n, m3n1;
unsigned Gap[800005];
inline void BFS() {
  for (Node* i(Peo + n); i >= N; --i) i->Dep = 0x3f3f3f3f;
  unsigned Hd(0), Tl(0);
  ++Gap[(Q[++Tl] = N + 1)->Dep = 0];
  while (Hd ^ Tl) {
    Node* Cur(Q[++Hd]);
    for (auto i:Cur->E) if((i.To->E[i.Inv].Cap) && (i.To->Dep >= 0x3f3f3f3f)) 
      ++Gap[i.To->Dep = Cur->Dep + 1], Q[++Tl] = i.To;
  }
}
inline unsigned DFS(Node* x, unsigned Come) {
  if(x == N + 1) {--Ans; return 1;}
  unsigned Res(Come);
  for (unsigned i(x->E.size() - 1); ~i; --i)
    if((x->E[i].Cap) && (x->E[i].To->Dep + 1 == x->Dep)) {
      unsigned Go(min(Res, x->E[i].Cap)), Push(DFS(x->E[i].To, Go));
      Res -= Push, x->E[i].Cap -= Push, x->E[i].To->E[x->E[i].Inv].Cap += Push;
      if(!Res) return Come;
    }
  if(!(--Gap[(x->Dep)++])) N->Dep = m3n1 + 1;
  ++Gap[x->Dep];
  return Come - Res;
}
signed main() {
  Ans = n = RD(), Pre = N + (m = RD()) + 1, Suf = Pre + m, Peo = Suf + m;
  m3n1 = (m << 1) + m + n;
  /*建边, 同上*/
  BFS();
  while (N->Dep <= m3n1) DFS(N, INFi);
  printf("%u\n", Ans);
  return Wild_Donkey;
}

在当前弧优化 (不放代码了, 这文章太 TM 长了) 之后, 少 T 了几个点, 但还是没跑过 Dinic.

所以查看正解, 需要用到 Hall 定理的一个推论, 如果 S 表示左部点的一个子集, R(S) 表示它们能连接的右部点的点集, 那么 n - max(|S| - |R(S)|) 就是二分图的最大匹配.

因为我们要求 n - 最大匹配, 所以就是求 max(|S| - |R(S)|).

结合此题连边方式的特殊性, R(S) 事实上是 S 中的所有连边区间的并, 我们知道, 一些区间的并, 就是这些区间的补的交的补, 这样比较好做.

转化为求 S, 使得 |S| 加上它所有连边补区间的交最大, 答案就是这个值减去 m.

因为显然这个交一定是一段区间, 所以我们可以用枚举区间的惯用伎俩, 枚举右端点, 线段树扫描左端点.

当交确定的时候, 这是需要让 S 最大. 那么一定是把所有连边补区间包含这个区间的都算上, 我们需要查询所有右端点 \geq R, 并且左端点 \leq L 的区间数量, 可以按右端点排序, 然后从大到小加入线段树, 查询 [1, L] 区间数量即可.

优化方面, 需要快速查询 L \in [1, R] 的 [1, L] 区间和加上 R - L + 1 的最大值, 所以首先需要给每个位置都减去 L, 然后每次查询之后全局加 R + 1.

所以我们要求的是线段树上点的前缀和减去 L 的最大值, 可以认为减 L 是序列 {-1, -1, ..., -1, -1} 的前缀和.

所以不如直接维护前缀和, 把单点修改变成区间修改, 然后查询区间最值即可.

对于 -L, 建树时维护即可.

具体实现仍有不同, 因为实在不想用有符号整型, 所以给线段树每个点赋初值 m - L, 最后多减一个 m 即可.

线段树方面因为是后缀修改和前缀查询, 优化了一些冗余判断.

统计答案时因为永远都要减 m, 所以放到最后一起统计, 这样临时答案就累计了 m << 1 的偏移. 因为交区间为空的情况不好询问, 所以提前将这种情况的答案统计上 (max(n - m, 0), 偏移后是 max(n + m, m << 1)), 输出时不要忘记修正 m << 1 的偏移.

从图论绕到我的主场数据结构, 真是如回家般亲切啊.

pair<unsigned, unsigned> a[200005];
unsigned m, n;
unsigned A, B, C, D, t;
unsigned Cnt(0), Ans(0), Tmp(0);
struct Node {
  Node* LS, * RS;
  unsigned Val, Tag;
  inline void PsDw() {
    if(Tag) {
      LS->Tag += Tag;
      RS->Tag += Tag;
      LS->Val += Tag;
      RS->Val += Tag; 
      Tag = 0;
    }
  }
  inline void Change(unsigned L, unsigned R) {
    if(A <= L) {++Val, ++Tag; return;}
    unsigned Mid((L + R) >> 1);
    PsDw();
    if(A <= Mid) LS->Change(L, Mid);
    RS->Change(Mid + 1, R);
    Val = max(LS->Val, RS->Val);
  }
  inline void Qry(unsigned L, unsigned R) {
    if(R <= A) {C = max(Val, C); return;}
    unsigned Mid((L + R) >> 1);
    PsDw();
    LS->Qry(L, Mid);
    if(A > Mid) RS->Qry(Mid + 1, R);
  }
}N[400005], * CntN(N);
inline void Build (Node* x, unsigned L, unsigned R) {
  if(L == R) {x->Val = m - L; return;}
  unsigned Mid((L + R) >> 1);
  Build(x->LS = ++CntN, L, Mid);
  Build(x->RS = ++CntN, Mid + 1, R);
  x->Val = max(x->LS->Val, x->RS->Val);
}
signed main() {
  n = RD(), m = RD(), Build(N, LE, RE);
  Ans = max(n + m, m << 1);
  for (unsigned i(1); i <= n; ++i) a[i].second = RD() + 1, a[i].first = RD() - 1;
  sort(a + 1, a + n + 1);
  for (unsigned i(n); i; --i) {
    if(a[i].second <= m) A = a[i].second, N->Change(LE, RE);
    if(a[i].first ^ a[i - 1].first) {
      A = a[i].first, C = 0, N->Qry(LE, RE);
      Ans = max(Ans, C + a[i].first + 1);
    }
  }
  printf("%u\n", Ans - (m << 1));
  return Wild_Donkey;
}

CF1288F

一个二分图, 有三种节点, R, B, U, 尝试给边染色使得 R 点连接的 R 边严格大于 B 边, B 点 连接的 B 边严格大于 R 边.

每条 R 边花费 r 的代价, B 边花费 b 的代价, 求满足条件的花费最小的染色方案并且求这个最小花费.

考虑最小费用最大流, 一个点从对面的点流入的流量和流向对面的点的流量表示它相邻的边染成不同的颜色, 一个点从源点流入的流量或流向汇点的流量表示它自己需要满足某种颜色严格大于另一种的限制, 这样在保证每个点流量平衡的前提下, 流入和流出的流量相等, 其中从源点流入的流量或者从汇点流出的流量就是自己同色的边比另一种颜色多出来的边数.

从源点向左部的 R 和右部的 B 连倒贴钱的流量为 1 的边, 表示至少应该多染一条 R/B.

从左部的 B 和右部的 G 向汇点连倒贴钱的流量为 1 的边, 表示至少应该多染一条 B/R.

规定左部 R 从右部点的流入流量代表染 B, 流出到右部点的流量代表染 G, 从源点流入的流量只要非负, 在流量平衡的前提下, 这个 R 点相邻的 R 边就一定比 B 边多.

其它点也是类似地保证方案的合法性, 左部点都是流入 B, 流出 R, 右部点都是流入 R 流出 B, 所以我们只要对于每条二分图上的边, 连一条从左往右的花费 r , 流量 1 的边表示这条边选 R 的情况, 连一条花费 b, 流量 1 的边表示这条边选 B 的情况.

但是一个点染的同色边不仅仅可以比异色边多一条, 也可以多 >1 条, 但是这个数量不会使得答案更优, 所以我们不在边权上进行诱导, 所以每条倒贴钱的边, 复制出一条免费的流量不限的边即可.

对于 U 点, 它们无论左右都和源汇连边, 表示它连接的 R 边 B 边谁多谁少无所谓, 所以也是都连免费的流量无限边.

图建完了, 接下来考虑流的意义, 一条流从源点流出, 经过一条边到达一个点. 如果这条边倒贴钱, 表示满足了一个点的限制, 然后通往另一个点, 花费这个点流出边对应的颜色的花费.

对于新的点, 如果这个流经过一条边通往汇点, 且倒贴钱, 说明又满足了一个点的限制, 如果这条边是免费的, 说明这个点的限制已经被满足了.

如果流经过这个点后没有通往汇点, 则相当于流入又流出, 给这个点的同时染了两种不同颜色的边, 花费了入边出边两条边的代价, 然后在新到达的点重复上面的过程.

如果一股流一条倒贴钱的边都没有经过, 那么它不会对局面的合法性造成任何影响, 因为没有一个点的限制被它所满足, 所以这股流只能使得答案更劣, 无需计算.

所以我们跑 EK + SPFA, 每次增广 (S, T) 的最短路, 当最短路非负的时候结束算法.

判断一个局面是否合法也很简单, 因为每个有色点的限制都被满足当且仅当所有的倒贴钱的边都被经过, 所以我们只要计算有多少边倒贴钱了即可.

unsigned a[10005], m1, n1, n2, r, b;
unsigned A, B, C, D, t, Tl(0), Hd(0);
unsigned Cnt(0), Ans(0), Tmp(0);
unsigned Pr[205][2][2];
char IO[205];
struct Node;
struct Edge {
  Node* To;
  unsigned Inv, Cap;
  int Val;
};
struct Node {
  vector<Edge> E;
  Node* Pre;
  unsigned Come;
  int Dis;
}N[405], * Q[100005], *N1(N + 1), * N2;
inline void Link(Node* x, Node* y, const unsigned Ca, const int Va) {
  x->E.push_back((Edge){y, 0, Ca, Va});
  y->E.push_back((Edge){x, 0, 0, -Va});
  x->E.back().Inv = y->E.size() - 1;
  y->E.back().Inv = x->E.size() - 1;
}
inline char SPFA() {
  for (Node* i(N2 + n2); i > N; --i) i->Dis = INF;
  Hd = Tl = 0;
  (Q[++Tl] = N)->Dis = 0;
  while (Hd ^ Tl) {
    Node* Cur(Q[++Hd]);
    for (unsigned i(Cur->E.size() - 1); ~i; --i)
      if((Cur->E[i].Cap) && (Cur->E[i].To->Dis > Cur->Dis + Cur->E[i].Val)) {
        Cur->E[i].To->Pre = Cur, Cur->E[i].To->Come = i;
        Cur->E[i].To->Dis = Cur->Dis + Cur->E[i].Val, Q[++Tl] = Cur->E[i].To;
      }
  }
  return N[1].Dis < 0;
}
signed main() {
  N2 = N1 + (n1 = RD()), n2 = RD(), m1 = RD(), r = RD(), b = RD();
  scanf("%s", IO + 1);
  for (unsigned i(1); i <= n1; ++i) {
    if(IO[i] == 'R') Link(N, N1 + i, 1, -INF), Link(N, N1 + i, 400, 0), ++Cnt;
    if(IO[i] == 'B') Link(N1 + i, N + 1, 1, -INF), Link(N1 + i, N + 1, 400, 0), ++Cnt;
    if(IO[i] == 'U') Link(N, N1 + i, 400, 0), Link(N1 + i, N + 1, 400, 0);
  }
  scanf("%s", IO + 1);
  for (unsigned i(1); i <= n2; ++i) {
    if(IO[i] == 'R') Link(N2 + i, N + 1, 1, -INF), Link(N2 + i, N + 1, 400, 0), ++Cnt;
    if(IO[i] == 'B') Link(N, N2 + i, 1, -INF), Link(N, N2 + i, 400, 0), ++Cnt;
    if(IO[i] == 'U') Link(N, N2 + i, 400, 0), Link(N2 + i, N + 1, 400, 0);
  }
  for (unsigned i(1); i <= m1; ++i) {
    A = RD(), B = RD();
    Link(N1 + A, N2 + B, 1, r), Pr[i][0][0] = A, Pr[i][0][1] = N1[A].E.size() - 1;
    Link(N2 + B, N1 + A, 1, b), Pr[i][1][0] = B, Pr[i][1][1] = N2[B].E.size() - 1;
  }
  while (SPFA()) {
    Node* Cur(N + 1);
    unsigned Flow(INF);
    while (Cur > N) Flow = min(Flow, Cur->Pre->E[Cur->Come].Cap), Cur = Cur->Pre;
    Ans += Flow * (Cur = N + 1)->Dis;
    while (Cur > N) Cur->Pre->E[Cur->Come].Cap -= Flow, Cur->E[Cur->Pre->E[Cur->Come].Inv].Cap += Flow, Cur = Cur->Pre;
  }
  Ans += Cnt * INF;
  if(Ans >= INF) {printf("-1\n");return 0;}
  printf("%d\n", Ans);
  for (unsigned i(1); i <= m1; ++i) {
    if(!(N1[Pr[i][0][0]].E[Pr[i][0][1]].Cap)) putchar('R');
    else if(!(N2[Pr[i][1][0]].E[Pr[i][1][1]].Cap)) putchar('B');
    else putchar('U');
  }
  return Wild_Donkey;
}

Day18: 模拟赛

期望 360 炸成 210, 真不是我假, 考完试就说我挂了 TMD 100+.

A

一个 ST 题, 放在 T1 还算合理.

但是...

样例诈骗不讲武德, ST 表写炸了样例全过, 结果爆 0.

unsigned Lst[2000005], a[2][1000005][20], Pos[1000005][2][2], Bin[1000005], Log[1000005], m, n, Cnt(0), Ans(0);
inline unsigned Find(unsigned L, unsigned x, unsigned y) {
  register unsigned Tmp(Log[y - x + 1]);
  return max(a[L][x][Tmp], a[L][y - Bin[Tmp] + 1][Tmp]);
}
int main() {
  n = RD();
  for (register unsigned b(0); b < 2; ++b) {
    for (register unsigned i(1); i <= n; ++i) {
      Lst[++Cnt] = a[b][i][0] = RD();
    }
  }
  sort(Lst + 1, Lst + Cnt + 1);
  unique(Lst + 1, Lst + Cnt + 1);
  for (register unsigned b(0); b < 2; ++b) {
    for (register unsigned i(1); i <= n; ++i) {
      a[b][i][0] = lower_bound(Lst + 1, Lst + n + 1, a[b][i][0]) - Lst;
      if(Pos[a[b][i][0]][0][1]) {
        Pos[a[b][i][0]][1][0] = b;
        Pos[a[b][i][0]][1][1] = i;
      } else {
        Pos[a[b][i][0]][0][0] = b;
        Pos[a[b][i][0]][0][1] = i;
      }
    }
  }
  for (register unsigned i(1), j(0); i <= n; i <<= 1, ++j) {
    Bin[j] = i, Log[i] = j; 
  }
  for (register unsigned i(2); i <= n; ++i) {
    Log[i] = max(Log[i], Log[i - 1]);
  }
  for (register unsigned b(0); b < 2; ++b) {
    for (register unsigned i(1); i <= Log[n]; ++i) {
      for (register unsigned j(1); j + Bin[i] <= n + 1; ++j) {
        a[b][j][i] = max(a[b][j][i - 1], a[b][j + Bin[i - 1]][i - 1]);
      }
    }
  }
  for (register unsigned i(n); i; --i) {
    if(Pos[i][0][0] ^ Pos[i][1][0]) {
      Ans = max(Ans, i);
      continue;
    }
    if(Pos[i][0][1] > Pos[i][1][1]) {
      swap(Pos[i][0][1], Pos[i][1][1]);
    }
    if(Pos[i][0][1] + 1 == Pos[i][1][1]) {
      continue;
    }
    Ans = max(min(i, Find(Pos[i][0][0], Pos[i][0][1] + 1, Pos[i][1][1] - 1)), Ans);
  }
  printf("%u\n", Lst[Ans]);
  return Wild_Donkey;
}

B

求一个数 x 和序列中所有数的差的平方和.

这个答案对 x 成二次函数关系, 所以只要用所有数的平方和和总和求出解析式然后 O(1) 求答案即可.

大水题, 本来可以 O(n), 但是数据非要开 3000.

所以我们 O(n) 枚举这个数即可, 总复杂度 O(n^2).

unsigned a[10005], m, n, Cnt(0), Sum(0);
unsigned long long Ans(0x3f3f3f3f3f3f3f3f), Tmp, A;
char b[10005];
inline void Clr() {}
int main() {
  n = RD();
  for (register unsigned i(1); i <= n; ++i) {
    Sum += (a[i] = RDsg() + 4000);
  }
  Sum /= n;
  for (register unsigned i(1000); i <= 7000; ++i) {
    Tmp = 0;
    for (register unsigned j(1); j <= n; ++j) {
      A = max(a[j], i) - min(a[j], i);
      Tmp += A * A;
    }
    Ans = min(Ans, Tmp);
  }
  printf("%llu\n", Ans);
  return Wild_Donkey;
}

C

我到 AC 都不知道暴力怎么写./kk

线段树 + 二分答案事实上可以优化成 ST + 二分答案, 这样就能将 O(n \log^2n) 优化到 O(n \log n).

然后我就看着老师三年前的代码拿着 O(n^3) 的复杂度跑得比我 O(n \log n) 都快.

int ma[205][205],mi[205][205],a[205],n,r,sum[205],mx=0,mn=0x7fffffff;
inline int in()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        mi[i][i]=0;
        sum[i]=sum[i-1]+a[i];
    }
    for(int i=n+1;i<=2*n-1;i++)
    {
        a[i]=a[i-n];
        mi[i][i]=0;
        sum[i]=sum[i-1]+a[i];
    }
    return 0;
}
int main()
{
    memset(mi,0x7f7f7f7f,sizeof(mi));
    memset(ma,0,sizeof(ma));
    in();
    for(int q=2;q<=n;q++)
    {
        for(int l=1;l<=2*n-q;l++)
        {
            r=l+q-1;
            for(int k=l;k<r;k++)
            {
                ma[l][r]=max(ma[l][r],ma[l][k]+ma[k+1][r]+sum[r]-sum[l-1]);
                mi[l][r]=min(mi[l][r],mi[l][k]+mi[k+1][r]+sum[r]-sum[l-1]);
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        mx=max(mx,ma[i][i+n-1]);
        mn=min(mn,mi[i][i+n-1]);
    }
    cout<<mn<<endl<<mx;
    return 0;
}

SCOI2003

区间 DP, 设计状态 f_{i, j} 表示区间 [i, j] 的最小折叠长度.

unsigned m, n;
unsigned A, B, C, D, t;
unsigned Cnt(0), Ans(0), Tmp(0);
unsigned Hash[105][105], f[105][105];
unsigned Pls[105];
char a[105];
signed main() {
  fread(a + 1, 1, 100, stdin);
  memset(f, 0x3f, sizeof(f));
  for (n = 0; a[n + 1] >= 'A'; ++n);
  for (unsigned Len(1); Len <= n; ++Len)
    for (unsigned i(n - Len + 1); i; --i)
      Hash[Len][i] = Hash[Len - 1][i + 1] * 31 + a[i] - 'A';
  for (unsigned i(0); i < 10; ++i) Pls[i] = 3;
  for (unsigned i(10); i < 100; ++i) Pls[i] = 4;
  Pls[100] = 5;
  for (unsigned Len(1); Len <= n; ++Len)
    for (unsigned i(n - Len + 1); i; --i) 
      f[Len][i] = Len;
  for (unsigned Len(1); Len <= n; ++Len) {
    for (unsigned L(n - Len + 1); L; --L) {
      for (unsigned i(1); i < Len; ++i) if(!(Len % i)) {
        char Flg(0);
        unsigned Tplt(Hash[i][L]);
        for (unsigned j(L + Len - i); j > L; j -= i)
          if(Hash[i][j] ^ Tplt) {Flg = 1; break;}
        if(!Flg) f[Len][L] = min(f[Len][L], f[i][L] + Pls[Len / i]);
      }
      for (unsigned len(1); len < Len; ++len)
        f[Len][L] = min(f[Len][L], f[len][L] + f[Len - len][L + len]);
    }
  }
  printf("%u\n", f[n][1]);
  return Wild_Donkey;
}

P1220

因为任意时刻关闭的路灯一定是一个连续的区间, 所以设计状态 f_{i, j, 0/1} 表示一个区间内的灯都关闭, 最后人在左/右边的花费.

发现对于第二种情况, 她一定不能得到比第一种情况优的答案, 因为如果它比第一种优 Dis_{i + 1, j} * (Sum_{1, n} - Sum_{i + 1, j}) 那么 f_{i + 1, j, 0} 的值就不是正确的, 因为我们可以找到一个方案比它更优, 也就是在 f_{i + 1, j, 1} 的基础上移动到 i + 1 上去.

所以我们可以简化转移:

对于 f_{i, j, 1} 的转移同理.

代码为了充分利用空间, 对于 i < j, f_{i, j} 表示 f_{i, j, 0}, 对于 i > j, f_{i, j} 表示 f_{i, j, 1}, 对于 i == j, f_{i, j} 表示 f_{i, j, 0/1}.

int n, L[1005], P[1005], at, sum[1005], f[1005][1005];
bool flg[1005];
int main() {
    cin >> n >> at;
    memset(f, 0x3f, sizeof(f));
    for (int i = 1; i <= n; i++) {
        cin >> L[i] >> P[i];
        sum[i] = sum[i - 1] + P[i];
    }
    f[at][at] = 0;
    for (int l = 2; l <= n; l++) {
        for (int i = 1; i + l - 1 <= n; i++) {
            int j = i + l - 1;
            f[i][j] = min(f[i + 1][j] + (L[i + 1] - L[i]) * (sum[i] + sum[n] - sum[j]), f[j][i + 1] + (L[j] - L[i]) * (sum[i] + sum[n] - sum[j]));
            f[j][i] = min(f[i][j - 1] + (L[j] - L[i]) * (sum[i - 1] + sum[n] - sum[j - 1]), f[j - 1][i] + (L[j] - L[j - 1]) * (sum[i - 1] + sum[n] - sum[j - 1]));
        }
    }
    cout << min(f[1][n], f[n][1]) << endl;
    return 0;
}

P4766 CERC2014

虽然正解是 O(n^3) 区间 DP, 但是这个题为什么没有写分治的呀?

先把题意抽象一下.