3.28测试总结
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
--------------------------------------------------------
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:
还不会...
--------------------------------------------------------
评论 (0)
