关于
联系
Oi大佬们
keyboard_arrow_down
本站已运行
载入天数...载入时分秒...
Woshiluo's Notebook
Woshiluo
2018年3月4日
链表入门 – 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

过不了几天,


textsms