题目链接:http://codeforces.com/contest/1099/problem/C
题意是有一串字符串,其中包含'?'和'*','?'可以将它上一个字符删去或者保留,'*'可以将它上一个字符删除或者保留或者复制任意个,然后输入一个数n,问能不能通过一些操作使字符串长度变为n且不含'?'和'*',可以的话,输出任意一种结果,如果不可以输出Impossible。
思路就是分情况去模拟,不太难,主要是实现过程。
AC代码:
#include <bits/stdc++.h>
using namespace std;
string str;
int n;
int main()
{
cin>>str;
scanf("%d",&n);
int len = str.length();
int xx = 0, yy = 0;
int pos;
for(int i=0;i<len;i++){
if(str[i] == '?') xx ++;
if(str[i] == '*'){
pos = i;
yy ++;
}
}
int ans = len - xx - yy;
if(ans == n){
for(int i=0;i<len;i++){
if(str[i] != '?' && str[i] != '*')
cout<<str[i];
}
puts("");
}
else if(ans < n){
if(yy != 0){
string s;
for(int i=0;i<len;i++){
if(i == pos - 1){
for(int j=0;j<n - ans;j++){
s += str[i];
}
}
if(str[i] != '?' && str[i] != '*') s += str[i];
}
cout<<s<<endl;
}
else puts("Impossible");
}
else{
if(ans - xx - yy > n) puts("Impossible");
else{
string s;
int cnt = 0;
for(int i=0;i<len-1;i++){
if(cnt < ans - n && (str[i+1] == '?' || str[i+1] == '*')){
cnt ++;
continue;
}
if(str[i] != '?' && str[i] != '*'){
s += str[i];
}
}
if(str[len-1] != '?' && str[len-1] != '*')s += str[len-1];
cout<<s<<endl;
}
}
return 0;
}