HNU: 小学期软件实训第一周（其实就是刷简单的 CCF 模拟题）

很明显这题水分极高，排序都帮忙排好了。如果你想显得不是那么水的话，可以考虑直接一遍迭代

那如果想稳一点的话就随便用个桶排序原理再找最大即可。基于本题的数据量来讲 map 倒是不怎么需要用，开个 10000 大小的数组就行

桶排序原理：把数字看作桶的编号，然后遇到某个数字就往对应的桶 kv [i]++ 即可。

这题稍微转了个弯，其实就是 0-10 里面少了 3 和 9，即变成了 8 个数字就进 1

唉，这不就八进制嘛，简单！

那接下来就好办了，把这个看起来像十进制的八进制数变成正常的八进制数不就好了。也就是 4-7 都减去 1，9 则减去 2。然后进行一次八进制求十进制操作就是答案啦！

这题也是一道暴力的题，确定一下合适的天数就行啦。

首先确定下这两个星期几总共包含了几天，然后对这个得到的天数不断自增 7，看看有几次是在 L-R 里边

这边星期就可以用 map<string, int> 来减少代码量啦，可以直接星期对应数字，节约一点敲代码时间

从这题开始就有挺多要根据名字来查找信息的题目了。这边到下面都会用到一个技巧，用结构体数组来存取名字，然后用 map 来存储名字对应的下标，这样将名字和数组下标就构成了一个双向的对应表。

而除了这个就以下几个要点要搞定：

排序规则不能写错，确定一个队名是不是存过了之类的，至于净胜球这些细节样例说明已经很明显了，不懂就看代码吧。

学过栈 (stack) 的都知道，这是栈运用最最经典的题型了。

简单的说，就是遇到左括号就进栈，遇到右括号就判断一下栈顶元素，如果栈为空或者不是对应左括号就非法，否则出栈。

最后记得字符串都走完了要注意一下栈是否为空，最后是空的栈才能说明括号完全匹配，该括号串合法

这题的字符串切割我写复杂了，其实直接 find 一下就行。

其实这题和第四题大体上是一样的，不过这里需要注意的是排序。先按常规排序之后再对前 n/2 个队伍以名字为依据排序（不会吧不会吧，不会还有人不知道字符串可以直接比大小的吗）

跟第四，第六题一样，录名字，算分数，排序。不过这里有个小坑需要注意一下，这里的排名不止计算到第十名，也就是说排序比较同一排名次数时是得一直往下比直到比出结果的（这个坑了我一个点）

这题算是栽了，被前面的题目直接名字下标两两对应给套了进去 QAQ，然后想着记录下标完再排完排名赋值后再根据下标重排。。。然后改了结构体，然后数据读入出错，然后两小时白给～

这题其实是应该先排序再做两两对应处理，然后开始查询需要查询的 id 对应排名，找这个排名的上下界。如果上界在 m 后或者这人没地社保没交够还想白嫖直接 sorry；其它情况下如果上下界相等就是唯一解；如果下界在 m 前就是稳了，输出上下界；如果排名刚好卡在那就很难受，概率是（m-l+1)/(r-l+1)，按题目说的就不用约分啦。

另外这题还让我知道了，原来 lower_bound 和 upper_bound 也可以加 cmp 参数 QAQ

这题啊，二叉树的经典题。要解决也就只需要知道什么是前中后序遍历， 然后知道原理找找数据规律就有了

前中后序遍历使用递归做的，那求它当然是递归啦！

HNU-OS 可还行…… 这题实际上用一个长度为 m 的数组模拟就能过（可能是数据太小了，我写这题的时候构建了一个很极端的数据应该能让这种做法妥妥超时）

然后我感觉应该用单链表写这题（理论上来讲这题的最优解应该也是单链表），从来没写过单链表的我（只记得原理）硬生生搓了个单链表出来 A 了这题

所以这里我不讲暴力模拟的做法，来讲讲单链表的解法（这 21 道题对我来说意义最大的也是这题）

开始时我们可以把整个长度看作是一个长度为 m，未被占用的块，其 id（标识符）不记。对于每个块，无论它是否被使用，都记为单链表的一个节点；

然后康康它给的三个操作：

• alloc n —— 分配 n 个字节内存，返回已分配块的正整数标识符 x (x 初始值为 0，每次分配增长 1)

这个操作可以将以前已经清除掉且长度合适的空块重新分配。因为不一定是最后的那段。好在我们把未分配也看作成一个空块，与被释放内存的块无本质上的差别。
所以这个操作转化成，从头到尾查询第一个可以被插入的空块

• 1，假设这个合适的空块长度为 l
  于是乎这个空块不再是空块了，它就被占用了，长度变为了 n，有了自己的 id—— 标识符；那如果不是那么刚刚好分配，剩下了 l-n 呢？我们在这个块的后边插入一个长度为 l-n 的空块
• 2，如果没有合适的空块呢？
  那当然是返回 NULL 啊～

• erase x —— 删除标识符 x 所在的块

这个操作看起来像简单的修改单链表的一个节点的数据，这听起来很容易，然而：
如果这个块的前后是空块呢？如果我们不进行合并，那么加 alloc 操作时遇到了一堆连续的空块，把他们加起来可插入但又无法插入其中的第一个时（插入到后面的会导致顺序出错）就很难受了

• 所以在把这个块变成空块之后，要进行前后是否是空块的检验与合并
  记得变成空块不是只改个占用状态，还要清掉 id 哦！当然找不到标识符 x 所在的块时记得返回 ILLEGAL_ERASE_ARGUMENT

• defragment —— 整理空余内存碎片，将所有块尽量靠近内存的开始位置，并保持各自的顺序

这个操作很明显转换成了，删除单链表中所有的空块，记录长度和 l，然后在单链表最后插入一个长度为 l 的空块

这题里面单链表的时间复杂度和空间复杂度无疑是非常优秀的，在痛心疾首我为什么不先试试暴力的同时窃喜第一次用到了单链表。单链表考一堆细节逻辑操作，我能用单链表把它写出来就很高兴了。

emmm，水题，没什么好讲的，过吧。

这题就考察二进制转十进制罢了，不过为了偷懒就直接用了个函数__builtin_popcount，能把十进制数对应二进制的 1 的数量求出来

这题其实一开始的时候想的是二进制取或，但后来想想那个数据量。。。算了

讲讲思路吧：首先我们要对每一列求和，那么我们得到 m 个和；然后开始枚举哪个开关扔了，我们用这堆和分别减去它对应的 1，如果有一个值为 0 就说明不行，我们遍历下一个。

如果一次遍历每个值都不为 0，那么就说明这 n-1 个开关可以开 m 个灯，也就是 YES 啦。

当然你要骗分的话，输出一次 YES 提交康康对几个点，对的少就换 NO 提交一次，就一堆分到手啦！

这题显然 y 没有什么用处，记录一下 x 的正负个数，如果有哪一边小于等于 1 就有可删除的点啦

这题如果用 getline 的话记得关掉 cin/cout 的缓存（反正就是加速器，不然会有一个点超时），或者用 gets（这个我真忘了）

另外提一句，stringstream 真香 && reverse 真香

这个提示给的是真的是。。。我看到立马去查了下 string.find

这题之后也还有好几题涉及字符串和数字转换，知道 string.find 和它的用法这题就不剩什么难点了。

无序度这个东西应该叫逆序对吧（都是学过线代的人了）

求逆序对其实比较好的方法应该是归并排序，但这题计算量撑死 50 * 100 * 99 / 2，多大点事啊，暴力算了。。。

然后排序，没有然后了。。。

向量叉乘求面积算计算几何的常识了，不过我就纳闷了没化简前错一半，化简后全对？

这题用海伦公式这种进度贼差的公式都能全对， 这不就很奇怪了嘛。。。

我们把每种轮换都先打个表，然后对询问的数枚举倍数后与表中每一种轮换的值进行比对即可（这样做也不会有前导 0 的干扰）

（我不知道 stringtream 可以直接转换字符串和整型，我一直都是手写转换的）

另外这题我取巧了，当这个数的数位很大 (2 的 64 次方大概 19 位吧）时我直接判定为 no 了，毕竟数位太大 unsigned long long 也存不下

而数位大于 9 时说明这个数得乘上 10 以上的数，位数会 + 1，如果想保持本身位数不变必须有前导 0。前导 0 越多这个数越难可能是循环数，所以我就取巧了一波。

这题按部就班地模拟一遍即可

刚开始看错了题目好多次。。。

先算出前面几位对应的十进制后暴力枚举最后一位，然后就那样了。。。