51Nod 1403 有趣的堆栈

Problem

大家都熟悉堆栈操作。一个堆栈一般有两种操作，push和pop。假设所有操作都是合法的并且最终堆栈为空。我们可以有很多方法记录堆栈的操作， （1） 对每个pop操作，我们记录它之前一共有多少个push操作。 （2） 对每个pop操作，我们记录这个被Pop的元素曾经被压上了几个。 例如：操作push, push, pop, push, push, pop, push, pop, pop, pop 用第一种方法 记录为 2, 4, 5, 5, 5 用第二种方法 记录为 0, 0, 0, 2, 4 这两种记录方法可以互相转化，我们的问题是，给定第二种记录方法的序列，请求出第一种记录方法的序列。

Solution

第i个位置变成i，然后扫到几，就在他前面几个数上加1，我也不知道为啥，推出来的。

Code

#include<stdio.h>
#include<set>
//#include<iostream>
#include<stack>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
typedef long long ll;
typedef long double ld;
typedef double db;
#define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
//using namespace std;
const int mod=998244353;
int mo(ll a,int p){
    return a>=p?a%p:a;
}

inline int rd() {
    int x = 0, f = 1;
    char ch;
    while (ch < '0' || ch > '9') {
        if (ch == '-')f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return f * x;
}
int n,x;
int f[1000020];
char pbuf[100000],*pp=pbuf;
void push(const char c) {
    if(pp-pbuf==100000) fwrite(pbuf,1,100000,stdout),pp=pbuf;
    *pp++=c;
}
void write(int x) {
    static int sta[35];
    int top=0;
    do{sta[top++]=x%10,x/=10;}while(x);
    while(top) push(sta[--top]+'0');
    push(' ');
}
int main(){
    //io_opt;
    n=rd();
    for(register int i=1;i<=n;i++){
        x=rd();
        if(x){
            f[i-x-1]++;
            f[i-1]--;
        }
    }
    register int las=0;
    for(register int i=1;i<=n;i++){
        las=1+las+f[i-1];
        write(las);
    }
    fwrite(pbuf,1,pp-pbuf,stdout);
    return 0;
}