2017.12.9 定段赛第二场 题解

| | 伟大的蚊子

2017.12.9 定段赛第二场 15:30分场

2017.12.9 定段赛第二场 15:30分场

Problem A

hdu2014

去掉Min和Max求avg

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    int n;
    while (scanf("%d",&n) == 1){
        int x, Max=0, Min=999;
        double sum = 0;
        for (int i = 0; i < n; i++){
            scanf("%d", &x);
            sum += x;
            Max = max(Max, x);
            Min = min(Min, x);
        }
        sum -= Max + Min;
        sum /= n - 2;
        printf("%.2lf\n",sum);
    }
    return 0;
}

Problem B

hihocoder1623

题意：一个数字（号码牌），倒过来可能是另一个数字，问正着倒着是否会产生歧义

const 每个数字可能产生的“歧义数字”, 然后看倒过来是什么即可

代码有点丑，见谅

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
 #include <bits/stdc++.h>
using namespace std;
map <int, int> mp;

// 这个map用来记录每个数字倒过来是什么数字
// 如果倒过来不是一个数字，就不在
inline void initmp(){
    mp[1] = 1;
    mp[2] = 2;
    mp[5] = 5;
    mp[6] = 9;
    mp[8] = 8;
    mp[9] = 6;
    mp[0] = 0;
}

inline void wtf(int n) {
    int x = 1, cnt = 1, ans = 0;
    // 依次处理1..n的所有号码看看是否有歧义
    for (int i = 1; i <= n; i++) {
        if(i == x * 10) cnt++, x = i;
        int p = i, tmp = 0;  // tmp为i倒过来后的号码
        bool ok = true;  // 这个bool用来标记是否有mp种没有的数字
        // 如果有，则说明不可能有歧义
        
        // 这个循环用来搞出i倒过来的数字
        for(int j = 0; j < cnt; j++, p /= 10) {
            if (mp.find(p%10) == mp.end()) {
                ok = false; break;
            }
            tmp = (tmp*10 + mp[p % 10]);
        }
        // 将有歧义的号码输出
        if (tmp<=n && ok && tmp!=i && (i%10)>0) {
            printf("%d\n", i);
        }
    }
}

int main(){
    initmp();
    for (int n; cin >> n;) {
        wtf(n);
    }
    return 0;
}

Problem C

hihocoder1361

百度百科凯撒密码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
using namespace std;
int main(){
    //freopen("fuck.in","r",stdin);
    string st;
    cin>>st;
    int len = st.length();
    bool vis[200];
    memset(vis,0,sizeof(vis));
    char a[30];
    int pos = 0;
    // 将单词预处理
    for (int i=0;i<len;i++){
        if (st[i] == 'J') st[i]='I';  // 读题，注意本题没有J字母
        if (vis[st[i]]) continue;  // 每个字母只有一次
        vis[st[i]] = 1;  
        a[pos++] = st[i];  // 将不重复的字母打出
    }
    // 将单词中未出现的字母依次填入
    for (char i='A';i<='Z';i++){
        if (vis[i]||i=='J')continue;
        a[pos++] = i;
    }
    // 输出答案，分行
    for (int i=0;i<25;i++){
        printf("%c",a[i]);
        if (i%5==4)puts("");
    }
    return 0;
}

Problem D

hiho1362

二分最矮的木桶高度h，也就说高度小于h的需要修一次，

当然木桶是圆的，维修起点不确定，我们可以枚举 [○・`Д´・○]

然后统计修了多少次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<cstdio>
#include<iostream>
using namespace std;
const int INF=0x3f3f3f3f;
const int N=1e5+100;
int n,m,len,a[N],b[N];

// 以start为起点，修木桶
bool repair(int start,int h){
    int cnt = 0;
    // 维修n的长度
    for (int i = start; i <= start+n; i++) if (b[i]<h) {
        i += len-1; // 维修len长度
        cnt++; // cnt为维修次数
    }
    return cnt <= m; // (。・`ω´・)
}

// 检查是否可以修到h高度
bool check(int h){
    // 复制一个木桶，下次check可能还需要用这个桶
    for (int i = 1; i <= n+len; i++) b[i] = a[i];
    // 因为木桶是一个环，所以它的起点是任意的
    // 既然是任意的，那么枚举起点，
    //任意起点维修成功则说明可以修到h高度
    for (int i = 1; i <= len; i++)
        if (repair(i, h)) return 1;
    return 0;
}

int main(){
    //freopen("fuck.in","r",stdin);
    scanf("%d%d%d", &n, &m, &len);
    for (int i = 1; i <= n; i++){scanf("%d",&a[i]);}
    // 对于一个环的处理，复制一遍
    for (int i = n+1; i <= n+len; i++) a[i] = a[i-n];
    // 二分修到的高度
    int L = 0, R = INF, ans;
    for (; L <= R;){
        int mid=(L+R)>>1;
        if (check(mid)){
            L = mid + 1;
            ans = mid;
        }
        else R = mid - 1;
    }
    printf("%d\n", ans);
    return 0;
}

Problem E

hdu6113

手写数字识别

题意： 给矩阵判断手写数字是0还是1

sol: 周围加一圈0，统计0的连通块数量，注意-1

题目大部分都是废话，主要是看0和1的定义，仔细读定义，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 222;
char maze[N][N];
int dx[4] = { 1, -1, 0,  0};
int dy[4] = { 0,  0, 1, -1};
int n,m;

// dfs搜索联通块
void dfs(int x, int y, char c){
    maze[x][y] = '2';  // 标记
    for(int i = 0;i < 4;i++){
        int xx = x + dx[i];
        int yy = y + dy[i];
        // 超出边界或者已经出现过了
        if(xx < 0 || xx > m || yy < 0 || yy > n || maze[xx][yy] != c) continue;
        dfs(xx, yy, c);
    }
}

int main(){
    while(~scanf("%d%d\n", &m, &n)){
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n;j++){
                scanf("%c", &maze[i][j]);
            }
            getchar();
        }
        m++, n++;
        // 在图外面加一圈0，
        // 因为原来图的1可能会顶格
        for(int j = 0; j <= n; j++) {
            maze[m][j] = '0';
            maze[0][j] = '0';
        }
        for(int i = 0; i <= m; i++) {
            maze[i][n] = '0';
            maze[i][0] = '0';
        }

        // 统计联通块的数量
        // cnt0表示有多少块由0组成的区域, 1同理
        int cnt0 = 0, cnt1 = 0;
        for(int i = 0; i <= m; i++){
            for(int j = 0; j <= n; j++){
                if(maze[i][j] == '0'){
                    cnt0++;
                    dfs(i, j, '0');
                } else if(maze[i][j] == '1'){
                    cnt1++;
                    dfs(i, j, '1');
                }
            }
        }
        // _(:3 」∠)_ 
        if(cnt0 == 2 && cnt1 == 1) printf("0\n");
        else if(cnt0 == 1 && cnt1 == 1) printf("1\n");
        else printf("-1\n");
    }
    return 0;
}