[COCI2008-2009#1] JEZ 题解

Bbaka · 2022-10-01 11:13:48 · 题解

题意

给定一个由 r \times c 个方格组成的矩形，左上角编号为 (0,0)，右下角编号为 (r-1,c-1) ，对于一个方格 (x,y) ，如果 x+y=x \bigoplus y 则方格为灰色，否则为白色。

然后一个人按照下图规律从 (0,0) 斜着走向 (r-1,c-1)，问他走到第 k 个格子时总共走过了多少灰色格子。

思路

先假设 r \leq c，对于 r>c 的情况可以将 r,c 交换，然后改变出发的方向即可。

因为人是斜着走的，我们可以直接从斜向考虑，对于一条斜线，上面所有的 x+y 都是相等的，我们记为 S，这样就只需要找有多少 x,y 满足 x \bigoplus y=S。

因为异或的性质，S 二进制如果某一位为 1 ，那么 x 和 y 中该位只能有一个 1，如果某一位为 0 ，那么 x 和 y 该位置要么同为 0 要么同为 1，如果两个位置同为 1，而且在 S 中该位置左边一位为 0 ，因为相加进位的关系，x 和 y 中这一位有且只有一个 1 才能保证 x+y=S，但是这一位异或就不可能为 0，同理，如果左边一位为 1 时也不合法，故 S 二进制下如果某一位为 0， x 和 y 中该位也只能为 0。

也就是说对于 S 的每一位，如果为 0，那么 x 和 y 这一位只能为 0，否则 x 和 y 这一位只存在一个 1，记 n 为 S 二进制下 1 的数目，对于 x 只有这一位选不选 1 ，故这条斜线上灰色格子的数量最大值为 2^n。

而当我们从 (0,y) 走到 (x,y-x) 时，所以说如果要求出途中经过的灰色格子数，我们可以先找到一个 x' 满足 x' \leq x 且 x' 的二进制下每一位 1 在 y 中该位置也为 1 ，然后将 x' 的二进制下和 y 同时为 0 的位置去掉，此时得到的数字就是在范围内你每一位选择选或者不选得到的答案数，将这个数加上一，也就是全不选的操作，就是路径上灰色格子的数目了。

int Fun(int y, int x) {
    int num = 0, res = 1;
    while (y) {  //找到y中每一位1并记录对应的值
        if (y & 1) {
            Bit[num] = res;
            num++;
        }
        y >>= 1;
        res <<= 1;
    }
    int tmp = 0;  // tmp记录格子数
    for (int i = num - 1; i >= 0; --i) {
        if (x - Bit[i] >= 0) {  //这里可以找到最大的灰色格子位置
            x -= Bit[i];
            tmp = tmp | (1 << (i));  //因为记录了y中每一位1，所以说直接可以求出最终答案数
        }
    }
    ++tmp; //最后加上全不选的答案
    return tmp;
}

这样我们就可以求出路径上每一条走满的斜线上灰色格子数，对于最后可能走不满的斜线，可以直接暴力求解，也可以做差求解即可。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
int Bit[128];
int Fun(int y, int x) {
    int num = 0, res = 1;
    while (y) {  //找到y中每一位1并记录对应的值
        if (y & 1) {
            Bit[num] = res;
            num++;
        }
        y >>= 1;
        res <<= 1;
    }
    int tmp = 0;  // tmp记录格子数
    for (int i = num - 1; i >= 0; --i) {
        if (x - Bit[i] >= 0) {  //这里可以找到最大的灰色格子位置
            x -= Bit[i];
            tmp = tmp | (1 << (i));  //因为记录了y中每一位1，所以说直接可以求出最终答案数
        }
    }
    ++tmp;  //最后加上全不选的答案
    return tmp;
}
signed main() {
    int r, c, k;
    int Now = 0;
    int ans = 0;
    bool dirt = true;
    scanf("%lld %lld %lld", &r, &c, &k);
    if (c < r) {
        swap(c, r);
        dirt = false;
    }
    --r;
    --c;
    for (int i = 0; i <= c; ++i) {  //分两部分解决，第一部分是从顶部开始的斜线
        int step = min(r, i) + 1;
        int cnt = Fun(i, min(r, i));
        if (Now + step < k) {
            Now += step;
            ans += cnt;
        } else {
            if (dirt) {
                int x = min(i, r);
                int y = i - x;
                while (Now < k) {
                    if (x + y == (x ^ y))
                        ++ans;
                    x--;
                    y++;
                    ++Now;
                }
            } else {
                int x = 0;
                int y = i;
                while (Now < k) {
                    if (x + y == (x ^ y))
                        ++ans;
                    x++;
                    y--;
                    ++Now;
                }
            }
            break;
        }
        dirt ^= 1;
    }
    if (Now == k) {
        printf("%lld\n", ans);
        return 0;
    }
    for (int i = 1; i <= r; ++i) {  //第二部分是从右侧开始的斜线
        int step = r - i + 1;
        int cnt = Fun(c + i, r) - Fun(c + i, i - 1);
        if (Now + step < k) {
            Now += step;
            ans += cnt;
        } else {
            if (dirt) {
                int x = r;
                int y = c - (r - i);
                while (Now < k) {
                    if (x + y == (x ^ y))
                        ++ans;
                    x--;
                    y++;
                    ++Now;
                }
            } else {
                int x = i;
                int y = c;
                while (Now < k) {
                    if (x + y == (x ^ y))
                        ++ans;
                    x++;
                    y--;
                    ++Now;
                }
            }
            break;
        }
        dirt ^= 1;
    }
    printf("%lld\n", ans);
}