九月月赛题解

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

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，这时候如果不存在王炸和四炸，那么出牌者就胜利了，所以要先处理王炸和四炸这种前置条件。接下来统计出双方每种牌型的最大牌，分别比较，有一种出牌者比应牌者大即胜利，否则出牌者失败。做这类题一定要先理好思路，先判断哪种情况后判断哪种情况。判断顺序不同，题目的难度不同。