超级记事本([IOI2012]龙虾抄写器-字典树)
#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #include<functional> #include<cmath> #include<cctype> #include<cassert> #include<climits> using namespace std; #define For(i,n) for(int i=1;i<=n;i++) #define Rep(i,n) for(int i=0;i<n;i++) #define Fork(i,k,n) for(int i=k;i<=n;i++) #define ForD(i,n) for(int i=n;i;i--) #define Forp(x) for(int p=pre[x];p;p=next[p]) #define RepD(i,n) for(int i=n;i>=0;i--) #define MEM(a) memset(a,0,sizeof(a)); #define MEMI(a) memset(a,127,sizeof(a)); #define MEMi(a) memset(a,128,sizeof(a)); #define INF (2139062143) #define F (1000000009) #define MAXN (100000+10) #define LogMAXN (20+10) typedef long long ll; struct Tnode { char c; int fa[LogMAXN],deep; Tnode():deep(0){MEM(fa) } Tnode(char _c,int _fa,int _deep):c(_c),deep(_deep){MEM(fa) fa[0]=_fa;} }a[MAXN]; int n,tot=1; void msm(int t) { for(int i=1;a[t].fa[i-1];i++) a[t].fa[i]=a[a[t].fa[i-1]].fa[i-1]; } void type(char c) { tot++; a[tot]=Tnode(c,tot-1,a[tot-1].deep+1);msm(tot); } void query(int p) { p=a[tot].deep-p; int now=tot; while(p) { int t=(int)(trunc(log2(p))); now=a[now].fa[t]; p-=1<<t; } printf("%c\n",a[now].c); } void undo(int p) { tot++; a[tot]=a[tot-1-p]; } int main() { freopen("spnp.in","r",stdin); freopen("spnp.out","w",stdout); scanf("%d",&n); For(i,n) { char s[2],c;int p; scanf("%s",s); switch(s[0]) { case'T':scanf(" %c",&c);type(c);break; case'Q':scanf(" %d",&p);query(p);break; default:scanf(" %d",&p);undo(p);break; } } // while(1); return 0; }
补充:软件开发 , C++ ,