CF676E：The Last Fight Between Human and AI

人类和电脑在一个多项式上进行博弈，多项式的最高次项已知，一开始系数都不确定。电脑先开始操作，每次操作可以确定某次项的系数，这个系数可以是任意实数。给出一个博弈中间状态，最后如果这个多项式被x-K整除就算人类赢，问人类是否有可能赢。n<=1e5，K和所有给出的系数的绝对值在1e4内，不确定的系数用？表示。

这个读入有点坑爹。。。

要使，做一下除法，余数大概长这个样子

问题即有没有可能使L为0。

（一）K=0时，决胜关键就在a0，如果a0确定了并且不为0那就完了，如果a0没确定，看轮到谁，轮到人类赢，轮到电脑输。

（二）K≠0时

（1）如果有系数未确定，看最后一步是谁走，如果是人类走，则最后相当于解一个一元一次方程，由于k不为0因此一定有解，如果电脑走则一定输。

（2）如果系数都确定了，就要检验这个式子是否为0，由于次数太高无法计算，因此取几个模数检验一下模完是否都是0，用秦九韶计算。

 #include<stdio.h>

 #include<string.h>

 #include<stdlib.h>

 #include<algorithm>

 //#include<assert.h>

 #include<math.h>

 #include<iostream>

 using namespace std;

 int n,k;

 #define maxn 100011

 #define LL long long

 const int mod[]={,,,,};

 int a[maxn];bool ok[maxn];char s[];

 int main()

 {

     scanf("%d%d",&n,&k);

     int cnt=;

     memset(ok,,sizeof(ok));

     for (int i=;i<=n;i++)

     {

         scanf("%s",s);

         if (s[]=='?') cnt++,ok[i]=;

         else

         {

             int t=;if (s[]=='-') t=-;

             int tmp=;for (int j=(s[]=='-');j<strlen(s);j++) tmp=tmp*+s[j]-'';

             a[i]=tmp*t;

         }

     }

     bool ans=;

     if (k==)

     {

         if (ok[])

         {

             if ((n+-cnt)&) ans=;

             else ans=;

         }

         else if (a[]==) ans=;else ans=;

     }

     else

     {

         if (cnt)

         {

             if (n&) ans=;

             else ans=;

         }

         else

         {

             bool flag=;

             for (int j=;j<;j++)

             {

                 LL ans=;

                 for (int i=n;i>=;i--)

                 {

 //                    cout<<ans<<endl;

                     ans=(ans*k+a[i])%mod[j];

                 }

 //                cout<<ans<<endl;

                 if (ans) flag=;

             }

             if (flag) ans=;

             else ans=;

         }

     }

     printf(ans?"Yes\n":"No\n");

     return ;

 }

巴特西

CF676E：The Last Fight Between Human and AI

最新文章

热门文章