8.13 愉快且排名新高的杭电8
1002-Breaking Down News
题意
给定长度为 $n$ 的数组 $a$ ,对于任意 $i$ 都有 $-1\leq a_i\leq 1$ 。想要将 $a$ 划分做若干块使得每块总和的 $sgn$ 和最大,每块的长度需要满足 $l\leq len\leq r$ 。
思路
由于 $dp_i$ 只能从 $dp_{i-r}-dp_{i-l}$ 转移过来,所以记录前缀和每次求区间最值。参考别人代码用 $multiset$ 和 $lowerbound$ ,怪好看的233
代码
1 |
|
1003-Clockwise or Counterclockwise
题意
给定在以原点为圆心的圆上三个点。问这三个点是顺时针还是逆时针。
思路
套了个求多边形面积的板子,判面积正负就过了。
代码
1 |
|
1006-Fluctuation Limit
题意
给定 $n$ 段限制,问能否找到可以满足每段限制的方案,方案之间差值最大为 $k$ 。
思路
因为不会 $dp$ 直接考虑贪心(确实不是 $dp$ )。求出每段满足题意的 $l$ 、$r$ ,最后倒推回去。
代码
1 |
|
1008-Hexacppn
题意
给定半径为 $n$ 的六边形网格图,可以任意选择起点,问不重复地走满全部网格且转弯最多的路径方案。
思路
团体智慧的聚集,小转画图,小庄造数据,小潘找规律写代码
分奇数和偶数进行分析
偶数时,直接从左上角开始从外到内的绕圈,最后会正好绕完
奇数时,可以视为前一个半径 $(r - 2)$ 的图外面再多绕一圈,绕法与偶数相同
写的时候就先把半径为 $3$ 和 $4$ 的结果写好,完事拿着前一个绕就行了,节省时间可以打个不同位置的表来绕
嗯,花花大法好
奇数情况:
1009-Isomorphic Strings
题意
给定串 $s$ ,问能否均等地划分成 $k$ 份,使得每份互为循环同构。
思路
备注:理论复杂度不低,但是很难卡满,$O(能过)$ ,甚至没到 $1s$
枚举每个因数,对每个因数 $check$ 。
求出第一块的哈希值,之后每块和第一块的对比。如果和第一块不同就枚举循环同构,递推求循环同构的哈希值,具体是 $(hash-a[pos_{now}]*bas[len-1])*seed+a[pos_{now}]$ 。找到就 $break$ ,所有循环同构都不满足就 $return$ 。
upd:wcy学号就是个除了吉利一无是处的花瓶(
代码
1 |
|
1011-Kidnapper’s Matching Problem
题意
给定长度分别为 $n$ 、$m$ 的 $a$ 、$b$ 数组,再给定数量为 $k$ 的集合 $S$ 。对于 $S$ ,定义 $2_{\oplus}^S$ 为 $S$ 所有子集的异或和集合。问有多少 $a$ 的长度为 $m$ 、起点为 $l$ 的连续子数组满足任意 $1\leq i\leq m$ 有 $a_{l+i-1}\oplus b_i \in 2_{\oplus}^S$ 。
思路
出题人:名字就暗示是 $kmp$ 了
求出线性基后将 $a$ 、$b$ 筛掉,剩下不能用线性基表示的部分仅当 $a$ 、$b$ 相等时可以消去,所以用剩下部分跑一遍 $kmp$ 求匹配数即可。
代码
1 |
|