Contest Info

date: 2018.11.29 19:30-24:30

practice link

Solutions

A. Numbers

题目大意：给出 \(n\)，求出 \(x+y=n,x>0,y>0\)，且 \(x\) 和 \(y\) 均为回文数的 \((x,y)\) 数量。

题解：首先枚举 \(x+y\) 时 \(n\) 的哪些位产生了进位，这样我们就能知道 \(x\) 和 \(y\) 每一位的和。下面分两种情况讨论：

• \(x\) 的长度小于 \(y\)：此时 \(y\) 的最高若干位已经确定，根据回文的性质可以直接求出 \(x\) 和 \(y\)，判断是否合法即可
• \(x\) 的长度等于 \(y\)：此时每一对位置相互独立，把每对位置的方案数相乘即可

时间复杂度 \(\mathcal{O}(2^{\log_{10}n}\log_{10}^{2}n)\)。

B. Broken Watch

签到题。

C. Tree

题目大意：

给出一棵\(n\le1000\)个节点的树，每个点要么是黑点要么是白点。

要求选出恰好\(m\le n\)个黑点（保证至少有\(m\)个黑点），最小化选出的点集中两个点的最大距离。

题解：

枚举每个点或边为点集的中心，求出每个点到它的距离，如果距离小于\(x\)的黑点有不少于\(m\)个则\(x\)是合法的解，求一个最小的\(x\)即可。

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

D. Space Station

题目大意：

给出一棵\(n\le1000\)个节点的树，每条边有个权值，现在要从\(1\)号点出发，遍历每一条边至少一次，再回到\(1\)号点，可以不超过\(m\le1000\)次使用跳跃，花费\(k\)的代价，从当前所在的任意点移动到另一个任意的点，求最小的代价。

题解：

假设不使用跳跃，一定是从\(1\)号点出发dfs一遍再回到\(1\)号点，每条边恰好经过了\(2\)次。

如果使用一次跳跃从\(u\)移动到了\(v\)，可以让\(u\)到\(v\)路径上的边的少经过一次。

如果有两次跳跃的路径（边集）有交，那么交的边没有被遍历到，就不合法。

问题转化为，选择不超过\(m\)条不相交路径（考虑至少包含一条边），最大化路径上的边权和。

要选择不相交的路径，那么对于每一个子树，经过了子树根的路径最多只有一条，否则就不合法。

令\(dp[u][i]\)表示\(u\)子树内有\(i\)个点作为路径的端点，最大的路径边权和。

当\(i\)为奇数的时候，有路径跨越了子树，否则，路径全在子树内部。

转移时子树背包一下即可，时空复杂度\(O(n^2)\).

E. Fishermen

签到题

F. Min Max Convert

题目大意：给定两个长度均为 \(n\) 的序列 \(A, B\)，要求你构造一个不超过 \(2n\) 的操作序列，将序列 \(A\) 变为 \(B\)。操作有两种，选择一个区间，把它们都变成 min，或者变成 max。

题解：我们把 \(B\) 分成若干段，每一段数字相同。那么 \(A\) 中必须要存在一个序列，能与 \(B\) 的划分一一对应，才可能有解。我们假设每一段为 \((l,r,p)\)，其中 \(l,r\) 表示 \(B\) 中一段的区间端点，\(p\) 表示它对应的数字在 \(A\) 中的出线位置。

我们从左往右扫一遍，对于 \(r<p\) 的段，我们把 \([l,p]\) 变成 \(A[p]\)；从右往左扫一遍，对于 \(p<l\) 的段，把 \([p,r]\) 变成 \(A[p]\)。然后再把 \(l\leq p\leq r\) 的段，变成 \(A[p]\)。

把 \([l,r]\) 变成 \(A[r]\) 的方法为，对 \([l,r-1]\) 做一次操作，然后对 \([l,r]\) 做一次操作。具体操作类型可以根据 \(A[r-1]\) 和 \(A[r]\) 的大小关系判断。

G. Matrix Queries

题目大意：一个 \(2^{n}\times2^{n}\) 的网格，有黑白两种颜色，开始全是白色。定义该网格的代价为：若它由一种颜色组成，代价为 \(1\)；否则代价为均分成 \(4\) 个正方形子网格的代价之和加 \(1\)。现有 \(q\) 次询问，每次把一行或一列取反，每次询问之后要求你回答网格的代价。

题解：我们可以对行和列分别维护每一种大小的“\(2\) 的幂”的块的数量。例如 \(0010\) 中有 \(1\) 个大小为 \(2\) 的块和 \(2\) 个大小为 \(1\) 的块。这可以用一个类似于 buddy system 的线段树来维护。

对于一个大小为 \(x\) 的行和一个大小为 \(y\) 的列，总共有 \(\frac{xy}{\min^{2}\{x,y\}}\) 个大小为 \(\min\{x,y\}\times\min\{x,y\}\) 的块。之后我们用容斥就很容易求出每种大小的块。之后模拟题意算代价即可。

时间复杂度 \(\mathcal{O}(nq)\)。

H. Modern Djinn

题面有毒。随机每个点的颜色，然后 check 满足的条件个数，迭代数次直到满足。

I. Inversion

题目大意：

\(p_1,\cdots,p_n\)是\(1\)到\(n\)的排列。

给出一个\(n\le1000\)个点，\(m\)条边的简单无向图，两个点\(u<v\)之间有边当且仅当\(p_u>p_v\).

求图中的极大独立集数量，即集合内部不存在边，集合外每个点至少存在一条与集合内点的边。

题解：

通过不等关系建出一个DAG，拓扑排序一下就得到了\(p\)数组。

图中的极大独立集等价于\(p\)中的极大单调上升子序列，令dp[i]表示前缀\(i\)以\(i\)结尾的极大单调上升子序列数量。

对于每个前缀最小值的位置\(i\)，可以作为开头的位置，dp[i]初值为\(1\)，否则为\(0\).

从小到大递推，当\(dp[i]\)计算完毕后，枚举\(j>i\)，如果\(p[i]<p[j]\)，且不存在\(i<k<j\)且\(p[i]<p[k]<p[j]\)的话，dp[i]就能转移到dp[j]，这个可以通过二维前缀和\(O(1)\)判断。

再对于每个后缀最大值的位置\(i\)，可以作为结束的位置，将dp[i]计入答案即可。

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

J. Rabbit vs Turtle

题目大意：

给出一张图，\(n\le10^5\)个节点，\(m\le10^5\)条边。

有只兔子和乌龟在赛跑，每条边乌龟和兔子各有一个需要的时间。

乌龟要经过的边按顺序给出，并且乌龟每当走过一条边，就会睡一段时间，每条边的这个时间也给出。

兔子要经过的边按顺序给出，兔子可能作弊，在某个点改变下一个目标点，之后一直走最短路。

当兔子开始作弊时，乌龟如果没有睡觉，则立即就会发现，否则它睡醒后立即会发现，乌龟一旦发现兔子作弊，之后都不会再睡觉。

如果乌龟和兔子同时到达算兔子赢。

问从哪些点开始作弊（要求改变目标点，且使得最短路严格变短），可以获胜。

题解：

按题意做一下就好了。

K. Points and Rectangles

题目大意：

二维平面上\(q\le10^5\)次事件，每次出现一个点或者一个与坐标轴平行的矩形，问每次事件后，有多少对矩形和点的包含关系。

题解：

无论是矩形找点还是点找矩形都可以容斥一下转成二维数点，按时间分治一下，时间复杂度\(O(n\log^2{n})\)，空间复杂度\(O(n)\).