洛谷P1092 虫食算

小咪咪 2022-05-31 12:42 138阅读 0赞

## 题目描述 ##

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

[http://paste.ubuntu.com/25448822/][http_paste.ubuntu.com_25448822]

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

现在，我们对问题做两个限制：

首先，我们只考虑加法的虫食算。这里的加法是N进制加法，算式中三个数都有N位，允许有前导的0。

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

[http://paste.ubuntu.com/25448824/][http_paste.ubuntu.com_25448824]

上面的算式是一个4进制的算式。很显然，我们只要让ABCD分别代表0123，便可以让这个式子成立了。你的任务是，对于给定的N进制加法算式，求出N个不同的字母分别代表的数字，使得该加法算式成立。输入数据保证有且仅有一组解

## 输入输出格式 ##

输入格式：

包含四行。第一行有一个正整数N(N<=26)，后面的3行每行有一个由大写字母组成的字符串，分别代表两个加数以及和。这3个字符串左右两端都没有空格，从高位到低位，并且恰好有N位。

输出格式：

包含一行。在这一行中，应当包含唯一的那组解。解是这样表示的：输出N个数字，分别表示A，B，C……所代表的数字，相邻的两个数字用一个空格隔开，不能有多余的空格。

## 输入输出样例 ##

输入样例\#1： 复制

5
    ABCED
    BDACE
    EBBAA

输出样例\#1： 复制

1 0 3 4 2

## 说明 ##

对于30％的数据，保证有N<＝10；

对于50％的数据，保证有N<＝15；

对于全部的数据，保证有N<＝26。

noip2004提高组第4题

一看就是个搜索题，上来二话不说就dfs每个字母，然后再判断，结果只得40分

错误代码：根本没有优化，暴力的说

#include<stdio.h>
    #include<algorithm>
    #include<iostream>
    #include<string>
    using namespace std;
    
    int alphar[26];
    bool book[26];
    bool isUsed[26];
    int N;
    string A, B, Add;
    
    bool check()
    {
    	int t;
    	for (int i = N - 1; i >= 0; i--)
    	{
    		int a = alphar[A[i] - 'A'];
    		int b = alphar[B[i] - 'A'];
    		int c = alphar[Add[i] - 'A'];
    		if (i == N - 1)
    		{
    			t = (a + b) / N;
    			if ((a + b) % N == c)
    				continue;
    			else
    				return false;
    		}
    		else
    		{
    			if ((a + b + t) % N == c)
    			{
    				t = (a + b + t) / N;
    				continue;
    			}
    			else
    				return false;
    		}
    	}
    	return true;
    }
    
    void dfs(int now)
    {
    	if (now==N && check())
    	{
    		for (int i = 0; i < N; i++)
    			cout << alphar[i]<<' ';
    		exit(0);
    	}
    	else
    	{
    
    		for (int i = 0;i<N; i++)
    		{
    			if (isUsed[i]) continue;
    			alphar[now] = i;
    			book[now] = true;
    			isUsed[i] = true;
    			dfs(now + 1);
    			book[now] = false;
    			isUsed[i] = false;
    		}
    	}
    }
    
    int main()
    {
    	//freopen("1.txt", "r", stdin);
    	cin >> N;
    	cin >> A >> B >> Add;
    	dfs(0);
    	return 0;
    }

正确思路：

参考题解：

1.[https://zzlzk.blog.luogu.org/solution-p1092][https_zzlzk.blog.luogu.org_solution-p1092]

2.[https://www.luogu.org/blog/user26834/solution-p1092][https_www.luogu.org_blog_user26834_solution-p1092]

*  说一下搜索怎么做
 *  这个题目第一个难点在于你要理解 n*n* 进制的加法
 *  n*n* 进制的加法就是在十进制的基础上满十进一改成满n*n* 进一
 *  由于这道题只考虑加法，所以进位只可能是 11 ，证明小学生都会，略
 *  搜索的大体思路就是从第 11 位的值开始搜，搜到最后一位，判断是否合法
 *  考虑剪枝
 *  33 个字符串的长度都是 n*n* ，由此可以想到一个最简单的剪枝
 *  最高位不能有进位
 *  如果有进位，显然第 33 个串的长度不会是 n*n* ，而是n+1*n*\+1 ，这并不合法
 *  一个剪枝显然不够啊，再想一个
 *  文字不太好描述，我们看图（不会用latex写竖式啊QAQ）
    
    ![qwq][]
 *  假设这是十进制下的加法，怎么判断这个竖式对不对？
 *  显然这个竖式是错误的，因为个位上(8+6) mod 10=4 \\not=5(8\+6)*m**o**d*10=4̸=5
 *  由此推广到每一位，但是还要考虑进位，不慌，看另一张图
    
    ![qwq][qwq 1]
 *  这个竖式是对的还是错的？
 *  这并不好判断，虽然(8+6) mod 10=4 \\not=5(8\+6)*m**o**d*10=4̸=5 ，但是这是中间位，有可能有进位
 *  如果有进位， 那么(8+6+1) mod 10=5(8\+6\+1)*m**o**d*10=5 ，这一位就是合法的了。
 *  综合上面的分析，得到了另一个剪枝方法
 *  用 A*A* 和 B*B* 表示两个加数，用 C*C* 表示两个加数的和
 *  如果某 i*i* 位，满足(A\[i\]+B\[i\])mod\\;n\\not=C\[i\](*A*\[*i*\]\+*B*\[*i*\])*m**o**d**n*̸=*C*\[*i*\] 和 (A\[i\]+B\[i\]+1)mod\\;n\\not=C\[i\](*A*\[*i*\]\+*B*\[*i*\]\+1)*m**o**d**n*̸=*C*\[*i*\]
 *  根据上面的分析，这种状态肯定不对，直接 return*r**e**t**u**r**n* 就好了
 *  或许还有别的剪枝，但是这两个应该够用了
 *  我的代码里还用了一个玄学的 next*n**e**x**t* 数组，有什么用照着样例手推一遍就知道了，比较好理解。实在看不懂可以私信我qwq

AC代码：

#include <iostream>
    #include <cstring>
    #include <cstdlib>
    #include <cstdio>
    #include <cmath>
    #define maxn 30
    using namespace std;
    
    bool use[maxn];//记录数字是否被用过
    char a[4][maxn];//存储三个字符串
    int ans[maxn];//存储答案
    int N;
    int id(char c)
    {
    	return c - 'A';
    }
    
    void dfs(int x, int y, int t)//x代表列，y代表行，t代表进位
    {
    	if (x == 0)//收到最后一列了
    	{
    		if (t == 0)//且最后一列的进位必须为0
    		{
    			for (int i = 0; i < N; i++)//输出
    				cout << ans[i] << ' ';
    			exit(0);
    		}
    		return;//不符合就返回
    	}
    	for (int i = x - 1; i>=1; i--)//剪枝1
    	{
    		int w1 = ans[id(a[1][i])];//w1表示第一行字符串代表的数字
    		int w2 = ans[id(a[2][i])];//w2表示第二行字符串代表的数字
    		int w3 = ans[id(a[3][i])];//w3表示第三行字符串代表的数字
    		if (w1 == -1 || w2 == -1 || w3 == -1)//如果这个位置上还没被赋值，就返回
    			continue;
    		if ((w1 + w2) % N != w3 && (w1 + w2 + 1) % N != w3)
    			return;//如果无论进位与否，都不能整除对应的w3就说明字符串不匹配，直接return ;
    	}
    	if (ans[id(a[y][x])] == -1)//如果这个位置没有数字
    	{
    		for (int i = N - 1; i >= 0; i--)//从N-1到0填充会快
    		if (!use[i])//如果这个数没有用过
    		{
    			if (y != 3)//且不是最后一行
    			{
    				//打上标记和记录
    				use[i] = true;
    				ans[id(a[y][x])] = i;
    				dfs(x, y + 1, t);//继续搜索下一行
    				//删除标记和记录
    				use[i] = false;
    				ans[id(a[y][x])] = -1;
    			}
    			else
    			{
    				int w = ans[id(a[1][x])] + ans[id(a[2][x])] + t;//两个数加上它们的进位
    				if (w%N != i)
    					continue;
    				//打上标记和记录
    				use[i] = true;
    				ans[id(a[3][x])] = i;
    				dfs(x - 1, 1, w / N);//搜索下一列，进位需要改变
    				//删除标记和记录
    				use[i] = false;
    				ans[id(a[3][x])] = -1;
    			}
    		}
    	}
    	else
    	{
    		if (y != 3)//继续搜索
    			dfs(x, y + 1, t);
    		else
    		{
    			int w = ans[id(a[1][x])] + ans[id(a[2][x])] + t;
    			if (w%N != ans[id(a[3][x])])//剪枝2
    				return;
    			dfs(x - 1, 1, w / N);//搜索下一列，进位需要改变 
    		}
    	}
    }
    
    int main()
    {
    	//freopen("1.txt", "r", stdin);
    	cin >> N;
    	for (int i = 1; i <= 3; i++)
    		scanf("%s", a[i] + 1);
    	memset(ans, -1, sizeof(ans));//用-1代表没填充
    	
    	dfs(N, 1, 0);
    	return 0;
    }

[http_paste.ubuntu.com_25448822]: http://paste.ubuntu.com/25448822/
[http_paste.ubuntu.com_25448824]: http://paste.ubuntu.com/25448824/
[https_zzlzk.blog.luogu.org_solution-p1092]: https://zzlzk.blog.luogu.org/solution-p1092
[https_www.luogu.org_blog_user26834_solution-p1092]: https://www.luogu.org/blog/user26834/solution-p1092
[qwq]: https://i.loli.net/2017/08/22/599bd0b8e5d0b.png
[qwq 1]: https://i.loli.net/2017/08/22/599bd3642a721.png