【Luogu1092】虫食算

Source and Judge

NOIP2004 提高组 T4
Luogu1092
Caioj1519

Problem

【Brief description】
所谓虫食算,就是原先的算式中有一部分被虫子啃掉了,
需要我们根据剩下的数字来判定被啃掉的字母。
来看一个简单的栗子:

1
2
3
43#9865#045
+ 8468#6633
=44445509678


其中#号代表被虫子啃掉的数字。
根据算式,我们很容易判断:第一行的两个数字分别是5和3,第二行的数字是5。

现在,我们对问题做两个限制:
首先,我们只考虑加法的虫食算。
这里的加法是N进制加法,算式中三个数都有N位,允许有前导的0。

其次,虫子把所有的数都啃光了,我们只知道哪些数字是相同的,
我们将相同的数字用相同的字母表示,不同的数字用不同的字母表示。
如果这个算式是N进制的,
我们就取英文字母表的前N个大写字母来表示这个算式中的0到N-1这N个不同的数字,
但是这N个字母并不一定顺序地代表0到N-1。
输入数据保证N个字母分别至少出现一次。
1
2
3
BADC
+CBDA
DCCC


上面的算式是一个4进制的算式。
很显然,我们只要让ABCD分别代表0123,便可以让这个柿子成立了。
你的任务是,对于给定的N进制加法算式,
求出N个不同的字母分别代表的数字,使得该加法算式成立。
输入数据保证有且仅有一组解.
【Input】
包含四行。
第一行有一个正整数N,
后面的3行每行有一个由大写字母组成的字符串,分别代表两个加数以及和。
这3个字符串左右两端都没有空格,从高位到低位,并且恰好有N位。
【Output】
包含一行。在这一行中,应当包含唯一的那组解。
解是这样表示的:
输出N个数字,分别表示A,B,C……所代表的数字,
相邻的两个数字用一个空格隔开,不能有多余的空格。
【Limited conditions】
N<=26
【Sample input】
5
ABCED
BDACE
EBBAA
【Sample output】
1 0 3 4 2
【Sample explanation】

Record

1h

Analysis1

请先思考后再展开

先打了个暴力,想着数据可能水【其实的确没有极限数据】
但依然TLE,但已经剪枝了
然后跟着题解,发现可以不递推进位,减更多
这时候还是差一点,然后就是一个神奇的玄学操作了:
重新编号(从后往前),dfs决断的时候编号从大到小
我一开始想着,这是为了搞掉首位进位(这个也是跟题解学的)
那既然如此编号从前往后,dfs的时候从小到大也一样吧
结果差距是几十倍??

考场上绝对不能这么玩,会死的很惨

Code1

请先思考后再展开
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
//Zory-2018
//****************头文件****************
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<set>
#include<string>
#include<map>
#include<iostream>
#include<algorithm>
#ifdef WIN32
#define BIGN "%I64d"
#else
#define BIGN "%lld"
#endif
using namespace std;
typedef long long ll;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
//****************全局常量****************
const int INF=0x3f3f3f3f;
//****************全局定义****************
int n;
int a[30];
bool used[30];
int jia1[30],jia2[30],he[30];
//****************实现****************
bool finaljudge()
{
int jw=0;
for(int i=1;i<=n;i++)
{
int x=a[jia1[i]],y=a[jia2[i]],z=a[he[i]];
if( (x+y+jw)%n!=z ) return 0;
jw=(x+y+jw)/n;
}
return 1;
}
bool check()
{
if(a[jia1[n]]+a[jia2[n]]>=n) return 0;
for(int i=1;i<=n;i++)//从后往前
{
int x=a[jia1[i]],y=a[jia2[i]],z=a[he[i]];
if(x<0 or y<0 or z<0) continue;//残缺
if( (x+y)%n!=z and (x+y+1)%n!=z ) return 0;
}
return 1;
}
int nxt[30];//新编号-Important
void Print()
{
for(int i=1;i<=n;i++) printf("%d ",a[i]);
exit(0);
}
void dfs(int x)
{
if(x>n)
{
if(finaljudge()) Print();
return;
}
//for(int i=0;i<=n-1;i++) 玄学操作
for(int i=n-1;i>=0;i--)
if(used[i]==0)
{
a[ nxt[x] ]=i;
if(check())
{
used[i]=1;
dfs(x+1);
used[i]=0;
}
a[ nxt[x] ]=-1;
}
}
int cnt=0;//新编号-Important
void putnxt(int x)
{
if(used[x]==0)
{
used[x]=1;//借用
nxt[++cnt]=x;
}
}
//****************主函数****************
char ch[30];
int main()
{
scanf("%d",&n);
scanf("%s",ch+1);for(int i=n;i>=1;i--) jia1[n-i+1]=ch[i]-'A'+1;
scanf("%s",ch+1);for(int i=n;i>=1;i--) jia2[n-i+1]=ch[i]-'A'+1;
scanf("%s",ch+1);for(int i=n;i>=1;i--) he[n-i+1]=ch[i]-'A'+1;
for(int i=1;i<=n;i++)//新编号-Important
{
putnxt(jia1[i]);
putnxt(jia2[i]);
putnxt(he[i]);
}
memset(used,0,sizeof(used));
memset(a,-1,sizeof(a));
dfs(1);
}

Analysis2

Code2

请先思考后再展开
1
2

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/posts/6a62.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%