题解 | CF297 / Codeforces Round 180 (Div. 1)

未独立完成的题目

A

题意

给你两个01串a, b，定义 parity(str): 如果 str 中有奇数个 1，返回 1，否则返回 0。有两种操作

把 parity(a) 附到a的最后
在a的前面删掉一个数

可以执行任意步操作，问你是否可以把a变成b。

题解

注意到如果a中有偶数个1，则1的数目不可能增多（如果a中有奇数个1，可以先在后面添上一个1，之后1的数目就不可能增多了）。并且通过合适的策略，可以把a变成任何一个1的数目小于等于它的01串。只要数一下a, b中1的数目即可。

总结

这题考场AC，并且重新思考时独立完成。

B

题意

有k种🐟，每种🐟都有一个重量，并且它们按照重量从小到大排序后有一个编号。Alice手上有n条🐟，Bob手上有m条🐟。给出Alice和Bob手上鱼的编号，问Alice手上的🐟的总重是否可以大于Bob。

题解

首先把这些编号离散化一下，再做个后缀和。从后往前扫，如果某个位置Alice手上的🐟的数量大于Bob了，我们就把这之后的🐟的重量全赋成INF，这之前的全赋成1。这样Alice手上的🐟的重量肯定大于Bob。

总结

这题考场AC，并且重新思考时独立完成。

C

题意

有一个数组s，包含n个互不相同的非负整数。让你分成两个数组a, b。使得

$a_i,b_i$ 为非负整数
$s_i=a_i+b_i$

同时，要求a, b中重复出现的数分别不超过 $\lceil \frac n 3 \rceil$ 。

题解

构造。把s数组排序后，

a数组的前 $\frac 1 3$ 填 $1\sim \frac n 3$ ，b数组对应填。
b数组的中间 $\frac 1 3$ 填 $\frac n 3 \sim \frac{2n} 3$ ，a数组对应填
b数组的最后 $\frac 1 3$ 填 $n-i-1$ ，a数组对应填。

这样保证了a数组的前面和后面是两两不同的，b数组的中间和后面是两两不同的。

总结

这题还记得是分三段构造，但是构造策略没想出来，未独立完成。

D

题意

用k种颜色拼成一个 $h*w$ 的地毯，同时对于每一对有公共边的方块给定了一个限制条件，要求它们同色或者不同色。这些限制条件只要满足 $3\over 4$ 即可。如果可以构造，给出一种方案。

题解

这题给了 $k$ 个颜色，实际上对于 $k\ge 2$ 的情况，只要两个颜色就可以了，并且总是可以构造。对于 $k=1$ 的情况简单判一下 E 的数量是否超过总数的 $3\over 4$ 。否则，注意到有 $h*(w-1)+w*(h-1)$ 个限制条件，我们先满足 $h*(w-1)$ 和 $w*(h-1)$ 中较大的限制条件，再在剩下的条件中挑一部分满足。可以先翻转一下，保证 $h\le w$ 。然后行内全满足，上下的关系总可以满足一半以上（先钦定第一个块的颜色，如果发现这样填下来满足不了一半，把整行颜色反转，就可以满足一半以上了），加起来超过总数的 $3\over 4$ 。

总结

独立完成。

E

题意

一个环上有2n个顶点。要求选择3条不重复的弦，在它们顶点处建6个熊洞，且每条弦的两个端点的距离（距离的定义是在环上经过的熊洞数，取较小值）相同，询问其方案数。

题解

三条弦总共有五种关系，其中2, 5是合法的。

五种类型

但是2, 5的方案比较难算，考虑从总方案中减掉1, 3, 4的方案。

假设我们能处理出每条弦的左边和右边弦的数量，记为 $L_i, R_i$ ，对于类型1，答案就是 $\sum L_i \cdot R_i$ 。把类型3和类型4一起计算。它们的共同点是从两条弦（对于类型3是顶上两条，对于类型4是竖着的两条）的角度观察，一条弦和自己相交，一条线和自己相离。那么情况数就是 $\sum (L_i + R_i)*(n-L_i-R_i-1)\over 2$ （每种情况会被计算两次）。

现在问题是怎么计算 $L_i,R_i$ 。设以弦 $(x_i,y_i)$ 的角度观察（ $x_i\lt y_i$ ），如果弦 $(x_j,y_j)$ 在自己左边（ $x_j\lt y_j$ ），则 $x_j\lt x_i$ ， $y_j\gt y_i \text{ or } y_j \lt x_i$ 或者 $y_j\gt x_j\gt y_i$ 。否则， $x_i\lt x_j\lt y_j\lt y_i$ 。这可以用二维偏序解决。复杂度 $n \log n$ 。

总结

未独立完成。