大大模拟题

最短代码 看不？！ 来————

#include<bits/stdc++.h>
#include<queue>
using namespace std;
int main(){
	int n,m;
	queue<int>q;
	cin>>n>>m;
	for(int i=1;i<=n;++i)q.push(i);
	while(!q.empty()){
		int k=m-1;
		while(k--){
			q.push(q.front());q.pop();
		}
		cout<<q.front()<<" ";q.pop();
	}
	return 0;
}

#include<iostream>
#include<queue>
using namespace std;
int main(){
	int n,m;
	cin>>n>>m;
	queue<int>q;
	for(int i=1;i<=n;++i)q.push(i);
	while(!q.empty()){
		int k=m-1;
		while(k--){
			q.push(q.front());q.pop();
		}
		cout<<q.front()<<" ";q.pop();
	}
	return 0;
}

题目非常简单，一眼丁真，用队列完成。

思路清晰即可。

#include<bits/stdc++.h>
using namespace std;
queue <int> q;//单向队列
int main(){
    int n,m,i=1;
    cin>>n>>m;
    for(int i=1;i<=n;i++) q.push(i);//把1～n入队
    while(!q.empty()){
        if(i%m==0){//如果是第n
            cout<<q.front()<<" ";//出列
            q.pop();
        }else{
            q.push(q.front());//如果不是就重新入队
            q.pop();
        }
        i++;//计数器
    }
    return 0;
}

折腾半天用vector实现了，发现题解上有人用queque更加简练：

相比vector的erase()，pop()无需考虑越界，且构建循环链表的做法更优雅。

vector： if (p==s.end()-1) p=s.begin();

queque：

q.push(q.front());

把两个代码对照下，是掌握vector和queque的不错范例。

#include <bits/stdc++.h>
using namespace std;

int main(){
    vector<int> s;
    int n,m;
    cin>>n>>m;
    for (int i=1;i<=n;i++) s.push_back(i); //因为数数从1开始，下标从1比较好理解
    
    int i=1; //数到第几人,到m后从1再开始
    auto p=s.begin(); //指针指向队列头 auto C++11后才支持，实际上是vector<int>::iterator
    while (s.size()>0){
        while (i++<m) { //数人头。注意i是自增前和m比较，当i=m-1时，跳出循环
            if (p==s.end()-1) p=s.begin(); //如果已经是结尾，下一个就是第一个（begin）
            else p++; //否则正常向后数一个        
        }
        cout<<*p<<' '; //输出
        s.erase(p); //踢出
        if (p==s.end()) p=s.begin();//当在最后一个元素上erase时，指针会指向队尾（不存在元素）
        i=1; //再从1开始数
    }

    return 0;
}

#P1996. 约瑟夫问题

前沿/引入

这道题就是大模拟，但是如何更加方便的模拟？当然是STL的std::queue容器

STL std::queue容器适配器介绍

定义

定义于头文件<queue>

template<
    class T,
    class Container=std::deque<T>
>class queue;

模版形参

T:存储的元素类型

Container:存储元素的底层容器，必须满足序列容器的要求（即线性表） 且必须具有以下函数： back() front() push_back() pop_front()

满足要求的标准容器有std::deque和std::list

默认为std::deque不需要填写

操作（仅涉及本题需要的）

1.元素访问

front() 访问第一个元素

2.容量

empty() 返回容器是否为空（为空则返回true，否则返回false）

3.修改

push(x) 将x插入到容器末尾 pop() 弹出首个元素

题目分析&操作

我们定义一个计数器cnt，用循环模拟报数。该轮报数的人报完后移植队列末尾。

当报数m次后就会出现出局的人，即弹出首个元素。

注意需要判断容器是否为空

code

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m;
    cin>>n>>m;

    queue<int>q;

    for (int i=0;i<n;i++)q.push(i+1);

    int cnt=0;

    while (!q.empty()){
        q.push(q.front());
        q.pop();

        cnt++;
        
        if (cnt==m-1){
            cout<<q.front()<<" ";
            q.pop();
            cnt=0;
        }
    }
    return 0;
}

record

其实这道题可以用双向链表来做 代码如下：

 //test CZ P1019
#include<bits/stdc++.h>
using namespace std;
int n,m,l,r,cnt,p,t;
class Linked_list{// 循环双向链表
	public:
		int head,tail,id;
		void Delete(int x,int &l,int &r); //删除操作
		void Memset(int n); //初始化
};
Linked_list ll[110];
void Linked_list::Delete(int x,int &l,int &r){
	ll[ll[x].head].tail=ll[x].tail; // 将当前的节点的前一个节点的右指针指向当前节点的后面一个节点
	ll[ll[x].tail].head=ll[x].head; // 将当前节点的后一个节点的左指针指向当前节点的前面一个节点
	if(x==l)l=ll[x].tail; // 如果当前元素是表头，则新的表头就是后一个位置
	if(x==r)r=ll[x].head; // 如果当前元素是表尾，新的表尾就是前一个位置
	ll[x].head=-1;
	ll[x].tail=-1;
}
void Linked_list::Memset(int n){
	for(int i=1;i<=n;i++){
		ll[i].id=i;
		ll[i].head=i-1;
		ll[i].tail=i+1;
		if(i==1)ll[i].head=n;
		if(i==n)ll[i].tail=1;
	}
}
int main(){
	scanf("%d%d",&n,&m);
	ll[0].Memset(n);
	l=1,r=n,p=1,t=p;
	while(l<=r){ // 保证链表的长度大于等于 1
		cnt++;
		t=p;
		p=ll[p].tail;
		if(cnt==m){
			if(ll[t].id==0)break; //如果遍历到到下标为0的元素就跳出循环
			printf("%d ",ll[t].id);
			ll[t].Delete(t,l,r);
			cnt=0;
		}
	}
	return 0;
}