ACDream手速赛2

地址：http://acdream.info/onecontest/1014

 

都是来自Codeforce上简单题。

 

A. Boy or Girl

简单字符串处理

 

B. Walking in the Rain

每次能移动1或2的距离。

答案为，ans = min{ max{e(i), e(i+1)} (其中i从0->n-1) };

 

C. Cutting Figure

输入为一个nxm的矩阵，#都是连通区域，考虑4连通，去掉最少的#让#区域不连通。

首先说明，在矩阵中一个#的连接最少是2的度，那么我们最多去掉2个#就可以满足，让#域不连通了。

a.如果#数量为1或者2的情况，结果就是-1。

b.其他情况，那么枚举每一个#的位置，假设去掉这个#，FloodFill这个#号周围的连通#号，看组成的区域是1个还是2个。

如果得到的是2个连通域，那么去掉这个#号就可以了，答案是1.否则在遍历所有是否去掉#的位置都没有得到区域为2个的，那么通过前面的说明，结果就是2。

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
char mt[55][55];
int used[55][55];
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
int n, m;
 
void dfs(int sx, int sy) {
    used[sx][sy] = 1;
    for (int i = 0; i < 4; i++) {
        int xx = sx + dx[i];
        int yy = sy + dy[i];
        if (xx >= 1 && xx <= n && yy >= 1 && yy <= m && !used[xx][yy] && mt[xx][yy] == '#') {
            dfs(xx, yy);
        }
    }
}
 
int main() {
    int i, j, k;
    while (scanf("%d%d", &n, &m) == 2) {
 
        memset(mt, 0, sizeof(mt));
        memset(used, 0, sizeof(used));
        for (i = 1; i <= n; i++)
            scanf("%s", mt[i] + 1);
        
        int ok = 0, cnt = 0, ans = 0;
 
        for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
            if (mt[i][j] == '#') {
                cnt++;
            }
 
        for (i = 1; i <= n && !ok; i++)
        for (j = 1; j <= m && !ok; j++) {
            if (mt[i][j] == '#') {
                int set_num = 0;
                memset(used, 0, sizeof(used));
                used[i][j] = 1;
                for (k = 0; k < 4; k++) {
                    int xx = i + dx[k];
                    int yy = j + dy[k];
                    if (xx >= 1 && xx <= n && yy >= 1 && yy <= m && !used[xx][yy] && mt[xx][yy] == '#') {
                        set_num++;
                        dfs(xx, yy);
                    }
                }
                if (set_num >= 2) {
                    ok = 1;
                }
            }
        }
        if (cnt <= 2)    puts("-1");
        else printf("%d
", ok ? 1 : 2);
    }
    return 0;
}

D. LCM Challenge

给定范围n，求在n之内的三个数，三个数可以相同或不同，他们的最小公倍要最大。

a.n为奇数，n,n-1,n-2互质。结果显然为n*(n-1)*(n-2)

b.n为偶数，n,n-1,n-3互质，结果为n*(n-1)*(n-3)