[转]NYOJ-511-移动小球
生活随笔
收集整理的這篇文章主要介紹了
[转]NYOJ-511-移动小球
小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
大學(xué)生程序代寫 struct?Node?? {?? ????int?order;?? ????Node?*left,*right;?? }node[N];?? void?build(int?n)?? {?? ????int?i,order=1;?? ????for(i=1;i<n;i++)?? ????????{?? ????????????node[i].order=i;?? ????????????node[i].right=&node[i+1];?? ????????????node[i+1].left=&node[i];?? ????????}?? ????node[1].left=&node[n];?? ????node[n].right=&node[1];?? ????node[n].order=n;?? }???然后就是A、B操作，下邊敘述一下A操作（將x放在y左邊）的實(shí)現(xiàn)方法： void?A(int?x,int?y)?? {?? ????Node?*p=&node[x],*q=&node[y];?? ????p->left->right=p->right;?? ????p->right->left=p->left;?? ????p->left=q->left;?? ????p->right=q;?? ????q->left->right=p;?? ????q->left=p;?? }???由于交換位置僅改變節(jié)點(diǎn)的左右指針，并沒有改變數(shù)組的下標(biāo)（下標(biāo)其實(shí)與order相同），所以查找球號時(shí)直接用下標(biāo)索引。 #include<stdio.h> ?? const?int?N=10005;?? struct?Node?? {?? ????int?order;?? ????Node?*left,*right;?? }node[N];?? void?build(int?n)?? {?? ????int?i,order=1;?? ????for(i=1;i<n;i++)?? ????????{?? ????????????node[i].order=i;?? ????????????node[i].right=&node[i+1];?? ????????????node[i+1].left=&node[i];?? ????????}?? ????node[1].left=&node[n];?? ????node[n].right=&node[1];?? ????node[n].order=n;?? }?? void?A(int?x,int?y)?? {?? ????Node?*p=&node[x],*q=&node[y];?? ????p->left->right=p->right;?? ????p->right->left=p->left;?? ????p->left=q->left;?? ????p->right=q;?? ????q->left->right=p;?? ????q->left=p;?? }?? void?B(int?x,int?y)?? {?? ????Node?*p=&node[x],*q=&node[y];?? ????p->left->right=p->right;?? ????p->right->left=p->left;?? ????p->right=q->right;?? ????q->right->left=p;?? ????p->left=q;?? ????q->right=p;?? }?? int?main()?? {?? ????int?ncase,n,m,i;?? ????char?cmd;?? ????int?x,y;?? ????scanf("%d",&ncase);?? ????while(ncase--)?? ????{?? ????????scanf("%d%d",&n,&m);?? ????????build(n);?? ????????while(m--)?? ????????{?? ????????????scanf("%*c%c%d%d",&cmd,&x,&y);?? ????????????switch(cmd)?? ????????????{?? ????????????case?'A':?? ????????????????A(x,y);break;?? ????????????case?'B':?? ????????????????B(x,y);break;?? ????????????case?'Q':?? ????????????????printf("%d\n",x?node[y].right->order:node[y].left->order);break;?? ????????????}?? ????????}?? ????}?? ????return?0;?? }?? 其實(shí)此題還可以不用鏈表，對比了一下，時(shí)間相差不大，相比而言非鏈表法更不容易出錯(cuò)。 ??? #include<cstdio> ?? const?int?N=10005;?? struct?xyz?? {?? ????int?prv,nxt;?? }a[N];?? void?build(int?n)?? {?? ????int?i;?? ????for(i=1;i<=n;i++)?? ????????{?? ????????????a[i].prv=i-1;?? ????????????a[i].nxt=i+1;?? ????????}?? ????a[1].prv=n;?? ????a[n].nxt=1;?? }?? void?A(int?x,int?y)?? {?? ????a[a[x].prv].nxt=a[x].nxt;?? ????a[a[x].nxt].prv=a[x].prv;?? ????a[x].nxt=y;?? ????a[x].prv=a[y].prv;?? ????a[a[y].prv].nxt=x;?? ????a[y].prv=x;?? }?? void?B(int?x,int?y)?? {?? ????a[a[x].prv].nxt=a[x].nxt;?? ????a[a[x].nxt].prv=a[x].prv;?? ????a[x].nxt=a[y].nxt;?? ????a[x].prv=y;?? ????a[a[y].nxt].prv=x;?? ????a[y].nxt=x;?? }?? int?main()?? {?? ????int?ncase,n,m,i;?? ????char?cmd;?? ????int?x,y;?? ????scanf("%d",&ncase);?? ????while(ncase--)?? ????{?? ????????scanf("%d%d",&n,&m);?? ????????build(n);?? ????????while(m--)?? ????????{?? ????????????scanf("%*c%c%d%d",&cmd,&x,&y);?? ????????????switch(cmd)?? ????????????{?? ????????????case?'A':?? ????????????????A(x,y);break;?? ????????????case?'B':?? ????????????????B(x,y);break;?? ????????????case?'Q':?? ????????????????printf("%d\n",x?a[y].nxt:a[y].prv);break;?? ????????????}?? ????????}?? ????}?? ????return?0;?? }?? ?????????? 作者：chao1983210400 發(fā)表于2013-7-23 23:52:07 原文鏈接 閱讀：12 評論：0 查看評論
http://acm.nyist.net/JudgeOnline/problem.php?pid=511
這道題很容易想到要構(gòu)建一個(gè)循環(huán)鏈表來確定每個(gè)球的相對位置，就是操作比較繁瑣，考慮情況較多。
首先要?jiǎng)?chuàng)建節(jié)點(diǎn)Node，每個(gè)節(jié)點(diǎn)都有一個(gè)初始順序order，指向左邊的Node*指針left，何指向右邊的Node*指針right。
[cpp] view plaincopyprint?然后給每個(gè)小球附上順序，并建立和左右的聯(lián)系。
[cpp] view plaincopyprint?1.將x左邊節(jié)點(diǎn)的right指針指向x的右邊節(jié)點(diǎn)
2.將x右邊節(jié)點(diǎn)的left指針指向x的左邊節(jié)點(diǎn)
3.將x的right指向y節(jié)點(diǎn)
4.將x的left指向y左邊的節(jié)點(diǎn)
5.將y左邊節(jié)點(diǎn)的right指向x節(jié)點(diǎn)
6.將y的left指向x節(jié)點(diǎn)
實(shí)現(xiàn)代碼：
[cpp] view plaincopyprint?同理可知操作B。
完整代碼如下：
[cpp] view plaincopyprint?思路基本一樣，直接給出代碼：
[cpp] view plaincopyprint?轉(zhuǎn)載于:https://www.cnblogs.com/java20130808/p/3241306.html
總結(jié)
以上是生活随笔為你收集整理的[转]NYOJ-511-移动小球的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 多个反斜杠的消除处理
- 下一篇： UNIX网络编程——UDP回射服务器程序