/ Vijos / 题库 / 加法表 /

题解

25 条题解

  • 0
    @ 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;
}
  • 0
    @ 2016-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;
    }
    ```

  • 0
    @ 2016-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
    没秒过，最后一个点

  • 0
    @ 2015-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标程不可以的！稍微处理下就是了，为了可读性，没有压缩，长了点

  • 0
    @ 2009-11-14 09:10:25

    记录号 Flag 得分 记录信息 环境 评测机

    R1745501 Unaccepted 70 From ctest－ P1596 FPC Evolution SmdCn

    程序提交时间

    2009-11-14 9:01:02

    From zhh1993

    加法表 全国青少年信息学奥林匹克分区联赛 (NOIp) 竞赛原题

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 0ms

    ├ 测试数据 06：答案正确... 0ms

    ├ 测试数据 07：运行超时...

    ├ 测试数据 08：运行超时...

    ├ 测试数据 09：答案正确... 0ms

    ├ 测试数据 10：运行超时...

    ---|---|---|---|---|---|---|---|-

    Unaccepted 有效得分：70 有效耗时：0ms

    我太弱了

    改不出来了。。

  • 0
    @ 2009-11-06 08:54:02

    输出时时按第一行的顺序输出，而非第一列的数据输出！

    崩溃了·····

  • 0
    @ 2009-10-10 17:39:15

    AC200题纪念

    每搜一个字母判断一下即可

  • 0
    @ 2009-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

  • 0
    @ 2009-09-15 13:15:26

    实践证明，第三组数据的表格当中有第一行以及第一列所没有包含的大写字符，要注意特别判断！！！这个问题坑了我n次提交

  • 0
    @ 2009-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

    额^^^^^^^^^^^^

  • 0
    @ 2009-09-05 16:12:54

    AC

  • 0
    @ 2009-09-05 13:23:28

    一开始直接枚举，60分。

    改成可行性减枝以后就0ms。

    因为n太小了。

  • 0
    @ 2009-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 有效耗时：9ms

    Flag 　　 Accepted

    题号 　　P1596

    类型(?) 　　其它

    通过 　　14人

    提交 　　113次

    通过率 　　12%

    难度 　　3

    一次AC 221行的程序 妈呀 是不是有点长了....

    第十四个通过....恩...不吉利不吉利

  • 0
    @ 2009-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这个数比较特别。

    用很朴素的搜索。主要注意第一列的顺序和可行性剪枝的一些细节。

  • 0
    @ 2009-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一定是就是进制数吗？这样就不用迭代进制数了。字母重复一定无解吗？

  • 0
    @ 2009-08-13 19:48:05

    雷人的题！我知道怎么回事了！横竖不一样！

  • 0
    @ 2009-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 有效耗时：0ms

    Flag 　　 Accepted

    题号 　　P1596

    类型(?) 　　其它

    通过 　　10人

    提交 　　92次

    通过率 　　11%

    难度 　　3

    提交 讨论 题解

  • 0
    @ 2009-08-06 22:03:17

    啊。。。。。原来有那样的数据。。。。横竖字母顺序不同。。

  • 0
    @ 2009-08-06 14:54:48

    这题比原题恶心多了 不能像原题那样数有几个两位数就是几（ps：加上check应该能过，但是我不对 一直60分 - -！）于是改用回溯+剪枝 秒杀了...实践告诉我们 搜索万岁 枚举无罪！哦也~

  • 0
    @ 2009-07-29 20:29:10

    第三个数据虾米

加法表

信息

ID
1596
难度
7
分类
搜索 点击显示
标签
递交数
670
已通过
110
通过率
16%
被复制
6
上传者
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  1. © 2005 - 2023 Vijos.org
  2. uibuild-2f1065f
  3. 沪ICP备14040537号-1