牛客博弈（思维+预处理+秦九韶算法）

佚名 6年前 (2019-04-16) 随笔 1347人围观抢沙发百度已收录

当所有的数字全部变为0时，下一个进行操作的人将无路可走，所以本题的关键在于：

如果k=1，那么比赛永无止境，结果为平局；如果k>1，计算出让所有数字变为0的总共的操作数，根据奇偶性判断，奇数先手胜，偶数后手胜。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

由于数据组数过多，我们选择预处理数组。对于[1, 1e+5]中每一个可能的整数p，[1, 100]中每一个可能的整数k，进行p/k操作，求使p变为0的操作数（根据题意，每一次从集合中删除p时，将增添k个$\lfloor p/k \rfloor$）。

上述操作本质上为求一个深度为$\lceil \log_k p \rceil$的满k叉树节点数，亦即等比数列求和：$k^{0}+k^{1}+k^{2}+...+k^{n-1}$

我们考虑使用秦九韶算法（霍纳法则），对于等比数列，可以归纳为：先乘以k再加1

代码：

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

int l, r, k;
int kp[105][100005];
void pre()
{
    for(int k=2;k<=100;++k){
        for(int p=1;p<=100000;++p){
            int temp=p;
            while(temp){
                temp/=k;
                kp[k][p]=kp[k][p]*k+1;//秦九韶算法，On实现一元n次多项式计算
            }
        }
    }
}
int main()
{
    pre();
    while(cin>>l>>r>>k){
        if(k==1) {cout<<"Draw"<<endl;continue;}
        int ans=0;
        for(int i=l;i<=r;++i)
            ans+=kp[k][i];
        if(ans%2) cout<<"XHRlyb"<<endl;
        else cout<<"Cwbc"<<endl;
    }
    return 0;
}

再插入一个更明显的更亲民的秦九韶算法：

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

int l, r, k;
int kp[105][100005];
void pre()
{
    for(int k=2;k<=100;++k){
        for(int p=1;p<=100000;++p){
            int temp=p;z=0;
            
            ////秦九韶算法，On实现一元n次多项式计算
            while(temp/k) {z++;temp/=k;}//计算最高次次数
            for(int i=z;i>=0;--i) kp[k][p]=kp[k][p]*k+1;
        }
    }
}
int main()
{
    pre();
    while(cin>>l>>r>>k){
        if(k==1) {cout<<"Draw"<<endl;continue;}
        int ans=0;
        for(int i=l;i<=r;++i)
            ans+=kp[k][i];
        if(ans%2) cout<<"XHRlyb"<<endl;
        else cout<<"Cwbc"<<endl;
    }
    return 0;
}