\(A.~ Hotelier\)
按题意模拟，开个桶判一下房间里有没有人，复杂度\(O(10n)\)
\(B.~Block Adventure\)
贪心，肯定背包里面的块尽可能多就比较好，所以每次在第i层时考虑把所有的都拿掉，然后看最少放出来多少个，如果全部放出来都不行说明无解。
复杂度\(O(n)\)
\(C.~Round Corridor\)
乍一看发现两个角度是固定的都是\(\dfrac{360}{n},\dfrac{360}{m}\)
于是问题就是你想求一下两个角度的\(lcm\)了，然后算多少个点会分一个块
分数求不出来，就给他们分别乘上一个\(nm\)
变成\(360m,360n\)的\(lcm\)再除以\(nm\)
这样会炸\(long ~long\)
我们继续化简，发现角度就是\(\dfrac{360* lcm(n,m)}{nm}\)
也就是\(360*\dfrac{nm/gcd(n,m)}{nm}\)
就是\(\dfrac{360}{\gcd(n,m)}\)
这个东西是个分数，用到\(double\)类型就不好了
单个的角度是\(\dfrac{360}{n}\)，所以块的个数就是\(\dfrac{360}{gcd(n,m)}/\dfrac{360}{n}\)（\(m\)类似）
也就是\(\dfrac{n}{\gcd(n,m)}\)，于是求一遍\(\gcd\)再做一下除法就好了
\(D~White Lines\)
我们发现行和列是单独的，所以分开处理，记\(line[i]\)为第\(i\)列是否可行。
接下来我们考虑枚举一个位置\((i,j)\)，计算以其为左上角的答案。
现在考虑列，可以发现这个矩形对其外面的列答案不会有影响。
所以未被其影响到的列的答案就是：
\[\sum_{l=1}^{i-1}line[l]+\sum_{r=i+k}^{n}line[r]\]
于是你发现对于其外面的部分我们就做一下\(line\)的前缀和就能\(O(1)\)得出答案了。
接下来考虑记一个函数\(f_{i,j}\)表示将\((i,j)\)至\((i,j+k-1)\)处全部染白后此列能否可行。
接下来我们考虑记白点为\(0\)，黑点为\(1\)。
那么\(f_{i,j}\)的计算就只要判一下\((i,1)\)至\((i,j-1)\)和\((i,j+k)\)至\((i,n)\)处是否有黑点即可。
显然我们可以对每一列记一个前缀和表示黑点的数量(这个前缀和的计算是\(n^2\)的)，然后\(O(1)\)计算\(f_{i,j}\)，于是计算\(f_{i,j}\)的复杂度也是\(O(n^2)\)
于是这个矩形影响到的列的答案就是：
\[\sum_{t=i}^{t=i+k-1}f_{t,j}\]
所以再对\(f_{i,j}\)做一个前缀和就可以将这一部分也变成\(O(1)\)的了，因为点对总数是\(n^2\)，总复杂度是\(O(n^2)\)
行同理。
\(E.~Compress Words\)
这道题也是非常毒了。。。
主要是题意，我猜应该有很多人和我一样以为是合并\(i\)和\(i-1\)吧
实际上题意是说每新读入一个新字符串就将其和已有的字符串合并。
\(Sol.\)
考虑每次新加入一个单词，我们可以枚举一个长度，判断其前缀和已有字符串的后缀是否相同。
这个相同用\(hash\)判就好了。
然后暴力算的话复杂度会带个\(\log\)，所以还要预处理一下每个数前面的系数的\(k\)次方在\(\%hash\)意义下是多少。
这样就是\(O(S)\)了
原文：https://www.cnblogs.com/Soulist/p/11656199.html