2016 年山东省 ACM 省赛总结

• 大意就是某人一共需要背 N 个单词，一共有 M 天的时间让他背单词，问：他最多每天需要背多少个单词。简单的一个除法，不能整除的时候答案加一。

• 输入一行字符串，把其中的单词镜像翻转后输出，单词的前后顺序不改变。这道题是我用 getchar() 函数水过的。

• 给一个地图，地图上的某些点是"#"，有些点是"."，要求找出地图上只与一个"#"相邻的"."的个数。这道是队友 A 水过的。

• 一道关于斐波那契数列的题目，给一个 N，把 N 分解输出为 N=若干个斐波那契数的和 的形式（例如：10=8+2），如果不能分解输出-1;
• 要求：这若干个斐波那契数里面不能有相邻的，因为相邻的两个斐波那契数可以表示为一个更大的斐波那契数
• 这道题目我完全没有管，两个队友在讨论了一下之后，然后发现不难，就写了（我也不知道代码谁写的），然后就过了。

• 一道模拟 炉石传说 游戏的简单模拟题（我们队因为队友 B 玩过这个游戏，所以题目都没读完整，直接看了看规则然后就写完了;然后就过了。
• 规则有点复杂就不一一叙述了（其实是因为我根本就不知道，逃。。。）

• 背景设定是这样的：你的电脑是 0 号机，有 N 个代理服务器 (proxy), 他们被标为 1-N 号机 (label),要访问的网站是 N+1 号机。
• 第 i 号电脑可以与第 j 号电脑连接，连接会有一个时延 (time lag),用 w 表示;这样这 N+2 台电脑可以够成一个网络。
• 现在的要求是 在代理网络总能够选择一个延时最短的线路访问到第 N+2 号网站 ( 如果可以访问的到的话 ) 的条件下,你如何选择你的 0 号机要连接的代理服务器 (proxy) 使得时延最小 ( 如果有多个 proxy，连接它们都能达到最小的时延，连接标号 (label) 最小的那个 )。
• 这道题目在读完题目之后我和队友 A 一致认为是一个最短路问题，于是我掏出了 dijkstra 模板并将其输入到了电脑上，调试了一下然后交了，然后忘记考虑如果时延相同要选择标号最小的那个代理服务器的条件了。
• 然后我把选择标号最小的代码块加上去了，然后提交，发现还是不对，然后再次读题，然后发现不应该直接判断起点 0 的时延，而应该把所有 0 号机可以连接的 proxy 都考虑一遍，也就是说这里需要在 dijkstra 模板外面手写一个循环来判断。
• 然后这样修改了几次代码之后，不知道为什么我把选择标号最小的代码快给写错了（后来仔细反省发现一开始是写对了的，是因为某次调试删掉之后，后来又重新添加上去了之后，写错了）
• 错误的地方为：我把一个整型数组的数组名 (dis) 错写成了一个布尔数组名 (vis)，这个错误在编译器里面是不会有任何 warning 和 error 的。于是因此多花了一个多小时的时间在这个上面。

• 一道关于博弈论的题目，也是我们最后在比赛结束前 10 分钟的时候做出来的题目。说实话能做出这道题目来真的是很幸运的。
• 题目描述为：有三堆石子，有两个玩选石子游戏的人，每人每次只能从一个石子堆里面拿走至少一颗石子，谁最后把所有石堆拿空谁赢。
• 现在题目问：有多少种方案 把这 N 个石子分成三堆，在两人都按最优方案取走石子的条件下，保证后手获胜。 输入 N，输出方案数量。
• 这到题目的做题过程如下：
  • 首先，两个队友在看完题目后一直在想这个题目的解决办法，想了很久没想出来。
  • 后来队友 A 偶然间说了句“我记得博弈论跟异或有关”，于是他们开始找所有后手必胜态的三个数字之间的异或关系，发现三个数字如果异或到一起结果为 0 的时候，后手必胜。
  • 然后我就提出了一个意见，如果这三个数字异或到一起结果为 0,而且这三个数字加在一起和为 N 的话，那么对于 N 的二进制位是不是有一些特殊要求。
  • 然后队友 B 就打了一个表，打印了 N 和 N 的二进制位以及 N 对应的方案数目。然后就发现了规律，然后就在提交两次后过了 ( 第一次忘记考虑方案数为 0 的情况了）。

上面是这次比赛过了的题目情况，还有一道题目我不得不提一下，那就是本次比赛里面的 H 题

• 题目意思很简单：
  1. 首先会给一个定义命令，定义若干个字符数组，并分配一些空间。
  2. 然后碰到输入 (gets) 命令输入字符串，碰到输出 (cout) 命令输出字符串。
  3. 碰到返回 (return) 命令结束本次数据。
• 然后有一些条件：
  1. 分配的字符输出的空间是连在一起的，输入会造成数组间的内存溢出;例如 char a[5], b[5]; 这样定义的两个数组各自的长度为 5,总长度是 10,如果给 a 输入一个长度为 6 的数组，字符会溢出到 b 的空间里面去，会在字符串的最后添加一个'\0'作为结束标志。
  2. 但是输入造成的溢出不会影响到总长度之外的内存空间。例如还是上面的例子，现在给 a 输入一个长度为 11 的字符串，它会保留前 10 个字符，并不会在最后加'\0'作为结束标志，因为已经没有空间了。
  3. 输出的时候从定义时分配的内存开始输出，碰到'\0'或者超出内存空间总长度则结束。
• 这道题目的思路真的不难，真的不难，不难。但是就是做不出来，做不出来，做不出来。我还有什么话可说呢。