11.18训练赛
2021/11/18 23:42:36
本文主要是介绍11.18训练赛,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
A.P1103 书本整理
显然的dp,dp[i][j]代表前i本书留下j本的最优答案,答案为dp[n][n - k]。
#include <bits/stdc++.h> #define fu(a, b, c) for (ll a = b; a <= c; a++) #define fd(a, b, c) for (ll a = b; a >= c; a--) #define dbg(x) cout << #x << '=' << x << ' ' #define mx(a, b) a = max(a, b) #define mn(a, b) a = min(a, b) #define f first #define s second using namespace std; using ll = long long; using pll = pair<ll, ll>; const ll N = 1e7; ll t, n, m, k, ans = N; ll x[N]; int main() { ios::sync_with_stdio(0), cin.tie(0); cin >> n >> k; pair<ll, ll> p[n + 1]; fu(i, 1, n) cin >> p[i].f >> p[i].s; sort(p + 1, p + n + 1); ll dp[n + 1][n - k + 1]; memset(dp, 60, sizeof dp), dp[0][0] = 0; fu(i, 1, n) fu(j, 1, n - k) { fd(i1, i - 1, max(i - k - 1, 0ll)) { t = i1 ? abs(p[i].s - p[i1].s) : 0; mn(dp[i][j], dp[i1][j - 1] + t); } mn(ans, dp[i][n - k]); } cout << ans; }
B.P4389 付公主的背包
这题的前置知识是生成函数与多项式,这里简单写一下,不详细推。
对体积为V的物品构建生成函数\(f(x) = 1 + x^v + x^{2v} + ... = \frac{1}{1 - x^v}\),
将所有的多项式相乘,次数对应的系数就是体积等于次数时的方案数。
直接做卷积显然会T,考虑取对数有\(\ln(\frac{1}{1 - x^v}) = \sum_{i >= 1} \frac{x^{vi}}{i}\)
那么我们就可以在\(mlogm\)时间内得到答案的对数,再多项式exp即可,套一个多项式模板就可以过,
代码等我整理完多项式模板再放。
C.CF1436E Complicated Computations
思考如何快速判断某个MEX值x能否被构造出来,只需要遍历所有
被x分隔的区间,数据结构加速一下,如果所有小于a[i]的数最后一次
出现的位置都大于a[i]上一次出现的位置,那么MEX值a[i]可以被构造。
#include <bits/stdc++.h> #define fu(a, b, c) for (ll a = b; a <= c; a++) #define fd(a, b, c) for (ll a = b; a >= c; a--) #define mx(a, b) a = max(a, b) #define mn(a, b) a = min(a, b) #define lb(x) (x & -x) typedef long long ll; using namespace std; const ll N = 1e5 + 1; ll t, n, m, a; ll T[N], lst[N], f[N]; void upd(ll p, ll x) { for (; p <= n; p += lb(p)) { T[p] = x; for (ll i = 1; i < lb(p); i <<= 1) mn(T[p], T[p - i]); } } ll qry(ll l, ll r) { ll res = 1e9; while (r >= l) { mn(res, lst[r]); for (--r; r - lb(r) >= l; r -= lb(r)) mn(res, T[r]); } return res; } signed main() { cin >> n; fu(i, 1, n) { cin >> a; if (a ^ 1) { f[1] = 1; if (qry(1, a - 1) > lst[a]) f[a] = 1; } upd(a, i), lst[a] = i; } fu(i, 1, n + 1) if (!f[i] && (i == 1 || qry(1, i - 1) <= lst[i])) { cout << i; return 0; } cout << n + 2; }
D.P2491 消防
在直径上尺取合法路径,详见[https://www.cnblogs.com/lemu/p/15510766.html]B题。
#include <bits/stdc++.h> #define fu(a, b, c) for (ll a = b; a <= c; a++) #define fd(a, b, c) for (ll a = b; a >= c; a--) #define mx(a, b) a = max(a, b) #define mn(a, b) a = min(a, b) using namespace std; using ll = long long; using pll = pair<ll, ll>; const ll N = 3e5 + 10; ll n, m, u, v, w, k, e, d1, d2 = 1e9; ll fa[N], d[N], l[N]; vector<pll> g[N]; void dfs(ll u, ll f) { fa[u] = f, k = d[u] > d[k] ? u : k; for (auto [v, w] : g[u]) if (v ^ f && !l[v]) d[v] = d[u] + w, dfs(v, u); } int main() { ios::sync_with_stdio(0), cin.tie(0); cin >> n >> m; fu(i, 2, n) { cin >> u >> v >> w; g[u].emplace_back(v, w); g[v].emplace_back(u, w); } dfs(1, 0), d[k] = 0, dfs(k, 0), e = k; for (ll i = k, j = k; i; j = fa[j]) while (i && d[j] - d[i] <= m) { mn(d2, max(d[e] - d[j], d[i])); l[i] = 1, k = i, dfs(i, fa[i]); mx(d1, d[k] - d[i]), i = fa[i]; } cout << max(d1, d2); }
E.P7597 猜树 加强版
暴力的做法是先得到所有节点的深度,然后从根节点开始递归询问子树。
考虑优化,选择一个大小最大的子树(重儿子),询问除它以外的所有子树,
就可以通过做差得到该子树,至于怎么选,只能想到随机,越大的子树被选择
的概率越高,复杂度我不会证。
#include <bits/stdc++.h> #define fu(a, b, c) for (ll a = b; a <= c; a++) #define fd(a, b, c) for (ll a = b; a >= c; a--) #define mx(a, b) a = max(a, b) #define mn(a, b) a = min(a, b) typedef long long ll; using namespace std; const int N = 5e3 + 1, M = sqrt(N - 1); ll t, n, m, k, a, b, c, ans; ll d[N], fa[N]; vector<ll> g[N]; inline ll q(ll x, ll y, ll z) { cout << "? " << x << ' '; if (x == 1) cout << y << ' '; cout << z << '\n'; cin >> m; return m; } void dfs(ll u) { if (!g[u].size()) return; ll r = g[u][rand() % g[u].size()], s = 0; for (ll v : g[u]) if (d[v] == d[u] + 1) { fa[v] = u; if (v == r || !s && d[r] - d[u] == q(1, v, r) + 1) { s = v; } else { ll c = q(2, 0, v); fu(i, 1, c) { cin >> a; if (a ^ v) g[v].emplace_back(a); } dfs(v); } } for (ll v : g[u]) if (!fa[v]) g[s].emplace_back(v); dfs(s); } int main() { cin >> n; fu(i, 2, n) { d[i] = q(1, 1, i); g[1].emplace_back(i); } dfs(1); cout << "!"; fu(i, 2, n) cout << ' ' << fa[i]; }
F.CF1436D Bandit in a City
比较容易想到一个二分贪心,因为较远的父节点拥有更多的选择,
所以叶子节点优先从距离较近的父节点得到权值。注意二分可能会爆ll,
当时济南的D题也是三分被卡int128很蛋疼。
#include <bits/stdc++.h> #define fu(a, b, c) for (ll a = b; a <= c; a++) #define fd(a, b, c) for (ll a = b; a >= c; a--) #define dbg(x) cout << #x << '=' << x << ' ' #define mx(a, b) a = max(a, b) #define mn(a, b) a = min(a, b) using namespace std; using ll = long long; using LL = __int128; const ll N = 1e6; ll t, n, m, k, w[N]; LL x[N]; vector<ll> g[N]; ll a, ok; void dfs(ll u = 1) { if (!g[u].size()) x[u] -= m; for (ll v : g[u]) dfs(v), x[u] += x[v]; if (x[u] > 0) ok = 0; } int main() { ios::sync_with_stdio(0), cin.tie(0); cin >> n; fu(i, 2, n) cin >> a, g[a].emplace_back(i); fu(i, 1, n) cin >> w[i]; ll l = -1, r = 2e14; while (l < r - 1) { m = l + r >> 1, ok = 1; copy(w + 1, w + n + 1, x + 1); dfs(), ok ? r = m : l = m; } cout << r; }
G.P1682 过家家
并查集处理一下得到每个女生集合对应可选的男生集合,
答案就是最小可选男生集合的大小 + k,(不超过n)。
#include <bits/stdc++.h> #define fu(a, b, c) for (ll a = b; a <= c; a++) #define fd(a, b, c) for (ll a = b; a >= c; a--) #define dbg(x) cout << #x << '=' << x << ' ' #define mx(a, b) a = max(a, b) #define mn(a, b) a = min(a, b) using namespace std; using ll = long long; const ll N = 251; ll n, m, k, f, ans; ll x[N], y[N], fa[N], a, b; bitset<N> g[N]; ll find(ll x) { return fa[x] ? fa[x] = find(fa[x]) : x; } void u(ll x, ll y) { ll fx = find(x), fy = find(y); if (fx ^ fy) fa[fx] = fy, g[fy] |= g[fx]; } signed main() { ios::sync_with_stdio(0), cin.tie(0); cin >> n >> m >> k >> f; fu(i, n + 1, 2 * n) fa[i] = -1; fu(i, 1, m) cin >> a >> b, g[a][b] = 1; fu(i, 1, f) cin >> a >> b, u(a, b); ans = n; fu(i, 1, n) mn(ans, k + (ll)g[find(i)].count()); cout << ans; }
H.P2803 学校选址 II
区间dp,dp[l][r][k]代表在区间l, r内建k所小学的最小距离和,k = 1时是个带权中位数问题。
#include <bits/stdc++.h> #define fu(a, b, c) for (ll a = b; a <= c; a++) #define fd(a, b, c) for (ll a = b; a >= c; a--) #define dbg(x) cout << #x << '=' << x << ' ' #define mx(a, b) a = max(a, b) #define mn(a, b) a = min(a, b) using namespace std; using ll = long long; const ll N = 101; ll n, m, k; ll x[N], ps[N], d[N], pd[N], dp[N][N][N]; void init() { // 双指针预处理k = 1 fu(i, 1, n - 1) { ll k = i; // k记录最优位置 fu(j, i + 1, n) { dis += (pd[j] - pd[k]) * x[j]; fu(k1, k + 1, j) { // 这里可以画个图看一下k移动时距离和的变化 ll nx_dis = dis + (ps[k1 - 1] - ps[i - 1] - (ps[j] - ps[k1 - 1])) * d[k1]; if (nx_dis > dis) break; dis = nx_dis, k = k1; } dp[i][j][1] = dis; dbg(dp[i][j][1]); } cout << '\n'; } } ll dfs(ll l, ll r, ll k) { if (r - l < k) // 区间内每栋楼都有一个学校 return 0; if (dp[l][r][k]) return dp[l][r][k]; fu(m, l, r - 1) fu(i, 1, k - 1) mn(dp[l][r][k], dfs(l, m, i) + dfs(m + 1, r, k - i)); } signed main() { ios::sync_with_stdio(0), cin.tie(0); cin >> n >> k; init(); fu(i, 1, n) cin >> x[i]; fu(i, 2, n) cin >> d[i], pd[i] = pd[i - 1] + d[i]; cout << dfs(1, n, k); }
这篇关于11.18训练赛的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-19永别了,微服务架构!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?