题面https://codeforces.com/contest/2266/problem/D题解https://www.luogu.com.cn/article/pk0sh4ce思路Code:voidsolve(){intn;cinn;vectorinta(n1,0);for(inti1;in;i){cina[i];a[i]-i;}sort(a.begin()1,a.end());a.erase(unique(a.begin()1,a.end()),a.end());na.size();// for(int i1;in;i)couta[i] ;// cout\n;//把下标处理对intt1;intans0;for(inti1;in;i){if(i1na[i]1a[i1])t;else{ansmax(ans,t);t1;}}ansmax(ans,t);coutans\n;return;}Conclusion循环移位这个套路在竞赛里出现频率极高因为它有一个非常强大的性质任意多个循环移位组合起来可以得到任意排列。也就是说一旦你发现某个操作等价于“把一段循环移位”你就可以认为这些元素可以随便重排问题立刻简化成“只看元素的值不看位置”。为什么循环移位这么常见因为很多操作的本质就是“把某个东西挪到前面其他往后挤”。比如把最后一个元素移到最前面把区间[i, j]整体旋转把某个数插到前面其他后移。这些操作在减去下标或加上下标之后往往就变成了纯粹的循环移位。循环移位的两个关键性质一个长度为 L 的循环移位可以拆成若干次相邻交换所以它能生成这个区间内的所有排列。不同区间的循环移位组合起来可以生成整个序列的任意排列只要区间能覆盖所有元素。所以一旦你证明“操作 循环移位”你就可以直接说这些元素可以任意重排。常见信号看到以下关键词就要警惕是不是循环移位操作里出现1、-1、-(j-i)这类与下标差有关的项操作把最后一个元素搬到前面其他元素往后挪操作后某个“差值”序列只是被重新排列了。这时候试着定义一个b_i a_i - i或b_i a_i i看看操作是不是变成了b的循环移位。总结循环移位之所以常见是因为它把“位置变化”和“值变化”解耦了原操作同时改变值和位置很乱减掉下标后位置变化被抵消只剩下值的重排而重排意味着我们可以忽略位置只关心值的集合。所以以后看到“操作后某些差值只是换了位置”就可以直接反应循环移位 → 可任意重排 → 只看值。这个直觉一旦建立很多题都会变得简单。
题面https://codeforces.com/contest/2266/problem/D题解https://www.luogu.com.cn/article/pk0sh4ce思路Code:voidsolve(){intn;cinn;vectorinta(n1,0);for(inti1;in;i){cina[i];a[i]-i;}sort(a.begin()1,a.end());a.erase(unique(a.begin()1,a.end()),a.end());na.size();// for(int i1;in;i)couta[i] ;// cout\n;//把下标处理对intt1;intans0;for(inti1;in;i){if(i1na[i]1a[i1])t;else{ansmax(ans,t);t1;}}ansmax(ans,t);coutans\n;return;}Conclusion循环移位这个套路在竞赛里出现频率极高因为它有一个非常强大的性质任意多个循环移位组合起来可以得到任意排列。也就是说一旦你发现某个操作等价于“把一段循环移位”你就可以认为这些元素可以随便重排问题立刻简化成“只看元素的值不看位置”。为什么循环移位这么常见因为很多操作的本质就是“把某个东西挪到前面其他往后挤”。比如把最后一个元素移到最前面把区间[i, j]整体旋转把某个数插到前面其他后移。这些操作在减去下标或加上下标之后往往就变成了纯粹的循环移位。循环移位的两个关键性质一个长度为 L 的循环移位可以拆成若干次相邻交换所以它能生成这个区间内的所有排列。不同区间的循环移位组合起来可以生成整个序列的任意排列只要区间能覆盖所有元素。所以一旦你证明“操作 循环移位”你就可以直接说这些元素可以任意重排。常见信号看到以下关键词就要警惕是不是循环移位操作里出现1、-1、-(j-i)这类与下标差有关的项操作把最后一个元素搬到前面其他元素往后挪操作后某个“差值”序列只是被重新排列了。这时候试着定义一个b_i a_i - i或b_i a_i i看看操作是不是变成了b的循环移位。总结循环移位之所以常见是因为它把“位置变化”和“值变化”解耦了原操作同时改变值和位置很乱减掉下标后位置变化被抵消只剩下值的重排而重排意味着我们可以忽略位置只关心值的集合。所以以后看到“操作后某些差值只是换了位置”就可以直接反应循环移位 → 可任意重排 → 只看值。这个直觉一旦建立很多题都会变得简单。
