【NOIP2012模拟8.9】监听还原

Description

Alice和Bob正在悄悄地给对方发信息，信息都是由英文小写字母组成的，他们约定，所有的字母都得经过一个字母表进行变换，以防泄漏。另一方面John却在监听。

John发现，Alice和Bob通信的时候，总是先发送加密后的密文，然后紧接着发送原文。

但是Alice和Bob似乎也意识到了似乎有人监听，有时候会随意中断了他们的通信。不过每次都是在发送完密文之后才停止传送的。也就是说，John截获到的信息是密文的全文以及前一部分原文。原文可能一个字符都没有，也可能原文的全文都被截获。

现在John比较头疼，他虽然已经得到了他们两个人通信的加密字母表，但是分不清楚什么地方是密文和明文的分界线。你能帮他还原回完整的传输内容吗？

如果有多种可能时，John认为那个最短的信息才是原始的。

Input

第一行是密码表格，包含26个小写字母，依次表示a-z加密后的字母。

第二行是John截获到的通信信息。

Output

包含一行，表示还原后的通信信息。

Sample Input

abcdefghijklmnopqrstuvwxyz abcdab

Sample Output

abcdabcd

Hint

通信长度L<=100000。

题解

数据不强，直接暴力就行 从n/2开始枚举每个交界点，往后面匹配，不成功就break hack数据：a·····ab

code

#include<cctype> #include<cstdio> #include<cstdlib> #define R register #define ll long long #define max(a,b) (a>b?a:b) #define min(a,b) (a<b?a:b) using namespace std; const int N=1e5+10; int n,k,last,z[N],head[N],to[N*2],next[N*2],w[N*2]; ll f[N][2]; inline void read(int &x){ x=0;char ch=getchar(); while(!isdigit(ch))ch=getchar(); while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); } inline void add(int a,int b,int c){to[++last]=b,w[last]=c,next[last]=head[a],head[a]=last;} inline void dfs(int u,int v){ R ll sum=0,ma=0; for(R int i=head[u];i;i=next[i]) if(to[i]!=v){ dfs(to[i],u),sum+=min(f[to[i]][0],f[to[i]][1]+w[i]); ma=max(ma,min(f[to[i]][0],f[to[i]][1]+w[i])-f[to[i]][1]); } if(z[u])f[u][0]=0x7ffffffffff,f[u][1]=sum; else f[u][0]=sum,f[u][1]=sum-ma; } int main(){ int a,b,c; read(n),read(k); for(R int i=1;i<=k;++i)read(a),z[a+1]=1; for(R int i=1;i<n;++i){ read(a),read(b),read(c); add(a+1,b+1,c),add(b+1,a+1,c); } dfs(1,1); printf("%lld",min(f[1][0],f[1][1])); }