【Fifty Project - D22】

5.1的记录忘了发了~

今日完成记录

《挪威的森林》

第五章，“我”收到了直子的回信，可以看出“我”确实还是很激动的，期待已久的。“只读罢开头几行，我便觉得周围的现实世界黯然失色了”，村上是真会写哇。直子说自己花费了很长时间调养，才渐渐可以拿笔表达，在疗养院生活得挺不错的，也表明了自己的态度，对“我”有一些歉意，觉得对“我”“有失公正”。最后还邀请“我”去疗养院见一面。七页信纸让“我”激动万分，何况还被邀请见面，收拾收拾就出发了。
第六章开了个开头，“我”一番周折来到疗养院，这个疗养院也是很神奇，从直子室友口中再次感觉到直子的过去应该很复杂，或者说是很痛苦。

Leetcode

每日一题

今天的每日一题是一个hard，一个之前写过的hard，当时自己也是想出来了，不过用了更笨的方法，然后看了题解学习了高效的做法，但是今天做又忘了高效做法，一点记不得，不过借助有序表做了一个介于高效和低效中间的实现。这怎么不算长进呢~

你可以安排的最多任务数：给定一个任务数组task（task[i]表示第i个任务的难度系数），一个工人数组 workers（workers[i]表示每个工人的能力），只有能力大于等于难度才能完成该任务，还给了pills个大力药丸，吃完大力药丸能力值直接上升strength，当然了大力药丸有副作用，每个工人最多吃一个。每个工人只能干一个任务。现在问你最多能完成几个任务。
思路：首先排个序，挑能力强的工人以及好做的任务（难度系数低的），观察数据范围，n是100000，应该是一个nlogn的解法，加上任务数也有二值性（忘了是不是叫二值性了，还是叫二分性？）（能完成2个肯定就能完成1个，不能完成3个肯定就不能完成4个），考虑用二分做，接下来就是处理check函数的实现了。判断是否能完成k个任务，肯定挑难度系数最低的k个任务以及工作能力最强的k个工人，直接暴力匹配，当工作能力匹配不上，就直接吃药，能力够了就匹配下一个，没有药或者能力依旧不够那说明干不了这事。提交一发发现WA了，因为没有最大化工人的能力，吃药的时候不能直接吃，应该找到最小满足要求的工人吃药，这样可以保留这些能力相对大的工人。我就想了用有序表（TreeMap）去每次匹配满足task[i] - strength的能力最小的工人，这个操作就是logn了，所以跑起来慢了点。题解的最优解是每次都用dq存储所有吃药或者不吃药都能完成该任务的工人，如果队头不吃药就能完成那就直接对头出队，不吃药；如果队头不吃药搞不定，那么队列中所有人不吃药都搞不定，就挑那个队尾的吃药能搞定且能力值最垃圾的去吃药。效率杠杠的。

0x3f题单

等值距离和：给定一个数组，要求计算这个数组每个元素的等值距离和，即对于元素arr[i]，遍历数组所有元素arr[j]，只要arr[i] == arr[j]，那么res[i] += |j - i|。要求计算出各个元素的等值距离和。
思路：用哈希表将所有等值元素下标分别入队，每次处理一个队列。用前后缀和可以快速计算队列中某个元素与所有其他元素的绝对距离和，由于顺序遍历，下标依次增大，所以队列中均为递增项，如下图，节点1、3、6、10、19就是其中的一个列表，图示计算节点6和其他节点的等值距离和，可见等值距离和由两部分组成，左侧部分可以用前缀和计算，右侧部分可以用后缀和计算。

如下是前缀和图示，后缀和也类似实现，实现前后缀和后即可快速计算当前点的等值距离和。（我的方法要算两个和数组，大佬们还有更快的直接计算一个和即可，有兴趣可以去leetcode题解翻一下，太牛辣）

构建回文串检测：给定一个字符串s，以及n次询问，每次询问包括l, r, cnt，问从s[l]到s[r]，至多替换cnt个字符为任意字符组成的新字符串再重新排列组合能否构成回文串。也就是这个字串最多换掉cnt个字符以后，所有字符能否构成回文串。
思路：这个有一点作弊嫌疑了，因为题单写的这个题属于前缀异或和，所以我就一直往这个方向想，不然真想不出来。从最简单的开始，如何判断一些字符能否构成回文串，当然就是判断他们之中是不是至多只有一个字符出现次数为奇数。这个性质就很异或。但是题目还给出了可以更换cnt个字符这个条件，也就是说应该是判断至多有cnt * 2 + 1个字符出现次数为奇数，因为改变cnt个就可以消除cnt * 2个奇数项。到这里我们应该想一个办法快速判断是否一个字串中的字符至多只有cnt*2 + 1个字符出现次数为奇数。我们用一个标志存储每个字符出现次数的奇偶性（异或，出现一次标志位为1，出现两次标志位为2，奇数次为1，偶数次为2），一个int变量有32位，于是用其中26位保存这26个字母的出现状态，然后对原字符串直接计算前缀异或数组，pre[i] 存储的就是前i位的出现情况。这样一来比对pre[i]和pre[j]有多少位不同，那就说明有多少个字符在这个字串中出现次数位奇数。

异或前缀这个思路真的好神奇，从来没想过，果然没有想象力的人还得多刷题