UVA12657 Boxes in a Line

我左移箱子,右移箱子,最后来了个倒着玩

日常简要分析


题目链接[https://www.luogu.org/problemnew/show/UVA12657]
明明是uva的题我为什么要放上luogu的链接 因为luogu访问快啊 题目中实际上我们是可以开看出我们要分去处理比较方便 我们先来看看这几层
  • 初始化
  • 读入
    • n,m
    • 操作
      1. 左移
      2. 右移
      3. 翻转
  • 求和并输出
那么我们挨个讲吧
#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;
struct node – 链表项 a – 链表 head – 链表头 last – 链表尾 n,m,x,y – 题目中有讲 mcnt – 判断第几个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移动到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.右移

与上面一样,自己理解一下不一样的地方,思考
  • 为什么更新headlast地方发生了改变
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();
    }
}
主程序貌似没有什么必要解释 你会发现把这些块连起来就是一个完整的代码qwq

思考的(非标准)答案||思路


这个是我脑洞大开的方法,毕竟这个程序真的不太好说 右移:
  • 为什么发生了改变
  • 原因十分简单,因为像左移会发生移动到头的情况,然而向右移虽然没有这个,但是有可能移到结尾 交换:
  • x,y颠倒
  • 简化处理步骤
  • 不直接交换
  • 你可以调试或者拿这个程序对拍,你会明白的 读入:
  • 相减
  • 如果你将倒过来,那么它的左右也就以然会颠倒,所以左移就变成了右移,反之亦然 求和输出:
  • 不在循坏条件中判断
  • 因为这样可能会漏掉最后一个,然后继续思考为什么会漏掉吧
如果你思路基本上和博主的对上了,那么开始自己写吧 如果没有对上,建议重新看并思考,必要时可以画画图,当然也可以直接留下评论问我 ]]>

2018.3.10 链表考试 解题报告

Start 杨老师突然就考试把我慌得一批 第四题被读入方法坑了一波,造成了oj能过评测机死活过不了的尴尬问题 前面三道题总体来说没有什么难度 第四题老杨没讲双向链表就考,搞得我怀疑自己是不是该加last项qwq

1.数列

题面


老师给我们的题面压根没法说,还是我来翻译吧 现在你要对一个空数列进行操作,你有两种书操作方法—’1’和’2’-分别代表添加和查询

输入

第一行一个n 后面n行每行两个数,a,b a表示操作方法,b表示被操作数 (1 1 表示往数列中加1 , 2 3表示查询3是否在数列中

输出

有几个 2 操作就输出几行,”Yes”表示存在,”No” 表示不存在

分析


老师上课讲过的 实际上二分优先队列也是一种办法/有大佬这么做 然而链表考试,我们把这个读入进来的数和一个大数(最好是质数)取模,对余数相同的见一个链表,到时候只需要查找这个余数就可以了

代码


#include <cstdio>
using namespace std;
struct node {
    int a;
    int next;
}dl[1100000];// dl[] 链表
int n,head[101000],len;// head[i] 余数为i的链表的开头
// len 表示链表长度
int main(){
    freopen("shulie.in","r",stdin);
    freopen("shulie.out","w",stdout);
    scanf("%d",&n);
    for(int i=0;i<=n;i++){
        dl[i].a=-1;
    }
    for(int i=1;i<=n;i++){
        int c,b;
        scanf("%d%d",&c,&b);
        if(c==1){// 添加
            int tmp=b%99997;// 求余
            len++;
            dl[len].next=head[tmp];
            dl[len].a=b;
            head[tmp]=len;
        }
        else {// 查询
            bool x=false;
            int tmp=b%99997;
            for(int i=head[tmp];dl[i].a!=-1;i=dl[i].next){// 遍历链表
                if(dl[i].a==b) {
                    x=true;
                    printf("Yes\n");
                    break;
                }
            }
            if(!x) printf("No\n");
        }
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}

2.约瑟夫问题

题面自己找,解析不用讲,我直接上代码吧qwq

代码


#include <cstdio>
using namespace std;
struct node{
    int next,data;// data 可废弃
}a[110000];// a[] 链表
int n,m;
int main(){
    freopen("king.in","r",stdin);
    freopen("king.out","w",stdout);
    int p,q;
    scanf("%d%d",&n,&m);// 读入
    for(int i=1;i<=n;i++){// 初始化,每个人的下一个都是自己旁边的
        a[i].data=i;
        a[i].next=i+1;
    }
    p=n;// 从 1 开始报数
    a[n].next=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m-1;j++){
            p=a[p].next; // 往下一个找
        }
        q=a[p].next;// 更新
        a[p].next=a[q].next;
        if(i==n)printf("%d",q);// 输出最后的赢家编号
    }
    fclose(stdin);
    fclose(stdout);
}

3.法雷队列

题面就简单说吧:
求分母小于n的所有最简真分数,然后再加上0/1,1/1然后按顺序输出就行了
分析???不存在的 因为我用的暴力,还需要解释? 因为题目中讲了: n<=100 暴力出奇迹

代码


#include <cstdio>
#include <algorithm>
using namespace std;
struct node {
    int m,s;
}d[100000];
int n,cnt,len;
bool cmp(node a,node b){
    double ta=double(a.s)/double(a.m);
    double tb=double(b.s)/double(b.m);
    return ta<tb;
}
// gcd判断互质
bool gcd(int a,int b){
    int r;
    while(b>0){
         r=a%b;
         a=b;
         b=r;
    }
    if(a==1) return true;
    else return false;
}
int main(){
    freopen("falei.in","r",stdin);
    freopen("falei.out","w",stdout);
    scanf("%d",&n);
    len++;
    d[len].m=1;
    d[len].s=0;
    // 枚举
    for(int i=1;i<=n;i++){// 转分母
        for(int j=1;j<i;j++){// 转分子
            if(j==1) {// 分子是1,100%最简分数
                len++;
                d[len].m=i;
                d[len].s=j;
            }
            else {
                if(gcd(i,j)){
                    len++;
                    d[len].m=i;
                    d[len].s=j;
                }
            }
        }
    }
    len++;
    d[len].m=1;
    d[len].s=1;
// sort排序万岁
    sort(d+1,d+len,cmp);
// 输出
    for(int i=1;i<=len;i++){
        printf("%d/%d ",d[i].s,d[i].m);
        if(i%10==0) printf("\n");
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}

4. TXT Editor

题面


现在你要编写一个文本编辑器,该编辑器支持以下4个操作: 1、L:光标左移一格 (若光标已在最左边就无视这次操作) 2、R:光标右移一格 (若光标已在最右边就无视这条操作) 3、a-z:在光标处插入一个字母 4、B:删除光标前的一个字母 (等同Backspace键,若光标已在最左边就无视这次操作) 初始文本为空,现在给你一个操作的序列S,求操作结束后文本编辑器里面的内容。

解析


虽然我们只学了单向链表,但也应当很容易想到双向队列:多加一个last 另外我们通过now表示目前的光标,就很容易想通了

代码


之前用\n判断输入结束然后t了简直心累,跑到oj上结果AC了233,改成EOF后出了一点莫名奇妙的问题qwq(总是在输出结尾加一个^@符号,也不知道是什么 虽然理论上ac但是安全起见我还是放EOF判断结尾法的代码吧qwq 刚好改EOf判断结尾时去掉了许多多余的代码 ]]>

链表入门 – Luogu 1996 约瑟夫问题

链表? 通常而言,我们说链表都是一种动态的数据结构,但是显然对于我这样的蒟蒻以及普通的竞赛考试而言,通过半静态的数组模拟也可以基本上完成对链表的模拟。 日常的日常—简单画图:

a         [ 0 ]            [1]            [2]           [3]
head -> |next|data| -> |next|data| -> |next|data| -> |next|data|
        |  2 | 2  |    |  3 | 4  |    | 1  | 3  |    | 0  |  1 |
如果我们想要遍历这个链表,就是这个顺序:
a[0]->a[2]->a[1]->a[3]-|
相信你已经看出来了next的作用,所以把一个数直接添加进链表的时间复杂度不比数组高哪去了2333 让我们来看看下面这道题:

题面


我们现在有两种操作 ‘ 1 ‘ 与 ‘ 2 ‘ , ‘ 1 ‘ 表示插入,’ 2 ‘表示询问一个数是否添加过 我们先看看这个样例 输入
5
1 3
1 5
2 3
1 4
2 2
输出
Y
N
不用说我们也知道,桶排是可以是解决一切,但是我们如果我们内存不够呢? 这是就要祭出链表了。 我们把要插入的数对大整数进行取模,然后存入p[i]数组及链表当中当中(i表示取模得到的结果) 这样一来我们就对取模解过相同的数建立了链表,接下来只需要递归遍历,这个速度查找,比大多数方法快好多了

约瑟夫问题

题面


题目链接:[https://www.luogu.org/problemnew/show/P1996]
无聊的约瑟夫 很好因为约瑟夫的无聊我们不得不去做这道题。 显然模拟以及数学方法都可以轻松 AC Qwq 不过我肯定还是要讲链表的方法的啦~

代码


可以去除data项
#include <cstdio>
using namespace std;
struct node{
    int next,data;// 不解释
}a[110000];// 假装自己是链表的 a[]
int n,m;
int main(){
// 初始化
    int p,q;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        a[i].data=i;
        a[i].next=i+1;
    }
    p=n;// 从 1 开始报数
    a[n].next=1;// 建立循环队列
    for(int i=1;i<=n;i++){// 每个人都要输出
        for(int j=1;j<=m-1;j++){// 把数传到下一个人
            p=a[p].next;
        }
        q=a[p].next;
        a[p].next=a[q].next;// 去除q节点
        printf("%d ",q);
    }
}
为什么我感觉还是模拟qwq

END

过不了几天, ]]>