P6429 [COCI2008-2009#1] JEZ 题解

· · 题解

原题链接

分析

看到题目的第一眼，发现这个人的走法比较鬼魅，但是我们考虑拆成一条条斜着走的路径。

对于当前 n 行 m 列的矩形，令 n \le m，我们发现第 1 \sim n 条路径的长度递增，第 n+1 \sim m 条路径的长度达到最大并且一直保持不变， 第 m + 1 \sim n + m - 1 条路径的长度递减。记录路径的端点，并用差分数组维护，我们就可以快速找到每一行可以走到的最右边的数是多少。

现在需要快速得到，对于一个数 x，有多少在 [0,y] 之间的数满足 x\oplus y=x+y。转化一下，我们发现只要 x 和 y 的二进制位上有至少一位都为 1，那么就不满足条件。我们求出不合法数的总和，答案就是 k 减去不合法数。那么对于从高到低的第 i 位，如果 y 的第 i 位是 0，跳过，找下一位。当前 y 的第 i 位是 1，我们假定这一位是 0，那么后面的位子就必须要有一个公共 1，简单计数。如果 x 的第 i 位也是 1，那么 y 就可以不用找了，因为已经找到一个 1 了，后面的数直接累加到答案里面。

具体实现可以看代码，总时间复杂度 O(n \log^2 V)，V 是值域大小。

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 1e6 + 10;
int n, m, d[N];
ll k, tot, step;

inline int pos(int x, int i) {
    return (x >> i - 1) & 1;//位运算找到 x 的第 i 位是 0 还是 1
}

inline int work(int x, int y) {//这里 x 和 y 是反着的
    int ans = 0;
    for (int i = 21; i; i--) {
        if (!pos(x, i)) continue;
        int cnt = 0;//记录 1 的个数
        for (int j = i - 1; j; j--) cnt += pos(y, j);
        ans += (1 << (i - 1 - cnt)) * ((1 << cnt) - 1);//0 的位子上随便选，1 的位子至少有一个 1
        if (!pos(y, i)) continue;
        for (int j = i - 1; j; j--)
            if (pos(x, j)) ans += 1 << (j - 1);
        ans++;//加上后面全部选 0 的
        return ans;
    }
    return ans;
}

int main() {
    cin >> n >> m >> k;
    int l, r, pos = 1;
    while (tot < k) {
        int cnt = (pos > n) + (pos > m);//判断路径的长度如何变化
        if (cnt == 0) step++;
        if (cnt == 2) step--;
        l = max(1, pos - m + 1);
        r = min(n, pos);//寻找端点
        step = min(step, k - tot);
        tot += step;//最多走 k 步
        if (pos & 1) d[r - step + 1]++, d[r + 1]--;
        else d[l]++, d[l + step - 1 + 1]--;//差分
        pos++;//奇偶性判断走的方向
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++, d[i] += d[i - 1])
        if (d[i]) ans += work(d[i] - 1, i - 1);//注意值域是从 0 开始的
    cout << k - ans;//总数减去不合法数
    return 0;
}