九月月赛题解

Markfound 2020-09-07 14:44:51 2020-09-07 16:17:06

先总结以下这次月赛暴露出来的比较严重的问题,有则改之无则加勉。

2.1.不写文件操作。如果你是根本不知道有这么一回事,那么没事,下次注意就好。如果你是忘了,那么就该打了。 如何避免:很多同学一开始都不写文件操作语句,只有在需要提交的时候再加上,这样就有可能会导致忘了加,这题白做。写代码前第一件事就是检查这次需不需要写文件操作,可以直接写,在与代码文件同目录下新建输入文件(如xiaoxue.in),把样例输进去即可。运行后在同目录下找输出文件(如xiaoxue.out)以文本形式打开查看即可。再有就是认真读题,写代码前第一件事就是确定这题需不需要文件操作。

2.题目看错。认真读题认真读题认真读题。不要误解出题人的意思,结合样例理解题目。

3.不过样例,不看解释。提交代码前一定要测试一下样例对不对,样例有解释也要看一下。

4.惧怕难题,有时间也不看完所有题目,觉得后面的题目我就是做不了。NO!不能拿100,1题偷鸡平均20分还是有很大可能的。能偷一点算一点,像这次比赛这种最容易被偷鸡的题目竟然还有很多人不偷鸡,太老实了。无脑输出Yes或者No拿一半分他不香吗?没必要空着。当然我相信是很多人题都没看。

5.编译错误。新手问题,提交前一定要编译成功并且样例通过。 以下是题解:

1.魔法幼儿园:

if...else...判断+输入输出。

典型错误:看错题并且没看样例直接原版输出、判断内容写错,"tql"写成"tpl"、不写或写错文件操作等等。

2.魔法小学:

偷鸡做法:直接输出Yes或者No。一半分到手。

正解:看数据范围,先快速幂,再素数判断(根号试除法即可),快速幂不会的话直接乘也能拿40分。

3.魔法初中:

题目说提取出数字即可,就不要再考虑前导零的问题了,如果有前导零而且要去掉会直接在题目中说的,此题数据没有前导零,所以你怎么处理前导零都不会错。关键语句if(n>='0'&&n<='9').

4.魔法高中:

同样的是注意数据范围,当然你实在不会做暴力求解也是可以拿一半分的。

正解:排序+二分查找。

思考方向:根据数据范围,考虑最大时间复杂度,想想脑子中这个时间复杂度的算法都有哪些可以解决的。有经验的同学表示一眼二分查找题。

5.魔法大学:

这题得分低过我的预期了,思维题。

先说用到的算法:简单并查集+....没了。

仔细读题,思维不够好的同学乖乖画图,不要空想。

仔细看样例2解释,非常重要的信息!

题目读明白后,可以先思考一下。一眼看出并查集的同学当我没说。

像这种题没有思路的时候,可以自己造数据,模拟一下解决的过程。

然后你会发现:对于所有第a行的被填过的点设为集合S,如果b行的某个点的与S中的某点同列,那么b行中的其他点就能在a行中对应的列生成点,这对于列也是一样的。那么这些行和列就能被看做为一个集合,最后封印阵被填满时就相当于行和列都合并成了一个集合。在两个没有交集的集合合并时,只需要添加一个点就能使得两个集合合并(同行或者同列的点,添加同行的点可以合并列,添加同列的点何以合并行),所以最后答案就是初始集合个数减一。

6.魔法研究生:

一道模拟题,暴力解决。

最重要的是找好模拟策略:牌型的判断顺序,把问题拆分成很多子问题。

一般是由最简单的情况入手:有人手中有王炸。到有人手中有相同的四张等等。

考察点:

1.考虑问题的全面性,会不会漏了某种情况。

2.代码能力,一大段的if...else..,200行起步的代码。

3.理清关系的能力,关系复杂,条件多。

解决方案:(仅供参考)

1.先判断能不能一次出光(相比来说比较好判断):是否刚好拥有每种牌型对应的数量,是的话可以一次性出光,否则进入下一步。

2.再判断能不能出一手,应牌者要不起:无非是相同牌型之间的大小判断,注意有两种特殊牌型,因为它们可以跨牌型出牌(王炸,四炸),先处理这两种。 比如说出牌者单张最大是9,应牌者单张最大是8,这时候如果不存在王炸和四炸,那么出牌者就胜利了,所以要先处理王炸和四炸这种前置条件。接下来统计出双方每种牌型的最大牌,分别比较,有一种出牌者比应牌者大即胜利,否则出牌者失败。 做这类题一定要先理好思路,先判断哪种情况后判断哪种情况。判断顺序不同,题目的难度不同。

恭喜以下

共 11 条回复

babyec

百人参赛,T5仅1人20分,其余全部0分,再创毒瘤辉煌[doge]

Jack_Kasluo

T5想法对了实在写调出来代码,吐了

Jack_Kasluo

实在调不出来代码,吐了

Leiyuxuan

并查集,图论题显然我会爆0(膜zre大佬,未来hk的ioi队长%%%,这次毒瘤的E题依旧吊打我们

Zelfan

苏中大佬牛啤

Leiyuxuan

T6没有顺子,差评(doge)

CrazyHeart

啊 什么 1004原来是二分搜索 我写了个超级偷懒的我也不知道怎么描述性质的东西 然后O(n)(似乎是?

Leiyuxuan

如果没想到二分的话显然树状数组维护维护区间最小值也是克星也是可行的qwq

Jack_Kasluo

T4二分对了但是输出白给,早知道把空格改换行就好了,吐了吐了,不得不说,题目本来不是很毒瘤,但是OI才是最毒瘤的

Markfound

这出的什么sb题目,前排diss出题人,过于简单(doge)

Jack_Kasluo

球T5代码,调了好久调不出来

AMAZE UI
Hello world!