题解：P11056 Fire and Big

wwz1428572008 · 2024-09-15 20:59:50 · 题解

考试时写了一个 O(n\sqrt{n}) 的做法，但常数比较大，只有 75 分。考完经过改进，AC 了本题。

做法

维护对于每个 n 先手必胜还是后手必胜。如果一个点可以在取后转换到后手必胜点，则它是先手必胜点，否则它是后手必胜点。所以可以在每个后手必胜点处向后更新，并记录。

由于任意 n 的倍数都可取，所以让一个数组记录哪些模 n 的余数已经有了后手必胜点。另一个数组记录接下来的后手必胜点。通过类似于滚动数组的优化，可以将空间优化到 O(n)。

代码

#include<iostream>
#include<cstdio>
#include<unordered_set>
using namespace std;
bool ok[500002];
bool w[500002];
unordered_set<int> s;
int read()
{
    char ch=getchar();
    int ret=0;
    while(!isdigit(ch))
        ch=getchar();
    while(isdigit(ch))
    {
        (ret*=10)+=ch-'0';
        ch=getchar();
    }
    return ret;
}
int main()
{
    int t=read(),n=read();
    int cur=0;
    for(int i=1;i<=n;i++)
    {
        while(ok[cur%n]||w[cur%n])
        {
            w[cur%n]=0;
            cur++;
        }   
        ok[cur%n]=1;
        s.insert(cur);
        for(int j=1;j*j<n;j++)
            w[(cur+j*j)%n]=1;
    }
    int x;
    while(t--)
    {
        x=read();
        if(s.count(x))
            putchar('B');
        else
            putchar('F');
    }
    return 0;
}