CF15 题解

CF15A题解

题目大意

给定一个坐标轴，轴上有 $n$ 座房子，每座房子的位置是 $x_i$，边长是 $a_i$。有个人想要贴着其中一座房子建造一座他自己的边长为 $t$ 的房子，请输出共有多少种建造方法。

题解

预处理出相邻房子之间的间隔，如果 $d>t$，对答案贡献为 $2$；如果 $d=t$，对答案贡献为 $1$。

CF15B题解

题目大意

在 $n\times m$ 的网格有两个点，两个点可以在网格内任意平移，但相对位置不能改变，也不能出网格。求网格上有多少个位置，这两个点无法通过平移达到。

题解

先计算出两个点的相对位置 $dx$ 和 $dy$，取绝对值变为非负数可以简化问题且不影响答案。

分情况讨论：

$1+2dx\le n$ 且 $1+2dy\le m$，此时只有网格相对的两个角处的两块矩形位置不能达到，答案 $dx\times dy$；
其余情况：只有网格两个角处的矩形位置能达到，答案 $nm-(n-dx)(m-dy)$。

CF15C题解

题目大意

有 $n$ 组石子，每组石子有两个参数 $x_i$ 和 $m_i$，该组石子一共有 $m_i$ 堆，第一堆有 $x_i$ 个，第二堆有 $x_i+1$ 个，第三堆有 $x_i+2$ 个 ...... 第 $m_i$ 堆有 $x_i+m_i-1$ 个。

两个人轮流从任意一堆石子中取任意数量的石子，把最后一个石子取走的人胜，问先手和后手谁有必胜策略。

$n\le 10^5\\x_i,m_i\le 10^{16}$

题解

这是一种叫做 Nim 的问题，结论：当所有石子堆数量的异或和=0时后手必胜，反之先手必胜。详见 Nim 游戏。

接下来，问题就转化为求若干个连续自然数区间的异或和由于 $x_i,m_i$ 非常之大，暴力不可行。我们注意到一个偶数 $2k$ 和它后面的奇数 $2k+1$ 的异或和满足 $2k\oplus 2k+1=1$。我们将一段自然数两两配对，数出 $1$ 的个数即可。

int qxor(int l, int r) {
    if(r == l) {
        return l;
    }
    if(r == l + 1) {
        return l ^ r;
    }
    int res = 0;
    if(l & 1) {
        res ^= l;
        ++l;
    }
    if((r & 1) == 0) {
        res ^= r;
        --r;
    }
    res ^= (bool)((r - l + 1) & 3);
    return res;
}

CF15D题解

题目大意

给你一个 $n\times m$ 的矩形，你需要从中依次选出若干个 $a\times b$ 矩形直至无法再选择，依次选择的矩形满足以下条件：

此矩形不能和之前的矩形重叠。
这个矩形在所有可选矩形中的花费最小。一个矩形的花费为：此矩形的权值和 $-$ 此矩形最小权值 $\times $ 矩形大小。
如果有多个花费最小的矩形，则优先选行坐标最小的，其次选列坐标最小的。

$n,m\le 10^3$

题解

我们考虑先求出所有矩形的代价。矩形权值和可以用前缀和维护，最小值可以用单调队列 $O(nm)$ 求出。具体的，先对每行单独维护出

$\(mx1_{xy}=\max_{i\in[y-b,y]}\{w[x][i]\}$\) 即向左边延伸长度为 $b$ 的区间中的最小值。接着，对 $mx1$ 维护 $\(mx2_{xy}=\max_{i\in[x-a,x]}\{mx1[i][y]\}$\) 这样，就维护出了任意矩形中的最小值。

将 $(n-a)(m-b)$ 个矩形按代价排序，从小到大选。如果发现当前的矩形和前面的矩形有重叠，就不选，反之则选。

如何判断当前的矩形和前面的矩形是否有重叠呢？一种想法认为可以使用二维树状数组标记矩形的四个角，查询时若整个矩形内没有被标记的点则说明没有重叠的矩形。我就是这么做的，时间复杂度 $O(nm\log n\log m)$，被卡常过不了。这里介绍一种均摊 $O(nm)$ 的做法。

我们发现所有矩形的尺寸相等，因此有如下结论：如果左上角为 $(x_0,y_0)$ 的矩形被选中了，那么左下角 $x\in[x_0-a+1,x_0+a-1],y\in[y_0-b+1,y_0+b-1]$ 的矩形都不能选。我们注意到新增一个矩形造成不能选的（左上角的）位置 $(x,y)$ 是 $ab$ 数量级的。又因为只有矩形被选出后才会对其他矩形造成影响，而且最多选出 $\frac{nm}{ab}$ 个矩形，每次只会对 $ab$ 个位置修改，均摊 $O(nm)$，查询 $O(1)$，可以通过本题。

总结来说，首先发现选出矩形的数量是有限制的，即修改要比查询的次数少很多数量级。我们可以牺牲修改的时间复杂度（均摊 $O(nm)$）而减少查询的时间复杂度（单次 $O(1)$，均摊 $O(nm)$），从而最优化总时间复杂度。