題目

代碼

#include<bits/stdc++.h> using namespace std; const int N=55; int T,sm,pm,px[N],py[N],pz[N]; char s[N],t[N],ans[N]; inline void solve_bit(int id,int k) {for(int i=1;i<k;i++)t[i+px[id]-1]=t[i+px[id-1]-1];for(int i=k+1,im=pz[id];i<=im;i++)if(t[i+px[id]-1]=='?')t[i+px[id]-1]='0'; } inline bool check(char *a,char *b) {for(int i=1;i<sm;i++){if(a[i]==b[i])continue;return a[i]>b[i];}return false; } inline void solve() {for(int i=1;i<=sm;i++)t[i]=s[i];int lst=1;pm=0;for(int i=1;i<=sm;i++){if(t[i]==','){px[++pm]=lst;py[pm]=i-1;pz[pm]=py[pm]-px[pm]+1;lst=i+1;}}for(int i=1;i<=pm;i++)if(t[px[i]]=='0')return;if(t[1]=='?')t[1]='1';for(int j=2,jm=py[1];j<=jm;j++)if(t[j]=='?')t[j]='0';for(int i=2;i<=pm;i++){if(pz[i]>pz[i-1]){if(t[px[i]]=='?')t[px[i]]='1';for(int j=px[i]+1,jm=py[i];j<=jm;j++)if(t[j]=='?')t[j]='0';}else{bool flag=false;for(int j=1,jm=pz[i];j<=jm&&!flag;j++){char tx=t[j+px[i-1]-1],ty=t[j+px[i]-1];if(isdigit(ty)){if(tx>ty){for(int k=j-1;k>=1;k--){if(t[k+px[i]-1]=='?'&&t[k+px[i-1]-1]!='9'){t[k+px[i]-1]=t[k+px[i-1]-1]+1;solve_bit(i,k);flag=true;break; }}if(!flag)return;}else if(tx<ty){solve_bit(i,j);flag=true;}}}if(!flag){for(int j=pz[i];j>=1;j--){if(t[j+px[i]-1]=='?'&&t[j+px[i-1]-1]!='9'){t[j+px[i]-1]=t[j+px[i-1]-1]+1;solve_bit(i,j);flag=true;}}if(!flag)return;}}}if(check(ans,t)){for(int i=1;i<=sm;i++)ans[i]=t[i];} } inline void Dfs(int k,int lst,int len) {if(k>sm)return solve();if(s[k]==','){if(k-lst<len)return;Dfs(k+1,k,k-lst);}else if(s[k]=='?'){if(k-lst>=len){s[k]=',';Dfs(k+1,k,k-lst);s[k]='?';}Dfs(k+1,lst,len);}else Dfs(k+1,lst,len); } int main() {scanf("%d",&T);while(T--){scanf("%s",s+1);sm=strlen(s+1);s[++sm]=',';for(int i=1;i<=sm;i++)ans[i]='a';Dfs(1,0,2);if(ans[1]=='a'){printf("impossible\n");continue;}else{for(int i=1;i<sm;i++)putchar(ans[i]);putchar('\n'); }}return 0; }

總結

以上是生活随笔為你收集整理的信息学奥赛一本通高手训练1682：最小字典序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。