3.28测试总结

--------------------------------------------------------
SuperOjP1581~1583
 
--------------------------------------------------------
T1:
设第一个输入的值是这个串的颜色,第二个输入的值为ai
发现两个数如果颜色相同,那么他们的距离就是|ai-aj|,否则就是n-|ai+aj|
然后排序来让数字有序来去掉绝对值
然后大讨论一下
--------------------------------------------------------
T2:
有一种可以AC的错误算法(数据太水了)
分治,每次先不考虑k的限制,找一个这样的跨过了mid的最长的子串
然后处理这个子串,如果他已经满足了k的限制,那么就更新一下答案,否则删掉最大(或者最小,都删会T,但是只删一个的话,时间复杂度就可以保证是n*log*log的,而且随机数据正确率很高,事实证明可以跑过所有数据)的位置,把原序列分成两节,递归的搞
 
标算:
首先,不难发现一个序列[l,r]满足条件的条件是对d同余且(max{al..ar}-min{al..ar})/d+1-r+l-1<=k
枚举一个l,维护一个w[r]表示(max{al..ar}-min{al..ar})/d+1-r+l-1,因此只需在区间中询问最右边的小于等于k的数,线段树即可
然后维护w[r],可以用维护两个单调队列来搞
--------------------------------------------------------
T3:
还不会...
--------------------------------------------------------