目录
写在前面
比赛地址：https://codeforces.com/contest/1928。
终于把欠下的一堆题补上了呃呃
天使骚骚共通线什么构式呃呃，一周目就想走老师线直通单身笑死我了。
A
签到。
发现等分后重新拼接可以得到 \(\frac{x}{2}\times 2y\) 与 \(\frac{y}{2}\times 2x\) 的两个矩形，检查它们是否与 \(x\times y\) 或 \(y\times x\) 相同即可。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define mp std::make_pair
#define pii std::pair<int,int>
#define LL long long
//=============================================================
//=============================================================
//=============================================================
int main() {
//freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
int T; std::cin >> T;
while (T --) {
int x, y; std::cin >> x >> y;
std::map <pii, int> m;
m[mp(x, y)] = 1, m[mp(y, x)] = 1;
int flag = 0;
if (x % 2 == 0) {
if (m[mp(x / 2, 2 * y)] == 0) flag = 1;
}
if (y % 2 == 0) {
if (m[mp(2 * x, y / 2)] == 0) flag = 1;
}
if (flag) std::cout << "YES\n";
else std::cout << "NO\n";
/*
x, y
y, x
x/2, 2y
y/2, 2x
*/
}
return 0;
}
B
知识点：双指针。
显然重复元素只会贡献一次，于是先去重。
然后考虑对于元素 \(b_1<b_2<\cdots<b_k\)，若它们加排列中元素后能够相等，则一定有 \(b_1 + n\ge b_k + 1\)，即 \(b_k - b_1\le n - 1\)。排序后双指针求最大的满足条件的区间即可。
//知识点：双指针
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
//=============================================================
//=============================================================
//=============================================================
int main() {
//freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
int T; std::cin >> T;
while (T --) {
int n; std::cin >> n;
std::map <int, int> m;
std::vector <int> v;
for (int i = 1; i <= n; ++ i) {
int x; std::cin >> x;
if (m.count(x)) continue;
m[x] = 1;
v.push_back(x);
}
std::sort(v.begin(), v.end());
int l = 0, r = 0;
while (r < v.size() && v[r] + 1 <= v[l] + n) ++ r;
-- r;
int ans = r - l + 1;
while (l < v.size()) {
++ l;
while (r < v.size() && v[r] + 1 <= v[l] + n) ++ r;
-- r;
ans = std::max(ans, r - l + 1);
}
std::cout << ans << "\n";
}
return 0;
}
C
知识点：数学
纯粹的数学题。
首先当 \(k< x\) 或 \(k\ge n\) 时显然不满足题意。
对于一满足题意的 \(k(k\ge x)\)，数列中 1 的位置可表示为 \(1 + y\times (2k-2) (y\ge 0)\)，则 \(x\) 的位置可表示为 \(1 + (y - 1)\times (2k-2) + (x - 1) (y\ge 1)\) 与 \(1 + y\times (2k-2) - (x - 1) (y\ge 1)\)，讨论一下：
-
若 \(n = 1 + (y - 1)\times (2k-2) + (x - 1) (y\ge 1)\)，则有：
\[2(k - 1)(y-1) = n - x \]于是考虑枚举 \(n-x\) 的所有因数 \(d=2\times (k-1)\) 解得 \(k=\frac{d}{2} + 1\)，若满足 \(x\le \frac{d}{2} + 1<n\) 且为整数则找到了一个解。
-
若 \(n = 1 + y\times (2k-2) - (x - 1) (y\ge 1)\)，则有：
\[2(k-1)y = n + x - 2 \]同理枚举 \(n+x-2\) 的所有因数求 \(k\) 的解即可。
总时间复杂度 \(O\left(t\sqrt{n+x}\right)\) 级别。
//知识点：数学
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
//=============================================================
//=============================================================
void Solve() {
LL x, n; std::cin >> n >> x;
LL d1 = n - x, d2 = n + x - 2;
LL ans = 0;
std::map <LL, bool> m;
if (d1 > 0) {
for (LL i = 1; i * i <= d1; ++ i) {
if (d1 % i != 0) continue;
if (!m.count(i) && (i % 2 == 0) && (i / 2 + 1 < n) && (i / 2 + 1 >= x)) {
ans ++, m[i] = 1;
}
if (!m.count(d1 / i) && ((d1 / i) % 2 == 0) && ((d1 / i) / 2 + 1 < n) && ((d1 / i) / 2 + 1 >= x)) {
ans ++, m[d1 / i] = 1;
}
}
}
if (d2 > 0) {
for (LL i = 1; i * i <= d2; ++ i) {
if (d2 % i != 0) continue;
if (!m.count(i) && i % 2 == 0 && (i / 2 + 1 < n) && (i / 2 + 1 >= x)) {
ans ++, m[i] = 1;
}
if (!m.count(d2 / i) && ((d2 / i) % 2 == 0) && ((d2 / i) / 2 + 1 < n) && ((d2 / i) / 2 + 1 >= x)) {
ans ++, m[d2 / i] = 1;
}
}
}
std::cout << ans << "\n";
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
int T; std::cin >> T;
while (T --) {
Solve();
}
return 0;
}
/*
1
10 1
5
10 1
10 2
10 3
10 4
10 5
1 2 1 2 1 2 1 2 1 2
1 2 3 2 1 2 3 2 1 2
1 2 3 4 3 2 1 2 3 4
1 2 3 4 5 4 3 2 1 2
1 2 3 4 5 6 5 4 3 2
1 2 3 4 5 6 7 6 5 4
1 2 3 4 5 6 7 8 7 6
1 2 3 4 5 6 7 8 9 8
*/
D
知识点：三分
位于不同小组的同一种族的两个体才会产生贡献，则当小组数 \(k\) 确定时，对于每个种族最优的分配方案是将所有个体均分到 \(k\) 个小组中。则此时若某种族有 \(c\) 个个体，则有 \(r = c\bmod k\) 个小组有 \(\left\lfloor\frac{c}{k}\right\rfloor + 1\) 个个体，其他 \(k-r\) 个小组有 \(\left\lfloor\frac{c}{k}\right\rfloor\) 个个体，贡献即为：
\[f= r \left(\left\lfloor\frac{c}{k}\right\rfloor + 1\right) \left(c - \left\lfloor\frac{c}{k}\right\rfloor - 1\right) \times b + (k - r) \left\lfloor\frac{c}{k}\right\rfloor \left(c - \left\lfloor\frac{c}{k}\right\rfloor\right)\times b \]则最终的总贡献值为：
\[g = \sum_{i=1}^{n} f_i - (k-1)\times x \]观察多项式 \(g\) 的形式显然总贡献 \(g\) 是关于小组数量 \(k\) 的单峰函数，三分求函数极值点即可。
总时间复杂度 \(O(n\log_{3}\max\{c_i\})\) 级别。
//知识点：三分
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 2e5 + 10;
const int kInf = 1e9 + 2077;
//=============================================================
int n, b, x, c[kN];
//=============================================================
LL Check(LL mid_) {
LL ret = -1ll * (mid_ - 1) * x, d = 0;
for (int i = 1; i <= n; ++ i) {
LL k = c[i] / mid_, r = c[i] % mid_;
d += 1ll * (mid_ - r) * k * (c[i] - k) * b;
d += 1ll * r * (k + 1) * (c[i] - k - 1) * b;
}
return ret + d / 2ll;
}
void Solve() {
std::cin >> n >> b >> x;
for (int i = 1; i <= n; ++ i) std::cin >> c[i];
std::sort(c + 1, c + n + 1);
LL ans = 0;
int l = 1, r = 2 * c[n];
for (; l < r; ) {
int mid1 = l + (r - l) / 3, mid2 = r - (r - l) / 3;;
LL ret1 = Check(mid1), ret2 = Check(mid2);
ans = std::max(ans, std::max(ret1, ret2));
if (ret1 < ret2) {
l = mid1 + 1;
} else {
r = mid2 - 1;
}
}
ans = std::max(ans, std::max(Check(l), Check(r)));
std::cout << ans << "\n";
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
int T; std::cin >> T;
while (T --) {
Solve();
}
return 0;
}
E
知识点：DP，构造
赛时没想到能 DP 预处理，恼弹一个。
首先所有位置均有 \(x\bmod y\) 的贡献，先令 \(s\) 与所有位置减去 \(n\times (x\bmod y)\)。此时所有位置均为 \(y\) 的倍数，若有解则 \(s\) 一定也为 \(y\) 的倍数，于是再令 \(s\) 与所有位置除以 \(y\)，则此时要构造的数列形态为：
\[\frac{x - x\bmod y}{y}, \frac{x - x\bmod y}{y} + 1, \cdots, 0, 1, 2, \cdots, 0, 1, 2, \cdots \]数列合法当且仅当数列之和为 \(s\)。
考虑枚举第一段 \(\frac{x - x\bmod y}{y}, \frac{x - x\bmod y}{y} + 1, \cdots\) 的长度 \(i\) 并检查使用剩下的位置 \(i+1\sim n\) 构造若干 \(0, 1, \cdots\) 能否凑出 \(s - \sum_{1\le j\le i} a_j\)。
上述检查对象可以 DP 预处理。具体地，记 \(f_{i}\) 表示凑出 \(i\) 最少需要多少个位置，初始化 \(f_{0}=0, \forall 1\le i\le s,\ f_i = \infin\)。转移时对于每个 \(i\) 枚举向后添加一段和为 \(j\) 长度为 \(k\) 的 \(0, 1, \cdots\)，则有：
\[f_{i} + k\rightarrow f_{i+j} (i+j\le s) \]注意为了输出方案还需要记录转移前驱。
转移过程中限制了 \(i+j\le s\)，而 \(j\) 的值是关于 \(k\) 的二次函数，则有 \(1\le j\le \sqrt{s}\) 成立，则上述 DP 时间复杂度为 \(O\left(s\sqrt{s}\right)\) 级别。
预处理后按照上述思路枚举第一段 \(\frac{x - x\bmod y}{y}, \frac{x - x\bmod y}{y} + 1, \cdots\) 的长度 \(i\)，再检查 \(f_{s - \sum_{1\le j\le i} a_j} \le n - i\) 是否成立即可。若成立则找到一组合法构造，令前 \(i\) 个位置为枚举的第一段，\([i + 1, i + f_{s - \sum_{1\le j\le i} a_j}]\) 为预处理的答案，剩余位置补 0，然后乘 \(y\) 加 \(x\bmod y\) 还原即可。
枚举的第一段长度最大为 \(O\left(\sqrt{s}\right)\) 级别，则总时间复杂度 \(O\left(s\sqrt{s} + n\right)\) 级别。
注意 \(f\) 不需要每组数据都进行预处理。
没开 LL WA 了发，警醒！
//知识点：DP，构造
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 2e5 + 10;
const int kInf = 1e9 + 2077;
//=============================================================
int n, x, y;
LL s;
int f[kN], from[kN], g[kN];
std::vector <int> ans;
//=============================================================
void DP(int lim_) {
f[0] = 0;
for (int i = 1; i <= lim_; ++ i) f[i] = kInf;
for (int i = 0; i <= lim_; ++ i) {
for (int j = 1, k = 1; i + j <= lim_; ++ k, j += k) {
if (f[i] + k + 1 < f[i + j]) {
f[i + j] = f[i] + k + 1;
g[i + j] = k + 1;
from[i + j] = i;
}
}
}
}
void Solve() {
std::cin >> n >> x >> y >> s;
s -= 1ll * n * (x % y);
if (s < 0 || s % y != 0) {
std::cout << "NO\n";
return ;
}
int r = x % y;
x = (x - r) / y, s /= y;
ans.clear();
ans.push_back(x);
LL s1 = x;
for (int i = 1; i <= n; ++ i) {
if (s1 > s) break;
if (f[s - s1] <= n - i) {
std::cout << "YES\n";
for (int j = s - s1; j; j = from[j]) {
for (int k = 1; k <= g[j]; ++ k) {
ans.push_back(k - 1);
}
}
while ((int) ans.size() < n) ans.push_back(0);
for (auto j: ans) std::cout << r + j * y << " ";
std::cout << "\n";
return;
}
ans.push_back(x + i);
s1 += x + i;
}
std::cout << "NO\n";
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
int T; std::cin >> T;
DP(kN - 10);
while (T --) Solve();
return 0;
}
/*
1
1 1 2 1
*/
F
gugugu~
写在最后
学到了什么：
- D：若可将贡献写成多项式形式，观察性质。
- E：DP 预处理构造方案，开
LL。