MyException - 我的异常网
当前位置:我的异常网» C++ » Luogu P1092 虫吃算

Luogu P1092 虫吃算

www.MyException.Cn  网友分享于:2013-09-28  浏览:0次
Luogu P1092 虫食算

题目描述

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

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个不同的字母分别代表的数字,使得该加法算式成立。输入数据保证有且仅有一组解

输入输出格式

输入格式:

 

包含四行。第一行有一个正整数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题

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 int n;//读入几进制0.1.2.3...n-1
  4 int res[26];//保存A.B..Z代表的数字
  5 int used[26];//保存这个对应数字是否被用,因为题目说每个字母只能代表一个数
  6 string a,b,c;//保存加数1,加数2,和
  7 int flag = 0;//是否已找到符合条件的唯一解//加上这个多对了2个点//
  8 //-----最多只能7个点了,原先是从abcd..填字母,改变
  9 char pos[26];//保存从右往左,从上往下的字母出现顺序,判断的时候也按这个顺序判断
 10 int  usedZiMu[26];//保存该字母是否已经出现
 11 
 12 //剪枝优化函数,来判断当前的字母的数字取法是否可行
 13 //题目就是一个可行与否的问题
 14 int Check()
 15 {
 16     int i;
 17     //看是否满足 a+b==c
 18     for (i=n-1;i>=0;i--)
 19     {
 20         char a1=a[i]-'A',b1=b[i]-'A',c1=c[i]-'A';//取三个数第i位置值
 21         if(res[a1]!=-1 && res[b1]!=-1 && res[c1]!=-1)//3个数都知道-----3个点
 22         {
 23             if( (res[a1]+res[b1])%n!=res[c1] &&//无进位
 24                 (res[a1]+res[b1]+1)%n!=res[c1])//有进位
 25                 return 0;
 26         }
 27         //加上后面这些多对了1个点
 28         if(res[a1]!=-1 && res[b1]!=-1 && res[c1]==-1)//如果只知道其中2个
 29         {
 30             int sum1,sum2;//sum1无进位,sum2有进位
 31             sum1 = (res[a1]+res[b1])%n;
 32             sum2 = (res[a1]+res[b1]+1)%n;
 33             if (used[sum1] && used[sum2])//可能填在c1的数都用了肯定不行
 34                 return 0;
 35         }
 36         if (res[a1]!=-1 && res[b1]==-1 && res[c1]!=-1)//和与一个加数知道
 37         {
 38             int js1,js2;//js1无进位,js2有进位
 39             js1 = (res[c1]-res[a1]+n)%n;
 40             js2 = (res[c1]-res[a1]-1+n)%n;
 41             if (used[js1] && used[js2])//可能填写咋b1位置的数都被用了
 42                 return 0;
 43         }
 44         if (res[a1]==-1 && res[b1]!=-1 && res[c1]!=-1)//和与一个加数知道
 45         {
 46             int js1,js2;//js1无进位,js2有进位
 47             js1 = (res[c1]-res[b1]+n)%n;
 48             js2 = (res[c1]-res[b1]-1+n)%n;
 49             if (used[js1] && used[js2])//可能填写咋b1位置的数都被用了
 50                 return 0;
 51         }
 52         
 53     }
 54     return 1;
 55 }
 56 /*剪枝策略只这样写,数据只过3个点
 57 int Check()
 58 {
 59     int i;
 60     //看是否满足 a+b==c
 61     for (i=0;i<=n-1;i++)
 62     {
 63         char a1=a[i]-'A',b1=b[i]-'A',c1=c[i]-'A';//取三个数第i位置值
 64         if(res[a1]!=-1 && res[b1]!=-1 && res[c1]!=-1)
 65         {
 66             if( (res[a1]+res[b1])%n!=res[c1] &&//无进位
 67                 (res[a1]+res[b1]+1)%n!=res[c1])//有进位
 68                 return 0;
 69         }
 70 
 71     }
 72     return 1;
 73 }
 74 */
 75 //严格判断当前所有字母的填数满足等式否
 76 int  OK()
 77 {
 78     int i;
 79     int jinwei=0;
 80     int jiahe;
 81     for (i=n-1; i>=0; i--)
 82     {
 83         char a1=a[i]-'A',b1=b[i]-'A',c1=c[i]-'A';
 84         
 85         jiahe = (res[a1]+res[b1]+jinwei)%n;//计算和
 86         jinwei =( res[a1]+res[b1]+jinwei)/n;//计算进位
 87         if (jiahe!=res[c1]) return 0;
 88     }
 89     if (jinwei>0) return 0;
 90     return 1;
 91 }
 92 void dfs(int k)//深搜,利用系统的堆栈枚举
 93 {
 94     int i;
 95     if (flag) return ;//已找到解
 96     if (!Check()) return;//现在的方法不合理--从if (!used[i]&&Check())移到这里多了1个点共7个了
 97     if(k==n)//找到可行解且唯一(题目得知),输出
 98     {
 99         if (OK())//如果当前所有字母填数满足等式则输出
100         {
101             for(i=0; i<=n-2; i++) cout<<res[i]<<' ';
102             cout<<res[n-1]<<endl;
103             flag=1;
104         }
105         return ;
106     }
107     //在第k层,也就是第k个字母所可能取得数为0...n-1中未用值枚举
108     for (i=n-1; i>=0; i--)
109     {
110         //如果i还没被占用,且满足剪枝条件,则进行下层遍历
111         if (!used[i] )
112         {
113             used[i]=1;//i被占用
114             res[pos[k]]=i;//第k个字母取数字i
115             dfs(k+1);
116             used[i]=0;//i被释放,可以被其他字母占用
117             res[pos[k]]=-1;//第k个字母释放
118         }
119     }
120     return ;
121 }
122 
123 int main()
124 {
125     int k=0,i;
126     //读入数据
127     cin>>n;
128     cin>>a>>b>>c;
129     memset(res,-1,sizeof(res));
130     memset(pos,-1,sizeof(pos));
131     //初始化
132     for (i=n-1; i>=0; i--)//从右向左
133     {
134         char a1=a[i]-'A',b1=b[i]-'A',c1=c[i]-'A';//全部转成对应数字下标
135         if (!usedZiMu[a1]) ///从上往下
136         {
137             usedZiMu[a1]=1;
138             pos[k++] = a1;
139         }
140         if (!usedZiMu[b1]) 
141         {
142             usedZiMu[b1]=1;
143             pos[k++] = b1;
144         }
145         if (!usedZiMu[c1]) 
146         {
147             usedZiMu[c1]=1;
148             pos[k++] = c1;
149         }
150     }
151     dfs(0);
152     return 0;
153 }

 

文章评论

5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
2013年美国开发者薪资调查报告
2013年美国开发者薪资调查报告
中美印日四国程序员比较
中美印日四国程序员比较
为什么程序员都是夜猫子
为什么程序员都是夜猫子
每天工作4小时的程序员
每天工作4小时的程序员
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
我的丈夫是个程序员
我的丈夫是个程序员
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
代码女神横空出世
代码女神横空出世
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
10个调试和排错的小建议
10个调试和排错的小建议
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
Java程序员必看电影
Java程序员必看电影
漫画:程序员的工作
漫画:程序员的工作
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
程序员的鄙视链
程序员的鄙视链
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
程序员都该阅读的书
程序员都该阅读的书
 程序员的样子
程序员的样子
总结2014中国互联网十大段子
总结2014中国互联网十大段子
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
程序员必看的十大电影
程序员必看的十大电影
程序员应该关注的一些事儿
程序员应该关注的一些事儿
程序员和编码员之间的区别
程序员和编码员之间的区别
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
编程语言是女人
编程语言是女人
一个程序员的时间管理
一个程序员的时间管理
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
老程序员的下场
老程序员的下场
我是如何打败拖延症的
我是如何打败拖延症的
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
Google伦敦新总部 犹如星级庄园
Google伦敦新总部 犹如星级庄园
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
旅行,写作,编程
旅行,写作,编程
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有