ACM模版

描述

题解

先不说题，先来吐槽一下 51Nod 的 bug，同样的代码，不一样的头文件，一个是 stdio.h 一个是 cstdio，可是时间差能达到近三倍……这让我很惆怅，如果说统一都是这样的话，我也就是习惯了，不幸的是，这种情况只是有时候出现，换一种代码提交，还是同样的测试，时间却又一样了（相差无几）……实在是不理解啊！

这个题一开始我是直接拿 f(3, 2) 试了试，没有发现啥好东西，继续试下去也没有什么发现，后来发现自己弄错了方法……正确的推导方式是这样打开的：

f[i][j]=f[i−1][j] Xor f[i][j−1]=f[i−2][j] Xor f[i−1][j−1] Xor f[i−1][j−1] Xor f[i][j−2]=f[i−2][j] Xor f[i][j−2]

以此类推，最后会获得：

f[i][j]=f[i−131072][j] Xor f[i][j−131072]

所以我们只需要预处理一下就好了，最后直接输出对应的结果就行了（代码 ONE）。

但是这个方法比较耗时，rank 1 的大神的代码（代码 Two）是定义了一个 100∗100 的矩阵来存储 [131072…131172][131072…131172] ，也是预处理一下即可，不过他的预处理函数我看得不是太懂……如果哪位朋友看懂了请告知我一下，让我也涨涨姿势吧！

代码

One：

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

const int MAXN = 131072;
const int MAXM = 100;
const int MAXA = MAXM + 10;
const int MAXB = MAXN + MAXM;
const int MAXC = MAXN + MAXM + 10;

int b[MAXA][MAXC];
int b_[MAXC][MAXA];

void init()
{
    for (int i = 2; i <= MAXM; i++)
    {
        for (int j = 2; j <= MAXB; j++)
        {
            b[i][j] = b[i - 1][j] ^ b[i][j - 1];
        }
    }
    for (int i = 2; i <= MAXB; i++)
    {
        for (int j = 2; j <= MAXM; j++)
        {
            b_[i][j] = b_[i - 1][j] ^ b_[i][j - 1];
        }
    }
}

int main()
{
    memset(b, 0, sizeof(b));
    memset(b_, 0, sizeof(b_));

    int a;
    for (int i = 2; i <= MAXB; i++)
    {
        scanf("%d", &a);
        b[1][i] = a;
        if (i >= 2 && i <= MAXM)
        {
            b_[1][i] = a;
        }
    }

    for (int i = 2; i <= MAXB; i++)
    {
        scanf("%d", &a);
        b_[i][1] = a;
        if (i >= 2 && i <= MAXM)
        {
            b[i][1] = a;
        }
    }

    init();

    int Q;
    scanf("%d", &Q);

    int n, m;
    for (int i = 0; i < Q; i++)
    {
        scanf("%d%d", &n, &m);
        cout << (b[n][MAXN + m] ^ b_[MAXN + n][m])<< endl;
    }

    return 0;
}

Two：

#include <stdio.h>

const int MAXN = 131072;
const int MAXM = MAXN + 100;
const int MAXA = MAXM + 10;
const int MAXB = 100;
const int MAXC = MAXB + 10;


int a[MAXA], b[MAXA];
int c[MAXC][MAXC];

inline int get_c(int x, int y)
{
    int ret = 0;
    for (int i = 2; i <= y; ++i)
    {
        if (((x - 2 + y - i) & (x - 2)) == x - 2)   // ???
        {
            ret ^= a[i];
        }
    }
    for (int i = 2; i <= x; ++i)
    {
        if (((x - i + y - 2) & (y - 2)) == y - 2)   // ???
        {
            ret ^= b[i];
        }
    }

    return ret;
}

int main()
{
    for (int i = 2; i <= MAXM; ++i)
    {
        scanf("%d", a + i);
    }
    for (int j = 2; j <= MAXM; ++j)
    {
        scanf("%d", b + j);
    }

    for (int i = 1; i <= MAXB; ++i)
    {
        c[0][i] = get_c(MAXN, i + MAXN);
    }
    for (int i = 1; i <= MAXB; ++i)
    {
        c[i][0] = get_c(i + MAXN, MAXN);
    }

    for (int i = 1; i <= MAXB; ++i)
    {
        for (int j = 1; j <= MAXB; ++j)
        {
            c[i][j] = c[i - 1][j] ^ c[i][j - 1];
        }
    }

    int Q;
    scanf("%d", &Q);

    int n, m;
    while (Q--)
    {
        scanf("%d%d", &n, &m);
        printf("%d\n", c[n][m]);
    }

    return 0;
}