上大分，赢！
A
考虑将每一条对角线上可以存放的砝码数量都记录一下，从大到小排序，然后直接暴力贪心选择。
此时可以发现数量一定形如 \(n,n-1,n-1,n-2,n-2,n-3,n-3,\ldots,1,1\) 这样的形式。直接暴力减即可。
时间复杂度为 \(O(n)\)。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 500100;
int a[N];
signed main() {
int T;
scanf("%lld", &T);
while (T--) {
int n, k;
scanf("%lld%lld", &n, &k);
vector<int> v;
v.emplace_back(n);
for (int i = n - 1; i; --i) v.emplace_back(i), v.emplace_back(i);
int cnt = 0;
int i = 0;
while (k > 0) {
k -= v[i];
++cnt;
++i;
}
printf("%lld\n", cnt);
}
}
B2
B1 做法同 B2。
考虑枚举每一个值 \(i\)，计算出其可以选择的最大数目。然后再枚举每一个值 \(i+1\)，计算其在选择尽量多 \(i\) 的前提下最大的数目。
然后计算出这个最大的开销，令 \(i\) 值选择了 \(v_1\) 个，\(i+1\) 值还有 \(v_2\) 个没有选择。则可以最多带来 \(\min(v_1,v_2)\) 的收益。所以答案就是 \(\min(m,iv_1+(i+1)v_2+\min(v_1,v_2))\)。
开一个 map 计算出 \(v_1\) 和 \(v_2\) 的最大值即可。时间复杂度为 \(O(n\log n)\)。
还是这张图：
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 500100;
int a[N], b[N];
signed main() {
int T;
scanf("%lld", &T);
while (T--) {
int n, m;
scanf("%lld%lld", &n, &m);
for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
for (int i = 1; i <= n; ++i) scanf("%lld", &b[i]);
map<int, int> mp;
for (int i = 1; i <= n; ++i) mp[a[i]] += b[i];
sort(a + 1, a + n + 1);
int mx = 0;
for (int i = 1; i <= n; ++i) {
int key = 0;
int val = a[i];
int remain = mp[a[i]];
remain = min(remain, m / val);
int aix = remain;
key = a[i] * remain;
remain = mp[a[i] + 1];
remain = min(remain, (m - key) / (a[i] + 1));
key += (a[i] + 1) * remain;
remain = min(aix, mp[a[i] + 1] - remain);
key += remain;
if (key > m) key = m;
mx = max(mx, key);
}
printf("%lld\n", mx);
}
}
C
首先考虑一下弱化版 CF1883E 的做法。
每一次将一个数乘以 \(2\)，很快就会爆 long long 甚至 __uint128。因此考虑一些优美的性质：
- \(\log_2 2a_i=1+\log_2 a_i\)。
也就是说，可以考虑对于每一个 \(a_i\)，都对其取一次 \(\log_2\) 操作。这样一来，问题转化为：
- 给定一个序列 \(a\)，每一次可以将某一个元素 \(+1\)，问多少次操作之后序列单调不递减。
这个问题就可以直接贪心的模拟了。
然后考虑本题。本题要求的是对一个数平方。也考虑同样的转化方式：
- \(\log_2(a_i^2)=2\log_2a_i\)。
- \(\log_2(2\log_2a_i)=\log_2a_i+\log_22=\log_2a_i+1\)。
也就是说，\(\log_2(\log_2(a_i^2))=\log_2a_i+1\)。对于每一个元素 \(a_i\) 做两遍 \(\log_2\) 就得到的上面简化后的问题。
时间复杂度为 \(O(n)\)，注意要使用 long double 否则会被卡精度。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 500100;
int a[N];
long double b[N];
signed main() {
int T;
scanf("%lld", &T);
while (T--) {
int n;
scanf("%lld", &n);
for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
bool ok = 1;
for (int i = 2; i <= n; ++i) if (a[i] < a[i - 1]) ok = 0;
if (ok) printf("0\n");
else {
int pre = 0;
ok = 1;
for (int i = 1; i <= n; ++i) {
pre = max(pre, a[i]);
if (a[i] == 1) {
if (pre > 1) {
ok = 0;
break;
}
}
}
if (!ok) puts("-1");
else {
for (int i = 1; i <= n; ++i)
b[i] = log2l(log2l(a[i]));
int cnt = 0;
for (int i = 2; i <= n; ++i) {
if (b[i] < b[i - 1]) {
double qwq = b[i - 1] - b[i];
int kif = (int)ceill(qwq);
cnt += kif;
b[i] += kif;
}
}
printf("%lld\n", cnt);
}
}
}
}
D
考虑 dp。
设 \(f_i\) 表示不存在以集合 \(i\) 结尾的字符，是否是合法的。
那么显然有下列的初始条件：
- \(f_p=0\)，若 \(p\) 为子状态数为 \(1\)，且唯一一个子状态为字符串结尾字符。
- \(f_p=0\)，若 \(p\) 状态包含其中一个长度为 \(k\) 的子区间中所有的元素。
- \(f_p=1\)，若 \(p\) 状态同时不满足下列的条件。
但是这显然是错的。因此考虑 dp 更新答案。
按照顺序枚举集合 \(i\in [1,2^c)\)。则有对于任意的一个 \(j\) 满足 \(j\) 是集合 \(i\) 中的一个子元素，\(f_j=f_j\text{ AND }f_{j\oplus2^i}\)。
最终就是在所有满足 \(f_i=0\) 的元素中，找到状态中含有 \(0\) 数量最多的那一个状态就是答案。
时间复杂度为 \(O(c2^c+nc)\)。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 500100;
int a[N], box[N], f[N];
signed main() {
int T;
scanf("%lld", &T);
while (T--) {
int n, c, k;
scanf("%lld%lld%lld", &n, &c, &k);
string s; cin >> s;
for (int i = 0; i < c; ++i) box[i] = 0;
for (int i = 0; i < k; ++i) ++box[s[i] - 'A'];
for (int i = 0; i < (1ll << c); ++i) f[i] = 1;
f[(1ll << (s[n - 1]) - 'A')] = 0;
for (int l = 0, r = k - 1; r < n; ++l, ++r) {
int mask = 0;
for (int j = 0; j < c; ++j)
if (box[j]) mask |= (1ll << j);
f[mask] = 0;
if (r < n - 1)
--box[s[l] - 'A'], ++box[s[r + 1] - 'A'];
}
for (int i = 1; i < (1ll << c); ++i)
for (int j = 0; j < c; ++j)
if (i >> j & 1) f[i] &= f[i ^ (1ll << j)];
int mi = c;
for (int i = 1; i < (1ll << c); ++i)
if (f[i]) mi = min(mi, c - (int)__builtin_popcountll(i));
printf("%lld\n", mi);
}
}