林厚从信息学奥赛课课通第7单元第5课队列

第7单元第5课队列例1：周末舞会。(party,1s,64MB)问题描述：假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。规定每个舞曲只能有一对跳舞者。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一个程序，模拟上述舞伴配对问题。输入格式：第1行两个正整数，表示男士人数m和女士人数n,1<=m,n<=1000;第2行一个正整数，表示舞曲的数目k，k<=1000。输出格式：共k行，每行两个数，之间用一个空格隔开，表示配对舞伴的序号，男士在前，女士在后。样例输入：246样例输出：112213241122例2：取牌游戏。(card,1s,256MB)问题描述：小明正在使用一堆共k张纸牌与n-1个朋友玩取牌游戏。其中，n<=k<=100000，2<=n<=100，k是n的倍数。纸牌中包含m=k/n张”good”牌和k-m张”bad”牌。小明负责发牌，他当然想自己获得所有”good”牌。他的朋友怀疑他会欺骗，所以他们给出以下一引些限制，以防小明耍诈：1）游戏开始时，将最上面的牌发给小明右手边的人。2）每发完一张牌，他必须将接下来的p张牌(1<=p<=10)一张一张地依次移到最后，放在牌堆的底部。3）以逆时针方向，连续给每位玩家发牌。小明迫切想赢，请你帮助他算出所有”good”牌放置的位置，以便他得到所有”good”牌。牌从上往下依次标注为#1，#2，#3，……输入格式：第1行，3个用一个空格间隔的正整数n、k和p。输出格式：m行，从顶部按升序依次输出”good”牌的位置。输入样例：92输出样例：378方法1利用普通队列模拟结合题目描述中的条件1和3不难推出“小明是第n个拿到牌的”，根据数据范围大致推导出队列存储容量“上界”为k+10*n*(100000/n)=1100000.#include<bits/stdc++.h>usingnamespacestd;#defineMAXN1500000inta[MAXN],b[MAXN];intmain(){freopen(“card.in”,”r”,stdin);freopen(“card.out”,”w”,stdout);intn,k,p,f=0,tail,q=0;cin>>n>>k>>p;for(inti=1;i<=k;i++)a[i=I;tail=k;for(int(i=1;i<=k/n;i++){ for(intj=1;j<=n;j++){ f++; a[++tail]=a[f]; }}}sort(b+1,b+1+1);for(inti=1;i<=k/n;i++) cout<<b[i]<<endl;return0;}方法2利用循环队列模拟实现#include<bits/stdc++.h>usingnamespacestd;#defineMAXN1100010intnxt[MAXN];boolans[MAXN];intmain(){freopen(“card.in”,”r”,stdin);freopen(“card.out”,”w”,stdout);intn,k,m;cin>>n>>k>>m;for(inti=1;i<k;i++)nxt[i]=i+1;nxt[k]=1;intp=k;for(inti=1;i<=k/n;i++){for(intj=1;j<n;j++){nxt[p]=nxt[nxt[p]];for(intl=1;l<=m;l++)p=nxt[p];}ans[nxt[p]]=true;nxt[p]=nxt[nxt[p]];for(intl=1;l<=m;l++)p=nxt[p];}for(inti=1;i<=k;i++)if(ans[i])cout<<i<<endl;return0;}练习1：海港(port,1s,256MB)题目描述:小K是一个海港的海关工作人员，每天都有许多船只到达海港，船上通常有很多来自不同国家的乘客。小K对这些到达海港的船只非常感兴趣，他按照时间记录下了到达海港的每一艘船只情况；对于第i艘到达的船，他记录了这艘船到达的时间ti(单位：秒)，船上的乘客数量ki，以及每名乘客的国籍x(i,1),x(i,2),…，x(i,k);。小K统计了n艘船的信息，希望你帮忙计算出以每一艘船到达时间为止的24小时(24小时=86400秒）内所有乘船到达的乘客来自多少个不同的国家。形式化地讲，你需要计算n条信息。对于输出的第i条信息，你需要统计满足ti-86400<tp<=ti的船只p，在所有的x(p,j)中，总共有多少个不同的数。输入格式：

第一行输入一个正整数n，表示小K统计了n艘船的信息。接下来n行，每行描述一艘船的信息：前两个整数ti和ki分别表示这艘船到达海港的时间和船上的乘客数量，接下来ki个整数x(i,j)表示船上乘客的国籍。保证输入的ti是递增的，单位是秒；表示从小K第一次上班开始计时，这艘船在第ti秒到达海港。保证

1<=n<=105，ki>=1,∑ki≤3∗10​5​​

，1<=x(i,j)<=105​​，1<=ti-1<ti<=109其中∑ki表示所有的ki的和，∑ki=k1+k2+……+kn。输出格式：输出n行，第i行输出一个整数表示第i艘船到达后的统计信息。输入输出样例输入样例#1：

314412222231013输出样例#1：

344说明【样例解释1】第一艘船在第1秒到达海港，最近24小时到达的船是第一艘船，共有4个乘客，分别是来自国家4,1,2,2，共来自3个不同的国家；第二艘船在第2秒到达海港，最近24小时到达的船是第一艘船和第二艘船，共有4+2=6个乘客，分别是来自国家4,1,2,2,2,3，共来自4个不同的国家；第三艘船在第10秒到达海港，最近24小时到达的船是第一艘船、第二艘船和第三艘船，共有4+2+1=7个乘客，分别是来自国家4,1,2,2,2,3,3，共来自4个不同的国家。输入样例#2：

41412233223864012348640215输出样例#2：

3334【样例解释2】第一艘船在第1秒到达海港，最近24小时到达的船是第一艘船，共有4个乘客，分别是来自国家1,2,2,3，共来自3个不同的国家。第二艘船在第3秒到达海港，最近24小时到达的船是第一艘船和第二艘船，共有4+2=6个乘客，分别是来自国家1,2,2,3,2,3，共来自3个不同的国家。第三艘船在第86401秒到达海港，最近24小时到达的船是第二艘船和第三艘船，共有2+2=4个乘客，分别是来自国家2,3,3,4，共来自3个不同的国家。第四艘船在第86402秒到达海港，最近24小时到达的船是第二艘船、第三艘船和第四艘船，共有2+2+1=5个乘客，分别是来自国家2,3,3,4,5，共来自4个不同的国家。【数据范围】练习2：瑞士轮(swiss,1s,256MB)问题描述：

在双人对决的竞技性比赛。如乒乓球、羽毛球、国际象棋中。最常见的赛制是淘汰赛和循环赛。前者的特点是比赛场数少。每场都紧张刺激，但偶然性较高。后者的特点是较为公平，偶然性较低，但比赛过程往往十分冗长。本题中介绍的瑞士轮赛制，因最早使用于1895年在瑞士举办的国际象棋比赛而得名。它能够看作是淘汰赛与循环赛的折中，既保证了比赛的稳定性，又能使赛程不至于过长。2*N名编号为1~2N的选手共进行R轮比赛。每轮比赛开始前，以及全部比赛结束后，都会依照总分从高到低对选手进行一次排名。选手的总分为第一轮开始前的初始分数加上已參加过的全部比赛的得分和。总分同样的，约定编号较小的选手排名靠前。每轮比赛的对阵安排与该轮比赛開始前的排名有关：第1名和第2名、第3名和第4名、……、第2K–1名和第2K名、……、第2N–1名和第2N名，各进行一场比赛。每场比赛胜者得1分，负者得0分。也就是说除了首轮以外，其他轮比赛的安排均不能事先确定，而是要取决于选手在之前比赛中的表现。

现给定每一个选手的初始分数及其实力值，试计算在R轮比赛过后，排名第Q的选手编号是多少。假设选手的实力值两两不同。且每场比赛中实力值较高的总能获胜。输入输出格式

输入格式：

输入的第1行是3个正整数N、R、Q。每两个数之间用一个空格隔开，表示有2*N名选手、R轮比赛以及我们关心的名次Q。

第2行是2*N个非负整数s1,s2,…,s2N，每两个数之间用一个空格隔开，当中si表示编号为i的选手的初始分数。第3行是2*N个正整数w1,w2,…,w2N，每两个数之间用一个空格隔开，当中wi表示编号为i的选手的实力值。

输出格式：

输出一行，包括一个整数，即R轮比赛结束后，排名第Q的选手的编号。输入输出例子

输入样例：

输出样例：

242