题解：SP27367 VECTAR11 - Game of Squares

changkyle · 2026-10-20 16:51:23 · 题解

题意

双方取数，每次能取一个平方数，取到对方不能再取则获胜，求先手有没有必胜策略。

思路

可以在询问之前把 10^6 之内的所有询问提前处理，所以对于每一次询问的回答是 O(1) 的。

重点：如何处理。由于越取越少，所以只能由小数值推向大数值，考虑 dp。若当前枚举到的数字减去任意一个小于当前数字的完全按平方数后必败，则当前必胜。若没有此类情况，则当前必败。 ::::success[代码]

#include<bits/stdc++.h>
using namespace std;
int T;  
int f[1000006];
int main(){
    cin>>T;
    for(int i=1;i<=1000006;i++){
        f[i]=0;
    }
    for(int i=1;i<=1000006;i++){
        for(int j=1;j*j<=i;j++){
            if(f[i-j]==0){
                f[i]=1;
                break;
            }
        }
    }
    while(T--){
        int i;
        cin>>i;
        if(f[i]==1){
            cout<<"Win\n";
        }
        else{
            cout<<"Lose\n"; 
        }
    }
    return 0;
}

:::: 也可以考虑打表（不细讲，这里用的是正解打表）。

令获胜为 1，失败为 0。

#include<bits/stdc++.h>
using namespace std;
int T;  
int f[1000006];
int main(){
    //cin>>T;
    for(int i=1;i<=1000006;i++){
        f[i]=0;
    }
    for(int i=1;i<=1000006;i++){
        for(int j=1;j*j<=i;j++){
            if(f[i-j]==0){
                f[i]=1;
                break;
            }
        }
    }
    for(int i=0;i<=1000000;i++){
        if(f[i]==1){
            cout<<"1,";
        }
        else{
            cout<<"0,"; 
        }
    }
    return 0;
}