3.29PDD笔试

做的有点累，感觉不是超级难对ACM选手肯定爆杀，鼠鼠拼尽力做出前两道，后两道不会一个图，一个dp大概是，只拿了0.25一共A了2.25/4。每次做这种题都有一种无力感。。。。做的就不想做了

1.5h AK交卷了前两题签到，后面两题大概 cf 1400 左右难度第三题：一开始以为是背包，后面看了下量级复杂度过不了，然后重新审题发现是求最大可取货物量，将物品数组从小到大排序，用 can[i] 表示以第 i 个物品为最小价值一个背包最多拿多少个物品。遍历一遍（双指针）初始化好 can 后，从右往左遍历 suf[i] 记录后缀最大 can 值，然后从左到右取最大 can[i]+suf[i+can[i]]，排序贪心复杂度 O(nlogn)第四题：一开始以为 dfs 序或者 topo 排序找一些性质，求最大回路（题意一开始不是很好懂），然后模拟一下可以发现，只有当前主路连向下一个主路的头尾的两个节点不重合时才能向右扩展合并，如果两个节点重合那就必须在这一层绕成圈和之前左边的主路合并，直接从左到右遍历，注意每一层都有两种取法——向右拓展和直接在当前层绕圈回去，复杂度 O(n)

出题人真疯了？？？？？笔试题又出数据结构，上次默写HLD这次默写主席树是吧？？？？t1贪心，t2dp，都算简单题吧，写的很顺。t3 求一个数组有多少子区间，使得区间端点和大于区间最大值，n1e5，值域1e6，262mb！！！！！！！考虑在笛卡尔树上做，那么就是在每个节点上求有多少跨越最大值的区间且区间端点的和大于最大值一个做法是考虑这个最大值把区间分成两部分，枚举小的那部分，设枚举到的为x，查询大的那部分有多少满足值大于max-x，这个显然可以直接上主席树做，枚举的复杂度于在笛卡尔树上枚举小的子树（其实不太等价，但是差不多就是这个意思），复杂度等于树上启发式合并，总体时间O(nlog^2),空间O(nlogn)然后坑点来了，首先上面那个枚举其实有一点conner case，不太好写，其次这个空间其实是开不下1e6的主席树的，你需要完全动态开点，初始树都不建来卡一下常，或者写离散化赛时被卡mle了，没调完。贵司是真的只招火箭毛毛虫高手吗？？？？upd：和队友聊了下，队友说可以先递归大子树，在再这个节点上做操作，这样就不需要做主席树的复杂操作了，可以直接上普通线段树/树状数组或者pbds::tree，不会mle

体感上来说比较简单1.签到题2.拓扑序找最长路，也比较签3.先排序。考虑枚举每个背包的最小物品，假设为i，那么可装进背包的物品数是一段以i开头的连续区间，设长度为pi。转化为选取两段不相交的子数组使加起来长度最大，树状数组维护前缀最大值即可4.有点麻烦，可行路径是从某个ai/bi出发，走到j，贯穿j的所有景点再回来，需要特判ai=bi的情况，做区间RMQ即可。(多测，然后对n的总数没限制，以为nlogn会T，结果就跑了2ms... 感觉数据水了)