| 记录编号 |
98090 |
评测结果 |
AAAAAAAWAA |
| 题目名称 |
816.复原序列 |
最终得分 |
90 |
| 用户昵称 |
 cstdio |
是否通过 |
未通过 |
| 代码语言 |
C++ |
运行时间 |
1.719 s |
| 提交时间 |
2014-04-21 17:31:35 |
内存使用 |
15.88 MiB |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
using namespace std;
const int SIZEN=20001,SIZESTEP=200;
string A,B;
vector<int> block;
int M;
bool stepf[SIZESTEP][SIZEN];
vector<int> tpable[2];
bool c[SIZESTEP][SIZEN][2];//0储存v-1是否可行,1储存v是否可行
bool visit[SIZESTEP][SIZEN];
bool ansable[SIZEN][2]={0};
//1是+,0是-
vector<int> reach[SIZEN];
bool tpf[2][SIZEN];
int BOT;
bool solution=false;
void getgraph(bool f[SIZEN],int bot,int n){
memcpy(tpf[0],f,sizeof(tpf[0]));
//cout<<sizeof(f)<<" "<<sizeof(tpf[0])<<endl;
//cout<<endl;for(int i=0;i<B.size();i++) cout<<f[i]<<" ";cout<<endl;
//for(int i=0;i<B.size();i++) cout<<tpf[0][i]<<" ";cout<<endl;
tpable[0].clear();
memset(c,0,sizeof(c));
for(int i=0;i<B.size();i++) if(f[i]) tpable[0].push_back(i);
for(int i=1;i<=n;i++){
int k=(i&1);
memset(tpf[k],0,sizeof(tpf[0]));
tpable[k].clear();
for(int t=0;t<tpable[k^1].size();t++){
//cout<<tpable[k^1][t]<<" ";
for(int j=tpable[k^1][t];j<=tpable[k^1][t]+1;j++){
if(tpf[k][j]) continue;
if(B[j]=='+'){
if(A[bot+i]=='+'||A[bot+i]=='?'){
if(tpf[k^1][j-1]){
c[i][j][0]=true;
tpf[k][j]=true;
}
}
else tpf[k][j]=0;
}
else if(B[j]=='*'){
if(A[bot+i]=='-'||A[bot+i]=='?'){
if(tpf[k^1][j-1]){
c[i][j][0]=true;
tpf[k][j]=true;
}
if(tpf[k^1][j]){
c[i][j][1]=true;
tpf[k][j]=true;
}
}
else tpf[k][j]=0;
}
if(tpf[k][j]) tpable[k].push_back(j);
//cout<<i<<" "<<j<<" "<<c[i][j][0]<<" "<<c[i][j][1]<<endl;
}
}
//cout<<" ";for(int j=0;j<B.size();j++){cout<<tpf[k][j]<<" ";}cout<<endl;
}
}
void work(void){
if(!solution){
printf("No Solution\n");
return;
}
BOT=A.size();
//int k=(A.size()-1)&1;
ansable[A.size()-1][0]=true;
reach[A.size()-1].push_back(B.size()-1);
memset(visit,0,sizeof(visit));
for(int i=A.size()-1;i>0;i--){
if(i<=BOT){
BOT=((i-1)/M)*M;
//cout<<i/M<<endl;
//cout<<"from "<<" "<<BOT<<": "<<endl;
getgraph(stepf[(i-1)/M],BOT,i-BOT);
memset(visit,0,sizeof(visit));
}
//cout<<i<<" "<<BOT<<endl;
for(int t=0;t<reach[i].size();t++){
int j=reach[i][t];//第i层,B[j]能到达
//cout<<i<<" "<<j<<endl;
if(visit[i-BOT][j]) continue;
visit[i-BOT][j]=true;
for(int r=0;r<=1;r++){
if(c[i-BOT][j][r]){
char ch=B[j+(r-1)];
if(ch=='+') ansable[i-1][1]=true;
else if(ch=='*') ansable[i-1][0]=true;
reach[i-1].push_back(j+(r-1));
}
}
}
}
for(int i=1;i<A.size()-1;i++){
//cout<<ansable[i][0]<<" "<<ansable[i][1]<<endl;
if(ansable[i][0]&&ansable[i][1]) printf("?");
else if(ansable[i][0]) printf("-");
else if(ansable[i][1]) printf("+");
}
printf("\n");
}
void getable(void){
memset(tpf[0],0,sizeof(tpf[0]));
tpf[0][0]=true;
memcpy(stepf[0],tpf[0],sizeof(tpf[0]));
tpable[0].push_back(0);
for(int i=1;i<A.size();i++){
int k=(i&1);
memset(tpf[k],0,sizeof(tpf[0]));
tpable[k].clear();
//cout<<tpable[k^1].size()<<endl;
for(int t=0;t<tpable[k^1].size();t++){
for(int j=tpable[k^1][t];j<=tpable[k^1][t]+1;j++){
if(tpf[k][j]) continue;
if(B[j]=='+'){
if(A[i]=='+'||A[i]=='?') tpf[k][j]=tpf[k^1][j-1];
else tpf[k][j]=0;
}
else if(B[j]=='*'){
if(A[i]=='-'||A[i]=='?') tpf[k][j]=(tpf[k^1][j-1]||tpf[k^1][j]);
else tpf[k][j]=0;
}
if(tpf[k][j]) tpable[k].push_back(j);
if(i==A.size()-1&&j==B.size()-1) solution=tpf[k][j];
}
}
/*for(int j=0;j<B.size();j++){
if(B[j]=='+'){
if(A[i]=='+'||A[i]=='?') tpf[k][j]=tpf[k^1][j-1];
else tpf[k][j]=0;
}
else if(B[j]=='*'){
if(A[i]=='-'||A[i]=='?') tpf[k][j]=(tpf[k^1][j-1]||tpf[k^1][j]);
else tpf[k][j]=0;
}
}*/
//cout<<i<<": ";for(int j=0;j<B.size();j++){cout<<tpf[k][j]<<" ";}cout<<endl;
if(i%M==0) memcpy(stepf[i/M],tpf[k],sizeof(tpf[0]));
//cout<<sizeof(tpf[0])<<endl;
}
//for(int i=0;i<=(A.size()-1)/M;i++){cout<<i*M<<": ";for(int j=0;j<B.size();j++){cout<<stepf[i][j]<<" ";}cout<<endl;}
}
void init(void){
cin>>A;
if(M<1) M=1;
int x;
while(scanf("%d",&x)!=EOF) block.push_back(x);
A="-"+A+"-";
B="*";
for(int i=0;i<block.size();i++){
for(int j=0;j<block[i];j++) B+="+";
B+="*";
}
M=sqrt(A.size()+0.0);
}
int main(){
freopen("recover.in","r",stdin);
freopen("recover.out","w",stdout);
init();
//cout<<A<<endl<<B<<endl;
getable();
work();
//cout<<A.size()<<" "<<M<<endl;
//cout<<clock()<<endl;
return 0;
}