1418:猴子选大王

Wesley13
• 阅读 676

题目连接(本题目链接失效内容同《围圈报数》):http://ybt.ssoier.cn:8088/problem_show.php?pid=1418

   围圈报数链接:http://ybt.ssoier.cn:8088/problem_show.php?pid=1334

  从队列到循环单链表写了一下午都写不出来,网上查了半天题解发现多数用到而且还用到迭代器(https://blog.csdn.net/u011954296/article/details/51351982),对于我那群没学过的娃来说比较难理解,还有用牛逼的数学公式推到出来只用20行代码就解决问题,反正我是想不到。晚间在家看孩子时,灵光一现,这个是不是可以用“双向循环链表”就可以克服下午遇到的种种问题,于是迅速花半个小时写出,代码很短,理解“双向循环链表”就很容写出了,加上详细注释,独家出品,如有雷同罚款100,仅供参考。但个人还是觉得这种数学的推理是值得推介的(https://www.cnblogs.com/jiu0821/p/4587507.html),一题多解,解后看别人题解,一定是提升算法学习非常有效的学习方法,建议大家多多看看别人的代码。

 1 #include<iostream>
 2 using namespace std;
 3 struct node{
 4     int pre;//存储之前节点下标 
 5     int x;//当前可以数得数 
 6     int nex;//存储之后节点下标 
 7 }q[1000100];//自定义循环双向链表的数据结构
 8             //思考为什么不能用单向循环链表??? 
 9 int main()
10 {
11     int n;
12     cin>>n;
13     for(int i=1; i<=n; i++)//构造循环双向链表 
14     {
15         cin>>q[i].x;
16         if(i==n) q[i].nex=1;
17         else q[i].nex=i+1;
18         if(i==1) q[i].pre=n;
19         else q[i].pre=i-1;
20     }
21     //for(int i=1; i<=n; i++)cout<<q[i].pre<<q[i].x<<q[i].nex<<endl;   //用于测试构造的循环双向链表是否成功 
22     int now=1;//从第一只猴子开始 
23     while(q[now].nex!=now && q[now].pre!=now)//当只剩下最后一只猴子时,他的之前节点和之后节点都指向它自己,于是他就是大王 
24     {
25         int xx=now, yy=q[now].x;//当前开始计数的猴子编号 
26         for(int i=xx; i<xx+yy-1; i++) now=q[now].nex; // 从当前猴子的节点开始报数到<被删除猴子>的节点,此时now为 <被删除猴子>的节点的下标 
27 
28         q[q[now].pre].nex=q[now].nex;//<被删除猴子>之前节点的之后节点更改为<被删除猴子>的之后节点 
29         q[q[now].nex].pre=q[now].pre;//<被删除猴子>之后节点的之前节点更改为<被删除猴子>的之前节点 
30         
31         now=q[now].nex;//更改now为删除猴子的下一个节点重复 
32         
33     }
34     cout<<now;
35     return 0;
36 }

AC后开心的去睡觉觉~~~

点赞
收藏
评论区
推荐文章
待兔 待兔
4个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Wesley13 Wesley13
3年前
hdu2204 Eddy's爱好
原题:点击打开链接(https://www.oschina.net/action/GoToLink?urlhttp%3A%2F%2Facm.hdu.edu.cn%2Fshowproblem.php%3Fpid%3D2204)题意很明确了,即:给你一个正整数N,确定在1到N之间有多少个可以表示成M^K(K1)的数。本题目为容斥原
Stella981 Stella981
3年前
2019 HDOJ Multi
服务器时不时爆炸,有点难受。题目链接:http://acm.hdu.edu.cn/userloginex.php?cid849(https://www.oschina.net/action/GoToLink?urlhttp%3A%2F%2Facm.hdu.edu.cn%2Fuserloginex.php%3Fcid%3D849)
Stella981 Stella981
3年前
Codeforces Round #479 (Div. 3) F. Consecutive Subsequence
标签:DP题目链接(https://www.oschina.net/action/GoToLink?urlhttp%3A%2F%2Fcodeforces.com%2Fcontest%2F977%2Fproblem%2FF)
可莉 可莉
3年前
2019 HDOJ Multi
服务器时不时爆炸,有点难受。题目链接:http://acm.hdu.edu.cn/userloginex.php?cid849(https://www.oschina.net/action/GoToLink?urlhttp%3A%2F%2Facm.hdu.edu.cn%2Fuserloginex.php%3Fcid%3D849)
Stella981 Stella981
3年前
POJ 1195 Mobile phones(二维树状数组)
题目链接:http://poj.org/problem?id1195(https://www.oschina.net/action/GoToLink?urlhttp%3A%2F%2Fpoj.org%2Fproblem%3Fid%3D1195)题意是有四种操作。当n0时:输入一个m表示初始化矩阵(m\m且值都为0)。
Stella981 Stella981
3年前
LOJ6500. 「雅礼集训 2018 Day2」操作(哈希+差分)
题目链接https://loj.ac/problem/6500(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Floj.ac%2Fproblem%2F6500)题解区间取反$01$串的经典套路是差分。我们令$b\_ia\_i\\{\\rmxor
Wesley13 Wesley13
3年前
Java大数统计
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid1316(https://www.oschina.net/action/GoToLink?urlhttp%3A%2F%2Facm.hdu.edu.cn%2Fshowproblem.php%3Fpid%3D1316)题目描述:!(https://o
Wesley13 Wesley13
3年前
BZOJ3168. [HEOI2013]钙铁锌硒维生素(线性代数+二分图匹配)
题目链接https://www.lydsy.com/JudgeOnline/problem.php?id3168(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fwww.lydsy.com%2FJudgeOnline%2Fproblem.php%3Fid%3D3168)题解
Stella981 Stella981
3年前
Gym101889B. Buggy ICPC(打表)
比赛链接:传送门(https://www.oschina.net/action/GoToLink?urlhttp%3A%2F%2Fcodeforces.com%2Fgym%2F101889)题目:!(https://oscimg.oschina.net/oscnet/54993c8b5f90544695020de0694c1