每日一题~cf 970 div3 (A思维，B小模拟，C二分，D排列数建图成环，E 26个字母暴力+前缀和，F 逆元，G 数论gcd ）

本文主要是介绍每日一题~cf 970 div3 (A思维，B小模拟，C二分，D排列数建图成环，E 26个字母暴力+前缀和，F 逆元，G 数论gcd ），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A 题意：
有 a 个1 ,b 个2.问是否能将这些数划分为两个数值相等的集合。
输出 YES 或者 NO
——————
问题等价于 将数组 分成两个数值相同的数组。所以sum 应该是偶数。也就是说 1 的个数是偶数。在i1的个数是偶数的情况下，将 2 分成两份，如果2 的个数是偶数，OK。如果是奇数那么需要1来补齐，如果1 的个数大于等于2那么可以补齐。（1 的个数是偶数，需要2个1来补齐，剩下的1平均分即可）。
以上是人类智慧的做法。
当然我们可以看到 a b 非常小，所以也可以暴力枚举1 和2 的个数。
（我赛时这么做的^ _ ^）

void solve()
{int a,b;cin>>a>>b;if (a&1){cout<<"NO\n";return;}if (b&1){if (a==0){cout<<"NO\n";return;}}cout<<"YES\n";
}

B题意：
我也不知道为什么，赛时看不懂题…花了很长时间来理解题意。
看不懂题，赛时我是真急了。
给你一个字符串，问是否能组成一个外圈都是1，内里都是0 的方阵。（字符串是矩阵从上到下从左到右上的数字）
——————
模拟，判断就可以了。下边从1开始。第一行最后一行，如果index %n ==0或者是1 那么是最左列和最右列。（当且只有这些位置是1，就可以了）。
C二分，感觉这个没啥好说的。
D题意：
一个排列形成的图，只有若干个环
建图，会形成 若干个圈，因此 F(i) 等于 i 所在循环中的黑色元素个数。因此，我们可以写出 O(n) 中的所有循环，并记每个 i 所在循环中的黑色元素个数。
这样其实是对每一个圈遍历了两遍， 赛时写了依托，超时了。

#include <bits/stdc++.h>
using namespace std;
void solve()
{int n;cin>>n;vector<int>a(n+1);vector<bool>vis(n+1);vector<int>ans(n+1);for (int i=1;i<=n;i++){cin>>a[i];}string s;cin>>s;s=" "+s;// 保证每一个环 只 遍历 一遍for (int i=1;i<=n;i++){if (vis[i])continue;vis[i]=true;int cnt=s[i]=='0';int x=a[i];while(x!=i){if (s[x]=='0')cnt++;vis[x]=true;x=a[x];}ans[i]=cnt;x=a[i];while(x!=i){ans[x]=cnt;x=a[x];}}for (int i=1;i<=n;i++){cout<<ans[i]<<" ";}cout<<"\n";}
int main()
{std::cin.tie(nullptr)->sync_with_stdio(false);int t;cin>>t;while (t--){solve();}return 0;
}

E题意：
定义了一个 交替字符串 奇数位置上的字符形同，偶数位置上的字符相同，字符串长度为偶数。
有两种操作
1 删除一个字符（只能进行一次）
2 将一个字符替换为任意一个字符
问 最少的操作数
——————
只有长度为奇数的字符串才进行操作1.
假设字符串的长度为偶数，那么我们可以分别查看奇数和偶数位置上的字符。因此，如果我们将偶数位置上的所有字符都改为出现次数最多的字符，那么奇数位置上的字符也是如此。奇数位置上的字符也是如此。
分别处理奇数位置和偶数位置，长度减去出现次数最多的字符 出现的次数，就是答案。
长度为奇数的字符串
先删除一个字符，之后做法同上文长为偶数的字符串的做法。字符串长度是2e5我们可以枚举删除的位置，那么如何快速得到 mx1 mx0（奇数位置某个字符出现的最大次数，偶数位置）

因为字符串只有小写字母，也就是最多是26种。（状态很少，一般都可以暴力）

所以我们可以遍历26个字符，打擂台的方式获得mx1,mx0;
删除一个字符后，这个字符的个数是一个前缀和一个后缀的和。我们可以处理前缀和来获得。
删除一个字符之后，后面的位置奇偶性改变了。
偶数的情况好想，主要是 奇数 的情况，要意识到枚举，删除一个字母之后，后面的奇偶改变，只有小写字母，意味着只有26种情况，完全可以暴力枚举的。

#include <bits/stdc++.h>
using namespace std;
int read()
{int x = 0, f = 1;char ch = getchar();while (!isdigit(ch)){if (ch == '-')f = -1;ch = getchar();}while (isdigit(ch)){x = (x << 1) + (x << 3) + ch - '0';ch = getchar();}return x * f;
}
const int N = 2e5 + 5;
int cnt[N][26][2];
// 代表 到位置 i，某个字母的 数量
// 0 代表 偶数 的位置，1 代表奇数的位置
void solve()
{int n;cin >> n;string s;cin >> s;s = " " + s;// 处理前缀和for (int i = 1; i <= n; i++){for(int j=0;j<26;j++){cnt[i][j][1]=cnt[i-1][j][1];cnt[i][j][0]=cnt[i-1][j][0];}cnt[i][s[i] - 'a'][i & 1] ++;}if (n & 1){int ans=1e9;// 枚举 删除 每一个数 ，这个数 之后 的 位置的奇偶性发生变化for (int i=1;i<=n;i++){int mx1=0,mx0=0;for(int j=0;j<26;j++){mx1=max(mx1,cnt[i-1][j][1]+cnt[n][j][0]-cnt[i][j][0]);mx0=max(mx0,cnt[i-1][j][0]+cnt[n][j][1]-cnt[i][j][1]);}ans=min(ans,n-mx1-mx0);}cout<<ans<<"\n";}else{int mx1 = 0, mx0 = 0;for (int i = 1; i <= n; i++){for (int j = 0; j < 26; j++){mx1 = max(mx1, cnt[i][j][1]);mx0 = max(mx0, cnt[i][j][0]);}}int ans=n-mx1-mx0;cout<<ans<<"\n";}
}
int main()
{std::cin.tie(nullptr)->sync_with_stdio(false);int t;cin >> t;while (t--){solve();}return 0;
}

F题：
就是考个逆元，我一直wa，没处理好 负数的情况。没有好好计算 中间数 最大可能值。导致一直wa
一定要好好分析啊

#include <bits/stdc++.h>
using namespace std;
#define int long long
int read()
{int x = 0, f = 1;char ch = getchar();while (!isdigit(ch)){if (ch == '-')f = -1;ch = getchar();}while (isdigit(ch)){x = (x << 1) + (x << 3) + ch - '0';ch = getchar();}return x * f;
}
const int mod = 1e9 + 7;
int qpow(int a, int b)
{a %= mod;int ans = 1;while (b){if (b & 1){ans = ans * a % mod;}a = a * a % mod;b >>= 1;}return ans;
}
void solve()
{int n;cin >> n;vector<int> a(n);int sum = 0;for (int i = 0; i < n; i++){cin >> a[i];sum += a[i];}和可能会超出 modsum %= mod;int ans = 0;for (int i = 0; i < n-1; i++){sum -= a[i]; 这里可能会出现负值sum=(sum+mod)%mod;ans = ans + (a[i] * sum%mod) % mod;ans %= mod;}cout << ans * qpow((n * (n - 1) / 2 % mod), mod - 2) %mod<< "\n";
}
signed main()
{std::cin.tie(nullptr)->sync_with_stdio(false);int t;cin >> t;while (t--){solve();}return 0;
}

G题意：

题目看完之后 是一点思路都没有啊。

进行的操作就是 将 任意两个数中那个较大的数，变成两个数的和或者是两个数的差。
进行任意次操作，问最大的mexk是多少。
每个数只能变成 整个数组的gcd的整数倍。（这里可以这样理解，每个数都是 gcd的倍数，所以进行两两加法和减法，生成的元素。依旧有gcd这个因数）贪心的想，因为我们要最大化mex ，所以我们将每个数尽可能的变小。也就是让小的数尽可能的出现。
所以 我们操作之后的数组 是 0 gcd 2*gcd … (n-1)*gcd
当 gcd 为1的时候，这个数组中的元素可以是任何值。
赛后补题的时候，用错字母了，框框wa

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5;
int n, k, a[N];void solve()
{cin >> n >> k;int d = 0;for (int i = 1; i <= n; ++i){cin >> a[i];d = __gcd(d, a[i]);}if (n == 1){cout << (k <= a[1] ? k - 1 : k) << "\n";return;}if (d == 1){cout << n - 1 + k << "\n";return;}int t = (n - 1) * (d - 1);if (k > t){cout << (n - 1) * d + (k - t) << "\n";return;}int tt = k / (d - 1);int le = k % (d - 1);cout << (le == 0 ? tt * d - 1 : tt * d + le) << "\n";
}signed main()
{int T;cin >> T;while (T--)solve();return 0;
}

这篇关于每日一题~cf 970 div3 (A思维，B小模拟，C二分，D排列数建图成环，E 26个字母暴力+前缀和，F 逆元，G 数论gcd ）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---