UVa12657 Boxes in a Line [双向链表]

题目链接: https://vjudge.net/problem/UVA-12657

用双向链表来模拟操作。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long ll;

const int maxn=100005;

int n,m,op,X,Y,inv,kase=0;
int Left[maxn],Right[maxn];

inline void link(const int &n1,const int &n2){
	Right[n1]=n2,Left[n2]=n1;
}

int main(){
//	freopen("temp.in","r",stdin);
	while(scanf("%d%d",&n,&m)==2){
		inv=0;
		for(int i=1;i<=n;i++){
			Left[i]=i-1;
			Right[i]=(i+1)%(n+1);
		}
		Right[0]=1,Left[0]=n;
		while(m--){
			scanf("%d",&op);
			if(op==4)  inv=!inv;
			else{
				scanf("%d%d",&X,&Y);
				if(op==3&&Right[Y]==X)  swap(X,Y);
				if(op!=3&&inv)  op=3-op;
				if(op==1&&X==Left[Y])  continue;
				if(op==2&&X==Right[Y])  continue;
				
				int LX=Left[X],RX=Right[X],LY=Left[Y],RY=Right[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(Right[X]==Y)
						link(LX,Y),link(Y,X),link(X,RY);
					else
						link(LX,Y),link(Y,RX),link(LY,X),link(X,RY);
				}
			}
		}
		int b=0;
		ll ans=0;
		for(int i=1;i<=n;i++){
			b=Right[b];
			if(i&1)  ans+=b;
		}
		if(inv&&(!(n&1)))  ans=(ll)n*(n+1)/2-ans;
		printf("Case %d: %lld\n",++kase,ans);
	}
	return 0;
}

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

您正在使用您的 WordPress.com 账号评论。 注销 /  更改 )

Google photo

您正在使用您的 Google 账号评论。 注销 /  更改 )

Twitter picture

您正在使用您的 Twitter 账号评论。 注销 /  更改 )

Facebook photo

您正在使用您的 Facebook 账号评论。 注销 /  更改 )

Connecting to %s

%d 博主赞过: