A 获得木头
个原木= 个木板, 个木板= 根木棍,所以 个原木= 根木棍。
现在有 个原木,一共可以得到 根木棍,输出 即可。
#include <bits/stdc++.h> using namespace std; // 2024 OneWan int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int x; cin >> x; cout << x * 8; return 0; }
B 采矿时间到!
只能垂直于矿道挖掘,的矩阵
所以我们考虑现挖 和 层,也就是说如果 为 的话,那么消耗 点体力挖掉。
然后再考虑挖 和 层,如果 为 且 被挖掉了,那么消耗 点体力挖掉。
如果 为 且 没有被挖掉,那么消耗 点体力挖掉。
#include <bits/stdc++.h> using namespace std; // 2024 OneWan string g[5]; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, h; cin >> n >> h; for (int i = 0 ; i < 5 ; i++) { cin >> g[i]; } int ans = 0; for (int i = 0 ; i < n ; i++) { if (g[1][i] == '*' && h) { g[1][i] = '.'; h--; ans++; } if (g[3][i] == '*' && h) { g[3][i] = '.'; h--; ans++; } } for (int i = 0 ; i < n ; i++) { if (g[0][i] == '*' && g[1][i] == '.' && h) { g[0][i] = '.'; h--; ans++; } if (g[4][i] == '*' && g[3][i] == '.' && h) { g[4][i] = '.'; h--; ans++; } } for (int i = 0 ; i < n ; i++) { if (g[0][i] == '*' && g[1][i] == '#' && h > 1) { g[0][i] = '.'; h -= 2; ans++; } if (g[4][i] == '*' && g[3][i] == '#' && h > 1) { g[4][i] = '.'; h -= 2; ans++; } } cout << ans; return 0; }
C 耕种时间到!
容易知道 ,所以收割 次以后所有小麦种子的等级都会为 。
因为 ,所以不需要考虑等级为 的种子,因为等级为 的会无限产生自己。
那么我们暴力枚举收割轮数,时间复杂度 。
#include <bits/stdc++.h> using namespace std; // 2023 OneWan using i64 = long long; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; vector<int> a(n + 1); for (int i = 1 ; i <= n ; i++) { cin >> a[i]; } int x; cin >> x; i64 ans = 0; for (int i = 0 ; i <= 30 ; i++) { i64 res = 0; for (int j = 1 ; j <= n ; j++) { if (a[j] == x) { res += 1LL << i; } a[j] = (a[j] + 2) / 3; } ans = max(ans, res); } cout << ans << "\n"; return 0; }
D 探索的时光
危险度之和为
已知 ,, 可以通过 的时间内求出。
然后再通过 的时间枚举 的值,对结果取 即可求出答案,总时间复杂度为
#include <bits/stdc++.h> using namespace std; // 2024 OneWan using i64 = long long; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; vector<int> a(n + 1); i64 A = 0, B = 0, C = 0; for (int i = 1 ; i <= n ; i++) { cin >> a[i]; A += a[i]; B += 1LL * i * a[i]; C += 1LL * i * i * a[i]; } i64 ans = 0x7fffffffffffffff; for (int i = 1 ; i <= n ; i++) { i64 x = i; i64 res = x * x * A - 2LL * x * B + C; ans = min(ans, res); } cout << ans << "\n"; return 0; }
E 来硬的
解法一
先考虑不使用魔法的做法,就是一个普通的01背包, 表示前 个煤炭,烧 个矿石所需要的最小时间。
然后答案就是 。
此时使用魔法,因为只能使用一次,所以我们可以枚举这一次,假设第 个煤炭变成了暗物质,那么煤炭分为了两个区间 内的煤炭和 区间 内的煤炭,此时我们需要这两个区间烧 个矿石。我们可以枚举左边区间烧 个矿石,右边区间则就烧了 个矿石。因为 ,所以时间复杂度是 ,以至于两边区间的求法,可以考虑前缀后缀01背包,即 表示前 个煤炭,烧 个矿石所需要的最小时间。 表示后 个煤炭,烧 个矿石所需要的最小时间。
则答案为
#include <bits/stdc++.h> using namespace std; // 2024 OneWan const int N = 1000005; int x[N + 5], y[N + 5]; using i64 = long long; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; vector dpL(n + 5, vector(m + 5, (i64) 1e14)); vector dpR(n + 5, vector(m + 5, (i64) 1e14)); for (int i = 1 ; i <= n ; i++) { cin >> x[i] >> y[i]; } dpL[0][0] = 0; for (int i = 1 ; i <= n ; i++) { for (int j = 0 ; j <= m ; j++) { dpL[i][j] = dpL[i - 1][j]; } for (int j = 0 ; j <= m ; j++) { dpL[i][min(m, j + x[i])] = min(dpL[i][min(m, j + x[i])], dpL[i - 1][j] + y[i]); } for (int j = m - 1 ; j >= 0 ; j--) { dpL[i][j] = min(dpL[i][j], dpL[i][j + 1]); } } dpR[n + 1][0] = 0; for (int i = n ; i >= 1 ; i--) { for (int j = 0 ; j <= m ; j++) { dpR[i][j] = dpR[i + 1][j]; } for (int j = 0 ; j <= m ; j++) { dpR[i][min(m, j + x[i])] = min(dpR[i][min(m, j + x[i])], dpR[i + 1][j] + y[i]); } for (int j = m - 1 ; j >= 0 ; j--) { dpR[i][j] = min(dpR[i][j], dpR[i][j + 1]); } } i64 ans = 0x7fffffffffffffff; for (int i = 1 ; i <= n ; i++) { int sum = max(0, m - 2 * x[i]); for (int L = 0 ; L <= sum ; L++) { i64 res = y[i] / 2 + dpL[i - 1][L] + dpR[i + 1][sum - L]; ans = min(ans, res); } } cout << ans; return 0; }
解法二
直接背包, 表示前 个煤炭烧炼 单位矿石,使用了 次魔法的最短时间。
F 快快乐乐剪羊毛
先把草皮整体往右移 ,这样保证所有羊都在最左边一块草皮的左侧,此时价值和为 。
然后向右移动草皮,每当一只羊到一块草皮的左端点时,更新价值加上 新草皮与旧草皮的差。
这样可以保证所有羊在所有可能情况下的价值和都被计算过一遍,最大更新次数为 直接用 set 存下即可。
怎么保证向右移动草皮的时间复杂度?
设 为一只羊所在的横坐标, 为草皮的左端点。那么对于第 块草皮,该羊的偏移量为 。
通过从小到大枚举偏移量,即可确认羊走到某块草皮的左端点。
#include <bits/stdc++.h> using namespace std; // 2024 OneWan using i64 = long long; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; vector<i64> w(n + 1); vector<int> v(n + 2); for (int i = 1 ; i <= n ; i++) { int x; cin >> x; w[i] = w[i - 1] + x; } for (int i = 1 ; i <= n ; i++) { cin >> v[i]; } i64 res = 0; map<i64, vector<int>> e; for (int i = 0 ; i < m ; i++) { i64 x; cin >> x; for (int j = 1 ; j <= n + 1 ; j++) { e[w[j - 1] - x].push_back(v[j] - v[j - 1]); } } set<i64> ans; ans.insert(res); for (auto &[_, vec] : e) { for (auto &x : vec) { res += x; } ans.insert(res); } cout << ans.size() << "\n"; return 0; }
G 不速之客
idea 由 thisislike_fan 提供。
解法一
容易知道当 的位数固定时,
由 可得,当 确定时,
所以如果我们知道 ,那么我们可以检验 这个区间内的数 是否符合条件即可。
暴力检验整个区间肯定是超时的,我们可以考虑求 减去
如何求在 中排列的个数?考虑到贪心找到 的最大的 的排列,然后它的排位就是我们要求的个数。
接下来考虑枚举
对于位数为 的整数 , 有 种取值。
相当于有 个不同的箱子, 个相同的小球,每个箱子可以为空,问有多少种方案。
通过插板法知道 的取值种数不多,所以我们可以爆搜枚举 和 通过贪心和康托展开求出问题答案的数量。
最后通过费马小定理求逆元算出答对问题的概率。
#include <bits/stdc++.h> using namespace std; using i64 = long long; int __OneWan_2024 = [](){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); return 0; }(); int m; i64 n, k; array<i64, 12> pow10{}, fact{}; array<int, 10> cnt{}; array<i64, 10> p{}; const i64 mod = 998244353; i64 work(i64 sum) { i64 R = min({n, max(pow10[m - 1] - 1, sum), pow10[m] - 1}); vector<int> num(m); i64 temp = R; for (int i = 0 ; i < m ; i++) { num[i] = temp % 10; temp /= 10; } reverse(begin(num), end(num)); array<int, 10> cur = cnt; i64 rk = 0; for (int i = 0 ; i < (int) num.size() ; i++) { i64 cur_ans = 1; for (int j = 0 ; j < 10 ; j++) { cur_ans *= fact[cur[j]]; } for (int j = 0 ; j < num[i] ; j++) { if (cur[j] == 0) continue; cur_ans /= fact[cur[j]]; cur_ans *= fact[cur[j] - 1]; rk += fact[(int) num.size() - i - 1] / cur_ans; cur_ans *= fact[cur[j]]; cur_ans /= fact[cur[j] - 1]; } if (cur[num[i]] == 0) return rk % mod; cur[num[i]]--; } return (rk + 1) % mod; } i64 ans = 0; void dfs(int len, int cur, i64 sum) { if (len == m) { ans = (ans + work(sum + k)) % mod; ans = (ans - work(sum - k - 1) + mod) % mod; return; } for (int i = cur ; i <= 9 ; i++) { cnt[i]++; dfs(len + 1, i, sum + p[i]); cnt[i]--; } } i64 qpow(i64 a, i64 b = mod - 2, i64 res = 1) { while (b) { if (b & 1) res = res * a % mod; a = a * a % mod; b >>= 1; } return res; } int main() { fact[0] = pow10[0] = 1; for (int i = 1 ; i <= 11 ; i++) { pow10[i] = pow10[i - 1] * 10; fact[i] = fact[i - 1] * i; } for (int i = 0 ; i <= 9 ; i++) { p[i] = 1; } cin >> n >> k; int mx = log10(n) + 1; for (int i = 1 ; i <= mx ; i++) { for (int j = 0 ; j <= 9 ; j++) { p[j] *= j; } m = i; dfs(0, 0, 0); } cout << ans * qpow(n % mod) % mod; return 0; }
解法二
我们可以选择对 进行拆位,此时我们需要先枚举位数 。
当 的时候,
令左半为 ,右半为 ,那么我们只需要找 即可。这是一个经典的问题。
怎么处理,因为合位之后需要有 位,而且前半是不能含有前导0的,所以 的位数固定了,那么 的位数是不固定的,因为 可以有前导0。暴力计算 存进数组,对 数组排序,二分找 的个数就好了。
需要注意的是,当 恰好等于 的时候, 恰好是前缀,这个时候 是不能选择大于后缀的,因为要保证 拼起来 。
#include <bits/stdc++.h> using namespace std; using i64 = long long; int __OneWan_2024 = [](){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); return 0; }(); const i64 P = 998244353; i64 p[11][12]; i64 qpow(i64 a, i64 b = P - 2, i64 res = 1) { while (b) { if (b & 1) res = res * a % P; a = a * a % P; b >>= 1; } return res; } int main() { for (int i = 0 ; i <= 10 ; i++) { p[i][0] = 1; } for (int i = 1 ; i <= 11 ; i++) { for (int j = 0 ; j <= 10 ; j++) { p[j][i] = p[j][i - 1] * j; } } i64 n, k; cin >> n >> k; int m = log10(n) + 1; i64 ans = min(n, 9LL); for (int i = 2 ; i <= m ; i++) { // 枚举位数 int sqrL = (i + 1) / 2, sqrR = i - sqrL; vector a(2, vector<i64>()); for (int L = p[10][sqrL - 1] ; L < p[10][sqrL] ; L++) { // 枚举左侧的数 int temp = L; int cnt = 0; i64 res = L * p[10][sqrR]; do { res -= p[temp % 10][i]; temp /= 10; cnt++; } while (temp); if (i == m) { if (L > n / p[10][m - cnt]) continue; if (L == n / p[10][m - cnt]) a[0].push_back(res); else a[1].push_back(res); } else { a[1].push_back(res); } } vector b(2, vector<i64>()); for (int R = 0 ; R < p[10][sqrR] ; R++) { // 枚举右侧的数 int temp = R; int cnt = 0; i64 res = R; do { res -= p[temp % 10][i]; temp /= 10; cnt++; } while (temp); if (i == m) { if (R <= n % p[10][m - cnt]) b[0].push_back(res); b[1].push_back(res); } else { b[1].push_back(res); } } for (int j = 0 ; j <= 1 ; j++) { sort(begin(b[j]), end(b[j])); } for (int j = 0 ; j <= 1 ; j++) { for (auto &x : a[j]) { int R = 0, L = 0; auto it1 = upper_bound(begin(b[j]), end(b[j]), k - x); if (it1 != begin(b[j])) { it1--; if (*it1 < (-k - x)) continue; R = it1 - begin(b[j]) + 1; } auto it2 = lower_bound(begin(b[j]), end(b[j]), (-k - x)); if (it2 != begin(b[j])) { it2--; L = it2 - begin(b[j]) + 1; } ans = (ans + R - L) % P; } } } cout << ans * qpow(n % P) % P; return 0; }
全部评论
(2) 回帖