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

A

取最大值, 取的值的数量是固定的
对长度n为偶数的数组, 一定是 n / 2
对奇数, 假如取值在奇数位, 那么是(n + 1) / 2, 取值在偶数位则是n / 2, 因此能取奇数位取奇数位

1. #include <bits/stdc++.h>
2. #define int long long
4. using namespace std;
6. const int N = 200010;
8. int n, m, k, q, ans;
10. int a[N], f[N][2];
12. void solve()
13. {
14.         cin >> n;
15.         int maxx = 0;
16.         int ans = n / 2;
17.         for (int i = 1; i <= n; i ++ )
18.         {
19.                 cin >> a[i];
20.                 maxx = max(a[i], maxx);
21.                
22.         }
23.        
24.         for        (int i = 1; i <= n; i ++ )
25.         {
26.                 if(a[i] == maxx && i % 2 == 1)
27.                 {
28.                         ans = (n + 1) / 2;
29.                 }
30.         }
31.        
32.        
33.         cout << maxx + ans << endl;
34. }
36. signed main()
37. {
38.         ios::sync_with_stdio(false);
39.         cin.tie(0);
40.         cout.tie(0);
41.         int T = 1;
42.         cin >> T;
43.         while (T -- )
44.         {
45.                 solve();
46.         }
47. }

复制代码

B

如今我们设第i 个点左面有b个线段端点, 右面有c个线段端点
假如这个点不是端点, 那么有b * c 个点经过它
假如是的话, 有b * c + b + c个点经过它(考虑它本身与其它端点相交)

1. #include <bits/stdc++.h>
2. #define int long long
4. using namespace std;
6. const int N = 200010;
8. int n, m, k, q, ans;
10. int a[N], b[N], c[N];
12. void solve()
13. {
14.         cin >> n >> q;
15.        
16.         for (int i = 1; i <= n; i ++ )
17.         {
18.                 cin >> a[i];
19.         }
20.        
21.        
22.         map<int, int> mp;
23.        
24.         for (int i = 1; i < n; i ++ )
25.         {
26.                 mp[i * (n - i)] += a[i + 1] - a[i] - 1;
27. //                cout << "i : " << i << " " << i * (n - i) << " " << mp[i * (n - i)] << "\n";
28.         }
29.        
30.         for        (int i = 1; i <= n; i ++ )
31.         {
32.                 mp[n - i + (i - 1) * (n - i + 1)] += 1;
33.         }
34.        
35.         for (int i = 1; i <= q; i ++ )
36.         {
37.                 int k;
38.                 cin >> k;
39.                 cout << mp[k] << " ";
40.         }
41.         cout << "\n";
42. }
44. signed main()
45. {
46.         ios::sync_with_stdio(false);
47.         cin.tie(0);
48.         cout.tie(0);
49.         int T = 1;
50.         cin >> T;
51.         while (T -- )
52.         {
53.                 solve();
54.         }
55. }

复制代码

C

这道题比较头脑
maxx 取同一种牌出现的最多的数目, sum 取总牌数
检查 i 可不可以作为一组deck的长度即可. 而检查只必要判断sum + i 是否大于maxx * i 和 (sum + i - 1) / i * i 这两者即可
这是由于假如分组, 那么至少分maxx组, 也至少分(sum + i - 1) / i 组

1. #include <bits/stdc++.h>
2. #define int long long
3. using namespace std;
5. const int N = 200010;
7. int n, m;
8. int a[N];
10. void solve()
11. {
12.         cin >> n >> m;
13.         int sum = 0, maxx = 0;
14.         for(int i = 1; i <= n; i ++ )
15.         {
16.                 cin >> a[i];
17.                 maxx = max(maxx, a[i]);
18.                 sum += a[i];
19.         }
20.        
21.         int ans = 1;
22.        
23.         for(int i = 2; i <= n; i ++ )
24.         {
25.                 int minn = max(maxx * i, (sum + i - 1) / i * i);
26.                 if(minn <= sum + m)
27.                 {
28.                         ans = max(i, ans);
29.                 }
30.         }
31.         cout << ans << "\n";
32. }
34. signed main()
35. {
36.         ios::sync_with_stdio(false);
37.         cin.tie(0);
38.         cout.tie(0);
39.         int T = 1;
40.         cin >> T;
41.         while (T -- )
42.         {
43.                 solve();
44.         }
45. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。