ACdream区域赛指导赛之手速赛系列(2)

回到作案现场：http://acdream.info/onecontest/1014

前言：自己出份山寨版的解题报告。

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

A - Boy or Girl

统计用了多少种单词，分奇偶数输出结论，能够用STL的set实现，我对map比較熟。所以果断用map水了。

/*

* this code is made by code4101

* Problem: 1080

* Verdict: Accepted

* Submission Date: 2014-05-19 01:47:38

* Time: 0 MS

* Memory: 1676 KB

*/

#include <iostream>

#include <map>

using namespace std;

int main()

{

    string s;

    map<char, int> a;

    while (cin >> s)

    {

        a.clear();

        for (int i = 0; i < s.size(); i++) a[s[i]]++;

        if (a.size()&1) cout << "IGNORE HIM!\n";

        else cout << "CHAT WITH HER!\n";

    }

    return 0;

}

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

B - Walking in the Rain

题目非常多无用的干扰信息。

题意非常easy，就是给n个砖块顺序排好，告诉你每块砖几天后坏。

然后问几天后"路径不通"，不通的定义是：①第一个或最后一个坏了 ②存在连续的两个坏了。

我是用递归，每次找到最小的非0值模拟暴力解（比赛中的我常常该去吃药了）。

后来__M子__给的思想是一次遍历就够了：遍历max（a[i]。a[i+1]），记录最小值，再与头尾比較。

/*

* this code is made by code4101

* Problem: 1079

* Verdict: Accepted

* Submission Date: 2014-05-19 02:01:47

* Time: 0 MS

* Memory: 1672 KB

*/

#include <iostream>

using namespace std;

int main()

{

    int n, a[1010], i, ans, t;

    while (cin >> n)

    {

        for (i = 0; i < n; i++) cin >> a[i];

        ans = min(a[0], a[n-1]);

        for (i = 0; i < n-1; i++)

        {

            t = max(a[i], a[i+1]);

            if (t < ans) ans = t;

        }

        cout << ans << "\n";

    }

    return 0;

}

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

C - Cutting Figure

就是给一个连通图，让你用最小的删除操作把它变成非连通图。事实上答案范围一定在-1~4之间（随便找一个点，把上下左右全删除。这个点就孤立了。最坏情况下把其变为非连通图），-1代表无法实现。再进一步分析，事实上答案仅仅有-1、1、2三种情况（角上的点最多去掉2个相邻的就孤立了）。

-1就是初始集合元素不超过2个。这样无论怎么删都是连通的。1的话要遍历，一个个顶点去掉，用BFS尝试看是不是非连通图（BFS用队列实现。这个不懂去补基础吧）。假设不是前两者，那么答案就一定是2了。

/*

* this code is made by code4101

* Problem: 1078

* Verdict: Accepted

* Submission Date: 2014-05-18 12:04:24

* Time: 0 MS

* Memory: 1688 KB

*/

#include <cstdio>

#include <iostream>

#include <cstring>

#include <queue>

using namespace std;

int n, m;

bool a[60][60], b[60][60], zero[60][60] = {};

struct point{

    int x, y;

};

// 推断一个b是不是连通

bool isconnected(int x, int y)

{

    // 先进行一遍BFS

    queue<point> A;

    point p, t;

    p.x = x; p.y = y;

    A.push(p); b[p.x][p.y] = 0;

    while (A.size())

    {

        t = A.front(); A.pop();

        if (b[p.x = t.x-1][p.y = t.y]) A.push(p), b[p.x][p.y] = 0;

        if (b[p.x = t.x][p.y = t.y-1]) A.push(p), b[p.x][p.y] = 0;

        if (b[p.x = t.x][p.y = t.y+1]) A.push(p), b[p.x][p.y] = 0;

        if (b[p.x = t.x+1][p.y = t.y]) A.push(p), b[p.x][p.y] = 0;

    }

    if (memcmp(zero, b, sizeof(b))) return 0;

    else return 1;

}

// 推断去掉随意一个#是不是连通

int fun()

{

    int i, j;

    for (i = 1; i <= n; i++)

    {

        for (j = 1; j <= m; j++) if (a[i][j])

        {

            memcpy(b, a, sizeof(a));

            b[i][j] = 0;

            int x, y;   // 起点

            if (b[x = i-1][y = j]);

            else if (b[x = i][y = j-1]);

            else if (b[x = i][y = j+1]);

            else if (b[x = i+1][y = j]);

            if (!isconnected(x, y)) return 1;

        }

    }

    return 2;

}

int main()

{

    while (cin >> n >> m)

    {

        memset(a, 0, sizeof(a));

        int sum = 0, i, j;

        for (i = 1; i <= n; i++)

        {

            getchar();

            for (j = 1; j <= m; j++)

            {

                if (getchar() == '#')

                {

                    sum += a[i][j] = 1;

                }

            }

        }

        if (sum <= 2) cout << "-1\n";

        else cout << fun() << "\n";

    }

    return 0;

}

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

D - LCM Challenge

这题我在蓝桥杯做过：http://www.coolnote.cn/problems/66/。这篇文章分析的非常具体：http://blog.csdn.net/u011669700/article/details/18702757，事实上我到如今还是不太懂原理；原题来自这里：

m=ProblemSet&a=showProblem&problem_id=1632" rel="nofollow">http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1632

。

/*

* this code is made by code4101

* Problem: 1077

* Verdict: Accepted

* Submission Date: 2014-05-19 02:15:50

* Time: 0 MS

* Memory: 1672 KB

*/

#include <iostream>

using namespace std;

int main()

{

    unsigned long long n, ans;

    while (cin >> n)

    {

        if (n <= 2)     ans = n;

        else if (n & 1) ans = n * (n - 1) * (n - 2);

        else if (n % 3) ans = n * (n - 1) * (n - 3);

        else            ans = (n - 1) * (n - 2) * (n - 3);

        cout << ans << '\n';

    }

    return 0;

}

秒客网

ACdream区域赛指导赛之手速赛系列(2)

相关文章