22蓝桥杯训练7
题目一：周末舞会-队列
Description:
假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。规定每个舞曲只能有一对跳舞者。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一个程序，模拟上述舞伴配对问题。
input:
第 1 行两个正整数，表示男士人数 m 和女士人数 n，1≤m，n≤1000； 第 2 行一个正整数，表示舞曲的数目 k，k≤1000。
output:
共 k 行，每行两个数，之间用一个空格隔开，表示配对舞伴的序号，男士在前，女士在后。
sample input:
2 4
6
sample output:
1 1
2 2
1 3
2 4
1 1
2 2
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
queue<int>vis1,vis2;
int main()
{
int n,m,k,s1,s2;
cin>>n>>m;
cin>>k;
for(int i=1;i<=n;i++)
vis1.push(i);
for(int j=1;j<=m;j++)
vis2.push(j);
for(int i=1;i<=k;i++)
{
s1=vis1.front();
vis1.pop();
s2=vis2.front();
vis2.pop();
cout<<s1<<" "<<s2<<endl;
vis1.push(s1);
vis2.push(s2);
}
return 0;
}
cpp
题目二：取牌游戏-队列-SET
Description:
小明正在使用一堆共 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，…
input:
第 1 行，3 个用一个空格间隔的正整数 N、K 和 P。
output:
M 行，从顶部按升序依次输出“good”牌的位置。(就是从小到大输出)
sample input:
3 9 2
sample output:
3
7
8
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+1;
queue<int>vis;
int a[N];
int main()
{
int n,k,p,num=0,q=0;
cin>>n>>k>>p;
for(int i=1;i<=k;i++)
vis.push(i);
while(!vis.empty())
{
int tmp=vis.front();
vis.pop();
num++;
if(num%n==0) a[q++]=tmp;
if(!vis.empty())
{
for(int i=1;i<=p;i++)
{
int tp=vis.front();
vis.pop();
vis.push(tp);
}
}
}
sort(a,a+k/n);
for(int i=0;i<k/n;i++)
cout<<a[i]<<endl;
return 0;
}
cpp
题目三：报数-队列-约瑟夫环
Description:
n个小朋友们坐成一个圆圈，编号分别为1，2，3.....n；第1个小朋友从1开始报数，报到m的小朋友离开座位；然后下一个小朋友从1接着报数；直到剩下最后一个小朋友为止；
input:
输入2个数字n和m;（1<=n,m<=1000）
output:
输出最后一个小朋友的编号！
sample input:
10 5
sample output:
3
#include <bits/stdc++.h>
using namespace std;
int n, m;
queue<int> s;
int main()
{
int num=1;
cin >> n >> m ;
for (int i = 1; i <= n; i++)
{
s.push(i);
}
while(s.size()!=1)
{
if(num==m)
{
s.pop();
num=1;
}
else
{
s.push(s.front());
s.pop();
num++;
}
}
cout<<s.front();
return 0;
}
cpp
题目四：酒桌游戏-队列
Description:
n个人围成一个圆桌，按照顺时针的顺序1，2，...n进行编号；某一个人开始报一个数字，然后顺时针的下一个人会报数+1；当某个人报的数字含有7或是7的倍数时，这个人退出游戏，其他人接着报数！直到剩下一个人为止！
input:
输入n,m,t；n代表人数，m代表开始报数的人的编号；t表示开始报数的人报出的数字是t; 然后接下来有n行，是这n个人的名字！
output:
输出最后一个人的名字！
sample input:
5 3 20
liming
wangze
gongxiangjun
wangming
chenzhen
sample output:
chenzhen
#include <bits/stdc++.h>
using namespace std;
int n, m, t;
queue<string> s;
string str;
bool check(int a)
{
int y;
while (a)
{
y = a % 10;
if (y == 7)
return 1;
a = a / 10;
}
}
int main()
{
cin >> n >> m >> t;
for (int i = 1; i <= n; i++)
{
cin >> str;
s.push(str);
}
int k = m - 1;
while (k--)
{
s.push(s.front());
s.pop();
}
while (s.size() != 1)
{
if (t % 7 == 0 || check(t))
{
s.pop();
t++;
}
else
{
s.push(s.front());
s.pop();
t++;
}
}
cout << s.front();
return 0;
}
cpp
题目五：海港-队列
Description:
小K是一个海港的海关工作人员，每天都有许多船只到达海港，船上通常有很多来自不同国家的乘客。 小K对这些到达海港的船只非常感兴趣，他按照时间记录下了到达海港的每一艘船只情况；对于第i艘到达的船，他记录了这艘船到达的时间ti (单位：秒)，船上的乘客数k,以及每名乘客的国籍x1,x2,x3,x4等； 小K 统计了这N 艘船的信息，希望你帮助计算出每1艘船到达为止的24小时（86400秒）内到达的船上的乘客来自多少个国家？
input:
第1行为一个n,表示有n条船； 接下来有n行，每行前2个数为t和k,表示这艘船的到达时间和船上的旅客数量！ 然后是这k个旅客的国籍（x1 x2 x3 .......都是整数）
output:
输出n行，每行代表这艘船到达为止的24小时（86400秒）内到达的船上的乘客来自多少个国家？ t[i]-t[p]<86400,t[i]表示当前船的时间，t[p]表示之前进海港的船！ 1<=n,k<=300000; 1<=ti<=1000000000;
sample input:
例子输入1：
3
1 4 4 1 2 2
2 2 2 3
10 1 3
例子输入2：
4
1 4 1 2 2 3
3 2 2 3
86401 2 3 4
86402 1 5
sample output:
例子输出1：
3
4
4
例子输出2：
3
3
3
4
include<bits/stdc++.h>
using namespace std;
int s,i,n,t,k,r,w[100001],x[300002],y[300002];
int main()
{
cin>>n;
while(n--){
cin>>t>>k;
while(k--){
y[++r]=t;cin>>x[r];
if(!w[x[r]])s++;
//w[i]表示当前国籍为i的人的数量
//x[i]表示第i个人的国籍
//所以这句就是说如果当前这个人的国籍没人，那么答案+1
w[x[r]]++;
//国籍为当前这个人的国籍的人的数量+1
}
while(t-y[i]>=86400)
//y[i]表示第i个人到达时间，t表示目前的时间
//当y[i]这个人到达时间与目前时间已经超过一天时
if(!--w[x[i++]])s--;
//这句话与下面这段代码等效
/*
w[x[i]]--;//国籍为当前这个人的国籍的人的数量-1
if(!w[x[i]])s--;//如果当前这个人的国籍没人，那么答案-1
i++;//换下一个人
*/
//而i不用重置是因为题目输入的t全都是升序排列，所以可以依次取下一个人
cout<<s<<endl;//最后输出答案
}
}
cpp
