题目描述

著名科学家卢斯为了检查学生对进位制的理解，他给出了如下的一张加法表，表中的字母代表数字。例如：

+    L    K    V    EL    L    K    V    EK    K    V    E    KLV    V    E    KL    KKE    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!”

输入输出样例

输入样例#1：

5+ L K V EL L K V EK K V E KLV V E KL KKE E KL KK KV

输出样例#1：

L=0 K=1 V=2 E=34

题解

这道题作为洛谷第一页的题，好久放在这里都尝试过【代码能力极差= =】

好吧仔细想想还是很简单的【都没怎么剪枝就 0ms】

作为一个加法表，理应包含该进制下所有的数字【不然相加的结果会冒出别的字母出来】

这样我们可以知道这是在n进制下的加法【这里n指字母个数】

既然一定有一个0，我们就可以直接找出那一行都是原数的就是0

其它的就dfs尝试给它赋予一个数字，通过该行的加法表用已知的检查是否合法

搜到n + 1就算出来啦

#include
     
      #include
      
       #include
       
        #include
        #include
         
          #include
          
           #define REP(i,n) for (int i = 1; i <= (n); i++)using namespace std;const int maxn = 13,maxm = 105,INF = 1000000000;map
           
             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!"<
            
              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!"<