生活随笔
收集整理的这篇文章主要介绍了
【20171111】Codevs 1064 虫食算80分
小编觉得挺不错的,现在分享给大家,帮大家做个参考.
题目描述 Description
所谓虫食算，就是原先的算式中有一部分被虫子啃掉了，需要我们根据剩下的数字来判定被啃掉的字母。来看一个简单的例子：
43#9865#045
+ 8468#6633
44445506978
其中#号代表被虫子啃掉的数字。根据算式，我们很容易判断：第一行的两个数字分别是5和3，第二行的数字是5。
现在，我们对问题做两个限制：
首先，我们只考虑加法的虫食算。这里的加法是N进制加法，算式中三个数都有N位，允许有前导的0。
其次，虫子把所有的数都啃光了，我们只知道哪些数字是相同的，我们将相同的数字用相同的字母表示，不同的数字用不同的字母表示。如果这个算式是N进制的，我们就取英文字母表午的前N个大写字母来表示这个算式中的0到N-1这N个不同的数字：但是这N个字母并不一定顺序地代表0到N-1)。输入数据保证N个字母分别至少出现一次。
BADC
+ CBDA
DCCC
上面的算式是一个4进制的算式。很显然，我们只要让ABCD分别代表0123，便可以让这个式子成立了。你的任务是，对于给定的N进制加法算式，求出N个不同的字母分别代表的数字，使得该加法算式成立。输入数据保证有且仅有一组解，
输入描述 Input Description
输入包含4行。第一行有一个正整数N(N<=26)，后面的3行每行有一个由大写字母组成的字符串，分别代表两个加数以及和。这3个字符串左右两端都没有空格，从高位到低位，并且恰好有N位。
输出描述 Output Description
输出包含一行。在这一行中，应当包含唯一的那组解。解是这样表示的：输出N个数字，分别表示A，B，C……所代表的数字，相邻的两个数字用一个空格隔开，不能有多余的空格。
样例输入 Sample Input
5
ABCED
BDACE
EBBAA
样例输出 Sample Output
1 0 3 4 2
数据范围及提示 Data Size & Hint
对于30％的数据，保证有N<＝10；
对于50％的数据，保证有N<＝15；
对于全部的数据，保证有N<＝26。
搜索，为了尽快剪枝，我选择了按照竖式从上至下，从右至左逐列检查，一旦不符就剪枝，然而还有两个点没过~~
1 //begin at 15:06
2 #include<stdio.h>
3 int n;
4 int equ[
3][
27];
5 char ch[
3][
27];
6 int dataLet[
27];
7 char dataNum[
27];
8 int search(
int x,
int y,
int extra)
//0=failure,1=success
9 {
10 if(x==
3)
11 {
12 int temp,ans;
13 if(y!=
0)
//pre last line
14 {
15 temp=(dataLet[equ[
0][y]]+dataLet[equ[
1][y]]+extra)%
n;
16 if(temp!=dataLet[equ[
2][y]])
//wrong
17 return 0;
18 else
19 {
20 extra=(dataLet[equ[
0][y]]+dataLet[equ[
1][y]]+extra)/
n;
21 ans=search(
0,y-
1,extra);
22 if(ans)
23 return 1;
24 else
25 return 0;
26 }
27 }
28 else//last last line
29 {
30 temp=(dataLet[equ[
0][y]]+dataLet[equ[
1][y]]+extra)%
n;
31 extra=(dataLet[equ[
0][y]]+dataLet[equ[
1][y]]+extra)/
n;
32 if(temp!=dataLet[equ[
2][y]]||extra)
//need to extra or wrong
33 return 0;
34 else
35 return 1;
36 }
37 }
38 else
39 {
40 int i;
41 int ans;
42 if(dataLet[equ[x][y]]!=-
1)
//used
43 ans=search(x+
1,y,extra);
44 else
45 {
46 for(i=
0;i<n;i++
)
47 {
48 if(dataNum[i]!=-
1)
49 continue;
50 dataLet[equ[x][y]]=
i;
51 dataNum[i]=equ[x][y]+
'A';
52 ans=search(x+
1,y,extra);
53 if(ans)
54 return ans;
55 dataLet[equ[x][y]]=dataNum[i]=-
1;
//used
56 }
57 }
58 return ans;
59 }
60
61 }
62 void testPrint(
int input)
63 {
64 printf(
"%d ",input);
65 }
66 void get(
char *
output)
67 {
68 scanf(
"%s",output);
69 getchar();
70 }
71 int main()
72 {
73 scanf(
"%d",&
n);
74 ch[
0][
0]=
getchar();
75 int i,j;
76 for(i=
0;i<n;i++
)
77 {
78 dataLet[i]=-
1;
79 dataNum[i]=-
1;
80 }
81 get(ch[
0]);
82 get(ch[
1]);
83 get(ch[
2]);
84 for(i=
0;i<
3;i++
)
85 {
86 for(j=
0;j<n;j++
)
87 {
88 equ[i][j]=ch[i][j]-
'A';
//turn to int
89 }
90 }
91 search(
0,n-
1,
0);
92 for(i=
0;i<n-
1;i++
)
93 {
94 printf(
"%d ",dataLet[i]);
95 }
96 printf(
"%d\n",dataLet[i]);
97 return 0;
98 }
99 //end at 15:57
转载于:https://www.cnblogs.com/CXSheng/p/7819327.html
《新程序员》：云原生和全面数字化实践50位技术专家共同创作，文字、视频、音频交互阅读
总结
以上是生活随笔为你收集整理的【20171111】Codevs 1064 虫食算80分的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。
