Codeforces Round 924 (Div. 2)
A - Rectangle Cutting
解题思路:
初始矩形长宽为\((a,b)\)，如果我们切\(a\),那么一定不能再拼接\(a\)，否则一定一样。所以我们拼接\(b\)，即将\(a\)对半分开得到两个\((\frac{a}{2},b)\)矩形拼接。
此时，如果\(\frac{a}{2} = b\)那么拼接出来的矩形和初始一样。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;
using piii = pair<ll, pair<ll, ll>>;
void solve()
{
int a, b;
cin >> a >> b;
if (a % 2 == 0 || b % 2 == 0)
{
if (a % 2 == 0)
{
if (b != a / 2)
{
puts("YES");
return;
}
}
if (b % 2 == 0)
{
if (a != b / 2)
{
puts("YES");
return;
}
}
puts("NO");
}
else
{
puts("NO");
}
}
int main()
{
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
B - Equalize
解题思路:
排序，如果一段非递减区间中最大值减最小值的差在\(n -1\)之内，那么区间中不同数的个数就是通过加一个排列能得到相同数的数量。
所以一个队列扫过去。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;
using piii = pair<ll, pair<ll, ll>>;
void solve()
{
int n;
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
sort(a.begin() + 1, a.end());
int ans = 0;
set<int> s;
deque<int> q;
for (int i = 1; i <= n; i++)
{
while (q.size() && a[i] - a[q.front()] >= n)
{
s.erase(a[q.front()]);
q.pop_front();
}
q.push_back(i);
s.insert(a[i]);
ans = max(ans, (int)s.size());
}
cout << ans << endl;
}
int main()
{
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
C - Physical Education Lesson
解题思路:
对于当前\(x\)有两种位置情况，一种是从\(1 \sim k\)时数到\(x\)，另一种是\(k - 1 \sim 2\)时数到\(x\)。
- 第一种：\(2k - 2= n - x = s\)
- 第二种：\(2k - 2 = n + (x - 2) = s\)。
我们对两种\(s\)分别枚举出其因子，然后求出\(k\)的个数即可。
代码：
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;
using piii = pair<ll, pair<ll, ll>>;
void solve()
{
int n, x;
cin >> n >> x;
int s = n - x;
vector<int> f;
for (int i = 2; i <= s / i; i++)
{
if (s % i == 0)
{
f.push_back(i);
if (s / i != i)
{
f.push_back(s / i);
}
}
}
f.push_back(s);
set<int> se;
for (auto v : f)
{
int t = (v + 2) / 2;
if (t != 1 && t >= x && t * 2 - 2 == v)
{
se.insert(t);
}
}
if (x > 1)
{
s = n + max(0, x - 2);
f.clear();
for (int i = 2; i <= s / i; i++)
{
if (s % i == 0)
{
f.push_back(i);
if (s / i != i)
{
f.push_back(s / i);
}
}
}
f.push_back(s);
for (auto v : f)
{
int t = (v + 2) / 2;
if (t > 1 && t >= x && t * 2 - 2 == v)
{
se.insert(t);
}
}
}
cout << se.size() << endl;
}
int main()
{
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
D - Lonely Mountain Dungeons
解题思路:
首先，根据\(\sum c_i \leq 2 \times 10^5\)，可以发现，我们可以枚举队伍的数量。最多有\(\sqrt{n}\)种不同的种族人数。
对于任意队伍数量\(i\)，我们发现，每个种族的人尽量平均地分到每个队伍中是最优的。
手算规律可以发现，对于每个种族人数\(v\)，给定要划分的队伍数\(i\)，平均划分得到的最大对数是可以\(O(1)\)计算得到的。
时间复杂度\(O(n log(2\times10^5))\)。种族数量的根号均摊\(+\) \(map\)的\(log\)查找，时间复杂度不一定对，但大概不会超过这个\(O(n \sqrt{n})\)。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using i128 = __int128_t;
using piii = pair<ll, pair<ll, ll>>;
ll qmi(ll a, ll b)
{
ll res = 1;
while (b)
{
if (b & 1)
{
res = res * a;
}
a = a * a;
b >>= 1;
}
return res;
}
void solve()
{
ll n, b, x;
cin >> n >> b >> x;
vector<ll> a(n + 1);
ll ma = 0;
map<ll, ll> cnt;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
ma = max(a[i], ma);
cnt[a[i]]++;
}
map<ll, ll> cost;
ll ans = 0;
for (int i = 1; i <= ma; i++)
{
ll sum = 0;
for (auto t : cnt)
{
ll x = t.fi / i;
ll y = t.fi % i;
ll res = (i - y) * (i - y - 1) / 2 * x * x;
if (y > 0)
{
res += y * (i - y) * x * (x + 1);
}
if (y > 1)
{
res += (y * (y - 1)) / 2 * (x + 1) * (x + 1);
}
if (res > cost[t.fi])
{
cost[t.fi] = res;
}
sum += t.se * cost[t.fi] * b;
}
sum -= (i - 1) * x;
ans = max(ans, sum);
}
cout << ans << endl;
}
int main()
{
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}