Voting CodeForces

有点意思的题

题意：有n个人投票，每次按照第1个人~第n个人的顺序发言，如果到某个人发言时他已经被禁止发言就跳过，每个人发言时可以禁止另一个人发言或什么也不做。最后只剩下一个人时，那个人的意见就是最终决定的意见。这些人分为D和R两派，也就是每个人有D和R两种意见中的一种，每一派的人都希望自己派的意见成为最终意见。假设每个人都作出最优选择，请根据每个人的派别判断最终决定的意见。

方法：第i个人发言的时候，就按照第i~第n，第1~第i-1的顺序找出第一个出现的与自己不同派别且没有被禁言的人，将其禁言。当只剩下某一派时，显然这一派的意见就是最终意见。

方法虽然简单，但是实现起来会遇到很多困难。

垃圾程序（模拟）1

 #include<cstdio>

 int type[];

 int next1[];//next1[i]表示i之后第一个不同党的位置

 int first1[];//first1[i]表示从前数起第一个i的位置

 int next2[];//next2[i]表示i之后第一个同党的位置

 int temp[];

 bool nok[];

 int n,now;

 int main()

 {

     int i;

     char c;

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

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

     {

         scanf("%c",&c);

         if(c=='D')

             type[i]=;

         else

             type[i]=;

     }

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

     {

         next1[i]=temp[type[i]^];

         temp[type[i]]=i;

     }

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

     {

         next2[i]=first1[type[i]];

         first1[type[i]]=i;

     }

     now=n;

     while(true)

     {

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

         {

             if(nok[i])    continue;

             if(now==)

             {

                 if(type[i]==)

                     printf("D");

                 else

                     printf("R");

                 return ;

             }

             while(nok[next1[i]]==true)    next1[i]=next2[next1[i]];

             while(nok[first1[i]]==true)    first1[i]=next2[next1[i]];

             if(next1[i])

             {

                 nok[next1[i]]=true;

                 next1[i]=next2[next1[i]];

             }

             else if(first1[type[i]^])

             {

                 nok[first1[type[i]^]]=true;

                 first1[type[i]^]=next2[first1[type[i]^]];

             }

             else

             {

                 if(type[i]==)

                     printf("D");

                 else

                     printf("R");

                 return ;

             }

         }

     }

     return ;

 }

垃圾程序（模拟）2

 #include<cstdio>

 int type[];

 int next1[];//next1[i]表示i之后第一个不同党的位置

 int first1[];//first1[i]表示从前数起第一个i的位置

 int next2[];//next2[i]表示i之后第一个同党的位置

 int temp[];

 bool nok[];

 int n,now;

 int main()

 {

     int i;

     char c;

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

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

     {

         scanf("%c",&c);

         if(c=='D')

             type[i]=;

         else

             type[i]=;

     }

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

     {

         next1[i]=temp[type[i]^];

         temp[type[i]]=i;

     }

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

     {

         next2[i]=first1[type[i]];

         first1[type[i]]=i;

     }

     now=n;

     while(true)

     {

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

         {

             if(nok[i])    continue;

             if(now==)

             {

                 if(type[i]==)

                     printf("D");

                 else

                     printf("R");

                 return ;

             }

             while(nok[next1[i]]==true)    next1[i]=next2[next1[i]];

             while(nok[first1[i]]==true)    first1[i]=next2[first1[i]];

             if(next1[i])

             {

                 nok[next1[i]]=true;

                 now--;

                 next1[i]=next2[next1[i]];

             }

             else if(first1[type[i]^])

             {

                 nok[first1[type[i]^]]=true;

                 now--;

                 first1[type[i]^]=next2[first1[type[i]^]];

             }

             else

             {

                 if(type[i]==)

                     printf("D");

                 else

                     printf("R");

                 return ;

             }

         }

     }

     return ;

 }

后来看了题解，发现可以用三个队列按照(i~n，1~i-1)的顺序分别存储（所有的，与当前人同派的，与当前人异派的）且未被禁言的人的序号

然后，又炸了两次...所以要小心

 //第i个人按照先i到n,再1到i-1的顺序找出第一个不同派别的deny

 #include<cstdio>

 #include<queue>

 using namespace std;

 bool type[];

 bool deny[];

 queue<int> q[],q2;

 int n;

 int main()

 {

     int i,now,now2;

     char c;

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

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

     {

         scanf("%c",&c);

         if(c=='R')

             type[i]=;

         q[type[i]].push(i);

         q2.push(i);

     }

     while(!q[].empty()&&!q[].empty())

     {

         now=q2.front();

         q2.pop();

         if(deny[now])    continue;

         //此时now就为当前要发言的（未被禁言的）人

         now2=q[type[now]^].front();//now要禁言的人

         q[type[now]^].pop();//由于now2被禁言，就不放回队列了

         deny[now2]=true;

         q[type[now]].pop();//第二次交加上的，now已经发完言，从队列中退出

         q[type[now]].push(now);//第三次交加上的，并放回到队列尾部

         q2.push(now);

     }

     if(q[].empty())

         printf("R");

     else

         printf("D");

     return ;

 }

巴特西

Voting CodeForces - 749C

最新文章

热门文章