当前位置: 代码迷 >> 综合 >> uva12657
  详细解决方案

uva12657

热度:30   发布时间:2023-12-06 21:54:22.0
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
using namespace std;
const int maxn=101000;
const int N=10;
//涉及到复杂数据结构的一些固定化操作,往往设计成函数模块int right1[maxn],left1[maxn];void link(int L,int R){right1[L]=R;left1[R]=L;
} int main(){int n,m;int kase=0;while(scanf("%d%d",&n,&m)!=EOF){memset(left1,0,sizeof(left1)); memset(right1,0,sizeof(right1));for(int i=1;i<=n;i++){left1[i]=i-1;right1[i]=(i+1)%(n+1);}left1[0]=n,right1[0]=1;int op,X,Y,inv=0;while(m--){scanf("%d",&op);if(op==4) inv=!inv;else{scanf("%d%d",&X,&Y);if(op==3&&right1[Y]==X)   swap(X,Y);if(inv&&op!=3) op=3-op;if(op==1&&X==left1[Y]) continue;if(op==2&&right1[Y]==X) continue;int XL=left1[X], XR=right1[X], YL=left1[Y], YR=right1[Y];if(op==1) { link(XL,XR); link(YL,X); link(X,Y); }else if(op==2) { link(XL,XR); link(Y,X); link(X,YR); }else if(op==3) {if(right1[X]==Y) { link(XL,Y); link(Y,X); link(X,YR);   }else { link(XL,Y);  link(Y,XR); link(YL,X); link(X,YR); }}}}int b=0;long long ans=0;for(int i=1;i<=n;i++){b=right1[b];if(i%2==1) ans+=b;}if(inv&&n%2==0) ans=(long long)n*(1+n)/2-ans;printf("Case %d: %lld\n",++kase,ans);}return 0;
}

 

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>using namespace std;
const int maxn=100100;
const int N=10;int right1[maxn],left1[maxn];void link(int L,int R){right1[L]=R,left1[R]=L;
}int main(){int n,m;  int kase=0;while(scanf("%d%d",&n,&m)!=EOF){memset(left1,0,sizeof(left1)); memset(right1,0,sizeof(right1));for(int i=1;i<=n;i++){left1[i]=i-1;right1[i]=(i+1)%(n+1);}left1[0]=n,right1[0]=1;int op,X,Y;		int inv=0;while(m--){scanf("%d",&op);if(op==4) inv=!inv;else{scanf("%d%d",&X,&Y);if(op==3) ;if(inv&&op!=3) op=3-op;if(op==2&&right1[Y]==X) continue;if(op==1&&left1[Y]==X) continue;int LX=left1[X],RX=right1[X],LY=left1[Y],RY=right1[Y];if(op==1){link(LX,RX);link(LY,X);link(X,Y);}else if(op==2){link(LX,RX); link(Y,X);  link(X,RY);}else if(op==3){if(right1[X]==Y){link(LX,Y); link(Y,X); link(X,RY);}else if(right1[Y]==X){link(LY,X); link(X,Y); link(Y,RX);}else {link(LX,Y); link(Y,RX); link(LY,X); link(X,RY);}}}}int b=0;long long ans=0;for(int i=1;i<=n;i++){b=right1[b];if(i%2) ans+=b;}if(inv&&n%2==0) ans=(long long)n*(1+n)/2-ans;printf("Case %d: %lld\n",++kase,ans);}return 0;
}

 

  相关解决方案