每日一题~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];
}
和可能会超出 mod
sum %= 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;
}