静态链表

定义

关于静态链表就是一个结构体，加上一个数组：

1
2
3
4
5
6
struct Card
{
    int sit;
    int next;
    int prev;
};Card a[1000];

静态链表原理

之所以会用到静态链表是因为纯粹的一位数组太慢了，每次处理差不多都是On(n),一个二重循环大多数数据都会超时的，包括移动一个元素，删除，插入一个元素能能，动一个就要动全身，所以要使用静态链表；

sit的具体含义是要分题目的，因为有些题中，要固定不变的量是不变的，有可能sit是一样需要移动的东西的编号，也有可能是一样东西的权值。next指的是这个东西下一个元素是哪一个，prev指的是上一个元素是哪一个，这样进行操作的时候就可以将为On(1)了。
eg:删除编号为15的元素

1
a[a[15].prev].next=a[15].next

这样我们只要让他的上一个元素所指向的下一个元素，为自己指向的下一个元素即可，然后就永远不会出现有个编号为15的元素了，因为其他没有任何一个元素的next是他，也就不可能访问到他了。

P1145作弊的发牌者

题目描述

贝茜正在与她的N-1(2 <= N <= 100)个朋友打牌。她们玩的牌一副为K (N <= K <= 100,000，K为N的倍数)张。所有牌中，一共有M(M = K / N)张“好 牌”，其余的K - M张为“差牌”。贝茜是游戏的发牌者，很自然地，她想把所 有好牌都留给自己。她热衷于获胜，即使为此必须采取一些不正当的手段。
在若干局游戏后，贝茜的朋友们开始怀疑贝茜在游戏中作弊，于是她们想了 个对策：使用新的发牌规则。规则具体如下：

  1. 贝茜把牌堆的最上面一张发给她右边的奶牛。
  2. 每当贝茜发完一张牌，她都得将牌堆顶部接下来的P(1 <= P <= 10)张牌 　　 放到底部去（一般把这个操作称为切牌）
  3. 然后，贝茜对逆时针方向的下一头奶牛重复上述的操作。

贝茜绝望地认为，她再也不可能获胜了，于是她找到了你，希望你告诉她， 将好牌放在初始牌堆的哪些位置，能够确保它们在发完牌后全集中到她手里。顺 带说明一下，我们把牌堆顶的牌定义为1号牌，从上往下第二张定义为2号牌，依此类推。

输入：

第1行: 3个用空格隔开的整数：N、K，以及P

输出：

第1..M行: 每行输出一个正整数，表示贝茜应该在初始牌堆的这个位置放一张好牌。所有的位置按升序输出。

题解：

看到这道题，大概想了想100000的数据，然后只能使用静态链表了。很简单，建一个机构体，然后删除一张牌的时候直接参考上面eg，然后洗牌（切牌）的时候，直接略过，让维护当前牌顶的ans直接等于接下来要操作的牌就好，然后用一个计数器，如果为总人数的倍数，记录下来删除的牌的sit值。

最后一个sort直接输出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<iomanip>
#include<cmath>
#include<string>
struct Card
{
    int sit;
    int next;
    int prev;
};
Card a[100001];
using namespace std;
int main()
{
    int player,num,wash;
    int er=num/player,ans=1,j=0,rem=0;
    int b[100001];
    cin>>player>>num>>wash;
    for(int i=1;i<num;i++)//初始值
    {
        a[i].sit=i;
        a[i].next=i+1;
        a[i].prev=i-1;
    }
    a[num].sit=num;
    a[num].next=1;
    a[num].prev=num-1;
    a[1].prev=num;
    for(;;)
    {
        j++;
        if(j%player==0) b[++rem]=a[ans].sit;//判断是否为作弊者的牌
        a[a[ans].prev].next=a[ans].next;
        a[a[ans].next].prev=a[ans].prev;
        ans=a[ans].next;
        for(int i=1;i<=wash;i++)//进行洗牌
            ans=a[ans].next;
        if(j==num)//判断是否出现两个牌这种死循环情况，退出
        break;//其实这里可以换成对rem的判断退出的
    }
    sort(b+1,b+rem+1);
    for(int i=1;i<=rem;i++)
    cout<<b[i]<<endl;
    return 0;
}