CFC.-Tokitsukaze-and-Two-Colorful-TapesC.-Where-is-the-Pizza
【CF】C. Tokitsukaze and Two Colorful Tapes+C. Where is the Pizza?
两道很像的的题目，都和环有关
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
于是总奉献为 22 + 24 - 12 - 32
同理左图也是，而左图中的3点可计算得到奉献为0
因为我们可以这样构造：
对于偶数环，我们考虑用最大值，最小值，次大值，次小值….
对于奇数环，我们和偶数环一样，但是我们最后要空一个不选，因为这个点的奉献为0，我们可以先给考虑其他环用，最后再来考虑（这里有贪心的想法）
那么到最后肯定是这样的形式 n2 + n-12 + n-32 … 0+0-0-0 … -32 - 22 - 12
我们可以发现对于任意一个环，其正奉献的个数和负奉献的元素一样，即都为[c/2]
其中c为
，C.Length为环的长度
那么根据我们的等差数列求和我们最后来化简一下答案
最后可以得到答案是 2*(nlen - lenlen)，即 2len(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" << endl
int 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" << endl
const 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;
}