Sgu练习

Published: by Creative Commons Licence

  • Tags:

题目后面加星号表示参考了别人的做法或题解，题目后面加问号的表示不会做。对于个人认为很好的问题，都会提供翻译。

100 A+B

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/100

题解

不值一提。

101 Domino

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/101

题解

问题实际上是要求找开欧拉迹。

102 Coprimes

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/102

题解

$N$很小，暴力就可以了。

103 Traffic Lights

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/103

题解

看上去挺复杂的题目。首先明确我们要求的是单源最短路径，因此可以选择dijkstra算法来作为主要框架。现在考虑我们到达顶点$v$的时候最短时间为$now$，现在我们打算前往$u$，那么我们必须等到什么时候才能出发呢？会发现$v$的灯循环最多$t_{uP}+t_{uB}$次，而$u$的灯也最多循环$t_{vP}+t_{vB}$次（超过这个时间后一定无解），因此我们可以暴力枚举下一个事件发生的时间，每一次要么$u$要么$v$的灯完成$1/2$个循环，因此暴力最多发生$800$次。

总的时间复杂度为$O(800M+V^2)$，还是很快的。

104 Little shop of flowers

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/104

题解

数据量很小，直接暴力DP即可。

105 Div 3

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/105

题解

一个数除3等于0，当且仅当这个数的十进制所有位的和能整除3。不难发现序列的规律是$1,2,0,1,2,0,\ldots$（这里的数值是模3后的数），因此结果就是$\lfloor \frac{n}{3} \rfloor \cdot 2 + [n = 2 \pmod 3]$。

106 The equation

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/106

题解

首先我们计算出$g=gcd(a,b)$，如果$c$不能整除$g$，则无解。否则我们利用扩展欧几里得定理得到一对$x_0,y_0$，满足：$\frac{a}{g}x_0+\frac{b}{g}y_0=-c$。

找到了后，我们现在确定有多少个整数$t$满足下面公式：

\[\left\{ \begin{array}{llll} \frac{a}{g}(x_0+\frac{b}{g}t)+\frac{b}{g}(y_0-\frac{a}{g}t)=-c\\ x_1\leq x_0+\frac{b}{g}t \leq x_2\\ y_1\leq y_0-\frac{a}{g}t \leq y_2 \end{array} \right.\]

对于类似于$kx+b\leq c$的不等式，可以分解为$x\leq \lfloor \frac{(c-b)}{k} \rfloor$。这样我们就能得到有效的$t$的区间$[l,r]$，最后就可以得出结果了。

107 987654321 problem

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/107

题解

先说一种比较复杂的做法，我们假设987654321是一个未知的9位数$y$。就是发现我们实际上要统计的是有多少长度不超过9位的数字$x$，满足$x^2=y\pmod 10^9$。很显然我们可以暴力枚举，但是时间复杂度是$O(10^{18})$。

但是实际上我们可以将$x$拆分成两部分，$x=a\cdot 10^5+b$，其中$a<10^4,b<10^5$。现在我们可以暴力枚举$b$，总共有$10^5$种可能，现在我们求当$b$确定时，$a$有多少是满足条件的，即

\[(a\cdot 10^5+b)^2\pmod 10^9=m\pmod 10^9\\ \Rightarrow 2\cdot 10^5\cdot ab+b^2=m\pmod 10^9\\ \Rightarrow 2\cdot 10^5b\cdot a+10^9k=m\]

注意到上面这个公式可以通过106题目中的技术进行求解，时间复杂度为$O(\log_210^9)$，因此总的时间复杂度为$O(10^5\cdot \log_210^9)$。

下面说一种简单的做法，打表会发现总共有$8$个长度不超过9的数的平方满足模$10^9$的时候等于$987654321$，且它们的长度都是$9$。所以直接判断一下也可以。

108 Self-numbers 2

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/108

题解

水题，暴力一下就可以了，但是由于只有4M的内存，所以需要开bitset。

109 Magic of David Copperfield II

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/109

题解

如果$n$是奇数，我们可以移动奇数步，之后将外围的所有满足$x+y=0\pmod 2$的坐标$(x,y)$移除，第二次，移动奇数步，将外围所有满足$x+y=1\pmod 2$的坐标$(x,y)$移除。重复上面过程直到只剩下一个顶点。

如果$n$是偶数，我们可以将其多加一行和一列，凑成奇数，到时候结果中忽略多余的元素即可。

110 Dungeon?

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/110

题解

就是简单的模拟一下三维空间移动。但是题目没有给的很清晰，球体是否可能会有交点，如果射线与球擦边算不算反射。精度也不确定。。所以最终还是WA。

111 Very simple problem

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/111

题解

要求求$y=\sqrt{x}$，记$n$为$x$的长度。我们知道可以用二分查找法解决经典的求平方根的问题，但是这里我们会发现二分查找法不能应用，原因是而二分的次数是$O(\frac{n}{2}\log_210)$，而每次乘法的费用为$n\log_2n$（如果使用FFT的话），这样总的时间复杂度为$O(n^2\log_2n\log_210)$，配合一个很大的常数。

我们可以尝试用加法运算来替代乘法运算。我们可以从高往低枚举有效数字，假设现在枚举到第$k$位，并且现在我们已经找到了一个$y$，满足$y^2\leq x$。现在我们需要判断$(y+10^k)^2$与$x$的关系。注意到$(y+10^k)^2=y^2+2\cdot 10^ky+10^{2k}$。我们可以维护了$y^2$，这样只需要要有限几次加法就可以将$y^2$转换为$(y+10^k)^2$。即每次只需要$O(n)$的时间复杂度就可以判断$(y+10^k)^2$是否合法。

由于总共枚举次数的上界为$O(5n)$，因此总的时间复杂度为$O(5n^2)$，但是常数很小（且这是最坏情况才会发生）。

顺带一提，java的BigInteger自带了square方法。

112 $a^b-b^a$

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/112

题解

就是普通的大数计算。

113 Nearly prime numbers

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/113

题解

暴力枚举。

114 Telecasting station

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/114

题解

经典问题。很显然如果对于点$x$，左边的总权小于右边的总权，稍微增加$x$可以得到更小的总权。同理如果左边的总权大于右边的总权，稍微减少$x$就可以得到更小的总权。

因此你可以用三分法，也可以直接遍历一遍维护一个前缀和，找到特殊的点$x$，左边右边的权重都不超过总权的一半。

115 Calendar

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/115

题解

调用一下日期API，呵呵。

116 Index of super-prime

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/116

题解

筛出10000以内的素数，之后DP即可，按照素数的概率为$\frac{1}{\ln n}$，因此应该不会超过100的。

117 Counting

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/117

题解

先将$k$做素因子分解。之后判断每个因子在$m$次幂后是否会大于$k$的该因子的出现次数。时间复杂度为$O(\sqrt{k}+n\log_2n)$。

118 Digital Root

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/118

题解

大数操作

119 Magic pairs

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/119

题解

如果$ax+by=0\pmod n$，那么一定可以推出$kax+kby=0\pmod n$。

但是并不知道怎么证明一定只有这些数。

120 Archipelago

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/120

题解

写个线性变换即可。

121 Bridges painting *

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/121

翻译

给定一个包含$n$个顶点且不含重边和自环的无向图，要求将每条边染色为黑色或白色，如果一个顶点度数超过1，那么要求这个顶点拥有至少一条黑边和白边。找出一种染色方案或报告无解。

题解

一开始以为是要搞一般图最大匹配，后来发现好像这么搞不行。

如果图包含多个连通块，那么我们可以独立处理每个连通块，现在我们认为图只有一个连通块。由于图连通，我们可以通过DFS生成任意一株生成树。如果我们对生成树中的边进行染色能保证所有度数超过1的顶点满足条件，那么其余边我们可以任意染色。我们可以用交替染色的技术。深度为0的顶点与深度为1的顶点的边全部染成白色，而深度为1的顶点与深度为2的顶点的边全部染成黑色，循环往复。

这样做之后，有哪些顶点可能不满足条件呢。生成树的根顶点$r$和所有度数实际上大于1的叶顶点$v$。先考虑叶顶点，由于叶顶点的度数超过1，因此至少还有一条没有出现在生成树中的边$(u,v)$，这时候$u$是$v$的某个祖先顶点，我们可以将$(u,r)$染成叶顶点缺少的颜色。现在只有根顶点$r$可能不满足条件。

我们可以考虑两种情况，如果图中存在某个顶点的度数恰好为$1$，那么我们将它作为根顶点进行DFS，那么不就可以避免上面可能出现的根顶点不满足条件的情况吗。

好的，接下来我们只需要考虑所有顶点的度数都大于1的情况，这意味着图中一定存在环。我们可以利用DFS找到任意一个环。这时候如果环的长度是奇数且所有顶点的度数都恰好为$2$，这时候就出现了一个奇环，奇环是无论如何都无法染色成功的，我们这时候直接返回无解即可。现在还剩下的可能是环是偶环，或者环中至少一个顶点$v$的度数超过$2$。前者我们可以保证环中的顶点都满足条件，后者我们可以保证环中的所有顶点除了$v$都满足条件，且$v$有额外的边。之后我们可以将环缩点，之后以该顶点作为根进行DFS，这时候会发现环缩点得到的根只缺一种颜色，而我们可以直接让深度为1的顶点的连边补充上这种颜色。

上面的就是全部的题解了，总的时间复杂度是$O(n+m)$，其中$n$是顶点数，$m$是边数。

122 The book

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/122

题解

找本组合数学的书，翻到哈密顿圈一节，可以看到上面白纸黑字写着：如果一个大小大于等于$3$的图，对于所有不邻接的顶点对$x,y$，都满足$deg(x)+deg(y)\geq n$，那么就一定存在哈密顿圈。

并且上面还提供了构造性算法。。。时间复杂度是$O(n^2)$。

123 The sum

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/123

题解

题目难度瞬间降低。。。暴力即可。

124 Broken line

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/124

题解

要检测一个顶点是否落在多边形呢，如果多边形是凸包，可以使用叉乘法来判断，否则可以通过计算一条以该顶点发出的射线与多边形边界的交点数目来计算，如果是奇数，则落在多边形内，否则不落在多边形中。可以找本计算几何的书看一下，推荐CF上大佬写的内容学习https://codeforces.com/blog/entry/59129。

125 Shtirlits

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/125

题解

我们将网格看成$n^2$个顶点，相邻的顶点之间可以连接一条边，从顶点$a$向顶点$b$连接一条边表示$a$的取值大于等于$b$的取值。对于两个相邻顶点$u,v$，边可能有三类，第一类从$u$到$v$的单向边，第二类从$v$到$u$的单向边，第三类从$u$到$v$的无向边（由两条不同的单向边组成）。

上面的建模中，顶点数$N$最多有$9$个，边数$M$最多有$12$条。数量级非常小，这是一个好消息，我们可以对每条边枚举种类，总共$3^{M}$种可能的方案（在$M$取到最大时数量级在50万左右）。而每次校验是否合法，我们可以校验进入每个顶点的单向边数目是否符合要求，以及方案中单向边不能组成环（我们将由无向边连接的顶点缩点即可），因此每次校验的时间复杂度为$O(N+M)$。

在找到一组方案后，我们只需要对顶点进行拓扑排序即可。

总的时间复杂度为$O((N+M)3^M)$，由于数据量很小，因此还是很快的。

126 Boxes

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/126

题解

规律题。首先我们可以发现状态由两个数值中的较小值确定，每次较小值都会增大一倍，接下来我们直接用较小值来代表整体状态。最终的状态一定是$0$，我们不断回推发现：

  1. $0$
  2. $\frac{1}{2}n$
  3. $\frac{1}{4}n$
  4. $\frac{1}{8}n,\frac{3}{8}n$
  5. $\frac{1}{16}n,\frac{3}{16}n,\frac{5}{16}n,\frac{7}{16}n$

可以看出除了第$0$层外，第$i$层的状态为$\frac{t}{2^i}n$，其中$t\leq 2^{i-1}$，且$t$是一个奇数。因此我们假设我们现在处于的状态$x$是有效状态，那么可以推出:

\[x=\frac{t}{2^i}n\Rightarrow t=\frac{2^ix}{n}\]

考虑到$t$是奇数，因此$i$可以唯一确定，这时候就能唯一确定$t$，判断一下是否有效即可。如果有效，那么就可以通过$i$步抵达结果。时间复杂度$O(\log_2n)$。

127 Telephone directory

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/127

题解

阅读题，随便写写就好了。

128 Snake *

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/128

题解

读错了两次题目。第一次忽略了每个顶点都必须包含以及没有连续线段，这时候就开始考虑最小环算法以及其Dijkstra的优化版本，最后给出的最优时间复杂度是$O(n^2\log_2n)$，过不去。后来发现必须包含所有顶点，那么问题就变成了旅行商问题，这是NP问题。

最后看了别人题解的时候，才注意到原来还有这么个条件：没有连续线段。

为了保证每个顶点多出现在多边形边界上，每个顶点都会正好作为一条水平和垂直线段的端点。这个性质非常重要，我们可以将处于同一行的多个顶点从左到右全部罗列出来$v_1,\ldots,v_k$，可以发现$v_1$只能与$v_2$匹配，$v3$只能与$v_4$匹配，那么线段的方案就唯一确定了。这样我们所需要做的工作实际上是校验得到的线段满足条件，即所有顶点连通且不存在两条线段中间相交。前者靠并查集可以解决，后者我们可以通过扫描线技术解决，具体就是从下向上遍历所有线段，如果遇到垂直线段$(x,b),(x,t)$的下部，就在$x$处$+1$，遇到上部，就$-1$，遇到水平线段$(l,y),(r,y)$，我们就统计区间$[l,r]$中的值是否为$0$。

实际上算法导论有给出$O(n\log_2n)$时间复杂度判断任意$n$条线段是否有交点的算法，可以自行参考。

129 Inheritance

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/129

题解

生成凸包后，计算线段与凸包上的边的交点，之后做截断即可。但是我并没有通过，可能板子或精度有问题。

130 Circle

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/130

题解

简单DP。

131 Hardwood floor

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/131

题解

稍微复杂点的DP，定义$f(i,j)$表示下面一行状态为$i$，上面一行状态为$j$，且每次放置的时候下面一行都至少会占用一个单元格（这个条件用于去重），问有多少种方案。之后我们得到的转移，利用转移可以计算$dp(i,j)$，表示处理了前$i$行，且第$i+1$行的状态为$j$，有多少种方案，显然$dp(i,j)$可以借助$f(j,t)$转移成$dp(i+1,t)$。统计一下即可。总的时间复杂度为$O((n+6)\cdot 2^{2m})$。

132 Another Chocolate Maniac

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/132

题解

这道题假如要求最多放多少个巧克力上去，那么就是经典的二分图匹配问题。

现在它要求的是最少放多少巧克力。自己推了下DP，用三进制来表示状态（因为存在竖直的巧克力），这样时间复杂度为$O((3^m)^2n)$，如果我们仅考虑有效的状态，那么在$m=7$的时候，有效状态有$1224$种，但是如果我们不允许同时存在两条竖直的巧克力（可以用两个平行巧克力代替），那么总共状态不超过$600$种。

之后利用一系列预处理技术，就可以保证通过了，时间复杂度为$O(3^{2k}+n\cdot 600^2)$。

133 Border

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/133

题解

简单的二维矩形统计问题，用BIT+离散化可以秒。

134 Centroid

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/134

题解

找重心裸题。$O(n)$。

135 Drawing Lines

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/135

题解

$\frac{(n + 1)n}{2} + 1$

136 Erasing Edges

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/136

题解

经典题型，$x$和$y$可以独立处理。现在给定一个$x$序列$m_1,\ldots, m_n$，要求$x_1,\ldots,x_n$。我们可以发现每个$x_i$都可以表示成$x_i=a_ix_1+b_i$的形式，最终我们需要求解$a_1x_1+b_1=x_1$。判断一下是否有解即可。

137 Funny Strings

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/137

题解

不错的问题。我按照我的思维路径讲。

首先首尾操作太麻烦了，我们可以提前旋转一下$S$，使得现在$S_0-1$，而$S_1+1$可以由$S$旋转得到。

现在假设选择的步骤为$t$，如果$g=gcd(t,n)>1$，那么我们发现$0,t,2t,\ldots$实际上等同于序列$0,g,2g,\ldots$（顺序不同）。而这意味着$S_0=S_g=\ldots=S_{0}-1$，这显然是不可能的。因此我们得出$g=1$。这时候旋转的序列应该为$S_0,S_t,S_{2t},\ldots$，且$S_0=S_t=\ldots=S_1+1=S_{t+1}+1\ldots=S_0$，即序列前若干个数等于$x+1$，后面的数全部等于$x$，而前面的数的数目很显然是$k'=k\pmod n$。

了解了上面的信息后，我们现在希望能找到一个数$z$，使得$k'$是最小的正整数，使得$k'z=1\pmod n$。首先很显然$k'$与$n$互质，且如果存在$z_1k'=z_2k'=1$，那么可以推出$n\mid z_1-z_2$，因此在$[0,n)$之中，$z$是唯一的。很显然$z=k'^{-1}\pmod n$，取逆操作可以通过扩展欧几里得算法实现。

时间复杂度为$O(\log_2n+n)$。

138 Games of Chess

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/138

题解

首先我们将比赛场次为1的顶点特殊处理，将其余场次至少为2的顶点，组成一个新的列表，列表中相邻的两个元素均发生一次比赛，且较大坐标的胜利。之后不断扫描列表，将列表中剩余比赛次数最大的家伙与场次为1的特殊顶点进行比赛，并且前者胜利。之后不断将列表中剩余比赛次数最大两个顶点进行比赛，这时候最小坐标的获胜。

这样所有的比赛次数都完成了，且我们按照从前往后的顺序扫描列表，输出当前顶点与之相关的所有比赛。

139 Help Needed! *

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/139

题解

将序列压缩成16长度的一维序列，之后统计序列中的逆序对个数。容易发现交换上下和左右元素都会使得逆序对的奇偶性发生改变，于是乎我们可以将0移动到右下角后，判断一下初始序列与目标序列的逆序对奇偶性是否一致。

当然这只是必要条件，我并没有找到充分性的证明，但是可以过题。

140 Integer Sequences

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/140

题解

记$g=gcd(p,a_1,a_2,\ldots, a_n)$，那么有解的必要条件是$g\mid b$。我们可以用扩展欧几里得定理得到这样的一组系数$b_0,b_1,\ldots,b_n$，满足$b_0p+b_1a_1+\ldots+b_na_n=g$，之后所有系数乘上$\frac{b}{g}$即可得到解。

这些说一下怎么使用扩展欧几里得定理求多个数的最大公约数以及系数，非常简单，比如要求$ax+by+cz=gcd(x,y,z)$，那么我们可以先求出$gcd(x,y)t+cz=gcd(x,y,z)$以及$a'x+b'y=gcd(x,y)$，那么合并后就是$ta'x+tb'y+cz=gcd(x,y,z)$，即$a=ta'$，$b=tb'$。

141 Jumping Joe

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/141

题解

首先利用扩展欧几里得定理求解$ax_1+bx_2=p$。之后我们将$x_1$和$x_2$除去$gcd(x_1,x_2)$后，下面我们认为$x_1$与$x_2$互质。

很显然每次让$a$增加$x_2$，对应的$b$会减少$x_1$。首先我们令$\mid a\mid+\mid b\mid$尽可能小，我们不妨认为$x_1\leq x_2$，记录$a',b'$为修正后的$a,b$，可以发现$b'=b-(a'-a)c1/c2$，那么我们要令$\mid a'\mid+\mid b-(a'-a)c1/c2\mid$尽可能小。画出图形后会发现这是一个下凸函数，函数极值点当$a'=a\pmod x_2$以及$a'=(a\pmod x_2)-x_2$的时候取到。

考虑这两个点的是否满足绝对值小于等于$k$，如果不满足就显然无解。否则之后判断$t=k-\mid a'\mid +\mid b'\mid$是否是偶数，如果不是我们必须进行微调（$a'$变更$x_2$）。是偶数，我们可以抵消掉它带来的影响，做法就是$x_1$的正数系数和负数系数都加上$t/2$。

总的时间复杂度为$O(\log_2n)$。

142 Keyword

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/142

题解

考虑长度为$L$时，我们发现原字符串最多禁止$n-L+1$个字符串，但是可能的字符串达到$2^L$。因此我们可以直接断定结果不会超过$20$。之后我们发现由于每个数只能取0和1，我们可以用二进制位来表示，这样我们从1到20枚举可能的长度，直到找到为止。

总的时间复杂度为$O(n\log_2n)$。

其实这里也可以讨论一下如果数值范围很大的情况下怎么处理，也非常简单，用哈希和哈希表来判断重复即可，时间复杂度不变，但是可能常数会略大。

143 Long Live the Queen

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/143

题解

简单的树上DP。

144 Meeting

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/144

题解

连续概率（这道题在概率书上应该也就一个一般难度的题）。首先简单起见，我们认为抵达的时间分别为$x$和$y$，且范围为$[0,1]$，且允许的绝对值差最大为$d$。（我们可以通过缩放所有因子得到这个形式的问题）

现在的问题被转换成了：在区间$[0,1]$任意取两个点$x,y$，要求满足$|x-y|\leq d$，且$x$与$y$均为均匀分布，即$f_x(t)=f_y(t)=1$，其中$t\in [0,1]$。

直接套入微积分公式可以得到

\[p(\|x-y\|\leq d)\\ =\int_0^1dx\int_{\max(0,x-d)}^{min(1,x+d)}dy\\ =\int_0^1(min(1,x+d)-\max(0,x-d))dx\\ =\int_0^1min(1,x+d)dx-\int_0^1\max(0,x-d)dx\]

求微积分可以用辛普森算法。也可以直接画图发现两者都是很简单的几何图形的面积，直接手推公式，前者对应的面积为$d+\frac{(1+d)(1-d)}{2}$，后者对应的面积为$\frac{(1-d)^2}{2}$，直接$O(1)$计算得出结果。

145 Strange People

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/145

题解

无人AC题。。

题目的解释是求k短路，自然就想到用A*算法跑。

146 The Runner

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/146

题解

要求对浮点数取模，但是会发现整个过程只有$L$是浮点数，且只有带最多四位小数，我们可以将$L$和所有周期的速度都乘上$10^4$，那么现在我们处理的都是整数了。最后结果再除去$10^4$即可。

147 The Runner

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/147

题解

没看懂题目。

148 B-Station

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/148

题解

比较经典的题目。由于费用非负，因此我们一定是希望让底部若干层破裂。我们可以暴力枚举破裂$k$个层，同时利用贪心算法就可以在$O(n^2)$时间复杂度内求解。

但是可以看出第$i$层是否需要人工毁坏，当且仅当$\sum_{j=n-k}^iW_i>L_i$。我们可以为每一层维护一个数值$L_i-\sum_{j=n-k}^iW_i$，当某一层的值变成负数时就变成免费的了。很显然随着$k$增大，每一层的数值是递减的。

现在在我们处理了后面$k$层的数值后，现在开始处理后$k+1$层的情况。这时候需要插入一条新的记录，同时将所有数值全部增加$W_{n-(k+1)}$。

由于数值的递减性，我们可以维护一个优先队列，不断从中检查是否有数值为负数的层级，并将其设置为免费即可。

总的时间复杂度为$O(n\log_2n)$。

149 Computer Network

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/149

题解

首先给定的结构一定是一棵树。

很显然的树上DP，如果我们手动维护一个大小不超过2的最大堆，这样时间复杂度就可以优化到$O(n)$。

这种类型的问题其实还有一个很重要的进阶技巧，就是先搞出dfs序，之后维护一颗线段树，由于dfs的特殊性质，任意一颗子树都正好对应线段树的某段区间。这样当我们从父亲顶点移动到某个孩子顶点时，可以通过两次线段树区间更新更新所有顶点的信息。当然这种方法用在这里大材小用，但是这种方法更容易被泛化且应用更加广泛。

150 Mr. Beetle II

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/150

翻译

对于一个网格图，每个单元的大小为$1\times 1$，给定两个二维点$(x_1,y_1),(x_2,y_2)$（点落在网格边界交点上），要求绘制从$(x_1,y_1)$到$(x_2,y_2)$的一条直线，并找到第$n$个相交的网格。

题解

暴力枚举，注意控制精度。

151 Construct a triangle

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/151

题解

我们可以认为$A$的坐标为$(0,0)$，$B$的坐标为$(x_B,y_B)$，$C$的坐标为$(x_C,y_C)$。可以推出$M$的坐标为$(\frac{x_B+x_C}{2},\frac{y_B+y_C}{2})$。代入公式得到：

\[(\frac{x_B+x_C}{2})^2+(\frac{y_B+y_C}{2})^2=m^2\\ \Rightarrow \frac{1}{4}(x_B^2+y_B^2+x_C^2+y_C^2)+\frac{1}{2}(x_Bx_C+y_By_C)=m^2\\ \Rightarrow x_Bx_C+y_By_C=2m^2-\frac{1}{2}(a^2+b^2)\]

这里我们可以令$(x_B,y_B)=(a,0)$，继续代入公式化简得到：

\[x_C=(2m^2-\frac{1}{2}(a^2+b^2))/a\\ y_C=\sqrt{b^2-x_C^2}\]

152 Making round

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/152

题解

每个候选人的比例都为$x$或$x(+1)$的形式，可以先都向下取整，之后可以如果比例未达到100%，就贪心找可以向上取整的数即可。

153 Playing with matches

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/153

题解

经典题目。一般会想到用SG函数来求，但是$N$非常大。一般的博弈问题都可以用DP来求，即定义$dp(i)$表示还剩下$i$个火柴，先手是否必胜，转移非常好推。

但是由于$N$很大，不能直接求DP。实际上大家了解矩阵快速幂技术，就会发现经常使用矩阵快速幂来优化类似类型的DP，但是这里不能用矩阵快速幂，原因是矩阵快速幂适用于线性递推关系，而这里出现的是逻辑关系。

虽然不能用矩阵快速幂，但是还有一种更加泛化的技术，我称之为函数快速幂（事实上每个矩阵其实也都是一个线性函数而已）。我们发现前面的最多9个数就可以唯一确定后面一个数，我们可以定义一个特殊的函数$f:Z_2^9\rightarrow Z_2^9$，其从一个长度为$9$的布尔向量转移为另外一个向量。且由于输入只有$2^9$种可能性，因此我们可以用一个整数数组来表示这样的函数。很容易发现函数的复合运算也是满足快速幂所需要的结合性的，因此我们可以利用快速幂技术快速求出$f^n$。我们只需要暴力求出前$dp(i)$，这里$i<9$，组成一个状态$s$，之后算出$f^{n-9+1}(s)$即可直接得出结果。

每个样例的时间复杂度为$O(9+2^9\log_2n)$，还是非常快的。

154 Factorial

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/154

题解

要统计$n!$尾部有多少个$0$，等价于统计$1,\ldots,n$中因子$5$的次数之和。所有给定$n$，我们可以$O(\log_5n)$得出$n!$后面的$0$的数目。

同时发现$n!$尾部的$0$的数目随着$n$的增加递增，因此可以用二分。总的时间复杂度为$O((\log_2n)^2)$。

155 Cartesian Tree

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/155

题解

笛卡尔树的模板题，首先所有的数值按照kx排列，之后用个队列就可以线性构建。

156 Strange Graph

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/156

题解

首先可以发现图是由若干个团，以及不同团之间的若干条路径所组成（路径上包含若干个度数为2的顶点）。由于每条团之间的路径中的顶点需要覆盖，因此我们必须保证团之间的路径被游历正好一次。如果我们将团看成一个顶点的话，会发现这时候得到的哈密顿回路实际上就是一条欧拉回路。

哈密顿回路我们没法求，但是欧拉回路是so easy。现在欧拉回路存在是存在哈密顿回路的必要条件，那能保证充分性吗。实际上如果我们找到了一个欧拉回路，这时候可能一些团中的顶点并没有出现在路径中，但是由于每个团至少进入一次以及出去一次（除非只有一个团），而进入团的顶点$v$与离开团的顶点$u$必定不同（团中的每个顶点最多只能与团外顶点建立一条边），因此我们在$u,v$之间将所有没有遍历到的团中顶点加入就好了 。

总的时间复杂度为$O(n+m)$。

157 Patience

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/157

题解

题目太长，先放着吧。

158 Commuter Train

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/158

题解

首先我们可以证明门0的偏移带的小数要么是$.0$，要么是$.5$。假如门的偏移的小数位为$.k$，其中$k$不是5。如果一个顾客的最靠近的左右两边的门距离相同，我们称他是平衡的，否则就是不平衡的，不平衡的情况下如果左边较近，则称为左倾，否则为右倾。在偏移为$.k$的时候会发现所有顾客都处于不平衡状态，而由于这时候最优，因此可以保证左倾的顾客数目和右倾的客人数目相同（否则假设左倾较多，则将车子稍微向右移会得到更大的结果）。这导致我们将车子向左或向右移动直到$.5$或$.0$处，最短距离的总和都是不变的。因此我们仅需考虑$.0$和$.5$就能找到最优解了。

$.5$太麻烦了，会带来精度问题，我们可以直接将所有坐标都乘上2，最后输出的时候再恢复即可。现在我们仅需考虑整数位置。

会发现$2L$和$N,M$都很小，我们可以直接暴力枚举每一个可能的偏移，这样总的时间复杂度为$O(L(N+M))$。

159 Self-Replicating Numbers

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/159

题解

不会，貌似是暴力。

160 Magic Multiplying Machine

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/160

题解

简单的DP。

161 Intuitionistic Logic

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/161

题解

太长的题，定义了一堆乱七八糟的东西，公式还是乱的，不做。

162 Pyramids

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/162

题解

说实话，我一开始也不知道怎么做，google了一下正四面体，查了下wiki，查到了一个叫做海伦公式的东西，于是乎就解决了。

163 Wise King

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/163

题解

题目很长，但是却异常简单。

164 Airlines *

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/164

翻译

给定一个包含$n$个顶点的无向完全图，每条边的颜色为$1$到$m$，要求从$1$到$m$中选择最多$\lceil\frac{m}{2}\rceil$种颜色，使得删除其他颜色的边后，图中任意两个顶点的最短距离不超过$3$。

题解

对于一个无向完全图，我们将所有边分成两类，$A$、$B$。那么必定存在一类边，使得这些边的的加入，可以保证任意两个顶点的最短距离不超过3。

下面提供一个证明，如果$A$满足条件，我们取$A$即可。现在仅考虑$A$不满足条件的情况，我们分两种情况讨论。

  • 在加入$A$后，如果两个顶点$x,y$不连通，那么我们发现$x$所在连通块中的所有顶点在$B$中，都与$y$直连，而$x$所在连通块外所有顶点在$B$中都与$y$直连，而$x$与$y$直连，因此我们可以发现任意两个顶点在$B$中距离都不超过$3$。
  • 在加入$A$后，如果两个顶点$x,y$距离超过$3$，现在$A$中与$x$直连的所有顶点在$B$中都与$y$直连，而在$A$中与$y$直连的所有顶点在$B$中都与$x$直连，而在$A$中既不与$x$直连，又不与$y$直连的顶点则在$B$中与$x$直连，并且不存在即与$x$直连又与$y$直连的顶点（否则$x,y$的距离就会不超过$2$）。因此我们发现图上的所有顶点距离都不超过$3$。

于是我们可以将图中的$m$个分类，均分成两部分。之后取一个合法的即可。

165 Basketball

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/165

翻译

给定一个序列$a_1,\ldots,a_n$，其中$|a_i|\leq m$，且$\sum_{i=1}^na_i=0$。要求重新排列序列中的元素，得到一个新的序列$b_1,\ldots,b_n$，满足对于任意一个区间$[l,r]$，都有$|\sum_{i=l}^rb_i|<2m$。

题解

不错的题目，下面按照我的思维轨迹给出做法。

首先任意区间太麻烦了，我们希望最大区间和绝对值只可能是$b$序列的前缀或后缀，这样会省力不少。且总和最大仅可能是前缀，总和最小仅可能是后缀。下面考虑如何转换问题。

先考虑我们一般怎么求最大区间和，传统的方式就是动态规划。那么现在我们假设$\sum_{i=l}^rb_i$最大，其中$l>1$，如何让这个假设不成立呢？只需要存在一个值$l'$，满足$\sum_{i=l'}^{l-1}b_i>0$即可。但是这样还是太麻烦了，我们直接要求$\sum_{i=1}^{k}b_i\geq 0$，其中$k=1,\ldots,n$。

为了满足上面提到的条件，我们可以使用一个贪心算法，如果已经加入队列的总和大于等于$m$，那么就加入一个负数，否则就继续加入正数。而由于所有数之和为$0$，因此这个算法最后一定能给出一个序列。

上面我们处理了最大绝对值为正数的情况，那为负数的情况怎么办。你会发现由于所有前缀和都是正数，而每个后缀与某个前缀会构成一个完整的序列，因此每个后缀都是负数，这也意味着最小和仅可能是$b$序列的某个后缀。而同时由于每个前缀和都属于$[0,2m)$，因此每个后缀和都属于$(-2m,0]$。至此，算法的正确性得到证明。

总的时间复杂度为$O(n)$。

166 Editor

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/166

题解

没读懂。

167 I-country

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/167

翻译

给定一个$n\times m$的网格，每个网格都写着一个整数。现在希望正好选择$k$个网格，这些网格连通，且从选中的网格中的任意一对起点终点，仅需要沿着上下左右中的两个方向，就可以通过选中的网格从起点移动到终点。（即选中的网格是凸的）

题解

以前题目的英文描述也真是绝了。题目里面并没有描述领地是否需要连通，而且方向的描述也莫名其妙的。

很显然的DP，用记忆化搜索个人觉得会更加好些一点。DP公式的样子大概长这样$f(i,l,r,dl,dr,t)$，其中$i$表示哪一行，$l,r$表示第$i$行包含的范围，$dl,dr$分别表示左右端点属性（0，1），$t$表示占据了多少网格。

要计算一个状态可以直接暴力，每次计算的时间复杂度为$m^2$。总的时间复杂度为$O(4n^2m^5)$，但是常数是小于$1$的。

还有最后要输出路径也是挺烦的，如果要用回溯，要写两份代码太麻烦了，直接开一些字节数组存上一个状态的信息即可。

168 Matrix

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/168

题解

简单的记忆化搜索，定义$g(i,j)$表示以第$i$行第$j$列到第$i$行第$m$列的所有单元最小值。那么如果$i=n$，则有$B(i,j)=\min(B(i,j+1),g(i,j))$，否则有$B(i,j)=\min(B(i+1,j),g(i,j))$。

169 Numbers

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/169

题解

好数不怎么好搞，但是完美数还是有破绽的。我们记前$k-1$位的数值为$x$，最后一位的数值为$y$，那么一个数是完美数，当且仅当：

\[\left\{ \begin{array}{lll} P(x)\cdot y&\mid& 10x+y\\ P(x)\cdot (y+1) &\mid &10x+(y+1) \end{array} \right.\]

考虑到$P(x)$是$10x+y$和$10x+(y+1)$的公约数，且$gcd(10x+y,10x+(y+1))=1$，因此我们而已得出$P(x)=1$，即前$k-1$位的数字都是$1$。

剩下的我们只要枚举最后一位即可。由于$n$非常小，我们可以直接暴力计算，时间复杂度为$O(10k)$。但是这里可以使用矩阵快速幂的技术，这样可以将时间复杂度优化到$O(10\log_2 k)$。

170 Particles

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/170

翻译

给定两个01序列，每次可以交换第一个序列中的两个相邻的不同数，问至少需要多少次交换操作，才能将第一个序列转换成第二个序列。

题解

经典问题，有兴趣可以看一下我另外一篇博客《树上算法》中的相邻元素最少交换次数这一节。

做法时间复杂度是$O(n)$。

实际上这个问题还可以加强成树上版本，每次可以交互相邻的两个顶点上的数值，最少需要操作次数。这个问题我也在《树上算法》中的相邻元素最少交换次数这一节中给出了线性时间复杂度的做法。

171 Sarov zones

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/171

翻译

有$k$个地区，$n$个学生，第$i$个地区可以为$c_i$个学生提供水平为$d_i$的测试（$\sum_{i=1}^kc_i=n$），第$i$个学生能通过难度最大为$l_i$的测试，且这个学生的权重为$w_i$。现在要求将每个学生分配给正好一个地区，且要求通过测试的学生的总权重最大。

题解

经典问题，是一个最大权前缀匹配问题（如果将地区按照测试难度排序，每个学生能匹配一个连续的地区），这个问题我在我的博客《一些贪心问题》中的前缀匹配问题一节中已经阐述得非常详细了，有兴趣可以去读一下。

总的时间复杂度为$O(n\log_2n)$。

172 Sarov zones

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/172

翻译

一幅$n$个顶点的图，$m$条边，要求对图进行二分染色。

题解

二分染色可以直接用DFS即可，也可以用并查集。

173 Coins

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/173

翻译

给定某个长度为$k-1$的未知01序列$A$，现在我们定义一个操作$X$，$X$作用在一个长度为$k$的序列$S$上，将序列循环左移一个单位（比如1001左移后变成0011）得到序列$S'$，之后对于每一位$1\leq i <k$，若$S_i'A_i=1$，那么就反转一次第$S_k'$，最后得到新的序列$S''$，换言之$S''=X(S)$。（比如$A=101$，而$S=1001$，先左移得到$S'=0011$，之后发现$S_3'A_3=1$，因此反转一次$S_4'$，最终的结果为$S''=0010$）

为了能找出$A$，提供了$L$个样例，第$i$个样例为$x_i,y_i$，其中$x_i,y_i$均为长度为$k$的01序列，且$y_i=X(x_i)$。且保证这$L$个样例能唯一确定$A$。

同时你还有一个长度为$n$的未知01序列$U$，你对它做了$m$次操作，第$i$次操作内容为选择一个长度为$k$的子序列，并应用操作$X$共$d_i$次。在经过了$m$次操作后，你得到了最终的01序列$V$，$V$已知。现在求解$U$。

题解

题目还是不错的，就是题目的英文描述有点看不懂，而且没有解释样例。

这个问题可以拆分成两个问题：

  1. 求解$A$。
  2. 还原$U$得到$V$。

先看第一个问题，我们发现我们实际上在求某个向量$A$，而对于任意一个样例$a,b$，满足$X(a)=b$，我们可以推出一个线性等式$\sum_{i=1}^{k-1}a_{i+1}A_i=a_1+b_k\pmod 2$。总共$L$个样例，因此我们可以得出$L$个线性等式，组合这些等式我们最后会得到一个多元一次线性方程组$MA=P$。这个可以利用高斯消元法求解$A$。

有了$A$，现在考虑怎么还原$U$。注意到循环左移以及按照前$k-1$位修改第$k$位这两个操作都是线性的，且都是可逆的。因此我们建立两个矩阵$T_1,T_2$分别表示前者和后者。那么对于每一个操作，我们按照逆序恢复原来的序列即可，当然由于一个操作可能应用很多次$X$操作，因此我们可以用矩阵快速幂来保证时间复杂度。

总的时间复杂度为$O(k^3+mn^3\sum_{i=1}^m\log_2d_i)$。

174 Walls

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/174

翻译

在二维平面上给定多条线段，线段只在端点处相交。问至少加入第几条线段后，所有加入的线段才能围住一块区域。

题解

如果加入的第$i$条线段$(p_1,p_2)$正好围住一块区域，那么在此之前$p_1$和$p_2$一定通过线段连通了。因此问题实际上是要判断连通性，先对所有端点离散化，之后用并查集处理一下连通性即可。

175 Encoding

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/175

题解

简单题，递归求解即可。时间复杂度为$O(\log_2n)$。

176 Flow construction

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/176

题解

题目比较明显就是有源汇有上下界最小流。这个可以参考我的博客《最大流算法》一节中的内容。

但是这道题还有一个难点，就是汇点可能有出边，同样的源点也可以有入边。这就会导致一个bug，最终算出的结果为负数，比如下面这组数据：

3 3
1 2 1 0
2 3 1 0
3 1 1 1

这个问题触发的原因是实际上这是一个环形流，但是由于我们从汇点向源点跑最大流的时候破坏了环形流。一个简单的修复方式是我们重新从源点向汇点跑$-f$的流量（一定能跑完，因为从发汇点向源点至少跑了这些流量），这样最大流就变成了$0$，就得到了一个合法的网络。

177 Square

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/177

翻译

给定一个01矩阵，一开始所有单元值全为0。现在有$m$个请求，每个请求选择一个子矩阵，将矩阵中的元素全部清除为0，或者全部清除为1。最后要求回答所有单元格值的和。

题解

四方树或者KD树均可以做到$n\times n$二维数组，$O(n)$时间复杂度的子矩阵修改和查询，因此总的时间复杂度为$O(nm)$。

178 Golden chain

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/178

题解

这道题，可以看出如果我们用$x$次就可以满足条件，那么$x+1$一定也可以。因此我们可以发现这是一个递增函数（false为0，true为1），于是可以用二分。现在我们考虑怎么校验$x$次是否满足条件，这个可以直接上贪心算法即可。

总的时间复杂度为$O(\log_2n\log_2\log_2n)$。

179 Brackets light

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/179

题解

水题，贪心就可以了。首先要得到的序列大于初始序列，就必须右移某个左括号，当然我们要尽可能保证公共前缀尽可能大。我么可以从后往前找，如果遇到$()$，就跳过，否则如果遇到$())$，那么就可以交换这个左括号和其右边贴着的右括号。同时将所有后面的所有左括号都提到这个左括号的后面即可。

如果初始序列为$()()\ldots ()$，那么就无法继续缩小的同时保证括号的正确性，这时候无解。

180 Inversions

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/180

题解

简单的二维逆序对统计，用BIT+离散化即可。

181 X-Sequence

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/181

题解

又是水题。由于$m$很小，那么我们会发现序列$a_i$的周期不超过$m$，我们可以暴力算出周期，之后利用周期快速计算即可。

需要注意当$k=0$的时候直接返回$A_0$就可以了，不要取模。

182 X-Sequence?

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/182

题解

excuse me？

183 Painting the balls

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/183

题解

一开始理解错了题目，以为是要放置若干个1，其余位置放0，使得每个1之间的距离小于$m$，且总权重最小。但是这样就有了一个bug，如果一个1左边有$m-1$个0，右边有$m-1$个0，那么在这$2m-1$个数（最左边的0到最右边的0）中只有一个数是1。

做法非常简单，DP就可以了，记录$dp(i,j)$表示第$i$个位置放1，且前面恰好有$j$个0。时间复杂度为$O(nm)$。

184 Patties

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/184

题解

水题。

185 Two shortest

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/185

翻译

给定一副$n$个顶点$m$条边的无向图，每条边都有一个长度。现在希望找到两条从顶点$1$到顶点$n$的最短路，且两条最短路没有公共边。

题解

独占路问题，可以参考我的另外一篇博客《最大流算法》中独占路问题一节。

时间复杂度为$O(nm)$。

186 The Chain?

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/186

题解

感觉自己学了假的英语？？？

187 Twist and whirl - want to cheat

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/187

题解

平衡树+惰性标记，$O(n+m\log_2n)$。分块应该也能过。

188 Factory guard

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/188

题解

由于$n$非常小，考虑每个顺时针和逆时针运动的士兵的贡献即可，时间复杂度为$O(n^2)$。

189 Perl-like Substr?

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/189

题解

excuse me again?

190 Dominoes

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/190

翻译

在一个$n\times n$的棋盘上面，有一些格子已经破损。现在要求你放置一些$1\times 2$或$2\times 1$的多米诺骨牌上去，要求覆盖所有完好的格子。输出一个放置方案。

题解

经典的题目。

先来考虑一下再所有棋子都是完好的情况下，该怎么放置，非常简单，如果$n$是奇数，就无解，偶数的情况下，我们只用一种多米诺骨牌即可完美放置。

下面我们来考虑这个问题，我们将每个网格看成一个顶点，而将相邻关系看成一条边。那么我们现在手上有一个无向图，仔细观察会发现下标和（$(x,y)$的下标和为$x+y$）为奇数的顶点只和偶数的顶点有连边，因此这还是一个二分图。而我们实际上要求的是最大匹配。

这个可以用匈牙利算法，时间复杂度为$O(nm)$。

191 Exhibition?

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/191

题解

怪题，跳过。

192 RGB

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/192

翻译

给定$n$条二维线段，每条线段都有颜色，且任意两条线段最多有一个交点。现在我们将线段的颜色投影到$X$轴上，对于某个坐标$x$，$(x,0)$的颜色为上方或下方最靠近的顶点的颜色。

现在要求输出每种颜色在$X$轴上的长度之和。

题解

首先$X$轴上下方太麻烦了，如果一条线段和$X$轴有交点，那么我们将线段做镜像处理（将线段拆成两条，$X$轴下方的线段通过镜像转移到$X$轴上方），很显然这样不会影响最终结果，但是会使得线段数翻倍。这样处理后所有线段都处于$X$轴上方。

之后我们将所有线段的端点和交点的横坐标值全部作为事件预处理处理并进行排序，之后按序处理事件（从左往右扫描）。我们取之前的事件$l$与现在的事件$r$的中点$m$，很显然在$(l,r)$上的颜色由最靠近的唯一一条线段决定，且这个线段在$m$处拥有最小的纵坐标值，我们利用这个性质就可以直接取到最靠近的线段，并计算贡献。处理事件后顺便将左端点小于等于事件的线段加入到列表中，将右端点小于等于事件的线段从列表中删除。

线段数最多为$O(n)$，事件最多有$O(n^2)$，总的时间复杂度为$O(n^3)$。

193 Chinese Girls' Amusement

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/193

题解

分三种情况讨论。

如果$n=2m+1$，那么我们可以取最大值$m$，因为$gcd(m,n)=1$。

如果$n=2m$，且$m-1$是奇数，那么$gcd(n,m-1)=gcd(m-1,2)=1$。

如果$n=2m$，且$m-1$是偶数，那么$gcd(n,m-2)=gcd(m-2,4)=1$。

194 Reactor Cooling

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/194

题解

无源汇有上下界可行流问题，可以参考我的另外一篇博客《最大流算法》中的无源汇有上下界可行流一节。

195 New Year Bonus Grant

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/195

题解

题目实际上要你求的是树上最大匹配。求最大匹配的算法有Edmond Blossom算法，但是注意到由于树是二分图，因此可以用匈牙利算法。但是图有点大，我们可以用动态规划来替代匈牙利算法，但是动态规划输出最终方案比较麻烦。因此我们可以使用贪心算法。

说一下贪心算法的流程，我们从父亲向孩子连有向边，之后求出树的拓扑序，我们按照拓扑序进行贪心处理。如果父亲和自己都没有被匹配，那么就建立匹配，否则跳过。

下面我们证明贪心算法的正确性。考虑一个叶子顶点，如果在最优解中，父亲和另外一个顶点匹配，那么我们在最优解中解除父亲与外人的匹配，而将该叶子节点与父亲进行匹配，发现得到的还是最大匹配。因此我们可以直接将叶子顶点与父亲建立匹配关系，这不会影响我们最终找到最优解。之后我们可以从树中删除该顶点和其父亲，因为二者的匹配关系已经确定，任何其它顶点都不会与它二人匹配，剩下的我们只需要在剩下的森林中找最大匹配，我们依旧可以继续用贪心算法求解。

总的时间复杂度为$O(n)$。

196 Matrix Multiplication

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/196

题解

记录$B=A^TA$，推一下公式：

\[B_{ij}=\sum_{k=1}^nA^T_{ik}A_{kj}\\ =\sum_{k=1}^nA_{ki}A_{kj}\]

而我们要求的是

\[\sum_{i=1}^m\sum_{j=1}^mB_{ij}=\sum_{i=1}^m\sum_{j=1}^m\sum_{k=1}^nA_{ki}A_{kj}\\ =\sum_{k=1}^n\sum_{i=1}^mA_{ki}\sum_{j=1}^mA_{kj}\\ =\sum_{k=1}^n(\sum_{i=1}^mA_{ki})(\sum_{j=1}^mA_{kj})\\ =\sum_{k=1}^n(\sum_{i=1}^mA_{ki})^2\]

其中$\sum_{i=1}^mA_{ki}$实际上是顶点$k$的度数，因此答案是$\sum_{k=1}^ndeg(k)^2$。

197 Nice Patterns Strike Back

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/197

题解

容易想到动态规划求法，仔细观察发现DP的转移是线性的，因此可以用矩阵快速幂进行优化，这里还需要用到大数运算。总的时间复杂度为$O(2^{15}\log_2n)$。

198 Get Out! *

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/198

翻译

给定$n$个圆形小岛，小岛可能会相互覆盖。以及一艘圆形船，允许船与小岛有最多一个交点（即相切，但不允许相交），问船是否能开到无穷远。

题解

读错了题，以为船长在某个小岛上，船来接他。后来发现船长就在船上，汗。

我们先将船压缩成一个点，对应的将所有小岛的半径增加船的半径大小。现在问船这个点是否与外界连通。如果不连通，那么必定存在一些连通的小岛，构成一个环，包含了这个船。于是我们现在要做的就是找到这些环。

我们只要将小岛作为顶点，而连通性可以用顶点之间的边来表示，于是我们得到了一个无向图。小岛连成的环对应无向图的某个环。但是环的数量可能很多（最多可以达到$O(2^n)$个），然而你会发现一个非常有趣的事情，就是能包含船这个点的环确实存在，那么对于该无向图的任意生成树，我们只需向生成树上增加某条边即可得到一个包含这个船的环。如果不理解，可以自己画一下图。于是乎我们只需要预处理任意一株生成树，之后不断尝试所有后备边即可，环的数目被减少到了$O(m)$个，$m$是边数且$m=O(n^2)$。

下面我们有了环如果判断船是否落在这个环内部呢。有现存的判断任意多边形是否包含某个点的算法，具体做法就是从这个点发射一条射线到无穷远，如果与偶数条边相交，那么就是在环外，否则在环内。这个算法的时间复杂度为$O(n)$。

因此总的时间复杂度为$O(n^3)$。

199 Beautiful People

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/199

题解

容易发现这道题实际要求求的是最长递增子序列，因此我们可以用一个平衡树解决这个问题。时间复杂度为$O(n\log_2n)$。

200 Cracking RSA

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/200

翻译

给定$m$个数，其中每个数的因子均为前$t$个素数。现在问这$m$个数有多少非空子集，满足子集中所有值的乘积是一个平方数（即使另外一个整数的平方）。

题解

好题。首先在数论的角度，我们可以利用算数基本定理，将每个数分解为一个长度为$t$的向量，其中向量的第$i$个维度存储这个数分解后$p_i$因子的指数，这里$p_i$是指第$i$个素数。

于是我们现在手头有$m$个长度为$t$的向量，我们希望找到这个向量的子集数，使得子集中的所有向量和在每个维度都是偶数（这些数乘积是平方数当且仅当每个维度的和都是偶数）。由于我们只关心每个维度的奇偶性，因此我们可以假定向量落在空间$\mathbb{Z}_2^{t}$上。

每个向量都有出现和不出现两个选择，现在我们得到了一个方程组：$\sum_{i=1}^tw_iV_i=0$，其中$V_i$为第$i$个数生成的向量，现在我们希望求$w$有多少种可能。我们可以用高斯消元求解出这个方程组的自由变量数目$k$，那么每个自由变量都可以取到$0,1$，因此总共的子集数应该为$2^k$，剔除空集，结果为$2^k-1$。这里注意$2^{100}$会爆long类型，需要用到高精度。

201 Cracking RSA

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/201

题解

给定一个DFA，要求计算有多少字符串被这个DFA接受。这个是简单的DP就够了，但是这里还额外有一个非吸收边的概念，这里我们可以把连续的非吸收边合并掉，如果非吸收边构成环，我们就直接删掉这条边即可。注意这里需要用到高精度。

202 The Towers of Hanoi Revisited

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/202

题解

WIKI上提到了有多柱汉诺塔的某个算法，但是这个算法对于柱子数超过4的情况下，没有证明最优。

203 Hyperhuffman

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/203

题解

题目中已经把做法都说明白了，也没有什么可说的了。

204 Little Jumper?

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/204

题解

看别人都是三分，不太懂怎么做。

205 Quantization Problem?

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/205

题解

太长不看。

206 Roads *

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/206

翻译

给定一副$n$个顶点$m$条边的无向连通图，第$i$条边的权重为$w_i$。其中前$n-1$条边恰好构成一株生成树。你可以执行任意次操作，每次操作都可以将某条边的权重$\pm 1$，现在要求利用操作最少次数，让前$n-1$条边组成的生成树为最小生成树。

题解

由于最小生成树同时也是最小瓶颈路的性质，我们只需要保证所有前$n-1$条边组成的生成树，加入后$m-n+1$条边中的任意一条后构成的环上，权重最大的边是加入的那条边。

考虑到我们要让前$n-1$条边的权重尽可能小，其余边的权重尽可能大，那么我们定义$c_i$表示在第$i$条边上执行的操作次数，那么最终第$i$条的权重应该为:

\[\left\{ \begin{array}{lcrr} w'_i&=&w_i-c_i&,i\leq n - 1\\ w'_i&=&w_i+c_i&,i\geq n \end{array} \right.\]

假设环上的边为$e_1,\ldots,e_k$，新加入的边为$e_j$。那么实际上就给出了$k$个约束条件，其中第$i$个约束条件为$w'{e_i}\leq w'{e_j}$，我们对其化简可以得出$c_{e_j}+c_{e_i}\geq w_{e_i}+w_{e_j}$。对所有后$m-n+1$条边计算它的约束方程组。

现在的问题就是我们有若干约束方程组，而要求我们最小化操作次数。这是标准的线性规划，但是问题在于线性规划的矩阵过大，我们无法高效求解。

但是发现每个约束条件只有两个未知数，这个和差分约束系统很像，但是由于求的是整体最小，因此不能用差分约束系统求解。

分界线，上面我的思路到此为止，之后我参考了其他人的题解，发现原来用到了KM算法，但是我从没学过KM（都是用最小费用流跑的），赶紧去学了一下，果然没学会，最后直接用别人写好的KM了。

但是实际上观察到每个约束条件的形式都是$c_i+c_j\geq w_i-w_j$，其中$i\leq n-1,j\geq n$。因此可以发现这是KM算法的顶标公式，我们可以用KM来解决这个问题。具体的做法可以参考我的另外一篇博客《匹配算法》中的Kuhn-Munkres算法一节。

时间复杂度为$O(m^3)$。实际上还是很快的。

207 Robbers

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/207

翻译

$n$个强盗分$m$个金币，第$i$个强盗应该分到$x_i$个金币，如果它分到$k_i$个金币，那么它的不满意度为$\mid k_i-x_i\mid$。现在我们希望通过分配金币，将所有人的不满意度和降到最低，给出一种分配方案。

题解

挺不错的题目，由于绝对值函数是一个下凸函数，因此我们可以用贪心算法解决这个问题。有兴趣的人可以阅读我的另外一篇博客《约束条件下的最优化问题》中的单调函数求和问题小节中的第二个问题。

总的时间复杂度为$O(m\log_2n)$，但是由于绝对值函数的特殊性，实际上这里我们可以优化到$O(n\log_2n)$。因为假如我们现在贪心情况下需要为第$i$个强盗分金币，且第$i$个强盗已经得到了$t$个金币，那么如果$t<x_i$，我们可以直接将其补全到$x_i$，因为下一次贪心还是他来拿。同理如果$t>x_i$，那么他会拿走剩下所有的金币。因此每个强盗都最多会被处理三次。

208 Toral Tickets?

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/208

题解

又到了考察英语阅读理解的时候了。

209 Areas?

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/209

题解

题目看懂了，但是不会做。

210 Beloved Sons

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/210

题解

裸的最大权二分图匹配。时间复杂度为$O(n^3)$。

211 Strange Counter

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/211

翻译

设计一个拥有$n$个寄存器的计数器，第$i$个寄存器存储的数值为$x_i$，每个寄存器可以存储$0,1,2$。且计数器的值为：$\sum_{i=0}^{n-1}2^ix_i$。

现在要求完成共$m$个操作，第$i$个操作给定$c_i$，要求向计数器增加$2^{c_i}$。且要求每次增加操作最多四个寄存器发生改变，要求输出一套方案。

题解

挺有趣的题目（想得到就有趣，想不到就恶心了）。

首先我们认为高位寄存器位于低位寄存器的右边。

下面，我们设计一套算法，在每个操作结束后，保证任意两个2之间都至少有一个0存在。很显然一开始的时候是满足这个条件的。

你会发现如果第$k$位为$2$，那么我们将第$k$位置$0$，同时将$k+1$位增加1，这样做计数器总和不会改变，且任意两个2之间依旧至少有一个$0$存在，且第$k$位变成了$0$。我们记这套操作为$up(k)$，很显然这套操作只会影响两个寄存器。

现在考虑向第$c_i$位加1：

  • 如果$c_i$位为0，那么操作后$c_i$的右边的2和左边的2之间可能就没有0了，我们可以暴力找到较高位的2的位置$k$，然后执行$up(k)$即可，总共操作次数最多应该为$3$次。
  • 如果$c_i$位为1，那么操作后$c_i$位为1，其可能与右边的2或左边的2中的一个之间没有$0$存在（不可能同时发现），如果是右边的2，就对它执行$up$操作，如果是左边的$2$，就执行$up(k)$，总共操作次数最多应该为$3$次。
  • 如果$c_i$位为2，那么操作后$c_i$位为1，而$c_i+1$位增加1，对$c_i+1$位考虑前两种情况即可。总共的操作次数最多为$4$次。

这样我们就给出了一个$O(nm)$的算法。

212 Data Transmission?

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/212

题解

由于不需要考虑反向弧，因此跑一轮Dinic即可。但是Dinic跑一轮的时间复杂度是$O(VE)$，是过不了的。

看到别人用的是最高标号预留推进算法过的，可惜我手头的HLPP板子是有问题的，因此只好跳过了。

213 Strong Defence

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/213

翻译

给定一个包含$n$个顶点，$m$条边的无向图，给定起点$s$和终点$t$，要求找到最多的不相交边集，使得任意一个边集的删除都会导致$s$和$t$的不连通（即边集是$s$到$t$的一个割集）。

题解

可以参考我的另外一篇博客《最大流算法》中的最多割集划分一节的内容。

时间复杂度为$O(n+m)$。

214 Weird Dissimilarity

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/214

题解

题目类似与最长公共子串，但是ascii码有200个字符吗？？？反正不知道什么原因，用char会报RE，用int就好了。

215 PL/Cool?

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/215

题解

看来是时候去学一下编译原理了。

216 Royal Federation

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/216

翻译

给定一个$n$个顶点组成的树，以及某个正整数常量$b$。要求将树分成若干个连通块，每个连通块的大小均处于$[b,3b]$中。要求输出任意一组方案。

题解

可以参考我的另外一篇博客《树上算法》中的子树划分问题。

时间复杂度为$O(n\log n)$。

217 Royal Federation

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/217

翻译

三维空间中，两个给定半径，长度为无限的圆柱体的轴线垂直且相交。给定两个圆柱的半径，问相交的体积。

题解

画画图，发现某个截面的面积是可以计算的，有了面积，我们就可以通过积分求体积。积分的算法可以使用自适应辛普森积分法。

218 Unstable Systems

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/218

翻译

给定$n$个顶点的带权二分图，顶点之间两两有边，求一个最小的数$x$，满足仅考虑权值不超过$x$的边存在完美匹配。找到$x$并输出一个完美匹配。

题解

由于完美匹配的存在性随着$x$的增大从不存在到存在，是个递增函数，因此可以二分。现在我们需要解决的就是对于某个数$m$，加入权值小于等于$m$的边后是否存在完美匹配。最快的算法是Dinic算法，时间复杂度为$O(n^{2.5})$。

加上二分带来的$O(\log_2W)$因子，其中$W$是最大权值。时间复杂度为$O(n^{2.5}\log_2W)$，感觉还是挺快的。

219 Synchrograph?

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/219

题解

没看懂

220 Little Bishops

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/220

题解

首先将整个矩形旋转45度，就会发现约束条件变成我们要做的是每一行每一列最多只能放一个棋子。我们要写的是简单的状压DP，但是这样的时间复杂度为$O((2n-1)^22^{2n-1})$，过不了时限。优化方式就是发现奇数行和偶数行可以独立统计，而奇数行的列和偶数行的列是不相交的。我们拆开统计，最后计算有多少种合并方案总和为$k$即可，时间复杂度被优化为$O((n-1)^22^{n})$。

221 Big Bishops*

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/221

翻译

考虑这样一个题目，给定一个$n\times n$的矩形，我们希望在上面放入一些棋子，每个棋子都可以攻击对角线上的其他棋子，现在希望你回答，正好放$k$个棋子，有多少种方案数。

题解

果然是220的升级版，如果220是毫无营养的话，这道题就能学到点东西了。

可以参考我的另一篇博客《动态规划题目》中的动态规划去后效性中的例题就可以理解了。

最终的时间复杂度为$O(n^2)$，注意需要高精度。

222 Little Rooks

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/222

题解

简单的组合数学

223 Little Kings

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/223

题解

状压DP，这样的话时间复杂度为$O(n^32^{2n})$，会超时。假设第$i$层的状态为$j$，那么在计算上一层的可能的状态的时候，我们不暴力枚举所有的$2^n$种情况，而是枚举所有$mask-(mask\&(j | (j » 1) | (j « 1)))$的所有子集，这样就能把时间复杂度降低到$(n^33^n)$，是可以通过的。

224 Little Queens

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/224

题解

很显然因为非常大的限制条件，最终的方案数一定不会多。因此我们可以写一个高效的剪枝，利用搜索搜出所有$n,k\leq 10$的答案，之后打表提交即可。

本地我写的跑10秒就能跑出所有结果了。

225 Little Knights

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/225

题解

不会，状压+打表应该可以过。

226 Colored graph

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/226

题解

拆点+最短路。

227 The art to the broad masses!

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/228

题解

没看懂

228 Archipelago

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/228

翻译

给定$n$正多边形，将顶点按顺时针排序编号，之后给出两个不同的顶点的坐标，要求求出所有顶点的坐标。

题解

同SGU120，我们先生成任意一个N正多边形，之后通过线性变换得到其余所有顶点坐标。

229 Divide and conquer

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/229

翻译

给定一个$n\times n$网格，其中一些网格中有值（为$1$），其余网格无值。现在我们希望将网格中的所有有值的单元格分为两部分，使得一部分可以通过若干次90度旋转和水平平移与另外一部分重合。

题解

看错了题，以为只能翻转90度一次，于是贡献了若干发WA。

这道题，我们可以这样看。对于翻转0度，90度，180度，270度，我们可以分别独立讨论。这样就只有四种情况（最终时间复杂度乘上个4）。之后我们随意枚举一个有值的单位格$a$，之后暴力枚举选择另外一个有值的单元格$b$，这里最多只有$O(n^2)$种可能性。接下来我们希望$a$旋转平移后和$b$重合，其它单元格遵循相同的变换。之后我们发现其余每个有值的单元格，其或者是第一部分，或者是第二部分。但是无论其是哪部分的，都会导致另外一个它旋转后得到的单元格处于另外一部分。

如果我们将单元格的值分成true，false表示其处于哪一部分。那么我们就得到了一个逻辑推导关系，并且如果这个逻辑推导关系成立，则两部分的单元格数目会正好相同。

我们可以通过2-sat来解决这里的逻辑推导关系。由于2-sat的时间复杂度是线性的，因此总的时间复杂度为$O(4n^4)$。

230 Weighings

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/230

题解

拓扑排序

231 Prime Sum

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/231

题解

由于任意两个奇素数之和一定是偶数，因此至少一个素数需要为2。剩下的就交給素数筛吧。$O(n)$。

232 Infinite Fraction

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/232

题解

如果大家学过后缀数组，会发现这里的比较和后缀数组的非常类似，都可以用倍增技术优化。因此时间复杂度为$O(T\log_2n)$，其中$T$是排序所需的时间。如果使用比较排序的话时间复杂度为$O(n(\log_2n)^2)$，然后成功超时。和我一起大吼，基数排序NB，于是时间复杂度可以优化到$O(4n\log_2n)$，这里每次排$16$位，堪堪卡入了时限内。

看了一下其他人的做法，发现好像正解是最大表示法，是线性时间复杂度的，没学过，赶紧学了一波。

233 Infinite Fraction?

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/233

题解

我的方式是直接线性变换转换成容易处理的形式，之后利用三分法求解。但是明明答案和样例完全一致，第一个测试用例就WA了？？？

234 Black-White King Strikes Back?

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/234

题解

太长，不看。

235 The Queen?

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/235

题解

皇后怎么走？可以过同色棋子吗？

236 Greedy Path

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/236

翻译

给定一个$n$个顶点$m$条边的简单有向图（无自环和重环），每个边都有容量和时间两个属性。现在希望找到任意一条环路（允许有重边但路径不能为空）。

我们希望找到所有环路中路径的总容量除上总时间最大的那条路径，即找到这样一条环路$R$，满足$\frac{C(R)}{T(R)}$最大，其中$C(R)$为路径中边的总容量，而$T(R)$是路径中边的总时间。如果有多条路径满足条件，则输出任意一条路径，否则输出$0$。

题解

这道题是很明显的分数规划题目，我们可以将其转换为二分过程，每次二分的校验过程中，我们会为每条边提供一个权重。并且在校验过程中，我们要做的是判断是否存在总权重非负的那条环路。

现在我们来讨论如何找到权重非负的环路。首先我们知道对于复合环结构，如果它的总权都是非负的，那么其中至少存在一个简单环，其总权非负。因此我们仅需要考虑长度不超过$n+1$的环即可。

我们可以直接暴力从每个顶点出发寻找，时间复杂度为$O(n^4)$。记$dp(i,j,k)$表示从$i$出发抵达$j$，共经过$k$条边的最大权值。配合外面的二分可能会超时。

或者我们可以利用倍增法找非负环。建立一个映射$f$，其中$f^k(i,j)$表示从$i$到$j$的所有长度不超过$k$的路径中总权重最大的路径的总权重。而我们只需要求出$f^{n+1}$，这里我们可以利用倍增法计算，时间复杂度降低为$O(n^3\log_2n)$。因此总的时间复杂度为$O(n^3(\log_2n)^2)$。

最后输出路径，可以通过做转移的时候记录中点信息完成。注意由于用到浮点数，因此要控制精度。

242 Student's Morning

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/242

题解

把每个大学拆成两个，那么学生放左边，大学放右边，找右边的完美匹配即可。时间复杂度为$O(nk)$。

247 Difficult Choice*

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/247

翻译

给定一个奇素数$p$，要求从$1,\ldots,2p$中取出$p$个数，满足取出的数之和能被$p$整除。问有多少取数方案。

题解

可以想到一个简单的DP，配合打表应该可以过。后来看了一下别人的解法，果然是数学题。

我们记$A={1,\ldots,p}$，$B={1+p,\ldots,p+p}$。由于$p$是奇素数，因此如果取$A$和取$B$，它们的和都是$0$（模$p$意义下）。因此这里已经有了两种方案。

这里我们引入一个定义：考虑由$A$的所有非空真子集组成的族$S$，现在我们给出一个划分，如果两个子集$X,Y$属于同一个划分，当且仅当存在一个整数$k$，满足$X+k=Y$，这里的$X+k$的意思是将每个$X$中的元素增加$k$得到的新的集合。很显然划分是正交的，且每个划分包含$p$个$A$的相同大小的子集，且每个子集的总和不同（由$p$和子集大小互质得出）。

考虑任意一个$B$的非空真子集，发现在$A$中所有满足子集长度条件的划分中，有$\frac{1}{p}$的比例使得总和为$0$。因此可以推出总数为：$\frac{ {2p\choose p} -2}{p}+2$。

剩下的就是高精度了。

247 Integer Linear Programming

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/247

翻译

给定$n$个非负未知整数$x_1,\ldots,x_n$，现在要求我们为其赋值，要求满足$\sum_{i=1}^nc_ix_i=v$的同时且$\sum_{i=1}^nx_i$最小。这里$n\leq 3, c_i,v\leq 10^6$。

题解

这个问题咋一看无从下手，我们无法直接用线性规划，因为线性规划有整数解需要系数矩阵$[c_i]$是全幺模矩阵，即$c_i=0,-1,1$，这显然是不满足的。

但是如果我们换一个视角来看问题，答案就昭然若揭了。我们现在有价值为$c_1,\ldots,c_n$的不同的无数硬币，我们需要用这些硬币购买一件价值为$v$的商品，问我们至少需要带多少硬币过去。这是一个典型的DP问题。

时间复杂度为$O(nv)$。

248 Matrix

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/248

翻译

要求将$0,1,\ldots,2^{n+m}-1$这些数填入一个$2^n$行$2^m$列的矩阵中，要求相邻单元格中二进制最多仅一位不同（矩阵第一行认为和最后一行相邻，第一列和最后一列相邻）。

题解

格雷码可以了解一下。对于由$0,\ldots,2^k-1$组成的格雷码序列，满足循环条件下相邻位二进制都正好有一位不同。

格列码可以解决循环序列，那如何解决矩阵呢。很简单我们将行号和列号都生成格雷码，之后拼接在一起即可。同一行仅比较列格雷码，同一列比较行格雷码，因此最多只有一位不同。

还有这道题输出非常大，用cout会导致TLE。解决方法就是先输出到stringstream中，之后一次性输出到cout中。

252 Railway Communication

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/249

翻译

给定一副有向无环简单图（无重边），有边权。现在选择若干条不相交路径，要求每个顶点正好属于一条路径。首先要求路径数最少，如果有多个方案满足条件，仅考虑路径覆盖的所有边的边权和最小。输出任意一个满足条件的方案。

题解

首先这是不想交路径覆盖问题，通过将原图建立成二分图，问题可以转换为二分图最大匹配问题。

但是这里还是有点区别的，就是要求路径覆盖的边权和最小，考虑所有路径覆盖的边正好是二分图的匹配集合，因此我们将原本求二分图的最大匹配改成求最小费用匹配即可。

这个可以通过KM算法解决，也可以直接上费用流。时间复杂度为$O(n^3)$。

253 Theodore Roosevelt

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/253

翻译

提供一个$n$个顶点的凸包，以及$m$个顶点，问有多少个顶点落在凸包内。

题解

可以用动态凸包直接解决。大概做法就是将凸包上的顶点放在平衡树上维护，按照根据凸包内部某个顶点$c$之间的极角进行排序，之后快速判断顶点$x$顺时针方向的第一个顶点$a$和逆时针方向的第一个顶点$b$，判断$x$是否落在$a,b,c$组成的三角形中即可。

时间复杂度为$O((m+n)\log_2n)$。

254 Strange Random

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/254

题解

发现$q$很小，暴力模拟即可。当然如果$q$很大，可以用平衡树进行优化。两种情况下时间复杂度为$O(nq)$和$O(n\log_2n)$。

255 Winsock 3 Beta*

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/255

翻译

判断是否存在唯一的$k$，满足$k+1$到$2k$之间二进制正好拥有三个$1$的数的数目恰好等于$m$。

题解

一道二进制技巧题目。

记$f(x)$，表示$x+1$到$2x$之间拥有多少个数正好拥有三个二进制$1$。现在我们来查看$f(x)$和$f(x+1)$的区别。我们发现仅对$f(x)$产生贡献的数为$x+1$，而仅对$f(x+1)$产生贡献的数为$2x+1$和$2x+2$。注意到由于$x+1$中二进制1的数目等于$2X+2$中的。这里我们得到了两个信息，$f(x)+1\geq f(x+1)\geq f(x)$，即函数$f$递增，同时$f(x+1)=f(x)+1$成立当且仅当$2x+1$中包含正好三个二进制1，当然这等价于$x$中正好包含两个二进制1。

有上面的性质可以得出$k$必定存在，但是是否唯一还不确定。题目要求我们判断$k$是否唯一，我们发现如果$k$是唯一的，那么一定有$f(k+1)>f(k)>f(k-1)$，这仅在$k-1=10\ldots 01$的情况时会发生。

现在我们记$g(n)=f(2^n)$，容易发现$g(n)={n \choose 2}$，即在$0$到$2^n-1$之间存在多少数的二进制1的数目正好为2。我们先找到最小的$n$，满足$g(n)\geq m$，之后判断$g(n-1)$是否等于$m-1$即可。这里如果$n=2$也是无解的（对应的$m=1$）。

每个用例时间复杂度为$O(\log_2m)$。

256 Balloons*

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/256

题解

这道题的惯性思维是建立一个DP公式类似于$dp(i,t_1,\ldots,t_n)$，表示仅前$i$分钟，第$j$个人需要$t_j$分钟休息，这样做时间复杂度会飙升到$5m5^n$，但是发现大部分人的休息时间都是0，因此我们可以建立一个更加简DP公式：$dp(i,p_1,p_2,p_3,p_4)$，表示仅考虑前$i$分钟，$p_j$是在$j$分钟前工作的。这样时间复杂度就降低为$O(5mn^4)$。

257 Debt

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/257

翻译

将$n$水晶分配给三个人，第$i$个水晶在第$j$个人眼中价值为$V_{i,j}$，其中$V_{i,j}=1,2$。现在要求将所有水晶分配给三个人，第$k$个人得到的水晶在他眼中价值必须不少于$T_i$。判断是否有解，有解输出任意一组。

题解

将水晶按照二进制掩码分成8类，并统计每一类水晶的数量。我们建立一副网络，每个水晶类型和人都对应图中的一个顶点，如果类型$i$的水晶在人$j$中眼中价值为$2$，那么我们就从水晶到人建立一条容量为无穷的管道。同时我们从源点向每个水晶类型连一条容量为这个水晶出现次数的管道。最后我们从第$i$个人向汇点连容量为$\lfloor \frac{T_i}{2}\rfloor$的管道。

很显然，如果上图有流量为$f$的网络流，那么正好有$f$个水晶被消耗，同时剩下$n-f$个水晶会以价值1分配给每个人，此时必定需要满足$n-f\geq T_1+T_2+T_3-2f$。化简一下公式可以发现$n+f\geq T_1+T_2+T_3$，即流$f$越大，我们越有可能有解。

这里我们可以直接跑出最大流，最后按照最大流分配水晶即可。

总的时间复杂度应该是$O(n+6^3)$。

258 Almost Lucky Numbers

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/258

题解

一开始想了个简单的数位DP，记$f(n,i,j,used,ceil,floor)$表示长度为$2n$的数字，现在处理到第$i$位，总和为$j$，$used$表示是否消耗了一次机会，$ceil$与$floor$用于校验数位DP的有效性。

但是这个是错误的，因为上面的DP会导致重复统计，它会统计$A$到$B$之间每个数有多少变换后的数值是幸运数的总和，比如$21$会被统计两遍，第一遍就是2变成1，第二遍就是1变成2。

之后想了个方法去掉了重复统计，定义新的数位DP，记$f(n,i,j,inc,dec,ceil,floor)$表示长度为$2n$的数字，现在处理到第$i$位，总和为$j$，现在通过换数最多可以使总和增大$inc$，或者减少$dec$。

新的DP公式是不会重复统计的，原因是如果有多个数位可以执行换数操作，我们始终在最高位上执行。这样每个数值其变换后的合法数值就是唯一的了。用同样的统计技术，就能正确统计了。

259 Printed PR

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/259

翻译

提供一台打印机，每次同时只能打印一份文件。你需要打印$n$个传单，第$i$个传单打印耗时$T_i$，投递需要的时间为$L_i$。你有无数的信使，因此一份传单打印完成后立刻就开始投递。现在问最少需要多少时间才能完成所有传单的打印投递。

题解

这个问题是比较经典的排序问题。要排序我们就需要给出偏序关系，现在考虑最优排列中某两个相邻的下标$i,j$，即第$i$个传单正好在第$j$个之间打印。

我们注意到假如我们交互$i,j$的打印顺序，那么时间不可能减小（否则就不是最优排列了），考虑交换对总时间带来的影响。记$T$为$i,j$之前打印的所有传单费时之和。那么先打印$i$对结果的贡献为$\max(T_i+L_i,T_i+T_j+L_j)$，而先打印$j$对结果的贡献为$\max(T_j+L_j,T_j+T_i+L_i)$。由前面知道$\max(T_i+L_i,T_i+T_j+L_j)\leq\max(T_j+L_j,T_j+T_i+L_i)$，这里我们可以直接推出$T_i+T_j+L_j\leq T_j+T_i+L_i\Rightarrow L_j\leq L_i$。

于是乎我们得到了一个最优排列的偏序关系，若$L_j\leq L_i$，那么$i$就需要排在$j$之前。

之后排个序，就出解了。

时间复杂度为$O(n\log_2n)$。

260 Puzzle

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/260

题解

高斯消元。

261 Discrete Roots

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/261

翻译

给定素数$p$，以及整数$a,k$，按序输出所有满足$x^k=a\pmod p$的$x$。

题解

离散对数经典题目，解法可以参考我的另外一篇博客《数论》中离散对数一节的问题3。

时间复杂度为$O(\sqrt{p})$。

262 Symbol Recognition

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/262

翻译

给定$k$个长度为$n$的二进制序列，要求生成一个长度为$n$包含最少1的二进制掩码串，满足这个掩码串与其余二进制串进行且运算得到的结果都不同。

题解

好题，想到后觉得酣畅淋漓。

首先我们将这些二进制序列两两亦或，得到${k\choose 2}$个二进制串。这里我们将这些二进制串理解为集合（0表示元素不存在，1表示存在），这样如果掩码串保含某个元素$x\in A\oplus B$，那么掩码串就能区分$A$和$B$。这样的话，问题就是我们要找到${1,\ldots,n}$最小的一个子集，这个子集和这${k\choose 2}$个集合每一个的交集均非空。

注意到由于$k\leq 6$，因此${k\choose 2}\leq 15$，这让我们能想到状压技术。

现在已经可以利用状压DP解决这个问题，定义$f(i,s)$表示仅考虑前$i$个元素，此时哪些集合满足条件的状态为$s$，之后直接DP即可。

时间复杂度为$O(nm2^{ {k\choose 2} })$。

263 Towers

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/263

题解

用平衡树找前驱后继第$k$大，时间复杂度$O(n\log_2n)$，空间复杂度$O(n)$。

264 Travel

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/264

翻译

$n$个女士和$n$男士去旅游。每个男士对所有女士都有一个偏好顺序，而每个女士对男士也有偏好列表。现在要将女士和男士进行配对，如果一对未配对的男女，对彼此的好感都超过现在的配对的对象，那么这样的配对方案是不稳定的。要求找出一组稳定的配对方案。

题解

稳定婚姻问题，随便找一本组合数学书都有介绍。

时间复杂度为$O(n^2)$。

269 Rooks

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/269

题解

动态规划去后效性。时间复杂度为$O(nkT)$，其中$T$是大数运算所需时间复杂度。

270 Thimbles

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/270

翻译

有$n$个碗，将一个硬币放在第一个碗下。接下来执行$m$次操作，每次交换两个不同的碗的位置。现在给定这$m$个操作，但是它们的顺序是没有给定的，要求回答最终硬币可能在哪些碗下面。

题解

首先将$n$个碗建立顶点。之后每个交换$a$与$b$的操作，我们在顶点$a$和顶点$b$之间加入一条无向边。

我们发现交换操作实际上等价于我们消耗一条边，并且如果硬币正好边的某个端点上 ，硬币需要沿着边移动。对于与顶点$1$不连通的顶点，很显然最终硬币肯定不会在这些顶点上，因此可以忽略这些顶点。接下来仅考虑与$1$连通的顶点。

生成任意一颗生成树，会发现生成树上深度不小于$2$的顶点$u$一定有可能，为啥？这意味着存在一条至少包含三个不同顶点的路径$v_1,\ldots,v_k$，其中$v_1=1$，$v_k=u$。我们可以先从图中删除路径上的所有边，现在的问题是我们是否可以清除其余所有边，每次清除的时候都不会影响硬币的位置。这是一定可以的，在$v_1$的时候我们删除所有不与$v_1$相关的边，在$v_2$的时候我们删除所有不与$v_2$相关的边，而在$v_3$的时候我们删除所有不与$v_3$相关的边，因此经过这三步，能留下的边要同时与$v_1,v_2,v_3$相关，当然这种边是不存在的。因此我们可以成功删除所有边，而不会影响硬币的位置。

之后考虑深度为1的顶点$u$。这要分多钟情况讨论。

  • 如果顶点$u$与$1$之间存在奇数条边，那么我们最后一定有机会停留在顶点$u$上，原因是我们可以只留下$u$与$1$之间的边（在1的时候删除所有不与$1$关联的边同时在$u$的时候删除所有不与$u$关联的边）。而奇数条边，保证我们在$1$与$u$之间往复，最后一定能停留在$u$。
  • 否则顶点$u$与$1$之间存在偶数条边
    • 如果$1$在某个至少拥有$3$个不同顶点的环中，或者还存在另外一个顶点与$1$拥有两条以上的边，那么硬币可以最终停留在$u$。
    • 否则硬币不可能最终停留在$u$

最后我们考虑顶点$1$。如果没有与$1$关联的边，那么最终硬币肯定会留在$1$。否则如果$1$在某个至少拥有三个不同顶点的环上，或者$1$与至少两个顶点之间存在至少两条边，或者1与某个顶点存在两条边，且这个顶点在某个环（不包含$1$）上。那么硬币就有可能停留在$1$，否则就没有可能。

上面的过程可以$O(n)$完成。

271 Book Pile

题意

https://codeforces.com/problemsets/acmsguru/problem/99999/271

题解

表述不清的题，是怎么旋转，顺时针还是逆时针？？但是实际上这里ROTATE不是旋转的意思，是翻转的意思。维护一个双端队列即可。时间复杂度为$O(n+m)$。

其实这道题假如$k$不是固定的话，也可以用平衡树进行加速，只是时间复杂度会变成$O((n+m)\log_2 (n+m))$。