每日一题（2022年4月4日）

题目一：

你有一个序列，现在你要支持几种 *** 作：

• insert x y，在从前往后的第xx个元素后面插入yy这个数。
  

  
  

  如果x=0x=0，那么就在开头插入。
  

  
  

• delete x，删除从前往后的第xx个元素。
  

  
  

• query k，询问从前往后数第kk个元素是多少。
  

  
  

输入格式

第一行一个整数mm，表示 *** 作个数。

接下来mm行，每行一个上面所述的 *** 作。

输出格式

输出若干行，对于每个查询 *** 作，输出答案。

做法一（链表）

链表写法参考《算法竞赛进阶指南》

#include
using namespace std;
​
struct{
    int value;
    int next,pre;
}node[1005];//创建链表结点
​
int head,tail,tot;
​
void init(){//链表初始化
    tot = 2;
    head = 1;tail=1;//定义链表表头和尾巴。

该链表表头仅起到标记的作用，无value值
    node[head].next=tail;
}
​
void insert( int p,int val){
    int q = ++tot; //新增结点
    node[q].value = val;
    node[q].next = node[p].next;
    node[node[p].next].pre = q;
    node[p].next = q;
    node[q].pre = p;
}
​
void delet(int p){
    node[node[p].pre].next = node[p].next;
    node[node[p].next].pre = node[p].pre;
}
​
int main(){
    int m;cin >> m;
    while(m--){
        string op;cin >> op;
        if(op == "insert"){
            int x,y;cin >> x >> y;//在第x个元素后插入y，若x为0，则删改表头
            int i = head;
            while(x--)
                i = node[i].next;
            insert(i,y);
        }
        if(op == "query"){
            int x;cin >> x;//查询第x个元素
            int i = head;
            while(x--)//检索第x个元素对于的下标
                i = node[i].next;
            cout << node[i].value << endl;
​
        }
        if(op == "delete"){
            int p;cin >> p;//删除第p个元素
            int i = head;
            while(p--)//检索第p个元素对于的索引（下标）
                i = node[i].next;
            delet(i);
        }
    }
}

STL做法

#include
using namespace std;
​
vector k;
string op;
int m;
​
int main(){
    cin >> m;
     while(m--){
        string op;
        cin >> op;
        if(op == "insert"){
            int x,y;cin >> x >> y;
            k.insert(k.begin()+x,y);//插入
        }
        if(op == "query"){
            int x;in >> x;
            cout << k[x-1] << endl;
        }
        if(op == "delete"){
            int p;cin >> p;
            k.erase(k.begin()+p-1);//删除
        }
    }
​
}

题目描述

现在有一个栈，有n个元素，分别为1,2,…,n1,2,…,n。

我们可以通过push和pop *** 作，将这n个元素依次放入栈中，然后从栈中d出，依次把栈里面的元素写下来得到的序列就是出栈序列。

比如n=3n=3，如果执行push 1, push 2, pop, push 3, pop, pop，那么我们pop *** 作得到的元素依次是2,3,12,3,1。

也就是出栈序列就是2,3,12,3,1。

现在给定一个合法的出栈序列，请输出一个合法的由push和pop *** 作构成的出栈序列。

这里要求push *** 作一定是按1,2,…,n1,2,…,n的顺序。

输入格式

        第一行一个整数nn，接下来一行nn个整数，表示出栈序列。

输出格式

        输出2n2n行，每行一个push x或pop的 *** 作，可以发现一个出现序列对应的 *** 作序列是唯一的。

题解一 – 模拟出栈入栈

#include
using namespace std;
#define rep(i,a,b) for(auto i = a; i <= b; i++)
​
int n;
int a[100005];
stack p;
​
int main(){
    cin >> n;
    rep(i,1,n) cin >> a[i];
    int cnt = 1;
    rep(i,1,n){
        p.push(i);
        printf("push %d\n",i);
        while(!p.empty() && p.top() == a[cnt]){
            p.pop();
            cnt++;
            puts("pop");
        }
    }
​
}

题解二 –更短更简练

#include
using namespace std;
​
int main()
{
    int n,x;
    cin>>n;
    int now=1;
    for(int i = 1;i <= n;i++)
    {
        scanf("%d",&x);//cin输入如果不解绑h
        while(now <= x) printf("push %d\n",now++);
        puts("pop");
    }
    return 0;
}