69. [NOIP2004] 虫食算

69. [NOIP2004] 虫食算

★★★   输入文件:alpha.in   输出文件:alpha.out   简单对比
时间限制:1 s   内存限制:128 MB

【问题描述】

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

43#9865#045 
   + 8468#6633

-----------

44445509678

其中#号代表被虫子啃掉的数字。根据算式,我们很容易判断:第一行的两个数字分别是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个不同的字母分别代表的数字,使得该加法算式成立。输入数据保证有且仅有一组解,

【输入文件】

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

【输出文件】

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

【样例输入】


ABCED 
BDACE 
EBBAA

【样例输出】

1 0 3 4 2

【数据规模】

对于30%的数据,保证有N<=10; 
对于50%的数据,保证有N<=15; 
对于全部的数据,保证有N<=26。

又填了一个坑,好爽,贴代码

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n,s[30],book,h[30];
 4 char a[90],b[30],c[30];
 5 void dfs(int x,int y,int z){
 6     if(book)return ;
 7     for(int i=1;i<=x;i++){
 8         if(s[a[i]-‘A‘]==-1||s[a[i+n]-‘A‘]==-1||s[a[i+2*n]-‘A‘]==-1)continue;
 9         if((s[a[i]-‘A‘]+s[a[i+n]-‘A‘]+1)%n!=s[a[i+2*n]-‘A‘]&&(s[a[i]-‘A‘]+s[a[i+n]-‘A‘])%n!=s[a[i+2*n]-‘A‘])return ;
10     }//每次都对所有位进行判断,因为加法最多对下一位加一,所以可以特判一下,如果有一位3个数都被附上值了,而上面两个相加不等于第三个,加一之后也不等于第三个,那么这种情况肯定不合法
11     if(!x){
12         if(!y){
13             for(int i=0;i<n;i++)cout<<s[i]<<" ";
14                 book=1;
15         }
16         return ;
17     }
18     if(z!=3){
19         if(s[a[(z-1)*n+x]-‘A‘]==-1){
20             for(int i=0;i<n;i++){
21                 if(h[i])continue;
22                 h[i]=1;s[a[(z-1)*n+x]-‘A‘]=i;
23                 dfs(x,y,z+1);
24                 h[i]=0;s[a[(z-1)*n+x]-‘A‘]=-1;
25             }
26         }
27         else dfs(x,y,z+1);
28     }
29     if(z==3){
30         if(s[a[2*n+x]-‘A‘]==-1){
31             int tem1=s[a[x]-‘A‘]+s[a[x+n]-‘A‘]+y;
32             if(!h[tem1%n]){
33                 s[a[2*n+x]-‘A‘]=tem1%n;h[tem1%n]=1;
34                 dfs(x-1,tem1/n,1);
35                 s[a[2*n+x]-‘A‘]=-1;h[tem1%n]=0;
36             }
37         }
38         else if((s[a[x]-‘A‘]+s[a[x+n]-‘A‘]+y)%n==s[a[x+2*n]-‘A‘])dfs(x-1,(s[a[x]-‘A‘]+s[a[x+n]-‘A‘]+y)/n,1);
39     }
40 }
41 int main()
42 {
43     freopen("alpha.in","r",stdin);
44     freopen("alpha.out","w",stdout);
45 //    freopen("1.txt","r",stdin);
46     scanf("%d",&n);
47     scanf("%s%s%s",a+1,b+1,c+1);
48     for(int i=n+1;i<=2*n;i++)a[i]=b[i-n];
49     for(int i=n*2+1;i<=3*n;i++)a[i]=c[i-2*n];
50     memset(s,-1,sizeof(s));
51     dfs(n,0,1);
52     return 0;
53 }

这道题我暑假就在做了,不过当时写了个100多行的长代码,,样例都没过,,然后就出去旅游了,就丢到现在了...这道题我今天写一共才用了50行,其实换一种写法这道题还是很简单的

最基本的思路,从最低位开始枚举,符合就继续往下搜,这里可以像我那样写,dfs多引入一个变量,会大大减少代码量,将a数组换成一个二维数组效果会更好。这样的话是可以拿到80分的

然后我看评论区dalao们的评论,又加了一个小剪枝,我本来对于第三个字符串处理的时候,是枚举所有可能情况,通过第一个和第二个对应位判断是否可行,,,然而并不需要这样,直接通过

前两位就可以推出第三位,这样会减少特判的时间以及for循环中++的时间,可以多过一个点,90分,第8个点非常毒瘤,我本地跑了1分钟,实在不知道怎么剪枝了,又去看了评论

我看的达哥的评论,刚开始还想怎么实现,后来发现其实特别简单。

引入达哥的话:“我是从右向左(也就是从低位到高位)深搜的,这样会导致有时的选择在高位的地方产生矛盾,却必须搜到高位才能剪掉,此时这个注定错误的选择已经形成了一棵很大的搜索树.只要每新选择一个数就判断高位是否产生矛盾即可”

对于任意一位,他对下一位的进位最多就是1,因为是加法。所以在每一次dfs中,我们特判一下那些已经确定了的位,判断一下第一个和第二个对应位加起来是不是等于第三个对应位,再判一下加一后是否符合(要对n取模),如果都不符合,那么这种情况一定是不合法的,就没有必要继续搜下去了,直接返回即可。

加了这个优化之后速度飙起来了,60秒变0.6秒。

时间: 09-19

69. [NOIP2004] 虫食算的相关文章

NOIP2004 虫食算

四.虫食算 (alpha.pas/dpr/c/cpp) [问题描述] 所谓虫食算,就是原先的算式中有一部分被虫子啃掉了,需要我们根据剩下的数字来判定被啃掉的字母.来看一个简单的例子: 43#9865#045     +    8468#6633        44445506978 其中#号代表被虫子啃掉的数字.根据算式,我们很容易判断:第一行的两个数字分别是5和3,第二行的数字是5. 现在,我们对问题做两个限制: 首先,我们只考虑加法的虫食算.这里的加法是N进制加法,算式中三个数都有N位,允许

[NOIP2004]虫食算 T4 简单搜索+剪枝

最近在刷搜索套餐 我先做了一道简单的 虫食算.... 我GO die了........... 这都是啥啊!!!!!!!!!!!!!!! 总之就是一个搜啊.... 从最右面开始搜 每一行行尾进行check 基本上能过9个点........ 剪枝的话 ,考虑检索前面的每一行 如果改行的数字都己经试过,那么就可以判断合法性,如果已经有两个试过的话,考虑第三个数是否可能(可能已经被用过) 注意:试数的时候从后向前试...坑爹的数据 注意进位即可 下面是代码,调试信息懒得删....搜索的第四层可删 略长.

(DFS)noip2004——虫食算

1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4 char a[4][28]; 5 bool vix[100],vi[28]; 6 int c[100],ge=1,an[100],t; 7 bool judge1() 8 { 9 char x,y,z; 10 for(int i=t;i>0;i--) 11 { 12 x=a[1][i];y=a[2][i];z=a[3][i]; 13 if

[Noip2004]虫食算 dfs

搜索问题的关键:优秀的搜索策略以及行之有效的减枝 对于这道题我们阶乘搜肯定不行所以我们按位搜,我们对每一位的三个数进行赋值,然后判解. 对于此一类的搜索乘上一个几十的常数来减枝往往要比直接搜要快得多,因为这样的问题他们都会有一个庞大的"之后",而且判断不存在较为容易,以我们多花一些时间进行减枝往往能达到剪掉许多枝的效果. 搜索还是看感觉,倒搜还是比正搜快...... #pragma GCC optimize("O3") #include <cstdio>

[NOIP2004] 提高组 洛谷P1092 虫食算

题目描述 所谓虫食算,就是原先的算式中有一部分被虫子啃掉了,需要我们根据剩下的数字来判定被啃掉的字母.来看一个简单的例子: 43#9865#045 +8468#6633 44445509678 其中#号代表被虫子啃掉的数字.根据算式,我们很容易判断:第一行的两个数字分别是5和3,第二行的数字是5. 现在,我们对问题做两个限制: 首先,我们只考虑加法的虫食算.这里的加法是N进制加法,算式中三个数都有N位,允许有前导的0. 其次,虫子把所有的数都啃光了,我们只知道哪些数字是相同的,我们将相同的数字用

【NOIP2004】虫食算

Description 所谓虫食算,就是原先的算式中有一部分被虫子啃掉了,需要我们根据剩下的数字来判定被啃掉的字母.来看一个简单的例子: 43#9865#045 +   8468#6633 44445509678 其中#号代表被虫子啃掉的数字.根据算式,我们很容易判断:第一行的两个数字分别是5和3,第二行的数字是5. 现在,我们对问题做两个限制: 首先,我们只考虑加法的虫食算.这里的加法是N进制加法,算式中三个数都有N位,允许有前导的0. 其次,虫子把所有的数都啃光了,我们只知道哪些数字是相同的

洛谷—— P1092 虫食算

https://www.luogu.org/problem/show?pid=1092 题目描述 所谓虫食算,就是原先的算式中有一部分被虫子啃掉了,需要我们根据剩下的数字来判定被啃掉的字母.来看一个简单的例子: http://paste.ubuntu.com/25448822/ 其中#号代表被虫子啃掉的数字.根据算式,我们很容易判断:第一行的两个数字分别是5和3,第二行的数字是5. 现在,我们对问题做两个限制: 首先,我们只考虑加法的虫食算.这里的加法是N进制加法,算式中三个数都有N位,允许有前

洛谷 P1092 虫食算 Label:dfs

题目描述 所谓虫食算,就是原先的算式中有一部分被虫子啃掉了,需要我们根据剩下的数字来判定被啃掉的字母.来看一个简单的例子: 43#9865#045 +8468#6633 44445509678 其中#号代表被虫子啃掉的数字.根据算式,我们很容易判断:第一行的两个数字分别是5和3,第二行的数字是5. 现在,我们对问题做两个限制: 首先,我们只考虑加法的虫食算.这里的加法是N进制加法,算式中三个数都有N位,允许有前导的0. 其次,虫子把所有的数都啃光了,我们只知道哪些数字是相同的,我们将相同的数字用

Luogu P1092 虫食算

题目描述 所谓虫食算,就是原先的算式中有一部分被虫子啃掉了,需要我们根据剩下的数字来判定被啃掉的字母.来看一个简单的例子: 43#9865#045 +8468#6633 44445509678 其中#号代表被虫子啃掉的数字.根据算式,我们很容易判断:第一行的两个数字分别是5和3,第二行的数字是5. 现在,我们对问题做两个限制: 首先,我们只考虑加法的虫食算.这里的加法是N进制加法,算式中三个数都有N位,允许有前导的0. 其次,虫子把所有的数都啃光了,我们只知道哪些数字是相同的,我们将相同的数字用