当前位置：首页 > news >正文

【补题】Codeforces Round 789 (Div. 1)C. Tokitsukaze and Two Colorful Tapes

news 2025/5/18 5:18:27

题意：按顺序给两排色块，然后可以选择对这相同的色块中进行数字的分配，最后求按下标顺序上面位置的数字减下面位置的数字。
如果不懂，原题链接：Problem - 1677C - Codeforces

思路：

1.首先确实不难想到环，或者说类似于并查集的联通、关系等。样例给出的也很明显，不同色块的匹配最终都会以环的形式连接。并且环与环之间没有联系。

2.问题就是怎么样分配成最大，但其实具体的分配是我们不需要管的，我们只要知道无论怎么分配，在一个环中,单个点自身对于答案的贡献只能是+w或者-w，这是由绝对值决定的。通过整体的方式对相同色块的考虑

一种色块只能对答案造成-2w和+2w和0的贡献，那么从贪心考虑，让大的数字都贡献+2w一定比分配成0或者-2w好
且因为任何一个-2w的色块都会匹配上一个+2w的色块，所以+2w的色块的数量一定为环色块总数 $\left \lfloor \frac{sum}{2} \right \rfloor$ ，-2w也同理 $\left \lfloor \frac{sum}{2} \right \rfloor$ ，最后会有一个sum%2 的0贡献色块

综上记录每个环能最多选出的色块，借助求和公式，化简得到2*(n-k)*k

代码：参考题解 CF1677C 【Tokitsukaze and Two Colorful Tapes】 - 洛谷专栏

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define int128 __int128
#define endl '\n'
#define IOS                  \ios::sync_with_stdio(0); \cin.tie(0);              \cout.tie(0);
const int N = 2e5 + 10;
const int INF = 1e18;
const int MOD = 998244353;int fid(int x, vector<int> &f)
{if (x == f[x])return x;return f[x] = fid(f[x], f);
}void solve()
{int n;cin >> n;vector<int> col1(n + 2);vector<int> col2(n + 2);vector<int> f(n + 2);for (int i = 1; i <= n; i++){cin >> col1[i];f[i] = i;}for (int i = 1; i <= n; i++){cin >> col2[i];}for (int i = 1; i <= n; i++){int u = fid(col1[i], f);int v = fid(col2[i], f);if (u != v)f[u] = v;}vector<int> cont(n + 2);for (int i = 1; i <= n; i++){cont[fid(i, f)]++;}int ans = 0;int sum = 0;for (int i = 1; i <= n; i++){if (i == f[i])ans += cont[i] / 2, sum++;}cout << sum << endl;cout << 2 * ans * (n - ans) << endl;
}signed main()
{IOS;int t = 1;cin >> t;while (t--){solve();}
}

查看全文

http://www.xdnf.cn/news/145963.html