https://codeforces.com/contest/1677/problem/C
https://codeforces.com/contest/1670/problem/C
两道很像的的题目，都和环有关
C. Tokitsukaze and Two Colorful Tapes
题目：
思路：
题意就是给定你两排颜色，要求在相同的颜色填相同的数字，最后让 最大
对于此类两排排列的问题，我们可以想到是否和环有关，观察发现，这两排数字其实可以构成k个环，对于例一有：
1 5 4 3 2 6
5 3 1 4 6 2
环①：1->5->3->4->1 长度为4
环②：2->6->2 长度为2
那么对于环上任意一个数，假设为h[i]，那么它的奉献就为 abs(h[i+1] - h[i]) + abs(h[i] - h[i-1])
可以发现，对于任意一个数，它只有以下几种情况
①.奉献为2*x
②.奉献为-2*x
③.奉献为0
用图表示就是
①②如右图所示
对于2点，有奉献p = 2 - 1 + 2 - 3 = 2*2 - 1 - 3
对于4点，有奉献p = 4 - 3 + 4 - 1 = 2*4 - 1 - 3
于是总奉献为 2*2 + 2*4 - 1*2 - 3*2
同理左图也是，而左图中的3点可计算得到奉献为0
因为我们可以这样构造：
对于偶数环，我们考虑用最大值，最小值，次大值，次小值....
对于奇数环，我们和偶数环一样，但是我们最后要空一个不选，因为这个点的奉献为0，我们可以先给考虑其他环用，最后再来考虑（这里有贪心的想法）
那么到最后肯定是这样的形式 n*2 + n-1*2 + n-3*2 ... 0+0-0-0 ... -3*2 - 2*2 - 1*2
我们可以发现对于任意一个环，其正奉献的个数和负奉献的元素一样，即都为[c/2]
其中c为，C.Length为环的长度
那么根据我们的等差数列求和我们最后来化简一下答案
最后可以得到答案是 2*(n*len - len*len)，即2*len*(n-len)
代码：
#include <iostream>
#include <algorithm>
#include<cstring>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <memory>
using namespace std;
#define ll long long
#define yes cout << "YES" << endl
#define no cout << "NO" << endlint vis[100005];
int a[100005];
int b[100005];
int posina[100005];ll getLen(int x)
{if (vis[x]){return 0;}vis[x] = 1;return 1LL + getLen(posina[b[x]]);
}void solve()
{memset(vis, 0, sizeof vis);int n;cin >> n;for (int i = 1; i <= n; i++){cin >> a[i];posina[a[i]] = i;}for (int i = 1; i <= n; i++){cin >> b[i];}ll len = 0;for (int i = 1; i <= n; i++){if (!vis[i]){len += getLen(i) / 2LL;}}cout << 2L * len * (n - len) << endl;
}int main()
{cin.tie(0)->sync_with_stdio(false);int t = 1;cin >> t;while (t--){solve();}return 0;
}C. Where is the Pizza?
题目：
思路：
我们观察发现，其实又是两个排列，而且也是可以构成环的，在这道题中我们只是多了一个约束条件，即d[i]，其作用是锁定了环的某个元素
为什么可以看出构成环呢？可以看到，对于任意一个数，它的位置只有两种选择，如果对于一个位置确定好了一个数，那么这个位置的另一个数的位置肯定也确定好了，以此类推，到最后肯定会形成一个环
进一步观察发现（其实是打表），我们可以知道，对于任意一个长度大于一的环，无论如何都只能有两种选法，同时如果这个环只要有一个被锁定了，那么就只能有一种选法
所以这道题我们只需要寻找环，如果这个环没有被锁定，且长度大于1，那么就将结果乘2
代码：
#include <iostream>
#include <algorithm>
#include<cstring>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <memory>
using namespace std;
#define ll long long
#define yes cout << "YES" << endl
#define no cout << "NO" << endlconst int MOD = 1e9 + 7;
int a[100005];
int b[100005];
int d[100005];
int posina[100005];
int flag = 0;
ll getlen(int x)
{if (!a[x]){return 0;}a[x] = 0;if (d[x] != 0){flag = 1;}return 1 + getlen(posina[b[x]]);
}void solve()
{int n;cin >> n;for (int i = 1; i <= n; i++){cin >> a[i];posina[a[i]] = i;} for (int i = 1; i <= n; i++){cin >> b[i];}for (int i = 1; i <= n; i++){cin >> d[i];}ll ans = 1;for (int i = 1; i <= n; i++){if (a[i]){flag = 0;if (getlen(i) > 1 && !flag){ans = ans * 2 % MOD;}}}cout << ans << endl;
}int main()
{cin.tie(0)->sync_with_stdio(false);int t = 1;cin >> t;while (t--){solve();}return 0;
}
