[luoguP1053] 篝火晚会（贪心 + 乱搞）

传送门

假设第一个位置是1，那么枚举它的左右两边是谁，有两种情况，然后可以递推求出序列。

然后可以贪心，两个序列有多少个不同的数，答案就是多少，具体为啥，yy一下即可

然后就是判断递推求出的序列和目标序列最少有多少个不同，也就是最大有多少个相同

因为是环，得破环为链，然后再判断的话是 n^2 的，显然超时。

另一个思路，就是不用破环为链，随便找一个节点为起点

看看每个位置的数到目标位置向左移的距离x，f[x]++

如果两个数到目标位置的距离相同，那么选其中一个数到目标位置后，另一个数也能到目标位置，多个数同理

这样我们就找最大的f[x]即可，nf[x]为答案

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define N 60001using namespace std;int n, ans;int f[N], a[N], X[N], Y[N];inline int read()inline void work()else a[i + 1] = a[i  1] ^ X[a[i]] ^ Y[a[i]];if(a[n] != X[1] || a[n  1] ^ X[a[n]] ^ Y[a[n]] ^ a[1])for(i = 1; i <= n; i++)f[((i  a[i]) % n + n) % n]++;for(i = 0; i < n; i++)ans = max(ans, f[i]);}int main()work();swap(X[1], Y[1]);work();printf("%d\n", n  ans);return 0;}

上一篇：[luoguP3172] [CQOI2015]选数（递推+容斥原理）

下一篇：[luoguP2219] [HAOI2007]修筑绿化带（单调队列）