静态链表+P1145作弊的发牌者

静态链表

定义

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

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;
}