nefu 1632 周末舞会-队列

#include <bits/stdc++.h>
using namespace std;
int m,n,k,tmp1,tmp2;
queue<int>q1,q2;
int main()
{
    cin>>m>>n>>k;
    for(int i=1;i<=m;i++)
        q1.push(i);
    for(int i=1;i<=n;i++)
        q2.push(i);
    while(k--)
    {
        tmp1=q1.front();q1.pop();q1.push(tmp1);
        tmp2=q2.front();q2.pop();q2.push(tmp2);
        printf("%d %d\n",tmp1,tmp2);
    }
    return 0;
}

nefu 1633 取牌游戏-队列

#include <bits/stdc++.h>
using namespace std;
int n,k,p,num,cnt,ans[100010];
queue<int>q;
int main()
{
    cin>>n>>k>>p;
    for(int i=1;i<=k;i++)
        q.push(i);
    while(!q.empty())
    {
        num++;
        int tmp=q.front();q.pop();
        if(num%n==0)ans[cnt++]=tmp;
        for(int i=1;i<=p;i++)
        {q.push(q.front());q.pop();}//数据应该保证了能取出p张牌，取出的过程中不会使队列为空
    }
    sort(ans,ans+cnt);
    for(int i=0;i<cnt;i++)
    printf("%d\n",ans[i]);
    return 0;
}

nefu 1634 报数-队列

这题就是著名的约瑟夫问题：N个人围成一圈，第一个人从1开始报数，报数到M的人就出局，下一个人再从1开始报数，报数到M的人就出局…直到最后只剩下一个人。
用C++的队列很方便：

#include <bits/stdc++.h>
using namespace std;
queue<int>q;
int main()
{
    int n,m,tmp,cnt;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        q.push(i);
    cnt=0;
    while(q.size()>1)
    {
        cnt++;
        tmp=q.front();q.pop();
        if(cnt%m!=0)q.push(tmp);
    }
    printf("%d\n",q.front());
    return 0;
}

C语言中用数组模拟队列：

#include <stdio.h>
int head,tail,a[1000001];
int main()
{
    int n,m,tmp,cnt;
    scanf("%d%d",&n,&m);
    tail=0;
    for(int i=1;i<=n;i++)
        a[++tail]=i;
    cnt=0;head=1;
    while(head<tail)
    {
        cnt++;
        tmp=a[head];head++;
        if(cnt%m!=0)a[++tail]=tmp;
    }
    printf("%d\n",a[head]);
    return 0;
}

nefu 1635 酒桌游戏-队列

与上一题相同的约瑟夫问题，用结构体处理序号和名字即可。

#include <bits/stdc++.h>
using namespace std;
struct node
{
    int num;
    string name;
}p[1001];
queue<node>q;
bool judge(int x)
{
    if(x%7==0)return 1;
    while(x)
    {
        if(x%10==7)return 1;
        x=x/10;
    }
    return 0;
}
int main()
{
    int n,m,t;
    string name;
    cin>>n>>m>>t;
    for(int i=1;i<=n;i++)
    {
        cin>>p[i].name;
        p[i].num=i;
    }
    for(int i=1;i<=n;i++)
        q.push(p[i]);
    for(int i=1;i<=m-1;i++)
    {q.push(p[i]);q.pop();}
    t--;
    while(q.size()>1)
    {
        t++;
        node tmp=q.front();q.pop();
        if(!judge(t))q.push(tmp);
    }
    printf("%s\n",q.front().name.c_str());
    return 0;
}

nefu 1662 Blash数集-队列-set

这题和nefu 574 丑数有点相似，把排序的过程想清楚就行了，不用队列也能做，丑数那题就是由前面几个数生成后面的数然后升序排列，这题也可以用做那题的思路做。

#include <bits/stdc++.h>
using namespace std;
int x,n,p1,p2,tmp1,tmp2,a[100010];
int main()
{
    cin>>x>>n;
    a[1]=x;p1=p2=1;
    for(int i=2;i<=100000;i++)
    {
        tmp1=a[p1]*2+1;
        tmp2=a[p2]*3+1;
        if(tmp1>tmp2){p2++;a[i]=tmp2;}
        if(tmp1<tmp2){p1++;a[i]=tmp1;}
        if(tmp1==tmp2){p1++;p2++;a[i]=tmp1;}
    }
    printf("%d\n",a[n]);
    return 0;
}

洛谷 P2058 海港

#include <bits/stdc++.h>
using namespace std;
struct node
{
    int t,x;//t为时间，x为国籍
};
queue<node>q;
int t,k,n,x,ans,a[300010];
inline int read()//快读，洛谷运行时间从389ms提速到205ms
{
    register int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
    return x*f;
}
int main()
{
    n=read();
    while(n--)
    {
        t=read();k=read();
        while(k--)
        {
            x=read();
            q.push({t,x});
            if(a[x]==0)ans++;
            a[x]++;
        }
        while(t-q.front().t>=86400&&!q.empty())
        {
            node tmp=q.front();q.pop();
            a[tmp.x]--;
            if(a[tmp.x]==0)ans--;
        }
        printf("%d\n",ans);
    }
    return 0;
}

nefu 1663 关系网络-队列

BFS，用队列实现最短步数的搜索。

#include <bits/stdc++.h>
using namespace std;
int n,beginx,endx,newx,a[101][101],vis[101];
int dir[4][2]={{1,0},{-1,0},{0,-1},{0,1}};
struct node
{
    int x,cnt;//cnt记录步数
};
queue<node>q;
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>beginx>>endx;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>a[i][j];
    q.push({beginx,0});//先把起点入队，开始时cnt=0
    while(!q.empty())//开始搜索，用队列实现BFS
    {
        node tmp=q.front();q.pop();//按队列顺序依次取出队首tmp
        if(tmp.x==endx){printf("%d\n",tmp.cnt-1);break;}//找到终点，输出答案，搜索结束
        vis[tmp.x]=1;//原节点变为"墙"
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(a[i][j]==1&&i==tmp.x&&vis[j]==0)
                q.push({j,tmp.cnt+1});
            }
        }
    }
    return 0;
}