当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

USACO Prime Cryptarithm 题解

发表于: 2013-05-08   作者:bbsunchen   来源:转载   浏览次数:
摘要: 此题很水,暴力搜索,然后根据条件判断,continue掉一些循环就可以了,简称,剪枝,一次过! 下面上代码: /* ID: bbsunch2 PROG: crypt1 LANG: C++ */ #include <iostream> #include <fstream> #include <stdlib.h> #include <vec

此题很水,暴力搜索,然后根据条件判断,continue掉一些循环就可以了,简称,剪枝,一次过!

下面上代码:

/*
ID: bbsunch2
PROG: crypt1
LANG: C++
*/
#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <vector>


using namespace std;

int main()
{
    ofstream fout ("crypt1.out");
    ifstream fin ("crypt1.in");

    int digitNum;
    vector<int> digits;

    fin >> digitNum;
    for(int i = 0; i < digitNum; i++)
    {
        int d = 0;
        fin >> d;
        digits.push_back(d);
    }
    int a1 = 0;
    int a2 = 0;
    int a3 = 0;
    int b1 = 0;
    int b2 = 0;

    int c1 = 0;
    int c2 = 0;
    int c3 = 0;
    int d1 = 0;
    int d2 = 0;
    int d3 = 0;

    int e1 = 0;
    int e2 = 0;
    int e3 = 0;
    int e4 = 0;

    int A = 0;
    int B = 0;
    int C = 0;
    int D = 0;
    int E = 0;

    int caseNum = 0;
    for(int a1i = 0; a1i < digits.size(); a1i++)
    {
        a1 = digits[a1i];
        for(int a2i = 0; a2i < digits.size(); a2i++)
        {
            a2 = digits[a2i];
            for(int a3i = 0; a3i < digits.size(); a3i++)
            {
                a3 = digits[a3i];
                A = a1*100 + a2*10 + a3;
                for(int b2i = 0; b2i < digits.size(); b2i++)
                {
                    b2 = digits[b2i];
                    C = b2 * A;
                    if(C < 100 || C > 999)
                    {
                        continue;
                    }
                    c1 = (int)(C / 100);
                    c2 = (int)((C % 100)/10);
                    c3 =  C % 10;
                    bool containC1 = false;
                    bool containC2 = false;
                    bool containC3 = false;
                    for(int i = 0; i < digits.size(); i++)
                    {
                        if(c1 == digits[i])
                        {
                            containC1 = true;
                        }
                        if(c2 == digits[i])
                        {
                            containC2 = true;
                        }
                        if(c3 == digits[i])
                        {
                            containC3 = true;
                        }
                    }
                    if(!(containC1 && containC2 && containC3))
                    {
                        continue;
                    }
                    for(int b1i = 0; b1i < digits.size(); b1i++)
                    {
                        b1 = digits[b1i];
                        D = b1 * A;
                        if(D < 100 || D > 999)
                        {
                            continue;
                        }
                        d1 = (int)(D / 100);
                        d2 = (int)((D % 100)/10);
                        d3 =  D % 10;
                        bool containD1 = false;
                        bool containD2 = false;
                        bool containD3 = false;
                        for(int i = 0; i < digits.size(); i++)
                        {
                            if(d1 == digits[i])
                            {
                                containD1 = true;
                            }
                            if(d2 == digits[i])
                            {
                                containD2 = true;
                            }
                            if(d3 == digits[i])
                            {
                                containD3 = true;
                            }
                        }
                        if(!(containD1 && containD2 && containD3))
                        {
                            continue;
                        }
                        B = b1 * 10 + b2;
                        E = A * B;
                        if(E < 1000 || E > 9999)
                        {
                            continue;
                        }
                        e1 = (int)(E / 1000);
                        e2 = (int)(E / 100) - e1 * 10;
                        e3 = (int)((E % 100) / 10);
                        e4 = (int)E%10;
                        bool containE1 = false;
                        bool containE2 = false;
                        bool containE3 = false;
                        bool containE4 = false;
                        for(int i = 0; i < digits.size(); i++)
                        {
                            if(e1 == digits[i])
                            {
                                containE1 = true;
                            }
                            if(e2 == digits[i])
                            {
                                containE2 = true;
                            }
                            if(e3 == digits[i])
                            {
                                containE3 = true;
                            }
                            if(e4 == digits[i])
                            {
                                containE4 = true;
                            }
                        }
                        if(containE1 && containE2 && containE3 && containE4)
                        {
                            caseNum ++;
                        }else
                        {
                            continue;
                        }
                    }
                }
            }
        }
    }

    fout << caseNum << endl;

    return 0;
}

 

运行结果 :

USACO 写道
USER: Chen Sun [bbsunch2]
TASK: crypt1
LANG: C++

Compiling...
Compile: OK

Executing...
Test 1: TEST OK [0.000 secs, 3356 KB]
Test 2: TEST OK [0.000 secs, 3356 KB]
Test 3: TEST OK [0.000 secs, 3356 KB]
Test 4: TEST OK [0.000 secs, 3356 KB]
Test 5: TEST OK [0.000 secs, 3356 KB]
Test 6: TEST OK [0.000 secs, 3356 KB]
Test 7: TEST OK [0.000 secs, 3356 KB]

All tests OK.
YOUR PROGRAM ('crypt1') WORKED FIRST TIME! That's fantastic
-- and a rare thing. Please accept these special automated
congratulations.

Here are the test data inputs:

------- test 1 ----
5
2 3 4 6 8
------- test 2 ----
4
2 3 5 7
------- test 3 ----
1
1
------- test 4 ----
7
4 1 2 5 6 7 3
------- test 5 ----
8
9 1 7 3 5 4 6 8
------- test 6 ----
6
1 2 3 5 7 9
------- test 7 ----
9
1 2 3 4 5 6 7 8 9
Keep up the good work!
Thanks for your submission!

 

USACO Prime Cryptarithm 题解

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
【问题描述】 据说如果你给无限只母牛和无限台巨型便携式电脑(有非常大的键盘),那么母牛们会制造出
题意分析: 给出4个长方形的高和长,以及给出6种基本布局,求合成无重叠的最小面积时的长和宽。 解题
/*打表把素数能组合的数先设置成相应的位数*/ /* if n equals two and n is No.1 position of prime
Google 的每一个亲儿子都倍受瞩目,比如 Nexus One 登场时被冠以“Super Phone”的称号,而 Nexus S
原题传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1016 Prime Ring Problem Time Limit: 400
http://acm.hdu.edu.cn/game/entry/problem/show.php?chapterid=2§ionid=1&problemid=2 #includ
这道题目,给你一组时间范围,求最大的时间跨度和最大的时间段间隔。题目看似挺简单,但是如果不加
我知道写这东西挺二,可是我确实被USACO的提交折腾了很久…… 首先,它的 TEXT Submitting Solution
Prime Ring Problem Time Limit: 4000/2000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Ot
PrimeUI是JSF框架Primefaces的团队开发的一套基于jquery/jquery-ui的一套前端控件库, github上有人
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号