我左移箱子，右移箱子，最后来了个倒着玩
日常简要分析
题目链接[https://www.luogu.org/problemnew/show/UVA12657]
- 初始化
- 读入
-
- n,m
- 操作
-
- 左移
- 右移
- 翻转
- 倒
- 求和并输出
#include <cstdio>
using namespace std;
struct node{
int next,last;
int n;
}a[110000];
int head,last;
int n,m,x,y,mcnt;
int temp;
node tmp1,tmp2;
bool zf=false;
case temp,tmp1,tmp2 – 临时项 zf – 判断是否颠倒
读入
inline void init(){
mcnt++;
// 先把箱子挨个排起来
for(int i=1;i<=n;i++){
a[i].n=i;
a[i].next=i+1;
a[i].last=i-1;
}
zf=false;// 一开始是不倒的
// 确定头和尾部
head=1;
last=n;
}
1. 左移
| n |
|last|next|
| 1 | | 2 | | 3 | | 4 |
| | 2| |1|3 | |2| 4| | 3| |
1 1 3
那么就要讲3的last改为1
1的next改为3 将1的nxet与1的last链接
将3的last的next改为1
inline void bian1(){
scanf("%d%d",&x,&y);
if(a[y].last==x||x==y) return ;
tmp1=a[x];tmp2=a[y];// tmp1,tmp2临时储存以防后面倒不动
if(x==last) last=a[x].last;// 如果需要移动是尾，那就更改尾部尾需要更改的last项上
if(x==head) head=tmp1.next;// 如果是头部，那就进行移动
else if(y==head) head=x;// 同上
/* 那么就要讲3的last改为1
1的next改为3
将1的nxet与1的last链接
将3的last的next改为1*/
a[tmp1.next].last=tmp1.last;
a[tmp1.last].next=tmp1.next;
a[tmp2.last].next=x;
a[x].last=tmp2.last;
a[x].next=y;
a[y].last=x;
}
2.右移
与上面一样，自己理解一下不一样的地方，思考- 为什么更新
head与last地方发生了改变
inline void bian2(){
scanf("%d%d",&x,&y);
tmp1=a[x];tmp2=a[y];
if(a[y].next==x||x==y) return ;
if(y==last) last=x;
else if(x==last) last=a[x].last;
if(x==head) head=tmp1.next;
a[tmp1.next].last=tmp1.last;
a[tmp1.last].next=tmp1.next;
a[x].last=y;
a[y].next=x;
a[tmp2.next].last=x;
a[x].next=tmp2.next;
}
3.交换
实际上本质依旧与前两个相同，但是我们要注意两个是相邻的状况，对于移动的部分是讲两者和两者的next与last更新，方法可以参照一种的图，依旧需要思考- 为什么当x在y后面需要交换?
- 为什么不直接交换两者的n?
inline void bian3(){
scanf("%d%d",&x,&y);
if(x==y) return ;
if(x==head) head=y;
else if(y==head) head=x;
if(x==last) last=y;
else if(y==last) last=x;
if(a[y].next==x) {int te;te=x;x=y;y=te;}
tmp1=a[x];tmp2=a[y];
if(a[x].next==y){
a[tmp1.last].next=y;
a[y].last=tmp1.last;
a[y].next=x;
a[x].last=y;
a[tmp2.next].last=x;
a[x].next=tmp2.next;
}
else {
a[tmp1.next].last=y;
a[y].next=tmp1.next;
a[tmp1.last].next=y;
a[y].last=tmp1.last;
a[tmp2.next].last=x;
a[x].next=tmp2.next;
a[tmp2.last].next=x;
a[x].last=tmp2.last;
}
}
4.倒
简单到我不想讲inline void bian4(){zf=!zf;}
读入
思考: 为什么颠倒时要用3相减
inline void read(){
for(int i=1;i<=m;i++){
scanf("%d",&temp);
if(temp==4) bian4();
if(zf&&temp!=3) temp=3-temp;
if(temp==1) bian1();
if(temp==2) bian2();
if(temp==3) bian3();
}
}
求和输出
注意: 务必使用long long (在样例中有体现) 思考: 为什么不在循环中判断break
inline void sum(){
long long sum=0,cnt=0;
if(!zf)// 正过来
for(int i=head;;i=a[i].next){
cnt++;
//printf("%d ",a[i].n);
if(cnt%2!=0) sum+=a[i].n;
if(i==last){
printf("Case %lld: %lld\n",mcnt,sum);
break;
}
}
else {// 反过来
for(int i=last;;i=a[i].last){
cnt++;
//printf("%d ",a[i].n);
if(cnt%2!=0) sum+=a[i].n;
if(i==head){
printf("Case %lld: %lld\n",mcnt,sum);
break;
}
}
}
}
End
int main(){
// freopen("233.in","r",stdin);
while(scanf("%d%d",&n,&m)!=EOF){
init();
read();
sum();
}
}
思考的(非标准)答案||思路
这个是我脑洞大开的方法，毕竟这个程序真的不太好说 右移:
- 为什么发生了改变
- 原因十分简单,因为像左移会发生移动到头的情况，然而向右移虽然没有这个，但是有可能移到结尾 交换:
- x,y颠倒
- 简化处理步骤
- 不直接交换
- 你可以调试或者拿这个程序对拍，你会明白的 读入:
- 相减
- 如果你将倒过来，那么它的左右也就以然会颠倒，所以左移就变成了右移，反之亦然 求和输出:
- 不在循坏条件中判断
- 因为这样可能会漏掉最后一个，然后继续思考为什么会漏掉吧