【NOIP2004】虫食算
2024-08-24 07:26:55
Description
所谓虫食算，就是原先的算式中有一部分被虫子啃掉了，需要我们根据剩下的数字来判定被啃掉的字母。来看一个简单的例子：
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个不同的字母分别代表的数字，使得该加法算式成立。输入数据保证有且仅有一组解
解题报告
搜索剪枝，实际上状态很少，考虑怎么样的搜索顺序使得状态最少，肯定是按位枚举，把确定的字母标记一下，并且标记哪些数字被用过，产生矛盾就停止搜索，注意回溯
另外就是判断每一位的等式是否成立，注意进位的问题，递归时记录即可
本人的实现很复杂，代码可以参考其他博客，大概方法是把三个串按dfs枚举顺序弄成一个序列，就可以避免8种讨论了
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define RG register
#define il inline
#define iter iterator
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
const int N=31;
char S[N];int n,a[N],b[N],c[N],val[N];bool d[N];
il void dfs(int x,int ad){
if(x==0){
if(!ad){
for(int i=1;i<=n;i++)printf("%d ",val[i]);
exit(0);
}
return ;
}
RG int i1=a[x],i2=b[x],i3=c[x],j,i;
if(val[i1]!=-1 && val[i2]!=-1 && val[i3]!=-1){
if((val[i1]+val[i2]+ad)%n==val[i3])
dfs(x-1,val[i1]+val[i2]+ad>=n);
return ;
}
if(val[i1]==-1 && val[i2]==-1 && val[i3]==-1){
if(i1!=i2)
{
for(i=n-1;i>=0;i--){
if(d[i])continue;
d[i]=true;val[i1]=i;
for(j=n-1;j>=0;j--){
if(d[j])continue;
val[i2]=j;val[i3]=(i+j+ad);d[j]=true;
if(val[i3]>=n)val[i3]-=n;
if(!d[val[i3]])
d[val[i3]]=1,dfs(x-1,i+j+ad>=n),d[val[i3]]=0;
else if(i3==i1 || i3==i2)dfs(x-1,i+j+ad>=n);
val[i2]=-1;val[i3]=-1;d[j]=false;
}
d[i]=false;val[i1]=-1;
}
}
else{
for(i=n-1;i>=0;i--){
if(d[i])continue;
d[i]=true;val[i1]=val[i2]=i;
val[i3]=(i+i+ad)%n;
if(!d[val[i3]])
d[val[i3]]=1,dfs(x-1,i+i+ad>=n),d[val[i3]]=0;
else if(i3==i1 || i3==i2)dfs(x-1,i+i+ad>=n);
d[i]=false;val[i1]=val[i2]=-1;
}
}
return ;
}
else if(val[i3]==-1){
if(val[i1]!=-1 && val[i2]!=-1){
val[i3]=(val[i1]+val[i2]+ad)%n;
if(!d[val[i3]])
d[val[i3]]=1,dfs(x-1,val[i1]+val[i2]+ad>=n),d[val[i3]]=0;
else if(i3==i1 || i3==i2)dfs(x-1,val[i1]+val[i2]+ad>=n);
val[i3]=-1;
return ;
}
if(val[i2]==-1)swap(i1,i2);
for(i=n-1;i>=0;i--){
if(d[i])continue;
val[i1]=i;d[i]=true;
val[i3]=(i+val[i2]+ad)%n;
if(!d[val[i3]])
d[val[i3]]=1,dfs(x-1,i+val[i2]+ad>=n),d[val[i3]]=0;
else if(i1==i3 || i3==i2)dfs(x-1,i+val[i2]+ad>=n);
val[i1]=-1;val[i3]=-1;
d[i]=false;
}
return ;
}
if(val[i3]!=-1){
if(val[i1]==-1 && val[i2]==-1){
for(i=n-1;i>=0;i--){
if(d[i])continue;
val[i1]=i;d[i]=true;
if(i+ad<=val[i3])val[i2]=val[i3]-i-ad;
else val[i2]=val[i3]+n-i-ad;
if(!d[val[i2]])
d[val[i2]]=1,dfs(x-1,val[i1]+val[i2]+ad>=n),d[val[i2]]=0;
else if(i2==i1 || i2==i3)dfs(x-1,val[i1]+val[i2]+ad>=n);
val[i1]=-1;val[i2]=-1;
d[i]=false;
}
}
else{
if(val[i2]==-1)swap(i1,i2);
if(val[i2]+ad<=val[i3])val[i1]=val[i3]-val[i2]-ad;
else val[i1]=val[i3]+n-val[i2]-ad;
if(!d[val[i1]])
d[val[i1]]=1,dfs(x-1,val[i1]+val[i2]+ad>=n),d[val[i1]]=0;
else if(i1==i3 || i1==i2)dfs(x-1,val[i1]+val[i2]+ad>=n);
val[i1]=-1;
}
}
}
void work()
{
scanf("%d",&n);
scanf("%s",S+1);memset(val,-1,sizeof(val));
for(int i=1;i<=n;i++)a[i]=S[i]-'A'+1;
scanf("%s",S+1);
for(int i=1;i<=n;i++)b[i]=S[i]-'A'+1;
scanf("%s",S+1);
for(int i=1;i<=n;i++)c[i]=S[i]-'A'+1;
dfs(n,0);
}
int main()
{
work();
return 0;
}
最新文章
- 动画黄金搭档:CADisplayLink & CAShapeLayer
- I/O知识
- IOS第五课——Gesture and TableView
- 关于JS的数据类型的一些见解
- 移动端调试工具-Weinre
- C# 保存窗口为图片（保存纵断面图）
- java线层的使用
- 字典（Tire树）
- Linux中通过命令直接删除文件中最后一行
- [原创]消灭eclipse中运行启动的错误:“找不到或无法加载主类”问题
- TCP学习总结（一）
- BZOJ3291Alice与能源计划——匈牙利算法+模拟费用流
- 关于form与表单操作
- scrapy安装
- ip+掩码
- Java NIO中的通道Channel（二）分散/聚集 Scatter/Gather
- python使用dbutils的PooledDB连接池，操作数据库
- DB2 SQL1477N问题
- Cookis与文件缓存的区别
- JVM知识（三）：内存模型和可见性