A
核心思路:这题的第一反应是直接统计a所有的0的数目和b所有的0的数目,然后两式相减。但是我们会发现一个问题,因为有些是可能不需要排序的,所有还有记录下a和b所有不同的个数的数目,再判断与我们之前的那个是不是相等的.
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e7 + 10;
int a[N], b[N];
int ca[2], cb[2];
void solve()
{
int n;
cin >> n;
int cnt = 0;
memset(ca, 0, sizeof ca);
memset(cb, 0, sizeof cb);
for (int i = 0;i < n;i++)
{
cin >> a[i];
ca[a[i]]++;
}
for (int i = 0;i < n;i++)
{
cin >> b[i];
cb[b[i]]++;
cnt += (a[i] != b[i]);
}
if (cnt == abs(ca[0] - cb[0]))
cout << cnt << endl;
else
cout << abs(ca[0] - cb[0]) + 1 << endl;
}
int main()
{
int t;
cin >> t;
while (t--)
{
solve();
}
}
B
核心思路:这就是一个经典的构造题了,我们需要使用b数组通过最大公约数来构造a数组。那换而言之我们是不是可用a数组通过最大公倍数构造出b数组呢。答案是肯定的。唯一需要注意的是b[0]和b[n]的值.
#include<bits/stdc++.h>
using namespace std;
#define IOS std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
const int N = 1e6 + 10;
int a[N], b[N];
int gcd(int a, int b)
{
return b ? gcd(b,a%b) : a;
}
void solve()
{
int n;
cin >> n;
for (int i = 0;i < n;i++)
cin >> a[i];
b[0] = a[0];
b[n] = a[n - 1];
for (int i = 1;i < n;i++)
{
b[i] = a[i] * a[i - 1] / gcd(a[i], a[i - 1]);
}
for (int i = 0;i < n;i++)
{
if (a[i] != gcd(b[i], b[i + 1]))
{
cout << "NO" << endl;
return;
}
}
cout << "YES"<<endl;
}
int main()
{
IOS;
int t;
cin >> t;
while (t--)
{
solve();
}
}
C
核心思路:这就是一个滑动窗口的问题。但是有个特别需要注意我们选中的数组下标和我们看的是不一样的,这个可以看样例2。他最后是会把\(l\sim r,映射为0\sim r-l\),这也是为什么我们可以使用滑动窗口的大小来进行判断。
#include<bits/stdc++.h>
using namespace std;
#define IOS std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
typedef long long LL;
const int N = 1e6 + 10;
int a[N], b[N];
void solve()
{
queue<int> q;
int n;
cin >> n;
LL ans = 0;
for (int i = 0;i < n;i++)
{
int x;
cin >> x;
while (x <= q.size())q.pop();//因为我们插入这个元素之后他的size又需要加1所以需要取等号
q.push(x);
ans += q.size();
}
cout << ans << endl;
}
int main()
{
IOS;
int t;
cin >> t;
while (t--)
{
solve();
}
}
没办法,D题的题目都看不懂,没办法补出来了
标签:int,cb,ca,Codeforces,cin,++,solve,825,Div From: https://www.cnblogs.com/xyh-hnust666/p/16927850.html