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

十一月 03, 2018 14134

当一个选手比你小，还比你强……

前言

题面 & 测试输入来自山河

T1. 求和

题面

小马克今年成为小学生。不久后她将进行她的第一次考试，其中包括数学考试。

她非常认真地复习，她认为自己已经准备好了。她的哥哥通过给她提出问题并解决的方式帮助她。

他的问题是给定一连串整数：依次由 1 个 1，2 个 2，3 个 3 等组成，即1223334444……。

现在他给马克两个整数 A 和 B； 他的任务是求出由第 A 个到第 B 个数的。如果 A 是 1， B是 3， 答案为 1+2+2=5。 给一个问题， 然后计算它们的和， 马克的哥哥能够验证答案正确与否。

输入输出格式 & 样例

输入格式：
输入文件 instruckcije.in 只有一行， 包括正整数 A 和 B。

输出格式：
输出文件 instruckcije.out 共一行， 为和的值。

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

输入样例#2：
1 1000
输出样例#2：
29280

数据范围

1 \leq A,B \leq 1000

解析

首先这题是一个签到题无误了

数据范围如此之小，我们可以直接把序列初始化出来，再处理出一个前缀和数组，最后输出即可。

时间复杂度…… O(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
namespace Solution {
    const int MAXLENGTH_1 = 1000 + 10;
    
    int seq[MAXLENGTH_1], sum[MAXLENGTH_1];
    
    void Init() {
        int now = 1, cur = 0, i = 0;
        while (i <= 1001) {
            ++cur;
            seq[++i] = now;
            if (cur == now) {
                cur = 0;
                ++now;
            }
        }
        for (int i = 1; i <= 1000; ++i) {
            sum[i] = sum[i-1] + seq[i];
        }
    }
    
    void Work1() {
        using FastIO::getint;
        Init();
        int x = getint();
        int y = getint();
        if (x > y) swap(x, y);
        FastIO::putint(sum[y] - sum[x-1], '\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;
    using namespace FastIO;
    Work1();
    return 0;
}

T2. 猜歌名

题面

“Guess the song” 是一项在年轻程序员中非常流行的游戏。它是一种集技能、智慧、 耐性于一体的游戏。这个游戏给玩游戏的人放音乐， 游戏者的目标是尽可能快地猜这首歌 的歌名。

Mirko 可能不是一个很好的程序员， 但他是一个世界级的猜歌者。

Mirko 总是在专辑里的某首歌播放出至少一半歌词的时候猜出歌名。所有歌名的单词是唯一的（没有一个单词会出现一次或更多次）。

写一个程序， 给出歌名和专辑名， 看看 Mirko 在这首歌的哪个点上（在多少个单词之后）猜出歌名。

输入输出格式 & 样例

输入格式：
第一行：包含一个整数 N， 它是一首歌里的单词数目。
接下来的 N 行每一行包含歌名的一个单词。
第 N+2 行： 包含一个整数 M， 它是专辑里的单词数目。
接下来的 M 行每一行包含专辑里的一个单词。
歌名和专辑里的所有单词由 1 到 15 个小写英文字母组成。

输出格式：
共一行， 包含一个数， 表示 Mirko 在第几个单词处猜出歌曲名。

输入样例#1：
3
sedam
gladnih
patuljaka
7
sedam
dana
sedam
noci
sedam
gladnih
godina

输出样例#1：
6

解析

我们称输入的N个单词为WN，输入的M个单词为WM

那么题目就是要求我们找出一个最小ANS，使得在WM中的前ANS个单词满足有至少一半的WN中的单词

那么数据范围依然极小，直接暴力算完

当然我看着貌似能二分答案太懒不写
单调性显然，当 \text{ANS} 成立的时候，满足 \text{ANS} \leq \text{ANS}_1 \leq \text{M} 的 \text{ANS_1} 都是成立的。

这里要注意的是当N为奇数时，N的一半 =\lfloor\frac{N}{2}\rfloor + 1 ，否则N的一半 =\frac{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
namespace Solution {
    const int MAXN = 50 + 10;
    const int MAXM = 10000 + 10;
    
    string song[MAXN];
    string album[MAXM];
    
    map<string, bool> vis;
    
    int n, m, most;
    
    inline bool Check() {
        int ret = 0;
        For (i, 1, n) if (vis[song[i]]) ++ret;
        return ret >= most;
    }
    
    void Work2() {
        cin >> n;
        For(i, 1, n) {
            cin >> song[i];
        }
        cin >> m;
        most = ((n % 2) == 0 ? n / 2 : n / 2 + 1);
        For(i, 1, m) {
            cin >> album[i];
            //cout << album[i] << endl;
            vis[album[i]] = true;
            if (Check()) {
                printf("%d\n", i);
                return;
            }
        }
    }
}

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;
    using namespace FastIO;
    Work2();
    return 0;
}

T3. 黑白棋

题面

Lagno 是一种二人智力游戏。 游戏设有一个黑方和一个白方。游戏桌面是正方形的， 包含 8 行 8 列。

如果黑方玩家走出这样一步棋：将一枚黑子放在任一空格上， 而在这个空格的八个方向（上、下、左、右和 4 个对角线方向）的至少一个方向上有一排白子被夹在这枚新下的黑子和其他黑子之间， 任何方向， 在新黑子和原来黑子之间的所有白子都要变成黑子。为这个游戏设计一个程序， 计算一步棋中黑方能转变的白子数量的最大值。

输入输出格式 & 样例

输入格式：
输入文件 lango.in 共 8 行， 每行 8 个字符；“.”代表一个空格；“B”代表黑子，“W” 代表白子。

输出格式：
输出文件 lango.out 共一行， 有一个整数， 表示一步中黑方能吃掉白子的最大数， 如果无法吃掉就输出“0”。

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

1
2
3
4
5
6
7
8
........
........
........
...BW...
...WB...
........
........
........

（这个说实话不等宽不行

输出样例#1： 

1
1

解析

暴！力！能！过！


输出0拿9分

暴力算法

数据范围如此之小，我们不如直接枚举所有空格点，对这个点进行八向扩展，累加答案，最后取 max 即可

正解

当然是DFS
我们还是枚举每一个点，只不过这次不暴力扩展了。
我们用dx[]和dy[]来记八个方向，根据它来扩展。
dfs(int now, int x, int y)中的now就表示现在是第now个方向

边界肯定是要判的（x < 1 || x > 8 || y < 1 || y > 8），当前是不是空格子也要判（s[i][j] == '.'），如果有任意一个满足就直接return -INF
如果当前碰到了一个黑格子，说明到头了，return 0即可
否则return dfs(now, x + dx[now], y + dy[now]) + 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
116
117
118
119
120
121
122
123
124
125
126
namespace Solution {
    const int dx[8] = {-1, 1, 0, 0, -1, -1, 1, 1};
    const int dy[8] = { 0, 0, -1, 1, -1, 1, -1, 1};
    const int MAXX_Y = 8 + 2;
    
    short Map[MAXX_Y][MAXX_Y];
    // 0: blank
    // 1: Black
    // 2: White
    
    int ans = 0;
    
    void Read() {
    	// 初始化
        for (int i = 1; i <= 8; ++i) {
            for (int j = 1; j <= 8; ++j) {
                char c;
                cin >> c;
                switch (c) {
                    case '.': {
                        Map[i][j] = 0;
                        break;
                    }
                    case 'B': {
                        Map[i][j] = 1;
                        break;
                    }
                    case 'W': {
                        Map[i][j] = 2;
                        break;
                    }
                }
            }
        }
    }
    
    int getAnswer(int x, int y) {
    	// 获取上下左右的可扩展数量
        int ret = 0;
        int current = 0;
        int ox = x;
        int oy = y;
        while (true) { ++current; ++x; if (Map[x][y] == 0) { current = 0; break; } if (Map[x][y] == 1) break; if (x == 8 && Map[x][y] == 2) { current = 0; break; } }
        if (current > 0) --current;
        ret += current;
        current = 0;
        x = ox;
        y = oy;
        while (true) { ++current; --x; if (Map[x][y] == 0) { current = 0; break; } if (Map[x][y] == 1) break; if (x == 1 && Map[x][y] == 2) { current = 0; break; } }
        if (current > 0) --current;
        ret += current;
        current = 0;
        x = ox;
        y = oy;
        while (true) { ++current; ++y; if (Map[x][y] == 0) { current = 0; break; } if (Map[x][y] == 1) break; if (y == 8 && Map[x][y] == 2) { current = 0; break; } }
        if (current > 0) --current;
        ret += current;
        current = 0;
        x = ox;
        y = oy;
        while (true) { ++current; --y; if (Map[x][y] == 0) { current = 0; break; } if (Map[x][y] == 1) break; if (y == 1 && Map[x][y] == 2) { current = 0; break; } }
        if (current > 0) --current;
        ret += current;
        current = 0;
        x = ox;
        y = oy;
        return ret;
    }

    int getAnswerAlt(int x, int y) {
    	// 获取四个对角线上的可扩展数量
        int ret = 0;
        int current = 0;
        int ox = x;
        int oy = y;
        while (true) { ++current; ++x; ++y; if (Map[x][y] == 0) { current = 0; break; } if (Map[x][y] == 1) break; if ((x == 8 || y == 8) && Map[x][y] == 2) { current = 0; break; } }
        if (current > 0) --current;
        ret += current;
        current = 0;
        x = ox;
        y = oy;
        while (true) { ++current; --x; --y; if (Map[x][y] == 0) { current = 0; break; } if (Map[x][y] == 1) break; if ((x == 1 || y == 1) && Map[x][y] == 2) { current = 0; break; } }
        if (current > 0) --current;
        ret += current;
        current = 0;
        x = ox;
        y = oy;
        while (true) { ++current; --x; ++y; if (Map[x][y] == 0) { current = 0; break; } if (Map[x][y] == 1) break; if ((x == 1 || y == 8) && Map[x][y] == 2) { current = 0; break; } }
        if (current > 0) --current;
        ret += current;
        current = 0;
        x = ox;
        y = oy;
        while (true) { ++current; ++x; --y; if (Map[x][y] == 0) { current = 0; break; } if (Map[x][y] == 1) break; if ((x == 8 || y == 1) && Map[x][y] == 2) { current = 0; break; } }
        if (current > 0) --current;
        ret += current;
        current = 0;
        x = ox;
        y = oy;
        return ret;
    }
    
    void Search() {
        for (int i = 1; i <= 8; ++i) {
            for (int j = 1; j <= 8; ++j) {
                if (Map[i][j] != 0) continue;
                ans = std::max(ans, getAnswer(i, j) + getAnswerAlt(i, j));
            }
        }
    }
}

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;
    using namespace FastIO;
    Read();
    Search();
    putint(ans, '\n');
    return 0;
}

正解

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
namespace Solution {
    const int dx[8 + 1] = {0, -1, -1, 0, 1, 1,  1,  0, -1};
    const int dy[8 + 1] = {0,  0,  1, 1, 1, 0, -1, -1, -1};
    const int INF = 2147482333;
    
    char s[8 + 2][8 + 2];
    
    int ans, Max;
    
    void Init() {
        for (int i = 1; i <= 8; ++i) {
            for (int j = 1; j <= 8; ++j) {
                cin >> s[i][j];
            }
        }
    }
    
    int DFS(int now, int x, int y) {
        if (x < 1 || x > 8 || y < 1 || y > 8 || s[x][y] == '.') return -INF;
        if (s[x][y] == 'B') return 0;
        return DFS(now, x + dx[now], y + dy[now]) + 1;
    }
}

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;
    using namespace FastIO;
    Init();
    for (int i = 1; i <= 8; ++i) {
        for (int j = 1; j <= 8; ++j) {
            for (int k = 1; k <= 8; ++k) {
                int p = 0;
                if (s[i][j] == '.') {
                    p = DFS(k, i + dx[k], j + dy[k]);
                    if (p > 0) ans += p; // 累计答案
                }
            }
            Max = std::max(Max, ans); // 更新答案
            ans = 0;
        }
    }
    putint(Max, '\n');
    return 0;
}

T4. 跳格子

题面

Nikola 现在已经成为一个游戏里的重要人物。这个游戏是由一行 N 个方格， N个方格 用 1 到 N 的数字表示。 Nikola 开始是在 1 号位置， 然后能够跳到其他的位置， Nikola 的第一跳必须跳到 2 号位置。随后的每一跳必须满足两个条件： 1、如果是向前跳， 必须比前面一跳远一个方格。 2、如果是向后跳， 必须和前面一跳一样远。 比如， 在第一跳之后（当在 2 号位置时）， Nikola 能够跳回 1 号位置， 或者向前跳到 4号位置。 每次他跳入一个位置， Nikola 必须付费。 Nikola 的目标是从一号位置尽可能便宜地跳到 N 号位置。 写一个程序， 看看 Nikola 跳到 N 号位置时最小的花费。

输入输出格式 & 样例

输入格式：
共有 N+1 行。 第一行：包含一个整数 N， 它是位置的编号。 第 2..N+1 行：第 i+1 行表示第 I 个方格的费用， 是一个正整数

输出格式：
只有一个数， 表示 Nikola 跳到 N 号位置时最小的花费。

输入输出样例

输入样例#1：
6 1 2 3 4 5 6
输出样例#1：
12

输入样例#2：
8 2 3 4 3 1 6 1 4
输出样例#2：
14

数据范围

2≤N≤1000 费用不大于500

解析

妥妥的DP

我们设 \text{f[i][j]} 表示跳到第 i 个格子上，可以向后跳 j 个格子的时候的最小花费

转移方程：

  • \text{(default) f[i][j] = LESS_INF}
  • 上一次向前跳，显然上一次跳了 j 格。 \text{f[i][j] = min(f[i][j], f[i-j][j-1]}
  • 上一次向后跳，显然上一次跳了 j 格。 \text{f[i][j] = min(f[i][j], f[i+j][j]}

最后加上本格的花费 \text{cost[i]} 就是 \text{f[i][j]}

需要注意的东西有两个，一个是边界，另一个是答案为 \text{min{f[n][i]} }(i \in [1, n-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
namespace Solution {
    
    const int MAXN = 1000 + 10;
    
    int cost[MAXN];
    int f[MAXN][MAXN];
    int n;
    
    int DFS(int now, int step, int ncost) {
    	// 写挂了的搜索
        if (now == n) return ncost;
        int ret = 2147482333;
        cout << "now = " << now << endl;
        cout << "ncost = " << ncost << endl;
        if (now + step + 1 <= n) ret = std::min(ret, DFS(now + step + 1, step + 1, ncost + cost[now + step + 1]));
        if (now != 1 && step != 0 && now - step > 0) ret = std::min(ret, DFS(now - step, step, ncost + cost[now - step]));
        return ret;
    }
}

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;
    using namespace FastIO;
    n = getint();
    For (i, 1, n) cost[i] = getint();
    int step = 0;
    //putint(DFS(1, 0, cost[1]), '\n');
    //for (int i = 1; i < n; ++i) {
    //    int now = 2147482333;
    //}
    int Min = 2147482333;
    for (int i = 2; i <= n; ++i) f[i][0] = 0x3f3f3f3f;
    for (int j = 1; j < n; ++j) {
        for (int i = n; i >= 1; --i) {
            f[i][j] = 0x3f3f3f3f;
            if (i > j) f[i][j] = f[i - j][j - 1];
            if (i + j <= n) f[i][j] = std::min(f[i][j], f[i + j][j]);
            if (f[i][j] != 0x3f3f3f3f) f[i][j] += cost[i];
            if (i == n) Min = std::min(Min, f[i][j]);
        }
    }
    putint(Min, '\n');
    return 0;
}

果然我还是太弱了 这题并没有A掉 差这题就AK了