题解

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
分类
搜索 点击显示
标签
递交数
667
已通过
109
通过率
16%
被复制
6
上传者