[洛谷 P1013] NOIP1998 提高组进制位

客官°小女子只卖身不卖艺 2021-11-23 15:52 203阅读 0赞

## 问题描述 ##

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

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进制加法

## 输入格式 ##

n（n≤9）表示行数。

以下n行，每行包括n个字符串，每个字串间用空格隔开。（字串仅有一个为‘+’号，其它都由大写字母组成）

## 输出格式 ##

① 各个字母表示什么数，格式如：L=0，K=1，……按给出的字母顺序。

② 加法运算是几进制的。

③ 若不可能组成加法表，则应输出“ERROR！”

## 样例输入 ##

5  
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=0 K=1 V=2 E=3  
4

## 解析 ##

看到这道题时，有没有想到搜索？然后就是一通码......然后过了。

但是，真的要用搜索吗？

我们可以观察一下。对于n进制中的数\\(i\\)，如果\\(i\\)加上某一个数\\(j\\)会变成两位数，那么可以得到如下不等式：  
\\\[ i+j>n-1 \\Rightarrow j>n-1-i \\\]  
而满足要求的\\(j\\)的个数有\\(n-1-(n-1-i)=i\\)个。由此我们可以得到结论，一个字母的值就是这个字母对应的行中两位数的个数。我们所需要做的只是验证是否正确。那么怎样验证呢？最直接的办法是直接往里面代，但能否用另外的方法将每个字母的值算出呢？

这个比较难想。对于一个数\\(i\\)，如果想要\\(j+k\\)的个位数为\\(i\\)，必须满足\\(i<k<n\\)。那么，假设满足条件的\\(k\\)有\\(a\[i\]\\)个，\\(i\\)的值就是\\(n-1-a\[i\]\\)。\\(a\[i\]\\)只用求一个字母在两位数的个位上出现的次数即可。

另外，如果一个数在同一行中出现了两次，显然也是不对的，直接结束即可。

在下面的代码中，因为行数是\\(n\\)，所以其实是\\(n-1\\)进制的加法。

## 代码 ##

#include <iostream> #include <cstdio> #include <string> #define N 10 using namespace std; int n,i,j,a[N],num[30]; char l[N]; int main() { cin>>n; for(i=0;i<n;i++){ char c; cin>>c; if(c!='+') l[i]=c; } for(i=2;i<=n;i++){ string s1,s; for(j=1;j<=n;j++){ cin>>s; if(j==1) continue; if(j!=2&&s==s1){ cout<<"ERROR!"<<endl; return 0; } s1=s; if(i!=1&&j!=-1){ int l=s.length(); if(l==2){ a[i-1]++; num[(int)s[l-1]]++; } } } } for(i=1;i<n;i++){ if(a[i]!=n-2-num[(int)l[i]]){ cout<<"ERROR!"<<endl; return 0; } } for(i=1;i<n;i++){ cout<<l[i]<<"="<<a[i]<<' '; } cout<<endl<<n-1<<endl; return 0; }

转载于:https://www.cnblogs.com/LSlzf/p/11129724.html