CCF ——游戏

墨蓝 2022-05-29 05:15 177阅读 0赞

<table style="margin:0px;padding:0px;color:rgb(0,0,0);font-family:'宋体';font-size:14px;text-align:center;background:rgb(192,214,221);"> 
 <tbody style="margin:0px;padding:0px;"> 
  <tr style="margin:0px;padding:0px;"> 
   <td style="margin:0px;padding:12px;background:rgb(248,248,248);text-align:center;width:100px;vertical-align:middle;color:rgb(0,87,164);">试题编号：</td> 
   <td style="margin:0px;padding:12px;">201712-2</td> 
  </tr> 
  <tr style="margin:0px;padding:0px;"> 
   <td style="margin:0px;padding:12px;background:rgb(248,248,248);text-align:center;width:100px;vertical-align:middle;color:rgb(0,87,164);">试题名称：</td> 
   <td style="margin:0px;padding:12px;background:rgb(255,255,255);">游戏</td> 
  </tr> 
  <tr style="margin:0px;padding:0px;"> 
   <td style="margin:0px;padding:12px;background:rgb(248,248,248);text-align:center;width:100px;vertical-align:middle;color:rgb(0,87,164);">时间限制：</td> 
   <td style="margin:0px;padding:12px;">1.0s</td> 
  </tr> 
  <tr style="margin:0px;padding:0px;"> 
   <td style="margin:0px;padding:12px;background:rgb(248,248,248);text-align:center;width:100px;vertical-align:middle;color:rgb(0,87,164);">内存限制：</td> 
   <td style="margin:0px;padding:12px;background:rgb(255,255,255);">256.0MB</td> 
  </tr> 
  <tr style="margin:0px;padding:0px;"> 
   <td style="margin:0px;padding:12px;background:rgb(248,248,248);text-align:center;width:100px;vertical-align:middle;color:rgb(0,87,164);">问题描述：</td> 
   <td style="margin:0px;padding:12px;"> 
    <div style="margin:12px 0px 20px;padding:0px;font-weight:bold;">
      问题描述 
    </div> 
    <div style="margin:0px 0px 0px 32px;padding:0px;">
      　　有 
     <span style="margin:0px;padding:0px;">n</span>个小朋友围成一圈玩游戏，小朋友从1至 
     <span style="margin:0px;padding:0px;">n</span>编号，2号小朋友坐在1号小朋友的顺时针方向，3号小朋友坐在2号小朋友的顺时针方向，……，1号小朋友坐在 
     <span style="margin:0px;padding:0px;">n</span>号小朋友的顺时针方向。 
     <br style="margin:0px;padding:0px;">　　游戏开始，从1号小朋友开始顺时针报数，接下来每个小朋友的报数是上一个小朋友报的数加1。若一个小朋友报的数为 
     <span style="margin:0px;padding:0px;">k</span>的倍数或其末位数（即数的个位）为 
     <span style="margin:0px;padding:0px;">k</span>，则该小朋友被淘汰出局，不再参加以后的报数。当游戏中只剩下一个小朋友时，该小朋友获胜。 
     <br style="margin:0px;padding:0px;">　　例如，当n=5, k=2时： 
     <br style="margin:0px;padding:0px;">　　1号小朋友报数1； 
     <br style="margin:0px;padding:0px;">　　2号小朋友报数2淘汰； 
     <br style="margin:0px;padding:0px;">　　3号小朋友报数3； 
     <br style="margin:0px;padding:0px;">　　4号小朋友报数4淘汰； 
     <br style="margin:0px;padding:0px;">　　5号小朋友报数5； 
     <br style="margin:0px;padding:0px;">　　1号小朋友报数6淘汰； 
     <br style="margin:0px;padding:0px;">　　3号小朋友报数7； 
     <br style="margin:0px;padding:0px;">　　5号小朋友报数8淘汰； 
     <br style="margin:0px;padding:0px;">　　3号小朋友获胜。 
     <br style="margin:0px;padding:0px;"> 
     <br style="margin:0px;padding:0px;">　　给定 
     <span style="margin:0px;padding:0px;">n</span>和 
     <span style="margin:0px;padding:0px;">k</span>，请问最后获胜的小朋友编号为多少？ 
    </div> 
    <div style="margin:12px 0px 20px;padding:0px;font-weight:bold;">
      输入格式 
    </div> 
    <div style="margin:0px 0px 0px 32px;padding:0px;">
      　　输入一行，包括两个整数 
     <span style="margin:0px;padding:0px;">n</span>和 
     <span style="margin:0px;padding:0px;">k</span>，意义如题目所述。 
    </div> 
    <div style="margin:12px 0px 20px;padding:0px;font-weight:bold;">
      输出格式 
    </div> 
    <div style="margin:0px 0px 0px 32px;padding:0px;">
      　　输出一行，包含一个整数，表示获胜的小朋友编号。 
    </div> 
    <div style="margin:12px 0px 20px;padding:0px;font-weight:bold;">
      样例输入 
    </div> 
    <div style="margin:0px 0px 0px 32px;padding:0px;font-family:'Courier New';font-size:16px;">
      5 2 
    </div> 
    <div style="margin:12px 0px 20px;padding:0px;font-weight:bold;">
      样例输出 
    </div> 
    <div style="margin:0px 0px 0px 32px;padding:0px;font-family:'Courier New';font-size:16px;">
      3 
    </div> 
    <div style="margin:12px 0px 20px;padding:0px;font-weight:bold;">
      样例输入 
    </div> 
    <div style="margin:0px 0px 0px 32px;padding:0px;font-family:'Courier New';font-size:16px;">
      7 3 
    </div> 
    <div style="margin:12px 0px 20px;padding:0px;font-weight:bold;">
      样例输出 
    </div> 
    <div style="margin:0px 0px 0px 32px;padding:0px;font-family:'Courier New';font-size:16px;">
      4 
    </div> 
    <div style="margin:12px 0px 20px;padding:0px;font-weight:bold;">
      数据规模和约定 
    </div> 
    <div style="margin:0px 0px 0px 32px;padding:0px;">
      　　对于所有评测用例，1 ≤&nbsp; 
     <span style="margin:0px;padding:0px;">n</span>&nbsp;≤ 1000，1 ≤&nbsp; 
     <span style="margin:0px;padding:0px;">k</span>&nbsp;≤ 9。 
    </div> 
    <div style="margin:0px 0px 0px 32px;padding:0px;"> 
     <br> 
    </div></td> 
  </tr> 
 </tbody> 
</table>

#include <stdio.h>
    #include <stdlib.h>
    typedef struct node
    {
        int data;
        struct node *next;
    }*LinkList,Lnode;
    void TraverseList(LinkList h, int M);
    void ListDelete(LinkList h,int M,int k);
    
    int main()
    {
        int n,k;
        scanf("%d %d",&n,&k);
        LinkList head;
        head = (LinkList)malloc(sizeof(Lnode));
        head->next = NULL;
        int i;
        LinkList p,q;
        q = head;
        for(i=1; i<=n; i++)
        {
            p = (LinkList)malloc(sizeof(Lnode));
            p->data = i;
            q->next =p;
            q = p;
        }
        p->next = head->next;
        //TraverseList(head,n);
        if(k==1)
            printf("%d\n",n);
            else if(n == 1)
                printf("%d\n",1);
        else
    
            ListDelete(head,n,k);
    
    
    
        return 0;
    }
    void TraverseList(LinkList h, int M)
    {
        int i = 1;
        LinkList p = h->next;
        printf("参与的人的编号为：\n");
        while (i<=M)
        {
            printf("%d\t", p->data);
            p = p->next;
            i++;
        }
        printf("\n");
    }
    
    void ListDelete(LinkList h,int M,int k)
    {
    
        int num = 1;
        LinkList p = h,q;
        while(M>1)
        {
            //printf("num == %d\n",num);
            //printf("未更改前：%d\n",p->data);
            if(num%k == 0 ||num%10 ==k)
            {
                q =p->next;
                p ->next = q->next;
                //printf("更改后：%d\n",p->data);
                //printf("淘汰%d号\n",q->data);
                free(q);
                num++;
                M--;
            }
    
            num++;
            p = p->next;
        }
        //printf("***************获胜者为：%d号***************",p->data);
        printf("%d\n",p->data);
    }

以上的代码只得了60分，没能来的及更改，待以后再改

附正确代码：

#include <iostream>
    #include <queue>
    using namespace std;
    int main() {
        int n=0,k=0,i=0,num=1;
        cin>>n>>k;
        queue<int, deque<int> > q; //定义一个队列来保存报数
        for(i=1;i<=n;i++) { //初始化队列
            q.push(i);
        }
        while(q.size()>1) { //判断队列是否只剩下一个元素
            int top = q.front(); //保存当前队首的元素
            q.pop();    //将当前队首元素值从队列中删除
            if(num%k!=0 && num%10!=k) { //判读当前的报数是否满足游戏规则
                q.push(top);    //若满足，则将队首重新插入队尾，等待下一轮游戏
            }
            num++;  //报数+1
        }
        cout<<q.front();    //输出队列q中仅剩的一个元素
        return 0;
    }

转载自：http://blog.csdn.net/Jason_first/article/details/79111163