洛谷 P1013 进制位 【搜索 + 进制运算】
2024-09-22 18:38:02
题目描述
著名科学家卢斯为了检查学生对进位制的理解,他给出了如下的一张加法表,表中的字母代表数字。 例如:
+ L K V E
L L K V E
K K V E KL
V V E KL KK
E E KL KK KV
其含义为:
L+L=L,L+K=K,L+V=V,L+E=E
K+L=K,K+K=V,K+V=E,K+E=KL
…… E+E=KV
根据这些规则可推导出:L=0,K=1,V=2,E=3
同时可以确定该表表示的是4进制加法
//感谢lxylxy123456同学为本题新加一组数据
输入输出格式
输入格式:
n(n≤9)表示行数。
以下n行,每行包括n个字符串,每个字串间用空格隔开。(字串仅有一个为‘+’号,其它都由大写字母组成)
输出格式:
① 各个字母表示什么数,格式如:L=0,K=1,……按给出的字母顺序。
② 加法运算是几进制的。
③ 若不可能组成加法表,则应输出“ERROR!”
输入输出样例
题解
这道题作为洛谷第一页的题,好久放在这里都尝试过【代码能力极差= =】
好吧仔细想想还是很简单的【都没怎么剪枝就 0ms】
作为一个加法表,理应包含该进制下所有的数字【不然相加的结果会冒出别的字母出来】
这样我们可以知道这是在n进制下的加法【这里n指字母个数】
既然一定有一个0,我们就可以直接找出那一行都是原数的就是0
其它的就dfs尝试给它赋予一个数字,通过该行的加法表用已知的检查是否合法
搜到n + 1就算出来啦
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<cctype>
#include<algorithm>
#define REP(i,n) for (int i = 1; i <= (n); i++)
using namespace std;
const int maxn = 13,maxm = 105,INF = 1000000000; map<char,int> Id;
int n,siz = 0,num[maxn];
bool used[maxn];
char names[maxn]; inline char RC(){
char c = getchar();
while (!isalpha(c) && c != '+') c = getchar();
return c;
} inline int code(char c){
if (!Id.count(c)){Id[c] = ++siz; names[siz] = c;}
return Id[c];
} struct Num{
int s[maxn],len; Num() {memset(s,0,sizeof(s)); len = 0;} bool iscal(){
REP(i,len) if (num[s[i]] == -1) return false;
return true;
} int getn(){
int ans = 0;
for (int i = 1; i <= len; i++) ans = ans * n + num[s[i]];
return ans;
} void getR(){
char c = getchar();
while (!isalpha(c)) c = getchar();
while (isalpha(c)){s[++len] = code(c); c = getchar();}
}
}sum[maxn][maxn]; void init(){
fill(num,num + maxn,-1);
scanf("%d",&n); n--;
int u; RC();
REP(i,n) code(RC());
REP(i,n){
u = code(RC());
REP(j,n) sum[u][j].getR();
}
bool flag = true;
REP(i,n){
flag = true;
REP(j,n) if (sum[i][j].len != 1 || sum[i][j].s[1] != j) {flag = false; break;}
if (flag){num[i] = 0; break;}
}
if (!flag){cout<<"ERROR!"<<endl;exit(0);}
} bool check(int u){
REP(i,n) if (num[i] != -1 && sum[u][i].iscal() && num[u] + num[i] != sum[u][i].getn())
return false;
return true;
} void dfs(int u){
if (u > n){
printf("%c=%d",names[1],num[1]);
for (int i = 2; i <= n; i++)
printf(" %c=%d",names[i],num[i]);
printf("\n%d\n",n);
exit(0);
}
if (num[u] != -1) dfs(u + 1);
else {
for (int i = 1; i < n; i++){
if (!used[i]){
num[u] = i;
if (check(u)) dfs(u + 1);
num[u] = -1;
}
}
}
} int main()
{
init();
dfs(1);
cout<<"ERROR!"<<endl;
return 0;
}
最新文章
- 安装redis
- eclipse添加easyExport插件,打开本地文件
- HTTP03--DNS知识
- Good Bye 2013 C
- JS变量的作用域
- 7. 星际争霸之php设计模式--中介者模式
- Codeforces Round #135 (Div. 2)
- ROS多个master消息互通
- c&; c++ enum
- [改善Java代码]别让null值和空值威胁到变长方法
- C++的类和对象
- oracle的位图索引和函数索引
- Win10更新补丁失败后出现无法更新正在撤销 解决办法
- eclipse添加tomcat服务器
- JS垃圾收集机制
- Dijkstra&#39;s algorithm
- java 创建过程
- 编译器是如何实现32位整型的常量整数除法优化的?[C/C++]
- 把py文件打成exe
- Haskell中cabal install glib遇到的问题
热门文章
- MyBatis.Net 配置
- .net core 部署 Docker 所遇到的几个问题
- selenium自动化之元素高亮显示
- Java学习计划
- Paper Reading - Deep Visual-Semantic Alignments for Generating Image Descriptions ( CVPR 2015 )
- New Year_2019
- Amazon 成功的秘訣是…
- Amazon及其亏本诱饵策略还能坚持多久?
- Yii2 UploadedFile上传文件
- LeetCode 48. Rotate Image (C++)