2025.1.12——1200
Q1. 1200
You are given a sequence \(a\), consisting of \(n\) integers, where the \(i\)-th element of the sequence is equal to \(a_i\). You are also given two integers \(x\) and \(y\) (\(x \le y\)).
A pair of integers \((i, j)\) is considered interesting if the following conditions are met:
- \(1 <= i < j <= n\);
- if you simultaneously remove the elements at positions \(i\) and \(j\) from the sequence \(a\), the sum of the remaining elements is at least \(x\) and at most \(y\).
Your task is to determine the number of interesting pairs of integers for the given sequence \(a\).
Input
- The first line contains three integers \(n, x, y\) (\(3 \le n \le 2 \cdot 10^5\), \(1 \le x \le y \le 2 \cdot 10^{14}\));
- The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^{9}\)).
Q2. 1200
Vasya has two hobbies — adding permutations\(^{\dagger}\) to arrays and finding the most frequently occurring element. Recently, he found an array \(a\) and decided to find out the maximum number of elements equal to the same number in the array \(a\) that he can obtain after adding some permutation to the array \(a\).
More formally, Vasya must choose exactly one permutation \(p_1, p_2, p_3, \ldots, p_n\) of length \(n\), and then change the elements of the array \(a\) according to the rule \(a_i := a_i + p_i\). After that, Vasya counts how many times each number occurs in the array \(a\) and takes the maximum of these values. You need to determine the maximum value he can obtain.
\(^{\dagger}\)A permutation of length \(n\) is an array consisting of \(n\) distinct integers from \(1\) to \(n\) in arbitrary order. For example, \([2,3,1,5,4]\) is a permutation, but \([1,2,2]\) is not a permutation (\(2\) appears twice in the array), and \([1,3,4]\) is also not a permutation (\(n=3\) but there is \(4\) in the array).
Input
The first line of each test case contains a single integer \(n\) (\(1 \le n \le 2 \cdot 10^5\)) — the length of the array \(a\).
The second line of each test case contains \(n\) integers \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 10^9\)) — the elements of the array \(a\).
Q3. 1200
Jay managed to create a problem of difficulty \(x\) and decided to make it the second problem for Codeforces Round #921.
But Yash fears that this problem will make the contest highly unbalanced, and the coordinator will reject it. So, he decided to break it up into a problemset of \(n\) sub-problems such that the difficulties of all the sub-problems are a positive integer and their sum is equal to \(x\).
The coordinator, Aleksey, defines the balance of a problemset as the GCD of the difficulties of all sub-problems in the problemset.
Find the maximum balance that Yash can achieve if he chooses the difficulties of the sub-problems optimally.
Input
Each test case contains a single line of input containing two integers \(x\) (\(1\leq x\leq 10^8\)) and \(n\) (\(1\leq n\leq x\)).
------------------------独自思考分割线------------------------
-
观察+数论
A1.
- 优化:排序后对于每个数二分找两侧边界。
- 有点细节
A2.
- 发现性质:最后选择的数上下界差小于 \(n\)。
- 排序后二分找到最多的数。
A3.
- 从答案 \(v\) 开始考虑,每个数必然是 \(v\) 的倍数,\(x\) 亦为 \(v\) 的倍数,则 \(v\) 必然为 \(x\) 的因子,对于每个因子若能够分为至少 \(n\) 份,则可以作为答案。
------------------------代码分割线------------------------
A1.
#include <bits/stdc++.h>
#define int long long //
#define endl '\n' // 交互/调试 关
using namespace std;
#define bug(BUG) cout << "bug:# " << (BUG) << endl
#define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl
#define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl
void _();
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cout << fixed << setprecision(6);
int T = 1;
cin >> T;
while (T--)
_();
return 0;
}
void _()
{
int n, x, y;
cin >> n >> x >> y;
vector<int> a(n + 2);
int sum = 0;
for (int i = 1; i <= n; i++)
cin >> a[i], sum += a[i];
sort(a.begin() + 1, a.end() - 1, [](int &e1, int &e2)
{ return e1 > e2; });
int res = 0;
for (int i = 1; i <= n; i++)
{
int s = sum - a[i];
int l = 0, r = n + 1;
while (r - l - 1)
{
int mid = l + r >> 1;
if (s - a[mid] >= x)
r = mid;
else
l = mid;
}
int d = r;
l = 0, r = n + 1;
while (r - l - 1)
{
int mid = l + r >> 1;
if (s - a[mid] <= y)
l = mid;
else
r = mid;
}
int u = l;
// bug2(d, u);
if (d <= u)
res += u - d + 1 - (i >= d && i <= u);
}
cout << res / 2 << endl;
}
A2.
#include <bits/stdc++.h>
#define int long long //
#define endl '\n' // 交互/调试 关
using namespace std;
#define bug(BUG) cout << "bug:# " << (BUG) << endl
#define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl
#define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl
void _();
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cout << fixed << setprecision(6);
int T = 1;
cin >> T;
while (T--)
_();
return 0;
}
void _()
{
int n;
cin >> n;
map<int, int> has;
for (int i = 1; i <= n; i++)
{
int x;
cin >> x;
has[x] = 1;
}
vector<int> a(1, 0);
for (auto [x, c] : has)
a.push_back(x);
int _n = has.size();
int res = 1;
for (int i = 1; i <= _n; i++)
{
int l = i, r = _n + 1;
while (r - l - 1)
{
int mid = l + r >> 1;
if (a[mid] - a[i] < n)
l = mid;
else
r = mid;
res = max(res, l - i + 1);
}
}
// for (auto v : a)
// cout << v << ' ';
// cout << endl;
cout << res << endl;
}
A3.
#include <bits/stdc++.h>
#define int long long //
#define endl '\n' // 交互/调试 关
using namespace std;
#define bug(BUG) cout << "bug:# " << (BUG) << endl
#define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl
#define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl
void _();
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cout << fixed << setprecision(6);
int T = 1;
cin >> T;
while (T--)
_();
return 0;
}
void _()
{
int x, n;
cin >> x >> n;
int res = 1;
vector<int> t;
for (int i = 2; i <= x / i; i++)
if (x % i == 0)
{
t.push_back(i);
if (x / i - i)
t.push_back(x / i);
}
t.push_back(x);
for (auto v : t)
if (x / v >= n)
res = max(res, v);
cout << res << endl;
}
标签:integers,le,2025.1,int,1200,mid,12,array,define From: https://www.cnblogs.com/jkkk/p/18671427