【CF】C. Tokitsukaze and Two Colorful Tapes+C. Where is the Pizza?

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" << 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;
}