首页 > 代码库 > UVA 12657 Boxes in a Line

UVA 12657 Boxes in a Line

2024-07-12 18:45:18   217人阅读

双向链表

注意：如果算法是最后处理翻转情况时，注意指令4翻转后1,2两个指令也要翻转处理；

　　　指令3 中交换盒子要注意两个盒子相邻的情况

 

 

 1 #include <iostream> 2 #include <cstring> 3 using namespace std; 4  5 int ri[100010],le[100010]; 6  7 void link (int l,int r){ 8     ri[l]=r;le[r]=l; 9 }10 11 void moveleft (int l,int r){12     link (le[l],ri[l]);13     link (le[r],l);14     link (l,r);15 }16 17 void moveright (int l,int r){18     link (le[l],ri[l]);19     link (l,ri[r]);20     link (r,l);21 }22 23 void exchange (int l,int r){24     int ll,rl,lr,rr;25     ll=le[l];rl=ri[l];lr=le[r];rr=ri[r];26     if (ll==r){27         link (lr,l);link (l,r);link (r,rl);28     }29     else if (l==lr){30         link (ll,r);link (r,l);link (l,rr);31     }32     else {33         link (ll,r);link (r,rl);34         link (lr,l);link (l,rr);35     }36 }37 38 int main (){39     int n,m,kase=0,inv;40     while (cin>>n>>m){41         inv=0;42         memset (ri,0,sizeof ri);43         memset (le,0,sizeof le);44         for (int i=0;i<=n;i++)45             link (i,i+1);46         for (int i=0;i<m;i++){47             int c;48             cin>>c;49             if (c==4)50                 inv++;51             else {52                 int x,y;53                 cin>>x>>y;54                 if (x==y)55                     continue ;56                 if (inv%2)　　//经过指令4后指令1,2也要翻转处理；57                     c=3-c;　　58                 if (c==1){59                     moveleft (x,y);60                 }61                 else if (c==2){62                     moveright (x,y);63                 }64                 else {65                     exchange (x,y);66                 }67             }68             //int temp=0;69             //for (int i=ri[0];i<=n&&temp<n;i=ri[i]){70             //    cout<<i<<" ";71             //    temp++;72             //}73         }74         long long ans=0;75         int f;76         if (n%2)77             f=0;78         else f=inv%2;79         int temp=0;80         for (int i=ri[0];i<=n&&temp<n;i=ri[i]){// cout<<ri[i]<<" ";81             if (temp%2==f){82                 ans+=i;83             }84             temp++;85         }86         cout<<"Case "<<++kase<<": ";87         cout<<ans<<endl;88     }89     return 0;90 }


联系
我们