NOIP2004提高组T4:虫食算

发布时间:2024年01月17日

题目链接

[NOIP2004 提高组] 虫食算

题目描述

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

43#9865#045 + 8468#6633  ̄ 44445509678 \begin{aligned} \verb!43#9865#045! \\ +\qquad \verb!8468#6633! \\[-1em]\underline{\kern{8em}} \\ \verb!44445509678! \\ \end{aligned} 43#9865#045+8468#6633?44445509678?

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

现在,我们对问题做两个限制:

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

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

BADC + CBDA  ̄ DCCC \begin{aligned} \verb!BADC! \\ +\quad \verb!CBDA! \\[-1em]\underline{\kern{4em}} \\ \verb!DCCC! \\ \end{aligned} BADC+CBDA?DCCC?

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

输入格式

输入的第一行是一个整数 n n n,代表进制数。

第二到第四行,每行有一个由大写字母组成的字符串,分别代表两个加数以及和。这 3 3 3 个字符串左右两端都没有空格,从左到右依次代表从高位到低位,并且恰好有 n n n 位。

输出格式

输出一行 n n n 个用空格隔开的整数,分别代表 A , B , … A,B, \dots A,B, 代表的数字。

样例 #1

样例输入 #1

5
ABCED
BDACE
EBBAA

样例输出 #1

1 0 3 4 2

提示

数据规模与约定
  • 对于 30 % 30\% 30% 的数据,保证 n ≤ 10 n \le 10 n10
  • 对于 50 % 50\% 50% 的数据,保证 n ≤ 15 n \le 15 n15
  • 对于 100 % 100\% 100% 的数据,保证 1 ≤ n ≤ 26 1 \leq n \leq 26 1n26

算法思想

根据题目描述,可以分析出下面一些有用的信息

  • 要求的是一个 n n n进制的加法算式,其中三个数都有 n n n 位,允许有前导的 0 0 0
  • 取英文字母表的前 n n n 个大写字母来表示这个算式中的 0 0 0 n ? 1 n - 1 n?1。相同的数字用相同的字母表示,不同的数字用不同的字母表示
  • 输入数据保证 n n n 个字母分别至少出现一次,输入数据保证有且仅有一组解。

题目中给出的数据范围比较小, 1 ≤ n ≤ 26 1 \leq n \leq 26 1n26,可以暴力搜索每个英文字母代表的数字。由于不同的数字用不同的字母表示,因此要搜索的状态空间为 26 ! ≈ 4 × 1 0 26 26!\approx4\times10^{26} 26!4×1026,显然要进行剪枝。

合法性剪枝

加法算式是按照从右向左的顺序进行计算的,要验证计算是否合法,即判断 ( a + b + t ) % n (a+b+t)\%n (a+b+t)%n是否等于 c c c,其中 t t t表示进位,如下图所示。
在这里插入图片描述

  • 如果当前列右边(绿色格子中)的所有数都已经确定了,那么进位 t t t也就确定了,如果 ( a + b + t ) % n ≠ c (a+b+t)\%n\ne c (a+b+t)%n=c,则该方案不合法。
  • 如果当前列右边(绿色格子中)存在不确定的数,那么进位 t t t 2 2 2种可能。
    • t = 0 t = 0 t=0时, ( a + b + 0 ) % n = = c (a+b+0)\%n == c (a+b+0)%n==c
    • t = 1 t = 1 t=1时, ( a + b + 1 ) % n = = c (a+b+1)\%n == c (a+b+1)%n==c
    • 当上述两种情况都不成立时,则该方案不合法。
  • 如果当前列是最高位(第 0 0 0列,从左到右输入),并且该列的和 ( a + b + t ) ≥ n (a+b+t)\ge n (a+b+t)n,即最高位有进位,则该方案也不合法。因为题目要求三个数都有 n n n 位。

以上就是需要进行合法性剪枝的情况。

优化搜索顺序

从上面的分析可以发现,当右侧的所有数确定了,进位 t t t也就确定了,此时能更快判断出是否需要剪枝。为了提高剪枝效率,应该优先确定右边的数字,按照从右向左的顺序进行搜索。

除此之外,还可以从大到小枚举字母代表的数字,提前剪去最高位有进位的搜索分枝。

时间复杂度

最坏情况下需要搜索的状态空间为 n ! n! n!,但由于剪枝的存在,实际搜索到的空间很小。

代码实现

#include <iostream>
#include <cstring>
using namespace std;
const int N = 30;
int n, q[N], ans[N];
bool st[N], used[N];
char s[3][N];
bool check()
{
    int t = 0; //进位初始化为0
    //从右向左检查算式每一列是否合法
    for(int i = n - 1; i >= 0; i --)
    {
        int a = ans[s[0][i] - 'A'], b = ans[s[1][i] - 'A'], c = ans[s[2][i] - 'A'];
        if(a != -1 && b != -1 && c != -1) //abc都已确认
        {
            if(t != -1) //进位已经确定
            {
                if((a + b + t) % n != c) return false; 
                if(!i && (a + b + t) >= n) return false; //最高位有进位
                t = (a + b + t) / n; //计算进位
            }
            else //进位不确定
            {
                if((a + b + 0) % n != c && (a + b + 1) % n != c) return false;
                if(!i && (a + b) >= n) return false; //最高位有进位
            }
        }
        else //abc只要有一位不确定,进位就不确定
        {
            t = -1;
        }
    }
    return true;
}
//搜索队列中的第t个字符所代表的数字
bool dfs(int t) 
{
    if(t == n) return true;
    //优化搜索顺序,从大到小枚举字母代表的数字
    for(int i = n - 1; i >= 0; i --)
    {
        if(!used[i])//如果数字i没有使用过
        {
            used[i] = true;
            ans[q[t]] = i; //搜索队列中第t个字母代表数字i
            if(check() && dfs(t + 1)) return true;//合法性剪枝
            used[i] = false; //恢复现场
            ans[q[t]] = -1;
        }
    }
    return false; //注意,当前方案不成功则返回false
}

int main()
{
    cin >> n;
    for(int i = 0; i < 3; i ++) cin >> s[i];
    //优化搜索顺序,从右向左将字母存储到搜索队列中
    for(int i = n - 1, k = 0; i >= 0; i --)
        for(int j = 0; j < 3; j ++)
        {
            int x = s[j][i] - 'A'; 
            if(!st[x]) //如果x没有出现过
            {
                q[k ++] = x; //将x放入搜索队列中
                st[x] = true;
            }
        }
    memset(ans, -1, sizeof ans); //-1表示字母代表的数字还未确定
    dfs(0);
    //从A开始输出每个字符代表的数字
    for(int i = 0; i < n; i ++) cout << ans[i] << " ";
    return 0;
}
文章来源:https://blog.csdn.net/qiaoxinwei/article/details/135652384
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。