写在前面
比赛地址：https://codeforces.com/contest/1875。
爱丽数码我真的好喜欢你啊为了你我要定制你的帆布包口牙！！！！
A
显然只会在剩余时间为 1 时使用工具，模拟即可。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
//=============================================================
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
//=============================================================
int main() {
//freopen("1.txt", "r", stdin);
int T = read();
while (T --) {
int a = read(), b = read(), n = read();
LL ans = 0;
for (int i = 1; i <= n; ++ i) {
ans += b - 1;
b = 1;
b += read();
b = std::min(b, a);
}
ans += b;
printf("%lld\n", ans);
}
return 0;
}
B
看到 \(k\) 这么大果断猜想若干次操作后一定会陷入某个拉扯的状态。
手玩下发现几轮操作后每次都是用自己手上的全局最小值换对面的全局最大值。
赛时懒得推具体几轮操作了，写了个暴力，出现上述情况后就可以直接判了。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 60;
const int kInf = 1e9 + 2077;
//=============================================================
int n, m, k, a[kN], b[kN];
int maxx, minx;
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
bool Judge(int now_) {
if (now_ % 2 == 1) {
return a[1] == minx && b[m] == maxx;
} else {
return b[1] == minx && a[n] == maxx;
}
}
//=============================================================
int main() {
//freopen("1.txt", "r", stdin);
int T = read();
while (T --) {
n = read(), m = read(), k = read();
maxx = -kInf, minx = kInf;
for (int i = 1; i <= n; ++ i) {
a[i] = read();
maxx = std::max(maxx, a[i]);
minx = std::min(minx, a[i]);
}
for (int i = 1; i <= m; ++ i) {
b[i] = read();
maxx = std::max(maxx, b[i]);
minx = std::min(minx, b[i]);
}
for (int i = 1; i <= k; ++ i) {
std::sort(a + 1, a + n + 1);
std::sort(b + 1, b + m + 1);
if (Judge(i)) {
int r = k - i + 1;
if (i % 2 == 1) {
if (r % 2 == 1) std::swap(a[1], b[m]);
} else {
if (r % 2 == 1) std::swap(b[1], a[n]);
}
break;
}
if (i % 2 == 1) {
if (a[1] < b[m]) std::swap(a[1], b[m]);
} else {
if (b[1] < a[n]) std::swap(b[1], a[n]);
}
}
LL sum = 0;
for (int i = 1; i <= n; ++ i) sum += a[i];
printf("%lld\n", sum);
}
return 0;
}
C
只能把林檎切成原来的 \(\frac{1}{2^k}\)，已知最后要全部拼成 \(\frac{n}{m}\) 的形式，则有解当且仅当 \(\frac{n}{m}\) 约分后分母为 \(2\) 的幂次。
显然拼起来的方案是唯一的，考虑每种大小的林檎块需要多少即可。于是考虑按照降序枚举林檎块的大小，将还未使用的所有林檎块都切成该大小，检查加上这些林檎块后能否恰好拼成 \(\frac{n}{m}\)，如果不能恰好拼成则减去所需的此大小的林檎块，再重复上述过程。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kInf = 1e9 + 2077;
//=============================================================
int n, m, tempn, tempm, g, flag;
std::map <int, int> mylog2;
LL ans;
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
int gcd(int x_, int y_) {
return y_ ? gcd(y_, x_ % y_) : x_;
}
LL Solve(int m_, int remain_) {
if (remain_ % m_ == 0) return 0;
LL ret = 1ll * remain_ * g;
remain_ *= 2;
return ret + Solve(m_, remain_ - remain_ / m_ * m_);
}
//=============================================================
int main() {
//freopen("1.txt", "r", stdin);
for (int i = 1, j = 0; i <= kInf; i <<= 1ll, ++ j) {
mylog2[i] = j;
}
int T = read();
while (T --) {
ans = flag = 0;
n = tempn = read(), m = tempm = read(), g = gcd(n, m);
tempn /= g, tempm /= g;
if (!mylog2.count(tempm)) {
printf("-1\n");
continue;
}
ans = Solve(tempm, tempn - tempn / tempm * tempm);
printf("%lld\n", ans);
}
return 0;
}
D
经过大力手玩可以发现下列显然结论：
- \(n\le 5000\)，则 \(\operatorname{mex} \le 5000\)。
- 删除后有贡献的数为 \(0\sim \operatorname{mex} - 1\)。
- 每次删除的数的权值是递减的，否则删除之后对 \(\operatorname{mex}\) 的减小没有贡献。
- 删除到某种权值时肯定是连续地把这一权值全部删完。
- 删完 0 之后代价也变为 0，相当于结束状态。
考虑删除权值直到把 0 删完的顺序，可以得到一个显然的 DP。设 \(f_{i}\) 表示恰好删到 \(\operatorname{mex}=i\) 时所需的最小代价，初始化 \(f_{\operatorname{mex}} = 0\)，考虑倒序枚举 \(f_{i}(0\le i\le \operatorname{mex})\) 即当前的 \(\operatorname{mex}\)，填表法更新 \(f_{j}(0\le j< i)\)（\(j\) 为当前正在删除的权值），预处理 \(\operatorname{cnt}_j\) 表示权值 \(j\) 的出现次数，则有转移 \(f_{j}\leftarrow f_{i} + (\operatorname{cnt}_j - 1) + j\)。
最终答案即为 \(f_{0}\)，总时间复杂度 \(O(n^2)\) 级别，可过。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 5010;
const LL kInf = 1e18 + 2077;
//=============================================================
int n, m, a[kN], cnt[kN];
LL f[kN];
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
void Solve() {
int mex = 0;
while (cnt[mex]) ++ mex;
for (int i = 0; i <= mex; ++ i) f[i] = kInf;
f[mex] = 0;
for (int i = mex; i >= 0; -- i) {
for (int j = i - 1; j >= 0; -- j) {
f[j] = std::min(f[j], f[i] + (cnt[j] - 1) * i + j);
}
}
printf("%lld\n", f[0]);
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
int T = read();
while (T --) {
n = read();
for (int i = 1; i <= n; ++ i) {
a[i] = read();
if (a[i] <= 5000) cnt[a[i]] ++;
}
Solve();
for (int i = 1; i <= n; ++ i) {
if (a[i] <= 5000) cnt[a[i]] = 0;
}
}
return 0;
}
E
咕咕
写在最后
学到了什么：
- B：进行轮数超多的过程定是有其独门绝技口牙！
- D：飞舞别惦记你那 b 贪心了，这 DP 都看不出来？