「模拟题」2018年12月26日

2018年12月15日学校模拟考

成绩:第四名

T1:100

T2:0

T3:30

题目数据

总结:简单的题还是能想到,有一点涉及到思维的题就死机了 很吃亏,而且明明自己现在的实力就这样还去无缘无故埋怨自己,不是太懂… 继续变强 勇往直前!

还以为自己没在想,结果… 反过来想想自己真的在想 既然没想出来那就是没想出来,我已经尽我当前实力的力了,下次继续加油。

好了,放松,加油!ヾ(◍°∇°◍)ノ゙

①泽泽在中国(china)

(china.cpp/1S/128M)

【题 目 描 述】

众所周知,在中国有个地方叫“万里长城”。
泽泽一天后山玩,在捉蟋蟀的时候,忽然看见一个奇怪的洞。泽泽好奇,就
钻了进去,结果„„

泽泽来到中国万里长城上。长城的城墙很高,泽泽翻墙翻不出去。后面的路又被堵住了,
于是泽泽只有一个选择:向前走。
泽泽向前一看,看见一块牌子,牌子上写道:
若要离开此地,就爬出长城吧。

泽泽无语。 平时泽泽最不擅长的就是长跑, 现在天不遂人愿, 他遇上了麻烦。
但是没有别的去路,于是他硬着头皮爬起来。
泽泽爬一个单位距离需要一个单位时间。
但是这座长城年久失修,地上出现了很多的坑和杂草堆。泽泽在这些地方爬行需要更长的时间。

现在泽泽知道这座长城的长度,以及哪些地方有坑和杂草堆,请算出泽泽需
要多少时间才能爬出长城。

【输 入 描 述】

第 $1$ 行 $2$ 个整数 $s,n$。$s$ 表示长城的长度,$n$ 表示有多少坑和杂草堆。

之后的 $n$ 行,每行 $3$ 个整数 $a_i,b_i,t_i$。表示从 $ai$ 到 $bi$ 的一段每个单位距离

泽泽需要 $ti$ 的时间。 泽泽在没有坑和杂草堆的地方每个单位距离需要时间 $1$。 (保证长度没有重合的)

【输 出 描 述】

一个整数,即泽泽爬出的时间。

【输 入 样 例】

20 5
2 4 2
6 7 4
8 10 2
11 11 5
17 20 5

【输 出 样 例】

52

【题 目 提 示】

这座长城泽泽需要走的时间的模拟图:
1 2 2 2 1 4 4 2 2 2 5 1 1 1 1 1 5 5 5 5

【数 据 范 围】

对于 $ 30% $的数据,$s<=50000$,$n<=100$
对于 $100% $的数据,$s<=2000000000$,$n<=500000$
(保证最后结果不超过 $long long$)

【题 解】

很简单的题, $30%$ 的数据只需要会用数组就能写,注意一下 $100%$ 数据,需要用到线性的处理方式。

所用知识:快速排序、基本模拟方式

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
#define fre yes

#include <cstdio>
#include <algorithm>

const int MAXN_NODE = 500005;
struct Node {
long long l, r, val;
} arr[MAXN_NODE];

bool cmp(Node x, Node y) {
return x.l < y.l;
}

int main() {
#ifdef fre
freopen("china.in", "r", stdin);
freopen("china.out", "w", stdout);
#endif

static long long s; static int n;
scanf("%lld %d", &s, &n);
for (int i = 1; i <= n; i++) {
scanf("%lld %lld %lld", &arr[i].l, &arr[i].r, &arr[i].val);
}

std::sort(arr + 1, arr + 1 + n, cmp);

long long left = 1, ans = 0;
for (int i = 1; i <= n; i++) {
if(left != arr[i].l) {
ans += arr[i].l - left;
} ans += (arr[i].r - arr[i].l + 1) * arr[i].val;
left = arr[i].r + 1;
}

if(arr[n].r <= s) {
ans += s - arr[n].r;
}

printf("%I64d\n", ans);
return 0;
}

②平平的棋子(pieces) (请将本题中的 ‘8’ 全部换成 ‘*’)

(pieces.cpp/1S/128M)

【题 目 描 述】

平平和丁丁在玩一个游戏。桌面上一行有 $n$ 个格子,一些格子中放着棋子。
平平和丁丁轮流选择如下方式中的一种移动棋子(图示中 o 表示棋子,8表示空着的格子):
1) 当一枚棋子的右边是空格子的话,可以将这枚棋子像右移动一格。
88o888 -> 888o88
2) 当一枚棋子的右边连续两个都有棋子,并且这个棋子往右边数第 3 格没
有棋子,那么可以将这个棋子可以跳过去那两个棋子
88ooo8 -> 888oo8

当任何一枚棋子到达最右边的格子时,这枚棋子自动消失。当一方不能移动时,这方输。
假设平平和丁丁都采取最优策略,平平先走,谁将取胜?

【输 入 描 述】

第一行一个整数 $T$ 表示数据组数, $0 < T < 10$。
之后 T 组数据,每组两行,第一行 $n$ 表示格子个数,第二行 $n$ 个字符表示每个格子的情况,
o 表示有棋子,*表示空着。

【输 出 描 述】

对于每组数据一个输出,M 表示平平赢,L 表示丁丁赢。

【样 例 输 入】

4
2
8o
5
8o888
6
88o88o
14
8o88ooo88oo88

【样 例 输 出】

L
M
M
L

【数 据 范 围】

$0 < T < 10$
对于 $50%$ 的数据, $n < 20$。
对于 $100%$ 的数据, $n < 1000$。

【题 解】

还以为是博弈论.. 看了几十分钟 随便猜了几个结论,选了一个过了几个手写样例的结论写上去..
结果发现 还是错的

我的解法:找到第一个 ‘o’ 的位置,记录 然后计算它到最后一位的长度是奇数还是偶数,然后计算 (X)

正确解法:对于每一个 ‘o’,我们都计算它到最后一位的距离,累加起来 然后判断是奇数还是偶数 (√)
奇数时 平平胜利 反之 丁丁胜利

解法依据:我们每次可以选择一个棋子走一格或者三格,在本质上并没有什么区别。 利用这个我们就能写出这个代码了

所用知识:位运算、思维

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
#define fre yes

#include <cstdio>

const int MAXN_CHAR = 2005;
char c[MAXN_CHAR];

int main() {
#ifdef fre
freopen("pieces.in", "r", stdin);
freopen("pieces.out", "w", stdout);
#endif
static int T, n;
scanf("%d", &T);
while(T--) {
scanf("%d", &n);
scanf("%s", c);

int pos = 0;
for (int i = 0; i < n; i++) {
if(c[i] == 'o') {
pos += n - i + 1;
}
}

if(pos & 1) {
puts("M");
} else puts("L");
} return 0;
}

③元元挖矿(mining)

(mining.cpp/1S/256M)

【题 目 背 景】

元元飞船的钻头开启了无限耐久+精准采集模式!这次它要将原矿运到泛光之源的矿石交易市场,
以便为飞船升级无限非概率引擎。

【题 目 描 述】

现在有 $m + 1$ 个星球,从左到右标号为 $0$ 到 $m$,元元最初在 $0$ 号星球。
有 $n$ 处矿体,第 $i$ 处矿体有 $a_i$ 单位原矿,在第 $b_i$ 个星球上。
由于飞船使用的是老式的跳跃引擎,每次它只能从第 $x$ 号星球移动到第 $x + 4$号星球或 $x + 7$ 号星球。
每到一个星球,元元会采走该星球上所有的原矿,求元元能采到的最大原矿数量。
注意,元元不必最终到达 $m$ 号星球。

【输 入 格 式】

第一行 $2$ 个整数 $n,m$。
接下来 $n$ 行,每行 $2$ 个整数 $a_i,b_i$。

【输 出 格 式】

输出一行一个整数,表示要求的结果。

【输 入 样 例】

3 13
100 4
10 7
1 11

【输 出 样 例】

101

【样 例 解 释】

第一次从 $0$ 到 $4$,第二次从 $4$ 到 $11$,总共采到 $101$ 单位原矿。

【数 据 范 围】

对于 $20%$ 的数据 $n=1,m<=10^5$
对于 $40%$ 的数据 $n<=15,m<=10^5$
对于 $60%$ 的数据 $m<=10^5$
对于 $100%$ 的数据 $n<=10^5$,$m<=10^9$,$1<=ai<=10^4$,$1<=bi<=m$

【题解】

DP正解(这里不写(rua~) 后面再补

暴力爆搜 30分

用数组表示当前星球有多少能采集的矿物质即可,就可以写出来,没有什么困难的

(这里作死用map还写了一遍 但是实际上.. 还是数组跑得快)

所用知识:bfs、map

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
# Map版
#define fre yes

#include <map>
#include <queue>
#include <cstdio>
#include <algorithm>

std::map<int, int> v;

struct Node {
int place ,val;
};

int main() {
#ifdef fre
freopen("mining.in", "r", stdin);
freopen("mining.out", "w", stdout);
#endif

static int n, m;
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) {
int x, y;
scanf("%d %d", &x, &y);
v[y] = x;
}

std::queue<Node> q;
q.push((Node){0, 0});
int ans = 0;
while(!q.empty()) {
Node u;
u.place = q.front().place;
u.val = q.front().val;
q.pop();

if(u.place > m) {
ans = std::max(ans, u.val);
continue;
} if(v[u.place]) u.val += v[u.place];
u.place += 4;
q.push(u);
u.place -= 4;
u.place += 7;
q.push(u);
} printf("%d\n", ans);
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
# 数组版
#define fre yes

#include <queue>
#include <cstdio>
#include <algorithm>

const int MAXN_INT = 100005;
int arr[MAXN_INT];

struct Node {
int place ,val;
};

int main() {
#ifdef fre
freopen("mining.in", "r", stdin);
freopen("mining.out", "w", stdout);
#endif

static int n, m, k;
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) {
int x, y;
scanf("%d %d", &x, &y);
arr[y] += x;
k = std::max(k, y);
}

std::queue<Node> q;
q.push((Node){0, 0});
int ans = 0;
while(!q.empty()) {
Node u;
u.place = q.front().place;
u.val = q.front().val;
q.pop();

if(u.place > m || u.place > k) {
ans = std::max(ans, u.val);
continue;
} if(arr[u.place]) u.val += arr[u.place];
u.place += 4;
q.push(u);
u.place -= 4;
u.place += 7;
q.push(u);
} printf("%d\n", ans);
return 0;
}
0%