Contest Info

date: 2018.11.23 10:31-15:31

practice link

Solutions

A. Appearance Analysis

签到题

B. Bipartite Blanket

题目大意：

给出一个二分图，左部有\(n\le20\)个点，右部有\(m\le20\)个点。

每个点都有个权值，问有多少个集合能被至少一个匹配覆盖，并且集合内点权值之和至少为\(t\).

题解：

由广义霍尔定理，我们可以分别计算两边可以被匹配覆盖的集合，排序之后，two pointer一下计算答案。

时间复杂度\(O(2^n\cdot n)\)，空间复杂度\(O(2^n)\).

C. Convex Contour

简单几何。

D. Dancing Disks

题目大意：有一个 \(6\times 6\) 的二维汉诺塔，且不要求小圆盘必须在大圆盘上面。现在在 \((1,1)\) 上以某种顺序摆放了 \(n\le4\times10^{4}\) 个圆盘，要将它们移动到 \((6,6)\)，且使得圆盘从上到下依次增大。每次可以将某根柱子最上面的若干个圆盘向右或向下移动一步，求一种方案。

题解：首先很显然我们可以将这些圆盘分成若干个大小连续的段，每段移动到右下角的某一个格子里。举例来说，设 \(n=6\)，不论 \((1,1)\) 中怎么排列，我们都很容易做到把 \(1\) 和 \(2\) 移到 \((1,2)\)，把 \(3\) 和 \(4\) 移到 \((1,3)\)，把 \(5\) 和 \(6\) 移到 \((1,4)\)。之后递归处理即可。

我们可以 \(dp\) 出这种方案能移动的圆盘的上限，可以发现只有 \(2\times10^{4}\) 多一点。对于 \((5,6)\) 的情况，我们发现按照上面的方法只能处理一个圆盘，但是实际上很容易处理 \(2\) 个圆盘的情况。对 \((6,5)\) 类似。那么此时能够处理的圆盘个数就大于 \(4\times 10^{4}\) 了。

E. Easy Equation

题目大意：求出 \(n\le1000\) 个 \(a^{2}+b^{2}+c^{2}=k(ab+bc+ac)+1\) 的解。

题解：显然 \(a=1,b=k,c=k(k+1)\) 是一个特解。注意到 \((k(b+c)-a,b,c)\) 也是一个解，并且该式轮换对称，因此还有两个同样形式的解。bfs 搜解即可。

tips：bfs 记得要记 vis 啊。。。

F. Free Figurines

题目大意：

有\(n\le10^5\)个大小互不相同的俄罗斯套娃，给出初始的包含关系，要求用最少的操作数变成目标的状态。

定义不被其它套娃包含的套娃是free的，可以使用的操作有两种：

• 把一个free的套娃放进当前不包含其它套娃的更大的free的套娃中
• 把一个free的不为空的套娃打开，拿出其直接包含的套娃

题解：

最优方案中，每个套娃是否free的状态至多改变两次：

首先决定拿出这一阶段哪些套娃需要变成free，从小到大决定，如果\(i\)的父亲发生了改变，则它自己需要变为free；如果\(i\)需要变为free，则其改变前后的父亲都要变为free；

每一个初始状态不为free而现在处于free状态的会为答案贡献一，然后现在处于free状态的如果在最终局面不是free的，答案再需要加一。

H. Hangar Hurdles

题目大意：

有一个\(n\times n\)的网格图，\(n\le1000\)，有一些位置是障碍。

\(q\le3\times10^5\)次询问，每次给出两个格子\(s\)和\(t\)，问可以从以\(s\)为中心出发，移动到以\(t\)为中心结束，不被障碍挡住的最大正方形的边长是多少，无解则输出零。

题解：

对于每个位置\(x\)二分求出以它为中心的最大正方形边长\(f(x)\)，之后建图，每两个相邻的格子连权值为\(\min f(x)\)的边，则等价于求\(s\)到\(t\)的最小瓶颈边权值，kruskal建树之后倍增即可。

时间复杂度\(O(n^2\log{n})\).

J. Jazz Journey

题目大意：

有\(n\le3\times10^5\)个城市，和一个长度为\(d\le3\times10^5\)的旅行序列，第\(i\)次旅行从城市\(a_i\)径直（不中转）坐飞机去\(a_{i+1}\)，共\(n-1\)次。

有\(m\le3\times10^5\)种机票可以买，每种机票的购买次数没有限制。

机票分为两种，一种是单程机票，从城市\(u\)到城市\(v\)；另一种是往返机票，从城市\(u\)到城市\(v\)，再从城市\(v\)到城市\(u\)，返程机票可以不使用，但是如果要使用，一定要先用掉去程机票。

保证有解，求最少的机票费用。

题解：

如果两次旅行的边不相同也不相反，那么这两次旅行是独立的。

对于每一对城市，记录来回旅行的\(01\)序列进行贪心。

贪心前首先保留每种机票最便宜的，然后用往返机票来更新单程票，然后如果有两个方向的单程票存在，用它们来更新往返机票。

这样操作之后，如果不满足两个方向的单程票都存在，那么另一种方向的旅行一定要用往返票，直接计算即可；

否则，选择往返票来进行两个不同方向的旅行一定不会更差，而总的往返票使用次数等于两种方向中较少的次数，枚举尽量凑出哪种往返票，取最小值即可。

时间复杂度\(O(n)\).

L. Lost Logic

题目大意：给出三个 \(n\le50\) 变量的布尔值，要求你构造出一个 \(2-SAT\)，使用不超过 \(500\) 条限制，使得它有且仅有上述三组解，或判断不存在。

题解：容易想到，只要将上述三组解满足的所有限制都加入，那么这个 \(2-SAT\) 如果多于三组解，就无解，否则就是一个答案。但是这样的限制太多了，不能控制在 \(500\) 条内。

考虑尽可能加入”有用“的限制。对于所有取值为 \(000\) 或 \(111\) 的变量，限制它们取该值；对于所有取值相等的变量，加上让它们相等的限制；对于所有取值相反的变量；加上让他们相反的限制。

现在可以注意到，未确定值的自由变量至多只有 \(3\) 个。如果是 \(0\) 个或 \(1\) 个，该解已经成立。如果是 \(2\) 个，简单地把不满足这两个变量的解限制掉即可。如果是 \(3\) 个，可以证明（暴搜）没有满足题意的方案。