一.stack和queue模拟应用

喜欢打牌的Nemaleswang
题目描述
Nemaleswang是一个退役狗，众所周知，Nemaleswang太喜欢打牌了，有一次训练赛的时候带着大家一起打牌，于是他被教练开除集训队，被迫退役了。但是Nemaleswang并不甘心就这样退役，他发明了一种新的打牌游戏，让大家沉迷于这个游戏，这样大家的水平都下降了，他就可以以不高的水平再回到集训队训练了，这个打牌游戏的规则是这样的。一.这个游戏只有两个玩家，A和B，按照一般的52张扑克牌（1到13，每种牌四张,一共52张牌），每个人随机拿到26张。二. A先开始，放下手上最上面的第一张牌，随后两人轮流出牌（按手牌顺序，不可打乱顺序），后一张放在前一张上面。三. 如果出现之前放下的牌s与当前要放下的牌t点数相同，则当前玩家获得[s, t]范围内的所有扑克牌，放入手牌最后面，放牌顺序为先放t,最后放s，也就是说，新手牌的最后一张牌是s而不是t（提醒：当前玩家应再出牌一次）。四.出现玩家没有手牌的情况时，游戏结束，有手牌的人获胜。（保证游戏一定会结束）
一种神奇的写法：

#include <bits/stdc++.h>
using namespace std;
const int maxn=105;
int t,n,m,temp[maxn],cherk[maxn],st;
queue<int>a,b;
stack<int>s;
int main()
{
    cherk[0]=1;
    for(int i=1;i<=13;i++)
        cherk[i]=cherk[i-1]<<1;
    cin>>t;
    while(t--)
    {
        while(!a.empty())a.pop();
        while(!b.empty())b.pop();
        while(!s.empty())s.pop();
        st=0;
        for(int i=0;i<26;i++)
        {
            int aa;
            cin>>aa;
            a.push(aa);
        }
        for(int i=0;i<26;i++)
        {
            int bb;
            cin>>bb;
            b.push(bb);
        }
        for(int i=1;;i++)
        {
            queue<int>*p;
            if(i&1) p=&a;
            else p=&b;
            int tmp=p->front();
            p->pop();
            s.push(tmp);
            if(st&cherk[tmp])//按位与：有0便为0，无0才为1；
            {
                for(int j=1;;j++)
                {
                    int tp=s.top();
                    s.pop();
                    if(st&cherk[tp])st^=cherk[tp];//异或：相同为0，不同为1；可用于开灯问题出现两次即为0对其他无影响
                    p->push(tp);
                    if(tmp==tp&&j!=1)break;
                }
                i--;
                continue;
            }
            else st|=cherk[tmp];//按位或：有1便为1，无1才为0
            if(p->size()==0)
            {
                if(i&1)printf("B\n");
                else printf("A\n");
                break;
            }
        }
    }
    return 0;
}

二、用函数fill()、fill_n()给stl中的容器赋值

例题：AT1893 編集
题意翻译
给定一个序列长度为N(N<=100),序列初始全部为0。给定两个数N，P，表示，接下来P(P<=100)次操作，接下来P行，每次给定一个区间（l，r）和一个整数（k），表示将区间
[l,r][l,r]
[l,r]中的元素全部替换为k。最后输出这个序列
[1,N][1,N]
[1,N]，每输出一个元素换行一次。
思路：这里用到的fill()、fill_n()和memset()类似，不过fill不仅可以给数组填充值，还可以为容器例如vector填充一定区间的值

fill 和fill_n函数是C++ Primer第十二章泛型算法部分内容，并把它们称为生成和变异算法，也就是说这两个函数只能对输入范围内已存在的元素进行操作。如果试图对空容器进行fill_n操作，会导致严重的运行错误，所以在对元素进行写入操作时要检查目标的大小是否足以存储要写入的元素。
fill函数的作用是：将一个区间的元素都赋予val值。函数参数：fill(vec.begin(), vec.end(), val); val为将要替换的值。
fill_n函数的作用是：参数包括 : 一个迭代器，一个计数器以及一个值。该函数从迭代器指向的元素开始，将指定数量的元素设置为给定的值。
注意： 不能在没有元素的空容器上调用fill_n函数，但是可以通过下面的方法改进：fill_n(vec.begin(),10,val);
为了保证算法有足够的元素存储输出数据，我们使用“插入迭代器”（insert iterator），插入迭代器是可以给基础容器添加元素的迭代器。
使用 back_inserter 的程序需要包含头文件#include<iterator>，将上面的程序改写成：

#include <iterator> 
 vector<int> vec; //定义一个空容器 
 fill_n (back_inserter(vec), 10 val);

在这个程序中，fill_n() 函数每写入一个值，都会通过back_inserter生产的插入迭代器实现。效果相当于在vec上调用push_back，在vec末尾添加10个元素。（转）

#include <iostream>
using namespace std;
int main()
{
    int a[10];
    fill(a,a+10,20);//三个参数，前面两个是地址，最后一个是填充值

    for(int i = 0;i<10;i++)
        cout <<a[i] << " " ;
    cout << endl;

    fill_n(a,5,-3);//三个参数，第一个是地址，第二个是个数，最后一个是填充值
    for(int i = 0;i<10;i++)
        cout <<a[i] << " " ;
    cout << endl;

    return 0;
}

（转）
输出结果：

20 20 20 20 20 20 20 20 20 20 
-3 -3 -3 -3 -3 20 20 20 20 20

原创题解如下：

#include<bits/stdc++.h>
using namespace std;
const int maxn=105;
int n,p,l,r,val;
vector<int>vect;
int main()
{
    cin>>n>>p;
    fill_n (back_inserter(vect),100,val);
    for(int i=0;i<p;i++)
    {
        cin>>l>>r>>val;
        fill_n(vect.begin()+(l-1),(r-l+1),val);
    }
    vector<int>::iterator it;
        for(it=vect.begin();it!=vect.begin()+n;it++)
            cout<<(*it)<<endl;
    return 0;
}

利用STL的模拟

目录

一.stack和queue模拟应用

二、用函数fill()、fill_n()给stl中的容器赋值