9.8总结-拓冰企业网站定制

整体总结：

1.部分分仍是一个大问题在部分分的情况下容易写炸

2.以后尽量把最后1h的时间全分配给打暴力时间少了容易写炸或者写不完

3.少用unordered_map这东西太慢了 OJ的机子能把这种写法卡炸尽量使用gp_hash_table 常数小时间复杂度非均摊所以不容易被卡

4.以后一定要在本地自己造大数据跑要确保不会超时如果感觉很悬可以评估一下评测机的性能再适度卡常

在草稿本上推导了一下发现是个dp 写了个转移拿unordered_map维护了一下就过了我原本的状态设计和题解是一样的但是被大样例卡了后面多记录了一个数组才过好像我是唯一一个设dp_{i,0/1/2}的

这种题目很容易想到可以二分考虑如何check 我们把图画出来就可以发现其实建出来的是一个内向基环树森林考虑经典套路将环上的每一个节点为根的树统计分讨一下其实只有两种情况直接讨论+指针优化查找可以做到 \(O((n+m)log2(m))\)

赛时打了三个性质挂了两个只拿到了最简单的一个性质一个无解判错一个实现有问题要加强部分分

我们考虑对于原序列的最大子段和和取出区间的子段和讨论一下先不考虑最大子段和唯一的情况显然是简单的直接拿最大子段和减去子段和即可
再考虑唯一的情况需要在序列上进行分讨直接线段树维护区间子段和即可

赛时没看懂题其实自己画一下样例的矩阵就很好理解了直接分析性质得到输出2得五分

分析完后需要许多群论知识来推导（