作者:wgsd325 | 来源:互联网 | 2023-10-10 20:17
题目链接:https:vjudge.netproblemUVA-12107题意:给出一个数字谜,要求修改尽量少的数,使修改后的数字谜只有唯一解。空格和数字可以随意替换,但不能增
题目链接:
https://vjudge.net/problem/UVA-12107
题意:
给出一个数字谜,要求修改尽量少的数,使修改后的数字谜只有唯一解。空格和数字可以随意替换,但不能增删,数字谜中所有涉及的数必须是没有前导零的正数。输入数字谜一定形如a*b=c,其中a、b、c分别最多有2、2、4位。
题解:
http://www.cnblogs.com/tyty-Somnuspoppy/p/6366725.html
1、因为输出字典序最小,所以每一位数按“*0123456789”顺序枚举。
2、如果当前要修改的数与即将被修改的数相同,则cnt不加1。
3、检查积的时候,为防超时,只枚举两个乘数,通过检查积的位数和积的已确定数字来验证。
4、遇到空格要跳过并检查返回结果。
代码:
#include
using namespace std;
typedef long long ll;
#define MS(a) memset(a,0,sizeof(a))
#define MP make_pair
#define PB push_back
const int INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
inline ll read(){
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn = 1e5+10;
string s,ss = "*0123456789";
pair<int,int> mp[3];
int maxd,num,len;
bool leadingzero(int x){
for(int i=0; i<2; i++)
if(mp[i].first == x) return true;
return false;
}
int changetodigit(string str){
int res = 0;
for(int i=0; i<(int)str.size(); i++)
res = res*10 + str[i]-'0';
return res;
}
bool check(){
int x = changetodigit(s.substr(mp[0].first,mp[0].second-mp[0].first+1));
int y = changetodigit(s.substr(mp[1].first,mp[1].second-mp[1].first+1));
char str[5];
sprintf(str,"%d",x*y);
int len = strlen(str);
if(mp[2].second-mp[2].first+1 != len) return false;
for(int i=mp[2].first; i<=mp[2].second; i++){
if(s[i] == '*') continue;
if(s[i] != str[i-mp[2].first]) return false;
}
return true;
}
void judge(int cur){
if(num>1) return ;
if(cur == mp[1].second+1){
if(check()) ++num;
return ;
}
if(s[cur] != '*') judge(cur+1);
else{
for(int i=1; i<11; i++){
if(i==1 && leadingzero(cur)) continue;
s[cur] = ss[i];
judge(cur+1);
s[cur] = '*';
}
}
}
bool dfs(int d,int cur){
if(d >= maxd){
string tmp = s;
num = 0;
judge(0);
if(num == 1) return true;
s = tmp;
return false;
}
if(cur == len) return false;
if(s[cur] == ' '){
if(dfs(d,cur+1)) return true;
}else{
char c = s[cur];
for(int i=0; i<11; i++){
if(i==1 && leadingzero(cur)) continue;
if(c == ss[i]) {
if(dfs(d,cur+1)) return true;
}else{
s[cur] = ss[i];
if(dfs(d+1,cur+1)) return true;
s[cur] = c;
}
}
}
return false;
}
int main(){
int cas = 0;
while(getline(cin,s)){
if(s[0] == '0') break;
len = s.size();
int cnt=0,start=0;
for(int i=0; i if(s[i] == ' '){
mp[cnt++] = make_pair(start,i-1);
start = i+1;
}
}
mp[cnt] = make_pair(start,len-1);
printf("Case %d: ",++cas);
for(maxd=0; ; maxd++){
if(dfs(0,0)){
printf("%s\n",s.c_str());
break;
}
}
}
return 0;
}