CodeCraft-21 and Codeforces Round 711 (Div. 2)
A. GCD Sum
题意
定义 \(gcdSum(x)=gcd(x,sum\ of\ digits\ of\ x)\)。
请你输出最小的 \(x\) 满足 \(x\ge n\),且 \(gcdSum(x)>1\)。
做法
直接暴力遍历即可,因为由 \(3\) 的倍数的性质可知,当
数位和是 \(3\) 的倍数时,原数也是 \(3\) 的倍数。故最多 \(3\) 次之后 \(gcdSum(x)\) 必然大于 \(1\)。
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
void solve() {
LL n;
cin >> n;
for (LL i = n; ; i++) {
LL sum = 0;
LL x = i;
while (x) {
sum += x % 10;
x /= 10;
}
if (__gcd(sum, i) > 1) {
cout << i << '\n';
break;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
B. Box Fitting
题意
给你 \(n\) 个高为 \(1\),宽为 \(2\) 的次幂的矩形,以及一个宽为 \(W\) 的盒子,你现在要把这些矩形塞进去,可以叠加,但宽度不能超过 \(W\),请问盒子高度最少是多少?
做法
考虑一个贪心,每层都尽可能先放大的,如果放不下就把高度 \(+1\)。
因为我们可以假设最优解,我们把最优解每层的块降序排列,并不改变结果,然后通过交换法可以证明我们贪心解是正确的。且这样做,我们可以保证上层的宽度一定不会大于下层的宽度。(由于 \(2\) 的次幂的原因)。
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
void solve() {
int n, W;
cin >> n >> W;
vector<int> cnt(35, 0);
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
cnt[__lg(x)]++;
}
int ans = 0;
while (true) {
int len = W;
for (int i = 20; i >= 0; i--) {
while (cnt[i] && len >= (1 << i)) {
cnt[i]--;
len -= 1 << i;
}
}
if (len == W) break;
ans++;
}
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
题意
你有一个 \(k\) 级的衰变粒子,前面有 \(n\) 面墙,当级别为 \(x\) 的粒子穿过一面墙的时候,若 \(x>1\) ,它会反射出一个
\(x-1\) 级的粒子,往回走,同时自己继续穿越后续的墙;若 \(x=1\) 则不发生反射。
请问一个 \(k\) 级的衰变粒子,穿越 \(n\) 面墙,一共能产生多少粒子?
做法
观察到数据范围 \(1\leq n,k\leq 1000\),可以考虑 DP。
设 \(dp[i][j]\) 表示级别为 \(i\) 的粒子,前面还需要穿过 \(j\) 面墙产生的粒子总数。
不难得到如下转移方程:
还需穿过 \(j\) 面墙,说明此时,我们在第 \(n-j+1\) 号墙面前,准备穿过它,那么我们会反射一个 \(i-1\) 级的粒子
从 \(n-j\) 开始穿越到 \(1\) 号,一共 \(n-j\) 面墙,然后 \(i\) 级粒子继续从 \(n-j+2\) 号到 \(n\) 号墙,一共 \(j-1\) 面墙。
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
void solve() {
int n, k;
cin >> n >> k;
vector<vector<int>> dp(k + 1, vector<int>(n + 1, 0));
const int mod = 1e9 + 7;
//表示衰变为 i 的粒子,前面还有 j 面墙要穿越产生的粒子数
for (int i = 1; i <= k; i++) dp[i][0] = 1;
for (int i = 1; i <= k; i++) {
for (int j = 1; j <= n; j++) {
dp[i][j] = (dp[i][j - 1] + dp[i - 1][n - j]) % mod;
}
}
cout << dp[k][n] << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
D. Bananas in a Microwave
题意
你有 \(n\) 个类型的操作,以及一个初始值 \(k=0\)。
在第 \(i\) 次操作,你必须按如下规则执行。
- \(t_i=1\),你可以选择执行 \(a_i\) 次 \(k\rightarrow \lceil k+x\rceil\) ,其中 \(0\leq a_i\leq y\)。
- \(t_i=2\),你可以选择执行 \(a_i\) 次 \(k\rightarrow \lceil k\times x\rceil\) ,其中 \(0\leq a_i\leq y\)。
现在问你对于 \(1\leq i\leq m\),把 \(k\) 变成 \(i\) 最少要几次操作。
做法
看数据范围 \(1\leq n\leq 100,1\leq m\leq 10^5\)。
我们不难想到一个暴力的 DP,我们设 \(dp[i][j]\) 表示考虑了前 \(i\) 次操作,值为 \(j\) 能不能被变出来。
转移就暴力枚举 \(0\leq a_i\leq y\) ,执行了几次,这样复杂度是 \(O(nm^2)\),显然要超时了。
考虑优化,这是我们就要思考,我们有没有必要每次都 for 满这个 \(y\)。
假设目前有个操作是 \(x=2\),\(y=6\),我们枚举的 \(j=3\),那么我们会依次更新:
\(3,5,7,9,11,13,15\),我们思考如果我们会枚举到 \(j=7\),我们是不是会依次更新:\(7,9,11,13,15,17,19\)
我们会发现此时 \(j=7\) 的更新范围是覆盖了从 \(j=3\) 往后更新的范围的,因为我们每次都是 \(+x\)。
那么就暗示我们 \(dp[i+1][7\backsim15]\) 这个状态我们不需要再以 \(j=3\) 为起点,暴力 for 次数去更新了,
因为我们知道当我们枚举到 \(j=7\) 为起点开始暴力 for 操作次数的时候,必然会更新 \(dp[i+1][7\backsim 15]\) 这些状态。所以我们就得到了优化,当 \(dp[i][cur]\) 是 \(true\) 是显然不需要再往下暴力更新了。
这样每一个 \(j\) 只会遍历一次,所以复杂度就是 \(O(nm)\) 的。乘法的操作也是同理。
Code
using namespace std;
typedef long long LL;
void solve() {
int n, m;
cin >> n >> m;
vector<int> dp(m + 1, 0), ans(m + 1, n + 1);
dp[0] = 1;
for (int i = 1; i <= n; i++) {
int t, y;
LL x;
cin >> t >> x >> y;
vector<int> ndp = dp;
for (int j = 0; j <= m; j++) {
LL cur = j;
if (!dp[cur]) continue;
for (int k = 1; k <= y; k++) {
if (t == 1) cur = (cur * 100000 + 100000 + x - 1) / 100000;
else cur = (cur * x + 100000 - 1) / 100000;
if (cur > m) break;
if (dp[cur]) break;
ndp[cur] = 1;
}
}
dp.swap(ndp);
for (int j = 1; j <= m; j++) {
if (dp[j]) ans[j] = min(ans[j], i);
}
}
for (int i = 1; i <= m; i++) {
if (ans[i] == n + 1) ans[i] = -1;
cout << ans[i] << " \n"[i == m];
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
t = 1;
while (t--) {
solve();
}
return 0;
}
- Codeforces CodeCraft Round 711 andcodeforces codecraft round 711 codeforces and round mocha educational codeforces round rated codeforces round 911 div codeforces div and grimoire codeforces round 864 div codeforces round 887 div codeforces round 863 div codeforces round 913 div codeforces round 915 div