「LYOI初中坑题组」模拟赛#2 题解

十一月 05, 2018 7434

暴力能过的题目

前言

题面 & 数据依然来自山河

评测 Powered by 洛谷OnlineJudge

T1. 复制-粘贴

题目描述

小 y 是一个聪明的程序员，但是他懒到了极致，在输入程序时甚至不愿意多打一行代码。

有一次，小 y 发现他的一个程序需要输入 n 行一模一样的代码，怎么办呢？

他首先输入了第 1 行，然后通过 1 次“复制-粘贴”命令得到了第 2 行，再通过 1 次“复制-粘贴”命令得到了第 3-4 行………..直到完成这 n 行代码的输入。

小 y 懒得得意洋洋，正好遇到初学编程的小 x，他就想考考小 x，顺便为难为难他以炫耀自己的聪明才智和编程水平。于是把“复制-粘贴”的伎俩告诉小 x，并让小 x 编程计算最少通过几次“复制-粘贴”命令可以得到正好 n 行的代码？

输入输出格式

输入格式：
一行一个正整数 n,

输出格式：
一行一个正整数，表示最少的“复制-粘贴”次数

输入输出样例

输入样例#1：
4
输出样例#1：
2

解析

简单推一下就可以知道答案是 \lceil log_2n \rceil

这里要注意的是C++中的 log 是以 e 为底的
求 \lceil log_2n \rceil 的代码为ceil(log(n) / log(2))

代码实现

1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int a;
    cin >> a;
    cout << ceil(log(a) / log(2)) << endl;
    return 0;
}

T2. 足球联赛

题目描述

一个足球联赛由 n 只球队构成。在一个赛季中，每只球队都要与其它球队各比赛两场。

一场比赛在主场，一场在客场。赢一场得 3 分，输一场不得分，平局两支队伍各得 1 分。现在，给你一个 n*n 的矩阵表示比赛情况。第 i 行第 j 列的字母表示在第 i 只队伍主场的比赛情况， W 表示主队赢， L 表示主队输， D 表示平局。

需要你求出得分最高的队伍的编号，如果有分数相同的，在一行中按字典序输出队伍编号。

输入输出格式

输入格式：
第一行，一个整数 n 。

接下来 n 行，每行 n 个字符，表示输赢情况。

第 i 行第 i 列为 - ,因为一只队伍不可能与自己比赛。

输出格式：
得分最高的队伍编号。如有多个在一行中输出，用一个空格分开

输入输出样例

输入样例#1： 

1
2
3
4
3 
-WW
W-W
WW-

输出样例#1： 

1
1 2 3

输入样例#2： 

1
2
3
4
5
6
5 
-DWWD
L-WLL
DD-WD
DDL-L
DDLL-

输出样例#2： 

1
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
/* -- Basic Headers -- */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>

/* -- STL Iterators -- */
#include <vector>
#include <string>
#include <stack>
#include <queue>

/* -- External Headers -- */
#include <map>
#include <cmath>

/* -- Defined Functions -- */
#define For(a,x,y) for (int a = x; a <= y; ++a)
#define Forw(a,x,y) for (int a = x; a < y; ++a)
#define Bak(a,y,x) for (int a = y; a >= x; --a)

/* -- Defined Words -- */

using namespace std;

namespace FastIO {
    
    inline int getint() {
        int s = 0, x = 1;
        char ch = getchar();
        while (!isdigit(ch)) {
            if (ch == '-') x = -1;
            ch = getchar();
        }
        while (isdigit(ch)) {
            s = s * 10 + ch - '0';
            ch = getchar();
        }
        return s * x;
    }
    inline void __basic_putint(int x) {
        if (x < 0) {
            x = -x;
            putchar('-');
        }
        if (x >= 10) __basic_putint(x / 10);
        putchar(x % 10 + '0');
    }
    
    inline void putint(int x, char external) {
        __basic_putint(x);
        putchar(external);
    }
}


namespace Solution {
    const int MAXN = 50 + 10;
    
    int n;
    int score[MAXN];
    char sc[MAXN][MAXN];
    
    void Read() {
        ios::sync_with_stdio(false);
        cin >> n;
        For (i, 1, n) {
            For (j, 1, n) {
                cin >> sc[i][j];
            }
        }
    }
    
    void Work() {
        ios::sync_with_stdio(false);
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (i == j) continue;
                switch(sc[i][j]) {
                    case 'W': {
                        score[i] += 3;
                        break;
                    }
                    case 'L': {
                        score[j] += 3;
                        break;
                    }
                    case 'D': {
                        score[i] += 1;
                        score[j] += 1;
                        break;
                    }
                }
            }
        }
        int Max = -2147482333;
        For (i, 1, n) Max = std::max(Max, score[i]);
        For (i, 1, n) if (score[i] == Max) cout << i << ' ';
        cout << endl;
    }
}

int main(int argc, char *const argv[]) {
#define HANDWER_FILE
#ifndef HANDWER_FILE
    freopen("testdata.in", "r", stdin);
    freopen("testdata.out", "w", stdout);
#endif
    using namespace Solution;
    Read();
    Work();
    return 0;
}

T3. 捕食关系

题目描述

在海洋中，有食肉类的鱼和食草类的鱼，某种食肉类的鱼捕食食草类的鱼当且仅当自己的体重大于对方。

现在给出两类鱼各自的体重，求有多少对捕食关系。

输入输出格式

输入格式：
每组测试数据有三行。

第一行有两个整数 m， n，分别代表食肉类的鱼的种类数和食草类的鱼的种类数。

第二行 m 个数，第三行 n 个数，代表各自的体重。

输出格式：
一个整数，表示有多少对捕食关系。

输入输出样例

输入样例#1：
5 3
8 1 7 3 1
3 6 1
输出样例#1：
7

解析

正解不会 暴力能过

我不知道纯暴力能不能过 反正我们要优化一下

首先把食草鱼体重从小到大排个序
那么我们在枚举食肉鱼的时候，就可以遇见在第一个体重更大的食草鱼的时候break掉，做法的正确性是显然的

时间复杂度均摊 O(n^2)

代码实现

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
/* -- Basic Headers -- */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>

/* -- STL Iterators -- */
#include <vector>
#include <string>
#include <stack>
#include <queue>

/* -- External Headers -- */
#include <map>
#include <cmath>

/* -- Defined Functions -- */
#define For(a,x,y) for (int a = x; a <= y; ++a)
#define Forw(a,x,y) for (int a = x; a < y; ++a)
#define Bak(a,y,x) for (int a = y; a >= x; --a)

/* -- Defined Words -- */

using namespace std;

namespace FastIO {
    
    inline int getint() {
        int s = 0, x = 1;
        char ch = getchar();
        while (!isdigit(ch)) {
            if (ch == '-') x = -1;
            ch = getchar();
        }
        while (isdigit(ch)) {
            s = s * 10 + ch - '0';
            ch = getchar();
        }
        return s * x;
    }
    inline void __basic_putint(int x) {
        if (x < 0) {
            x = -x;
            putchar('-');
        }
        if (x >= 10) __basic_putint(x / 10);
        putchar(x % 10 + '0');
    }
    
    inline void putint(int x, char external) {
        __basic_putint(x);
        putchar(external);
    }
}


namespace Solution {
    const int MAXNM = 20000 + 10;
    
    int n, m;
    int bigFish[MAXNM], smallFish[MAXNM];
    
    void Read() {
        using FastIO::getint;
        m = getint();
        n = getint();
        For (i, 1, m) {
            bigFish[i] = getint();
        }
        For (i, 1, n) {
            smallFish[i] = getint();
        }
    }
    
    void Work() {
        int cnt = 0;
        sort(smallFish + 1, smallFish + 1 + n);
        For (i, 1, m) {
            For (j, 1, n) {
                if (smallFish[j] >= bigFish[i]) break;
                ++cnt;
            }
        }
        FastIO::putint(cnt, '\n');
    }
}

int main(int argc, char *const argv[]) {
#define HANDWER_FILE
#ifndef HANDWER_FILE
    freopen("testdata.in", "r", stdin);
    freopen("testdata.out", "w", stdout);
#endif
    using namespace Solution;
    Read();
    Work();
    return 0;
}

T4. 幻方

题目描述

大家都知道 n 阶奇数幻方吧？如下为一个 5 阶幻方：

17 24 1 8 15

23 5 7 14 16

4 6 13 20 22

10 12 19 21 3

11 18 25 2 9
现在，输入奇数 n，输出该奇数幻方最右下角的元素值。

输入输出格式

输入格式：
一行一个数 n。

输出格式：
一行一个数，表示该奇数幻方右下角的值。

输入输出样例

输入样例#1：
5
输出样例#1：
9

解析

找规律

指点迷津

代码实现

不给