Topcoder SRMs

首先提供官方题解：

2016 之前
 较新的题解

UPD: 民间题解：集训队作业

另外，TopCoder 的插件中，moj 做得不错，repo （最新版浮点数 spj 在 c++11 下不会 CE 了， Emacs 选手可能需要手动调整缩进，当然有 java 编译器的可以自己动手改～）

SRM 555

Easy - CuttingBitString

按照题意 DP 即可（居然数组开小 FST 了一发，看来不要小看 $n \le 50$ ）

Medium - XorBoard

既然是 xor，只需要考虑奇偶性。枚举行列奇数次操作数量，判断 1 的数量是否合法。然后组合数计算一下即可。

Hard - MapGuessing

有许多性质没有发现。。。

首先枚举起始位置，暴力模拟判断是否合法以及哪些格子被覆盖了（这里要注意判断每一步结束后是否合法，并更新答案）。

那么只有这些格子能够修改（修改的意义是目标状态与初始状态不同），方案为 $2 ^ {|S|}$ 。

因为有多个这样的集合，它们之间有交集，所以需要跑容斥。

但是这样的集合最多有字符串长度个， $n \le 36$ 。所以常规容斥不能做。

但是考虑这些集合是由同一套操作产生的，它们的影响范围（指针移动范围）是相同的，假设为 $L$ 。

那么如果两个集合的起始点距离 $> L$ , 显然没有贡献，对答案的贡献为 $2 ^ {|\varnothing|} = 1$ （不考虑容斥正负号）。

所以每次只需要考虑相距不超过 $L$ 的集合。

又因为合法集合个数为（至多） $n - L$

所以每次需要考虑的集合个数为 $\min(L, n - L) \le 18$ , 在可接受范围。

那么就可以跑容斥了。

SRM 556

Easy - XorTravelingSalesman

直接 BFS 一遍就可以了。

Medium - LeftRightDigitsGame2

写了一个 Div2 Hard 的贪心。结果 FST 了。

实际上是数位 DP，而且由于题目的性质，需要同时记录两侧的状态（长度以及大小比较）

Hard - OldBridges

题目具有迷惑性。循环流显然无法解决同时在一座桥上双向行走，将限制扩大两倍跑单向流也无法阻止 $a_1 \rightarrow b_2$ 的流。（怪不得当时无人 A）

题解上的办法很鬼畜：首先跑一边以 $(a_1, b_1)$ 为源， $(a_2, b_2)$ 为汇的网络流，再跑一遍 $(a_1, b_2)$ 为源， $(a_2, b_1)$ 为汇的网络流。两遍均合法才输出 Yes。

正确性：

首先将两个流相加，那么原来不合法的 $a_1 \rightarrow b_2$ 变成了 $a_1 \rightarrow b_2 \rightarrow a_2$ 。其它的不合法情况也同理，画张图会发现所有流变成了 $a_1 \rightarrow a_2$ 的流（的两倍）。

同样的，两个流相减可以得到 $b_1 \rightarrow b_2$ 流。

然后将流量除以 2。因为容量为偶数（或 INF），则流量一定为偶数。

然后可以发现对于一条边，当前流量 $|\frac{f_1 + f_2}{2}| + |\frac{f_1 - f_2}{2}| \le \max(f_1, f_2) \le \text{cap}$ 所以方案合法。

所以就能够判定了。

SRM 557

Easy - FoxAndMountainEasy

根据题意将给定的操作的 $\Delta h$ 求出来。注意 $h_0 + \Delta h <0$ 的情况以及操作次数奇偶性的判定。（后者样例中居然没有！）

Medium - Incubator

需要一些前置知识：

反链：一个元素的集合（是全集的子集），两两之间不能确定大小关系。（用图论的语言来描述就是在有向图上的点集，使得两两之间不存在有向路径）

Dilworth’s Theorem：给定一个集合，以及集合中一些元素的大小关系（可能存在环），则其反链的最大大小等于其最小链精确点覆盖（用链覆盖点恰好一次）。

然后就可以变成二分图匹配经典问题了。

但是有两点注意：这个定理需要先求出传递闭包。其次对于非 DAG，我们也可以直接建出二分图跑匹配。

Hard - XorAndSum

首先需要了解线性基 ( 非常抱歉，没有链接 )。

首先我们先构建出一个线性基。

然后我们只需要最大化线性基元素和。线性基外的就直接取最大值。根据线性基的性质，这是符合题意的。

那么我们在构出线性基之后，首先用较低位基的值去消去较高位基的值二进制下对应位上的 1。那么对于每一个基都得到了其最小值，异或上最大值之后，就得到了其最大值。<!—（这是 Selina 口胡的）—>

SRM 558

（各种细节写挂，各种 FST）

Easy - Stamp

枚举长度之后直接 dp。（注意更换颜色与不更换颜色的转移的区别！）

Medium - Ear

可以枚举大三角形的底边 A，D，那么对于每个小三角形的 P 点对应的合法的底边数量是确定的。

然后可以发现合法的 P, Q, 构成了关于 A，D 的极角的二维偏序。BIT 处理。注意处理共线的情况。

Hard - SurroundingGame

某道校内训练题的原题。最小割。

SRM 559

（感觉 Medium 和 Easy 顺序反了。。。）

Easy - HyperKnight

不会找规律的表示，写一发容斥。

结果容斥写了好久（好像就多了一个组合数 $\binom{n}{k}$ ）。。。（最后写成了直接 DP+ 组合数，其实也就是容斥的原始形式）

Medium - HatRack

题目很长，其实就是给出一棵树，求它有几种编号的映射方案使得其成为一棵完全二叉树 , 且 $x$ 的左右儿子（若存在）为 $2x, 2x + 1$ 。

直接 $O(n^3)$ dp 即可。发现有许多状态本质相同，可以优化到 $O(n ^ 2)$ .

Hard - CircusTents

二分答案不难想到。

在一开始想的时候，发现有些圆的路径可能会绕过某些圆，但是仔细观察会发现，这样的圆一定不会是最小值所在的圆，而且忽略非 0 号圆的弧线不会影响答案。

然后就可以二分出每个圆所对应的合法区间然后求交来判定。

SRM 560

Easy - TomekPhone

经典贪心。

Medium - DrawingPointsDivOne

容易发现通过坐标变换，可以将一次（逆向）操作变成 $(x, y) \rightarrow (x, y), (x + 1, y), (x , y + 1), (x + 1, y + 1)$ 也可以发现 $x$ 次操作后，它形成了一个边长为 $x+1$ 的正方形。

（然后我就直接根据这个来判定，然后样例都过不去。。。）

可以发现我们忘记了判新加的点（不一定是通过上述过程构造的）。如果我们反向考虑这个过程，就会发现，每一个 $x$ 的正方形，对应在 $x - 1$ 步前出现的点（有可能是新加的，也可能是构造的），那么我们可以据此来判定 $k$ 步时是否合法（检查每一个正方形大小是否合法）。

发现正方形大小可以 DP 计算，而且答案具有可二分性，总复杂度 $O(n^2\log n)$

Hard - BoundedOptimization

（可能涉及微积分）

有一个 StraightForward 的做法，枚举每个点是否为 LowerBound，UpperBound 还是中间的某个值。然后暴力对每个中间值求导，高消。直接求 $O(3^n n^3)$ 。发现每一个中间值集合相同的方程列出来相似，可以只做 $2^n$ 次高消 $O(3^n n^2+2^n n^3)$ 。

首先发现在最优解中，取中间值的形成了团（可用反证法），设集合为 $S$

枚举其余点为最大还是最小值。设 $S$ 的和 $\sum_{i \in S} x_i =M$ 。

那么就会发现 $i$ 号点（ $i \in S$ ）对答案贡献为 $x_i \cdot (\sum_{j \notin S, (i, j) \in E} x_j + \frac{1}{2}(M - x_i) )$

设 $A_i = \sum_{j \notin S, (i, j) \in E} x_j + \frac{1}{2}M$ .

则这一部分的答案为 $\sum x_i(A_i - \frac{1}{2} x_i), \sum x_i = M$ ，其极值为 $x_i = A_i + \frac{M - \sum A_i} {|S|}$ 。

证明：考虑每一维的偏导为 $A_i - x_i$ , 容易发现当每一维偏导相等时取极值（反证，考虑向偏导大的那一维移动 $\epsilon$ ），所以可以解出上式。

最后只需要判断取值范围即可。

SRM 561

Easy - ICPCBalloon

$2 ^ n$ 枚举气球大小，后面直接贪心。

Medium - CirclesGame

根据包含关系建树。然后暴力计算每棵子树的 SG。

Hard - Orienteering

考虑已知 $k$ 个点的情况下求答案：首先构造回路，长度为 $2 \times \text{ 生成树大小 }$ ，然后变成路径，最多减去生成树直径。

考虑两部分分开计算期望：

生成树大小：考虑每一条边，它在生成树中出现当且仅当它两边两个子树均有点被选，为 $\binom{n}{k} - \binom{size}{k} - \binom{n-size}{k}$ 种方案（所有方案减去只在一边的方案 , $n$ 表示关键点数， $size$ 表示一侧子树大小）

直径：枚举直径端点 $A, B$ 。考虑 2-BFS 求直径方法，我们规定有多个 dis 最大值，选取编号最大的作为端点，那么我们就会发现一个点 $C$ 能够出现在以 $AB$ 为直径的树上当且仅当下面两者均满足（反之 $C$ 将成为端点）：

$dis_{AC} < dis_{AB}$ 或 $dis_{AC}=dis_{AB}$ 且 $C < B$
$dis_{BC} < dis_{BA}$ 或 $dis_{BC}=dis_{BA}$ 且 $C < A$ .
那么可以统计出合法点数，乘上组合数即可得到方案数。复杂度 $O(n ^ 3)$

在程序实现的时候，看起来组合数会存不下，但因为最后还需要除以 $\binom{n}{k}$ ，所以可以在预处理组合数时除掉，或者直接用 double 存。因为 double 有 16 位精度，所以最后再将两个大数相除，前几位也是准确的，而且期望值显然在 $O(\text{ 棋盘大小 })$ 级别，精度不会爆炸。

一直在做 CF，换换风格。

SRM 562

Easy - PastingPaintingDivOne

直接模拟，计算每个格子的贡献。

Midium - CheckerFreeness

首先判凸四边形等价于判线段相交，可以用四个叉积来判。

那么我们只需要预处理其中两个叉积（判断白点在黑点形成直线的哪一侧）预处理，并压到 bitset 中，之后枚举两白一黑判断是否存在第四个黑点的时候，直接利用位运算判断就可以了。复杂度 $O(\frac{n^4}{w})$ 。

另外，我们可以发现如果有合法解，其中一条边一定在两个凸包中的一个上（稍微画一下图就明白了）。复杂度 $O(n^3)$

Hard - InducedSubgraphs

情况很复杂。

首先每个方案可以一一映射为，一开始在树上有 $k$ 个连通的点的点集（初始点集），进行 $n - k + 1$ 次操作，每次删去一个点，并加入之前没加入过的一个点，使得点集依然连通。称最后一步后形成的点集为终止点集。

$k = 1$

答案为 $n!$ 。

$k \le \frac{n}{2}$

此时初始点集和终止点集没有交，可以发现它的形态应该类似初始点集 $\rightarrow$ 一条链 $\rightarrow$ 终止点集。

此时枚举链的端点，然后两端 DP 统计有多少种合法的删点序列。（显然每次只能删点集中的叶子节点）

$k > \frac{n}{2}$

此时初始点集和终止点集有交，且交集连通。它们的差可能被分成若干个和交集相连的连通块。我们可以统计每个点在交集中的合法方案，最后除以交集大小 $2 \times k - n$ 在乘上交集自身标号方案 $(2 \times k - n)!$ 。

我们确定一个点一定在交集中后，以这个点为根 DP： $f_{i, j, k}$ 表示 $i$ 子树内，只属于初始点集的有 $j$ 个点，只属于终止点集的有 $k$ 个点的方案，背包转移即可。同时需要维护每个子树的合法删点序列数。总复杂度 $O(n^5)$ 。

SRM 563

Easy - FoxAndHandle

逐位确定，确定前面是否合法。

Medium - SpellCards

答案就是这个东西的背包。

因为一定存在一个位置，它后面有大于 $L - 1$ 个不选的物品（反证法）。然后把它转到开头，删掉。然后就做完了。

Hard - CoinsGame

（曾经听过讲课，但是还是不会。。。）

类似于图哈希，每个点首先有个相同的哈希值。然后将它向上下左右四个方向移动的哈希值压在一起作为新哈希值并离散化（取最小表示），迭代至稳定。

此时哈希值相同一定是“共生死”的。把只选相同哈希值集合的减去就是答案。

切题的时候发现了一个大 bug:

(鉴于 TC 有将解题代码封装成类，这个 bug 很重要)

见下面三份代码（struct 和 class 同理）：

struct F {
  void g() {
    static int a[50];
    memset(a, 0, sizeof a);
    for (int i = 0; i < 60; i++) a[i] = 1;
    printf("%d\n", a[49]);
  }
};

struct F {
  void g() {
    int a[50];
    memset(a, 0, sizeof a);
    for (int i = 0; i < 60; i++) a[i] = 1;
    printf("%d\n", a[49]);
  }
};

struct F {
  void g(); 
};
void F::g() {
  static int a[50];
  memset(a, 0, sizeof a);
  for (int i = 0; i < 60; i++) a[i] = 1;
  printf("%d\n", a[49]);
}

在我的电脑（g++ (Ubuntu 7.3.0-27ubuntu1~18.04) 7.3.0）上开 -fsanitize=address 编译后，只有第 2、3 份代码会 RE。。。不知所措。。。

这个的影响（个人写代码上）主要影响 TC 的解题以及矩阵乘法。

不知道是 bug 还是 feature。

（听 zrf 说在一定的下标范围内，-fsanitize 也不会 RE）

UPD: 在 14.04（NOI Linux），16.04，18.04 下均有此问题，另外 clang++ （version： clang version 6.0.0-1ubuntu2）也有此问题。。。

然而在 Mac 的 g++ 上就神奇 RE 了。。。

SRM 564

Easy - KnightCircuit2

小规模暴力，大规模直接输出 $w \times h$ 。

Medium - AlternateColors2

分类讨论。

我先按照 $r, g, b$ 的大小关系，然后再按照 $k$ 在三段中的哪一段分，一共有六类，每一类有若干个不等式，推到爆炸。

但如果先按照三段分类，那么会少几种情况。（把式子合并之后还可以 $O(1)$ 做。）

Hard - DefectiveAddition

比较显然的是，如果某个数限制为 $2^{x} - 1$ 的话，那么 $n$ 中最后 $x$ 位的限制实际是无效的，因为我们可以通过这个数来调整答案。

另外一点是，如果某个数前面某一位开始已经严格小于限制的话，之后的位也可以自由选取。

那么我们可以枚举最先「严格小于限制的数」小于限制的位置 $x$ ，（首先 $x$ 位之前的异或和要和 $n$ 相同），然后 DP 出方案数：记 $f_{i, j, 0/1}$ 为前 $i$ 个数，第 $x$ 位异或和为 $j$ （这一位是没有可以自由选取的数的），是否存在「在第 $x$ 位小于限制的数」的方案数 $\times 2^x$ 的值。（因为一个数要拿来作调整用）此时每种自由选取的位的集合的贡献为 $2^{\text{可以自由选取的位的数量}}$ ，枚举每个数在哪里严格小于限制（或者和原数相等）转移。

最后加上每个数都与限制相等时的贡献。

SRM 565

Easy - MonstersValley

一开始写的时候没有想到可以交换状态和值来 DP（把花费而不是攻击力压成第二位）。。。

然后写了个奇怪的贪心，然后过了 sys test。。。

它长这样：

std::priority_queue <long long> q1;
int ans = 0;
long long cur = 0;
int n = dread.size();
for (int i = 0; i < n; i++) {
  if (cur >= dread[i]) {
    if (price[i] == 1) q1.push(dread[i]);
  } else {
    if (price[i] == 1) {
      ans++;
      if (!q1.empty() && q1.top() > dread[i]) {
        cur += q1.top(); q1.pop();
        q1.push(dread[i]);
      } else {
        cur += dread[i];
      }
    } else {
      if (!q1.empty() && cur + q1.top() >= dread[i]) {
        long long val = q1.top(); q1.pop();
        cur += val;
        ans++;
        q1.push(dread[i] - val);
      } else {
        cur += dread[i];
        ans += 2;
      }
    }
  }
}
return ans;

也就是说：

如果当前的攻击力足够，就跳过；
如果当前的攻击力不够：
- 如果它的代价为 $1$ ，那么直接买入是最优的（因为前面没选的一定比它攻击力低）；
- 如果它的代价为 $2$ $2$ ，那么有两种情况：
  - 用 $1$ 的代价购买前面没有选且攻击力最大的（用优先队列维护）
  - 用 $2$ 的代价直接购买他。
    此时，我们先选第一种（因为它的代价小），并将二者差值加入优先队列，表示第二种情况。这个时候我们会发现后面的操作依然是合法的。（假设原来两个数为 $a, b$ ，优先队列中存在 $b - a$ 。在之后在处理权值为 $c$ 的时候，优先队列中存在 $c - (b - a) = c - b + a$ ，那么在下次选择的时候，相当于花 $3$ 的代价选 $a + c$ ）

~~也许是对的吧。。。。~~（随机数据根本拍不爆）

Medium - TheDivisionGame

可以利用归纳法证明，每个数的 $\text{SG}$ 值就是这个数质因数个数，可以用区间筛得到。

然后只需要求出那些区间异或和为 $0$ , 那么只需要到 $l - 1$ 和 $r$ 的前缀和相同即可。

Hard - UnknownTree

~~就是分类讨论，分成三个点在一条链上或是有分叉，然后确定每个点与他们三个的相对位置，然后计数~~，但是实在写不动。。。

UPD(after a month)：终于写完了，确实很翔。但是如果想清楚了还是可写的。首先定位三个关键点（Y 型已经确定了，一条链的话两两距离也只有 $O(n)$ 种情况，因为只有在关键点的子树中或者链上才能确定距离），然后算出每个点挂在哪个子树下（注意特判不合法），然后分别计算每个子树。需要交换关键点的时候可以用一些 trick 来避免【人类的本质】。

![Failed System Test](/images/TC SRM 741 FST.png)

SRM 566

Easy - PenguinSledding

通过大胆猜想~~+ 小心求证~~，可以发现合法的图只有（非孤立点全部连通的）三元环和菊花，分别计算。注意一条边和没有边的情况会算重。

Medium - PenguinEmperor

发现每 $n$ 步移动是一个循环，将 $n$ 步的转移预处理后矩阵快速幂，最后的余数暴力计算。 $O(n^3\log T)$ ，可能需要松。

发现转移矩阵是循环矩阵，可以变成卷积操作。 $O(n^2 \log T)$ 或 $O(n (\log n + \log T) + n ^ 2)$ 。

最后的余数暴力部分能不能做得更优？

Hard - FencingPenguins

首先预处理出每条直线是否合法（会不会将同色点分成两块），并算出每个点在直线的左边还是右边（压成 long long）。

然后破环成链。则所有的连线必须没有交（环之间形成类似树的结构），每个环可以认为是两部分（类似于一条线段）：内部若干条线段相连，外部一条线段。

（然后设计了若干 DP，发现细节爆炸）

然后考虑区间 DP： $f_{i,j}$ 表示 $[i, j]$ 区间且 $i, j$ 有连边方案； $g_{i, j}$ 表示 $[i, j]$ 的方案数。其中 $f$ 的转移需要利用辅助 DP $h_{i, j, 0/1}$ 记录目前包围的区域是否已经有点，然后枚举最后一条直线转移。

$g$ 的转移类似，分当前这个位置是否为一个环的端点转移，有区间覆盖时枚举覆盖环的左端点。在两部分转移的时候要判定线段是否合法以及不被任何一个环覆盖区域是否有点，可以画图分析。（在代码上需要注意，有个地方可能要判一个四边形是否合法，小心其退化成三角形的情况，还有其它一些边界情况需要处理）

复杂度 $O(n^3)$

（感觉这两场的 Hard 解法较为直观，但是关键是把细节想清楚，而且事实上实现起来也很复杂）

SRM 567

Easy - TheSquareRootDilemma

容易得出 $O(n \sqrt n)$ 做法：将 $\sqrt x$ 表示为 $a \sqrt b$ （ $b$ 不为完全平方数），然后数对合法当且仅当 $b$ 相同。

我们也可以枚举 $b$ ，计算有多少 $a$ 满足条件。（ $\lfloor \sqrt{\frac{n}{b}} \rfloor$ 个）。 $b$ 可以用线性筛筛出。（ $O(n)$ ）

Medium - StringGame

容易发现一些结论：每个字符串重排时会按照每个字母权值从小到大排；并且对原串字典序比较可以变成对每个串字母数量的数组字典序的比较。

所以对于每个串，我们可以直接每次暴力寻找一个接下来能填的字母，然后将字典序已经比询问串大的串删去，不参与接下来的判定。因为需要判定的串只会越来越少，所以之前合法的字母之后依然合法，所以一旦不合法之后无论怎样调整都不会合法。

Hard - Mountains

直接记忆化搜索（将每列的高度压起来）就过了！～

复杂度证明：

可见区间为空集，这一层状态数和上一层相同；
可见区间为全集，状态数只和这一层有关，共 $O(m)$ 个;
其它情况，考虑到需要满足的限制，画图可以发现左端点的可行高度最多为 $2$ ，所以每个上一层的状态只会扩展最多 $2$ 个新状态。

所以总状态数至多为 $O(2^n \times n)$ ，复杂度为 $O(2^n \times m n ^ 2)$ 。

SRM 568

自闭了自闭了。。。

Easy - BallsSeparating

其实还是状压最好写。

Medium - EqualSums

关键在于发现原条件等价于每次给一行加一个数，或给一列加一个数得到的矩阵。

然后就变成了 $2 \times n$ 的向量的关系，值域一定是 $[0, 9]$ 。

暴力枚举，然后就可以根据每个格子上的等式推出相关的格子的值。不同的“连通块”答案独立。

需要 unique 拆分的表示（例如保证行的最小值为 $0$ ）（你信我卡在 unique 上了吗？）

Hard - DisjointSemicircles

（没有想到这个建模，感觉可能是个 trival 的东西。。。）

枚举每个已经确定的半圆是在上还是在下，可以发现每个半圆内同向的点的数量为偶数。

然后就可以前缀和之后变成两个点的奇偶关系，连边直接跑。

$\displaystyle O\left( 2^{\frac{n}{2}} n \right)$ 最慢点 100ms。

SRM 569

成功沦为 SB。

Easy - TheDevice

容易发现每一位上至少要有 011。然后就判挂了。。。

Medium - TheJediTest

又被数据范围迷惑，写了个指数级的东西。( $f_{i,j}$ 表示到第 $i$ 位，有 $j$ 个人没有确定位置，转移的时候考虑前两个)

只要从小到大能放则放即可。

Hard - MegaFactor

简单来说，就是 $f(n,k) = f(n,0) + \sum_{i=1}^k f(n - 1, k)$ ，可以矩阵快速幂。

然后要把 $b$ 不是质数的先拆成质数，对这个质数的每个幂次都做一遍，然后有个除以 $2$ 或者 $3$ 下取整，要再算一遍模 $2$ 或 $3$ 的余数。或者模 $2P$ / $3P$ 。