Codeforces Round 975 (Div 2) A - C 题解

A

取最大值, 取的值的数量是固定的

对长度n为偶数的数组, 一定是 n / 2

对奇数, 如果取值在奇数位, 那么是(n + 1) / 2, 取值在偶数位则是n / 2, 因此能取奇数位取奇数位

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 200010;

int n, m, k, q, ans;

int a[N], f[N][2];

void solve()
{
cin >> n;
int maxx = 0;
int ans = n / 2;
for (int i = 1; i <= n; i ++ )
{
cin >> a[i];
maxx = max(a[i], maxx);

}

for(int i = 1; i <= n; i ++ )
{
if(a[i] == maxx && i % 2 == 1)
{
ans = (n + 1) / 2;
}
}


cout << maxx + ans << endl;
}

signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T = 1;
cin >> T;
while (T -- )
{
solve();
}
}

B

现在我们设第i 个点左面有b个线段端点, 右面有c个线段端点

如果这个点不是端点, 那么有b * c 个点经过它

如果是的话, 有b * c + b + c个点经过它(考虑它本身与其它端点相交)

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 200010;

int n, m, k, q, ans;

int a[N], b[N], c[N];

void solve()
{
cin >> n >> q;

for (int i = 1; i <= n; i ++ )
{
cin >> a[i];
}


map<int, int> mp;

for (int i = 1; i < n; i ++ )
{
mp[i * (n - i)] += a[i + 1] - a[i] - 1;
//cout << "i : " << i << " " << i * (n - i) << " " << mp[i * (n - i)] << "\n";
}

for(int i = 1; i <= n; i ++ )
{
mp[n - i + (i - 1) * (n - i + 1)] += 1;
}

for (int i = 1; i <= q; i ++ )
{
int k;
cin >> k;
cout << mp[k] << " ";
}
cout << "\n";
}

signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T = 1;
cin >> T;
while (T -- )
{
solve();
}
}

C

这道题比较思维

maxx 取同一种牌出现的最多的数目, sum 取总牌数

检查 i 可不可以作为一组deck的长度即可. 而检查只需要判断sum + i 是否大于maxx * i 和 (sum + i - 1) / i * i 这两者即可

这是因为如果分组, 那么至少分maxx组, 也至少分(sum + i - 1) / i 组

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 200010;

int n, m;
int a[N];

void solve()
{
cin >> n >> m;
int sum = 0, maxx = 0;
for(int i = 1; i <= n; i ++ )
{
cin >> a[i];
maxx = max(maxx, a[i]);
sum += a[i];
}

int ans = 1;

for(int i = 2; i <= n; i ++ )
{
int minn = max(maxx * i, (sum + i - 1) / i * i);
if(minn <= sum + m)
{
ans = max(i, ans);
}
}
cout << ans << "\n";
}

signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T = 1;
cin >> T;
while (T -- )
{
solve();
}
}

原文地址：https://blog.csdn.net/2301_81278039/article/details/142615522

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！