2020.09.12【NOIP提高组&普及组】模拟赛C组2
发布日期:2021-06-21 02:54:44 浏览次数:5 分类:技术文章

本文共 5125 字,大约阅读时间需要 17 分钟。

总结:这次比赛成绩并不理想,虽然策略得当\(P.S.\):太多题有多组数据,但是样例只有一个数据

各题题解和改题情况

T1 匹配

题面

描述

给你一个由{a,b…z,A,B….Z}组成的字符串,我们把大写字母{A,B….,Z}当作括号,这26个字母形成13对括号,(A,Z),(B,Y)………(M,N),每对中的第一个字母表示左括号”(”,第二个字母表示右括号”)”。

一个匹配的表达式是指左括号和右括号要配对,也就是说所有的左括号的右边都有一个右括号和它配对,而且如果一个左括号在某一个配对的括号的中间,那么跟它配对的右括号也必须在该配对的括号中间。
例如AabcZBBefYeY是一个匹配的表达式。而AabcBZY不是,因为(B,Y)中在(A,Z)的中间,而Y不在。同样AabcZZA也不是,因为第二个Z没有配对的A。
小写字母{a,b,…z}不表示括号,可以出现在任何地方。你的任务是决定给定的字符串是否是匹配的。

输入

输入包括多组测试数据,每组测试数据第一行是一个整数N,表示字母的个数,接下来第二行是N个字母。

输出

对于每组测试数据,输出1或0,1表示匹配,0表示不匹配。

样例输入

12

AabcZBBefYeY

样例输出

1

题目大意

每两个字母对应一种匹配的括号,具体的,如 (A,Z),(B,Y)………(M,N)

问你给定的字符串是否满足括号匹配(小写字母啥也不是)

总结 & 题解

这道题其实并不难,但是要细心,学会造对拍数据。

真的是裸的 \(O(n)\) 栈,但是要注意

感谢某位比我先考完试的大喊了一声提醒了我
可是我加了一个多组数据的时候
一个
return 0拯救了我!

应得:

实际:

T2 生日蛋糕

题面

描述

今天是你的生日,家里给你买了个\(N*N\)的蛋糕,蛋糕被分成\(N*N\)个单元格,水平和垂直方向各切一刀,这样分成4份。

然后你妹妹、爸爸、妈妈依次取一份,最后才轮到你取。
蛋糕上有的单元格上有巧克力,有的没有,不幸的是你一家4口都喜欢吃,而且每个人都很自私,轮到他取的时候都会毫不客气地取其中巧克力最多的蛋糕。
问你该如何切才能使得自己获得最多多少个巧克力。
如下图的蛋糕,其中”#”表示有巧克力,”.”表示没有.

下面是两种可行的切法:
第一种切法,你最终只能拿到2个巧克力,而第二种可以得到3个。
输入

输入第一行是一个整数N,表示蛋糕的边长。接下来N行,每行N个字符(“#”或”.”)描述蛋糕的情况。

输出

输出第一行输出一个整数M表示你最大可以获得巧克力的个数。

接下来输出两个整数R和C,描述切割方法,R表示水平切线是介于第R行和R+1行之间,C表示垂直切线介于第C列和第C+1列之间。
如果有多种切法,输出任意一种即可。

样例输入

8

..#..#..
.##..#..
......#.
.##.....
..#.#...
......#.
........
..#..#..

样例输出

3

3 4

题目大意

给你一个矩阵表示一块蛋糕,上面有一些巧克力,现在让你横竖各一刀切成四块

问四块中最小巧克力块数最大值和切法

总结 & 题解

这道题正常发挥:

用时也很正常

主要难点:矩阵前缀和

\(sum_{i,j}\) 表示以 (1,1) 为左上角,以 (i,j) 为右下角的巧克力总块数

先列出式子:\(Sum_{i,j}=Sum_{i,j-1}+Sum_{i-1,j}-Sum_{i-1,j-1}+map_{i,j}\)

解释

\(Sum_{i,j-1}\)


\(Sum_{i-1,j}\)


\(Sum_{i-1,j-1}\)

这就相当于一个容斥原理

然后直接暴力枚举切的行和切的列,分别求出四块的块数并取 min ,并和答案比较,最后输出

T3 游戏

题面

描述

玩家1和玩家2在\(N*N\)的棋盘玩游戏,一开始皇后被放置在棋盘上的某个位置,两人轮流移动,玩家1先移。

每次移动玩家可以把皇后向左边移动若干步,或者向下面移动若干步,或者沿着左下方的斜线移动若干步。
如下图,“X”表示皇后”Q”一次移动可以移到的位置。

游戏将会以皇后到达左下角而告终。谁把皇后移到左下角就获胜。例如下图:
玩家2将获得比赛的胜利。
告诉你皇后一开始的位置。你的任务是计算出最后谁将赢得比赛的胜利,假设两个玩家都是聪明绝顶每次移动都会采用最优策略。
输入

输入包含多组测试数据(<10组)。

对于每组测试数据,输入包含两行,第一行包含一个整数N,描述棋盘的大小,
第二行输入两个整数I,J,其中I表示开始皇后所在列(丛左数起),J表示行(从上数起)。

输出

对于每组输入数据,输出1或2,表示是哪个玩家赢得比赛的胜利。

样例输入

500

331 297
500
127 423
500
117 429
500
124 424

样例输出

1

1
1
2

总结 & 题解

我也想到找规律,但是过于肤浅,遇到这种题应该深入探究。

转载于

这个题其实是有规律的

规律:
(如果一个位置0则从该点出发后手必胜)
(如果一个位置1则从该点出发先手必胜)
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
从这张图可以看出:
0具有对称性。
比如:(2,3)是0,(3,2)也是0
然后,我们把0的位置挑出来:
1 1
2 3
3 2
4 6
5 8
6 4
7 11
8 5
9 14
10 16
11 7
12 19
13 21
14 9
15 24
16 10
17 27
18 29
19 12
21 13
24 15
27 17
29 18

好像看起来没什么规律,但是先去个重:

1 1

2 3
4 6
5 8
7 11
9 14
10 16
12 19
13 21
15 24
17 27
18 29

我们可以发现这样的规律:

1 1——差值是0

2 3——差值是1
4 6——差值是2
5 8——差值是3
7 11——差值是4
9 14——差值是5
10 16——差值是6
12 19——差值是7
13 21——差值是8
15 24——差值是9
17 27——差值是10
18 29——差值是11

不难看出,差值是递增的,每个数刚好出现一次

每次求这样一对数时:

第一个数是之前没出现过的数的最小的那个
第二个数是第一个数+差值

然后判断输入的x和y是否出现在这些数对中。

证明

有一个棋盘

我们假设标为 1 是先手胜,标上 2 是后手胜
我们发现有两个凹进去的地方,自然都是 2
那么所有能到 2 的都是 1,
以此类推

那为什么一个数只能出现一次呢?

很明显横着和竖着都被覆盖了

那为什么差值是递增的呢?

图中标黄色的 1 ,把差值为 1 的覆盖了,差值只能为 2,下一次差值为 2 的又被覆盖了,差值只能为 3,以此类推

T4 最大利润

题面

描述

政府邀请了你在火车站开饭店,但不允许同时在两个相连接的火车站开。任意两个火车站有且只有一条路径,每个火车站最多有50个和它相连接的火车站。

告诉你每个火车站的利润,问你可以获得的最大利润为多少。
例如下图是火车站网络:

最佳投资方案是在1,2,5,6这4个火车站开饭店可以获得利润为90
输入

第一行输入整数N(<=100000),表示有N个火车站,分别用1,2。。。,N来编号。

接下来N行,每行一个整数表示每个站点的利润,接下来N-1行描述火车站网络,每行两个整数,表示相连接的两个站点。

输出

输出一个整数表示可以获得的最大利润。

样例输入

6

10
20
25
40
30
30
4 5
1 3
3 4
2 3
6 4

样例输出

90

题目大意

在一棵树上选点,会得到它的权值,单选了这个点就不能选它的儿子,问最大权值

总结 & 题解

双向建边开了一倍空间,70分飞了,应该细心检查。

应得:

实际:
树形 DP 模板题,和“没有上司的晚会”双倍经验。

完结

  1. 比赛时要学会打对拍数据,检验程序。(T1)
  2. 比赛前要有规划,这点做得还行(T2)
  3. 当别的题都做完了可以深入研究规律题,不要太肤浅(T3)
  4. 所有题都做完了要检查明显的错误如数组大小、输入输出格式(T4)


The End

转载地址:https://blog.csdn.net/KonjakuLAF/article/details/115714536 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:2020.10.17【普及组】模拟赛C组 总结
下一篇:c++ RMQ

发表评论

最新留言

路过按个爪印,很不错,赞一个!
[***.219.124.196]2024年04月04日 13时46分56秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章