HNU: 小学期软件实训第二周（继续划水）

跟上周那道题很像吗，不过不是对每个单词反转，而是把整句反转，单词不反转

用栈解决即可

看起来其实就是每个字符串做标准化处理后统计，一顿 map 了事

这题实际上就是找只出现过一遍的名字，其它名字都是出现过两次的。

这里给两个方法：（我用的是第一种）

第一种是 map 存储，某个名字被录第一遍时存储，录第二遍的时候就删除（不是次数 + 1，不然后面找出来会超时），然后迭代器查 map（map 此时只存了答案）

第二种是对所有名字排序，然后查 i 和 i+1 是不是相同的（i 为偶数，从 0-(2n-4)），一直查到不是相同的。如果没查到就是 i=2n-2 的名字。

PS：用 cin 记得读入优化！

这题属实复杂，直接看我代码注释边理解吧。

这题其实在于每行的空格数不定，所以取出倒数第二个判断是不是 no 比较麻烦

没关系，问题不大，我们整行读入，然后切割完丢进栈里，然后取第二个嘿嘿嘿

剩下的统计就是小事啦！

纯模拟，每步换人走，可以写个递推

然后每步走完判断有没有到达终点、超出边界、跳格、打到另一个人

刚开始没注意到第一格要黑色，栽了。然后没想到直接暴力搜就行。。。

这里建议从大棋盘到小棋盘开始搜，搜到就能直接 break 了（搜索怎么搜？看注释！！！）

这题也老麻烦了。。。

第一个是查询时大小写不影响，也就是说读入时就要做标准化处理

第二个是得刚刚好长度的单词，比如 find 匹配不了 finding，所以就不能直接字符串 find 啦

直接看代码注释吧。。。

本来以为是贪心的，然后一想 aaaa，emmm 贪心不科学啊，按经验就是动态规划啦

知道是 dp 题后就简单了。老师放水说了一个一个加，那就很明显了

对于每个长度 l，都有初始 dp[l]=dp[l-1]+a

构建状态转移方程 dp[l] = min(dp[l], dp[mid]+b)(以 mid 为切割点切割长度为 l 的子串，右半是左半的子串时转移。(l+1)/2<=mid<l)

这题也是又臭又长，看起来很麻烦但写起来也还好（我刚开始跳了这题

这题直接看代码注释吧

这个提示我没看到，但其实无所谓，set 和 map 都自带排序，去重也无所谓，用 map 的话直接桶排序原理就是

水题一道，直接模拟过。。。

其实这题应该叫 “冰雹猜想”，也是纯模拟，一个 while 解决（能不写递归就不写递归）

显然这个数离最大值最小值的平均值越近越好，

所以我们考虑排序完直接 lower_bound，然后查左右（当然直接暴力一个一个查也行）

把两个数的约数和分别算出来比较就行。。。水题一道

当然要优化也是有的，只是打起来麻烦，就不写了

计算 i^2 和（i 和小于总天数），然后加上剩余天数 *(i+1) 就行

这题的数据量。。。字符串长度不大于 10，26 进制转化成 10 进制也不会爆 int。可以直接转换成 10 进制作加法，然后再转化回来就行

那如果要应对大数据？用高精度加法吧 (小学加法原理就是了)

具体可以看关于 C++ 高精度运算的几种方式

其实就是 0,3,5… 再倒回来到 1，分奇偶判断下就行

我们找一找 1 的位置，找规律绕圈出来就行

又是一道统计的水题。。。

这题和第九题相对比较有思考量一点

找出所有感染者的思路较难，所以我们反向寻找，找到安全的人的数目。

而安全的人有什么特点呢？

我们将安全的人分为两个部分：一部分人初始位置小于零号感染者；另一部分人初始位置大于零号感染者。

初始位置小于零号感染者的人要想不被感染，其速度只能小于等于右边所有人的最小速度。因为我们将零号感染者看做在右边。右边速度最小的那个人一定会被零号感染者感染。而左边人的速度要是大于这个最小速度，那么也会被感染。

所以初始位置大于零号感染者的人要想不被感染，其速度只能大于等于左边所有人的最大速度。

然后就是各种代码了。你可以像我一样，直接以上面的思路直接模拟

也可以以速度作为第一关键字，位置作为第二关键字排序，然后找第一个位置大于零号等于位置的编号和最后一个位置小于等于零号位置的编号，这两个编号之间的人（包括编号对应人的本身）就是感染者（为什么？自行理解）