这样考虑,每次区间+1,对应差分数组a[i++],a[i+k]--。 那么当a[i]<0时连一条i->i+k的边,当a[i]>0连一条i-k->i的边。 整个数组被拆分成若干条有向链或者环(两点配对了),把数组变成全0(1和n+1位置除外)需要从每条链的起点开始处理,链中的点会受到前面点的影响。 可参考赛中代码(有点丑):https://ac.nowcoder.com/acm/contest/view-submission?submissionId=46825912
点赞 评论

相关推荐

牛客网
牛客网在线编程
牛客网题解
牛客企业服务