25 条题解
-
0wlt0716 LV 9 @ 2021-10-16 11:30:47
#include<iostream> #include<cstdio> #include<cstring> #include<map> #include<string> #include<algorithm> using namespace std; const int maxn = 20; const int INF = 1000000000; int n; int vis[maxn]; bool solved; int num[maxn]; string lt[maxn][maxn]; int nc; map<char, int> id; int ID(char ch) { if (ch == '+') return -1; if (!id.count(ch)) id[ch] = nc++; return id[ch]; } bool check () { for (int i = 1; i < n; i++) { int num1 = num[ID(lt[i][0][0])]; if (num1 < 0) continue; for (int j = 1; j < n; j++) { int num2 = num[ID(lt[0][j][0])]; if (num2 < 0) continue; const string &s = lt[i][j]; bool ok = true; for (int k = 0; k < s.size(); k++) if (num[ID(s[k])] < 0) ok = false; if (!ok) continue; int tmp = 0; for (int k = 0; k < s.size(); k++) tmp = tmp*nc + num[ID(s[k])]; if (tmp != num1 + num2) return false; } } return true; } bool dfs (int dep) { if (dep == nc) return true; for (int nb = 0; nb < nc; nb++) if (!vis[nb]) { num[dep] = nb; vis[nb] = 1; if (!check()) { num[dep] = -1; vis[nb] = 0; continue;} if (dfs(dep+1)) return true; num[dep] = -1; vis[nb] = 0; } return false; } int main () { // freopen("in.txt", "r", stdin); cin >> n; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) { cin >> lt[i][j]; if (!i && !j) continue; num[ID(lt[i][j][0])] = -1; if (lt[i][j].size() > 1) num[ID(lt[i][j][1])] = -1; } solved = dfs(0); // cout << solved << "\n"; if (!solved) cout << "Wrong!\n"; else { for (int i = 1; i < n; i++) cout << lt[0][i][0] << "=" << num[ID(lt[0][i][0])] << " "; cout << "\n" << nc; } return 0; }
-
02016-09-11 20:25:25@
字母个数就是进制,不知道为什么,莫名其妙就AC了
```c++
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<string>
#include<algorithm>
using namespace std;const int maxn = 20;
const int INF = 1000000000;int n;
int vis[maxn];
bool solved;
int num[maxn];
string lt[maxn][maxn];int nc;
map<char, int> id;
int ID(char ch) {
if (ch == '+') return -1;
if (!id.count(ch)) id[ch] = nc++;
return id[ch];
}bool check () {
for (int i = 1; i < n; i++) {
int num1 = num[ID(lt[i][0][0])];
if (num1 < 0) continue;
for (int j = 1; j < n; j++) {
int num2 = num[ID(lt[0][j][0])];
if (num2 < 0) continue;
const string &s = lt[i][j];
bool ok = true;
for (int k = 0; k < s.size(); k++)
if (num[ID(s[k])] < 0) ok = false;
if (!ok) continue;
int tmp = 0;
for (int k = 0; k < s.size(); k++)
tmp = tmp*nc + num[ID(s[k])];
if (tmp != num1 + num2) return false;
}
}
return true;
}bool dfs (int dep) {
if (dep == nc) return true;
for (int nb = 0; nb < nc; nb++) if (!vis[nb]) {
num[dep] = nb; vis[nb] = 1;
if (!check()) { num[dep] = -1; vis[nb] = 0; continue;}
if (dfs(dep+1)) return true;
num[dep] = -1; vis[nb] = 0;
}
return false;
}int main ()
{
// freopen("in.txt", "r", stdin);
cin >> n;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
cin >> lt[i][j];
if (!i && !j) continue;
num[ID(lt[i][j][0])] = -1;
if (lt[i][j].size() > 1)
num[ID(lt[i][j][1])] = -1;
}solved = dfs(0);
// cout << solved << "\n";
if (!solved) cout << "Wrong!\n";
else {
for (int i = 1; i < n; i++) cout << lt[0][i][0] << "=" << num[ID(lt[0][i][0])] << " ";
cout << "\n" << nc;
}return 0;
}
``` -
02016-03-21 08:10:10@
测试数据 #0: Accepted, time = 0 ms, mem = 572 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 576 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 568 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 568 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 568 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 568 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 572 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 572 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 568 KiB, score = 10
测试数据 #9: Accepted, time = 15 ms, mem = 572 KiB, score = 10
Accepted, time = 15 ms, mem = 576 KiB, score = 100
没秒过,最后一个点 -
02015-03-25 20:36:44@
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;bool exist[100]; //检查出现的字符个数
int n,num[100],n2; //n不解释,num:每个字符的值,n2进制
string ch[13][13]; //表格void init()
{
n2 = 0;
memset(num,0,sizeof(num));
scanf("%d",&n);
for (char i = 'A'; i <= 'Z'; ++ i)
exist[(int)i] = false;
for (int i = 1; i <= n; ++ i)
for (int j = 1; j<= n; ++ j)
{
cin >> ch[i][j];
if (!exist[(int)ch[i][j][0]])
{
exist[(int)ch[i][j][0]] = true;
++ n2;
}
}
-- n2; //减去那个加号……
}void try_work()
{
bool ten;
ten = false;
for (int i = 2; i <= n; ++ i)
{
int temp;
temp = 0;
for (int j = 2; j <= n; ++ j)
{
if (ch[i][j].length() == 2)
{
if ( num[(int)ch[i][j][0]] != 0 && num[(int)ch[i][j][0]] != 1)
{
cout<<num[(int)ch[i][1][0]];
cout<<"Wrong!";
exit(0);
}
else
{
ten = true;
num[(int)ch[i][j][0]] = 1;
}
++ temp;
}
}
if (num[(int)ch[i][1][0]] == 0)
num[(int)ch[i][1][0]] = temp;
else
if (!ten)
{
cout<<"Wrong!";
exit(0);
}
}
}void judge()
{
for (int i = 2; i <= n; ++ i)
{
int a;
a = num[(int)ch[i][1][0]];
for (int j = 2; j <= n; ++ j)
{
int b,c;
b = num[(int)ch[1][j][0]];
if (ch[i][j].length() == 1)
{
c = num[(int)ch[i][j][0]];}
if (ch[i][j].length() == 2)
{
c = num[(int)ch[i][j][1]] + n2 * num[(int)ch[i][j][0]];
}
if (a + b != c)
{
cout<<"Wrong!";
exit(0);
}
}
}
}int main()
{
init();
try_work();
judge();
for (int i = 2; i <= n; ++ i)
cout << ch[1][i] << "=" << num[(int)ch[1][i][0]] << " ";
cout << endl << n2;
return 0;
}
不解释,谁说NOIP标程不可以的!稍微处理下就是了,为了可读性,没有压缩,长了点 -
02009-11-14 09:10:25@
记录号 Flag 得分 记录信息 环境 评测机
R1745501 Unaccepted 70 From ctest- P1596 FPC Evolution SmdCn
程序提交时间
2009-11-14 9:01:02From zhh1993
加法表 全国青少年信息学奥林匹克分区联赛 (NOIp) 竞赛原题编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 0ms
├ 测试数据 07:运行超时...
├ 测试数据 08:运行超时...
├ 测试数据 09:答案正确... 0ms
├ 测试数据 10:运行超时...
---|---|---|---|---|---|---|---|-
Unaccepted 有效得分:70 有效耗时:0ms我太弱了
改不出来了。。 -
02009-11-06 08:54:02@
输出时时按第一行的顺序输出,而非第一列的数据输出!
崩溃了····· -
02009-10-10 17:39:15@
AC200题纪念
每搜一个字母判断一下即可 -
02009-09-27 00:59:13@
第一次进前100~
Flag Accepted
题号 P1596
类型(?) 其它
通过 27人
提交 207次
通过率 13%
难度 3按字母搜索,而不是按表搜索.
这样表中是否存在第1行和第1列所没有的字母的问题就不用讨论了.
表给出字母的顺序问题也不用讨论了.
每搜一个字母的值就验证一次.若不匹配就回溯.
最后只要按顺序把应有的字母的值输出.题中说了要输出X1=0,X2=1,X3=2...
这句话的意思就是有多少个字母就是多少进制
字母重复是可能有解的,只是题中的数据无解有点让人无语,字母重复问题居然占了一半.
第一次提交:编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:运行超时|格式错误...
├ 测试数据 03:答案错误... ├ 标准行输出
├ 错误行输出├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 0ms
├ 测试数据 07:运行超时|格式错误...
├ 测试数据 08:运行超时|格式错误...
├ 测试数据 09:答案正确... 0ms
├ 测试数据 10:答案错误... ├ 标准行输出
├ 错误行输出判断了一下字母重复后:
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 0ms
├ 测试数据 07:答案正确... 0ms
├ 测试数据 08:答案正确... 0ms
├ 测试数据 09:答案正确... 0ms
├ 测试数据 10:答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:0ms -
02009-09-15 13:15:26@
实践证明,第三组数据的表格当中有第一行以及第一列所没有包含的大写字符,要注意特别判断!!!这个问题坑了我n次提交
-
02009-09-09 17:56:33@
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案错误... ├ 标准行输出
├ 错误行输出├ 测试数据 05:答案错误... ├ 标准行输出
├ 错误行输出├ 测试数据 06:答案正确... 0ms
├ 测试数据 07:答案正确... 0ms
├ 测试数据 08:答案正确... 0ms
├ 测试数据 09:答案错误... ├ 标准行输出
├ 错误行输出├ 测试数据 10:答案正确... 0ms
---|---|---|---|---|---|---|---|-
Unaccepted 有效得分:70 有效耗时:0ms
额^^^^^^^^^^^^ -
02009-09-05 16:12:54@
AC
-
02009-09-05 13:23:28@
一开始直接枚举,60分。
改成可行性减枝以后就0ms。
因为n太小了。 -
02009-08-29 16:38:18@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 9ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 0ms
├ 测试数据 07:答案正确... 0ms
├ 测试数据 08:答案正确... 0ms
├ 测试数据 09:答案正确... 0ms
├ 测试数据 10:答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:9msFlag Accepted
题号 P1596
类型(?) 其它
通过 14人
提交 113次
通过率 12%
难度 3一次AC 221行的程序 妈呀 是不是有点长了....
第十四个通过....恩...不吉利不吉利 -
02009-08-28 20:26:35@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 0ms
├ 测试数据 07:答案正确... 0ms
├ 测试数据 08:答案正确... 0ms
├ 测试数据 09:答案正确... 0ms
├ 测试数据 10:答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:0ms
1A。
第13个A。13这个数比较特别。
用很朴素的搜索。主要注意第一列的顺序和可行性剪枝的一些细节。 -
02009-08-20 01:18:28@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 0ms
├ 测试数据 07:答案正确... 0ms
├ 测试数据 08:答案正确... 9ms
├ 测试数据 09:答案正确... 9ms
├ 测试数据 10:答案正确... 9ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:27ms
仍有疑问,n一定是就是进制数吗?这样就不用迭代进制数了。字母重复一定无解吗? -
02009-08-13 19:48:05@
雷人的题!我知道怎么回事了!横竖不一样!
-
02009-08-13 19:59:05@
好阴险的题!
有的数据顺序不对,一定要交换顺序!
害我弄了一下午....用小号骗数据才知道是这么回事.....第90道题,纪念一下
另外,第10个AC!
---|---|---|---|---|---|---|---|---|--
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 0ms
├ 测试数据 07:答案正确... 0ms
├ 测试数据 08:答案正确... 0ms
├ 测试数据 09:答案正确... 0ms
├ 测试数据 10:答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:0msFlag Accepted
题号 P1596
类型(?) 其它
通过 10人
提交 92次
通过率 11%
难度 3提交 讨论 题解
-
02009-08-06 22:03:17@
啊。。。。。原来有那样的数据。。。。横竖字母顺序不同。。
-
02009-08-06 14:54:48@
这题比原题恶心多了 不能像原题那样数有几个两位数就是几(ps:加上check应该能过,但是我不对 一直60分 - -!)于是改用回溯+剪枝 秒杀了...实践告诉我们 搜索万岁 枚举无罪!哦也~
-
02009-07-29 20:29:10@
第三个数据虾米