2024.3.2 训练记录（6）

CF 1922E Increasing Subsequences

题目链接

很容易发现，一段长为 i 的上升序列有 $2^i$ 的贡献（包括空串）

所以按位考虑，先考虑最高位的1，后面的递减给出贡献就可以

这一题学到的是用到log2最好使用 __lg()

#include <bits/stdc++.h>using namespace std;#define int long long
using i64 = long long;typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;const int N = 10;
const int mod = 1e9 + 7;
const int maxn = 1e6 + 10;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;void solve()
{int n;cin >> n;int tmp = __lg(n);vector<int> ans;for (int i = 0; i < tmp; i ++ ) ans.push_back(i);for (int i = tmp - 1; i >= 0; i -- )if ((n >> i) & 1) ans.push_back(i);cout << ans.size() << '\n';for (auto t : ans) cout << t << ' ';cout << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t -- ){solve();}
}

CF 1915G Bicycles

题目链接

比想象中简单的带状态表示的低智dijkstra

再添加一维保存当前最小的s即可

#include <bits/stdc++.h>using namespace std;#define int long long
using i64 = long long;typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;const int N = 10;
const int mod = 1e9 + 7;
const int maxn = 1e6 + 10;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;void solve()
{int n, m;cin >> n >> m;vector<vector<PII>> g(n + 1);while (m -- ){int u, v, w;cin >> u >> v >> w;g[u].push_back({v, w});g[v].push_back({u, w});}vector<vector<int>> dist(n + 1, vector<int>(1010, INF));vector<vector<bool>> st(n + 1, vector<bool>(1010));vector<int> s(n + 1);for (int i = 1; i <= n; i ++ ) cin >> s[i];priority_queue<PIII, vector<PIII>, greater<PIII>> q; // 距离 当前点 最小的sdist[1][s[1]] = 0;q.push({0, {1, s[1]}});while (q.size()){auto t = q.top();q.pop();int dd = t.first, ver = t.second.first, mins = t.second.second;if (st[ver][mins]) continue;st[ver][mins] = true;for (int i = 0; i < g[ver].size(); i ++ ){int j = g[ver][i].first, d = g[ver][i].second;int ns = min(s[j], mins);if (dist[j][ns] > dd + mins * d){dist[j][ns] = dd + mins * d;q.push({dist[j][ns], {j, ns}});}}}int ans = INF;for (int i = 1; i <= 1000; i ++ ) ans = min(ans, dist[n][i]);cout << ans << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t -- ){solve();}
}

CF 1934B Yet Another Coin Problem

题目链接

本来想用dp，但是一看范围好大就不敢用，然后想到是不是先预处理一下小一点的数，然后大的数多出来的部分全部用15，但是觉得这样写好莫名其妙就没写，赛后发现就是这样qaq

#include <bits/stdc++.h>using namespace std;#define int long long
using i64 = long long;typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;const int N = 1e3 + 10;
const int mod = 1e9 + 7;
const int maxn = 1e6 + 10;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;int p[N];void solve()
{int n;cin >> n;if (n <= N){cout << p[n] << '\n';return;}int ans = 0;int tmp = n / 15;ans += tmp - 15;n = n % 15 + 15 * 15;ans += p[n];cout << ans << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);for (int i = 1; i <= N; i ++ ) p[i] = INF;p[1] = 1, p[3] = 1, p[6] = 1, p[10] = 1, p[15] = 1;for (int i = 2; i <= N; i ++ ){if (i - 1 > 0) p[i] = min(p[i - 1] + 1, p[i]);if (i - 3 > 0) p[i] = min(p[i - 3] + 1, p[i]);if (i - 6 > 0) p[i] = min(p[i - 6] + 1, p[i]);if (i - 10 > 0) p[i] = min(p[i - 10] + 1, p[i]);if (i - 15 > 0) p[i] = min(p[i - 15] + 1, p[i]);}int t = 1;cin >> t;while (t -- ){solve();}
}

CF 1934C Find a Mine

题目链接、

因为不太会找两条线的交点于是用循环一个个判断是不是（别骂了。。。

于是成功T的很惨

后来发现数据范围太大了，没法用这个方法找交点水过去，于是开始解方程组，交点解出来了又忘记判断是不是在合法范围内。。。

大概思路就是先判断左上角的点，然后判断右下角的点，这样可以把两个地雷锁定在一条or两条线上，第三次判断左下角的点，判断这个顶点产生的一条线与前两次判断产生的一条or两条线会形成一个or两个交点，第四次询问其中的一个交点，是的话直接输出，不是就输出另一个交点

发现交互题比其他题型要简单（
特别是询问次数少的，次数越少越简单

#include <bits/stdc++.h>using namespace std;#define int long long
using i64 = long long;typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;const int N = 10;
const int mod = 1e9 + 7;
const int maxn = 1e6 + 10;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;void solve()
{int n, m;cin >> n >> m;cout << "? " << 1 << ' ' << 1 << endl;int a, b;cin >> a;if (a == 0){cout << "! 1 1" << endl;return;}int k1 = -2 - a;cout << "? " << n << ' ' << m << endl;cin >> b;if (b == 0){cout << "! " << n << ' ' << m << endl;return;}int k2 = b - n - m;cout << "? " << n << ' ' << 1 << endl;int c;cin >> c;if (c == 0){cout << "! " << n << ' ' << 1 << endl;return;}int x = n - c, y = 1;int k3 = x - y;if ((k3 - k1) % 2 == 0){int xx = (k3 - k1) / 2;int yy = -xx - k1;if (xx >= 1 && xx <= n && yy >= 1 && yy <= m){cout << "? " << xx << ' ' << yy << endl;int d;cin >> d;if (d == 0){cout << "! " << xx << ' ' << yy << endl;return;}}}int xx = (k3 - k2) / 2;int yy = -xx - k2;cout << "! " << xx << ' ' << yy << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t -- ){solve();}
}

CF 1912K Kim’s Quest

题目链接

求方案数的问题，首先要能考虑到两种方法：

• 组合数学
• 动态规划

因为这道题的限制比较复杂，用组合数学非常困难，于是想到dp

奇偶性，和具体的数是多少无关，所以输入a的时候就把转换成奇偶，奇数1偶数0

dp[i][j][k] 表示前 i 个数中，最后一位是 k，倒数第二位是 j 的方案数

具体还是看代码吧，也还没有完全想清楚

#include <bits/stdc++.h>using namespace std;#define int long long
using i64 = long long;typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;const int N = 10;
const int mod = 998244353;
const int maxn = 1e6 + 10;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;void solve()
{int n;cin >> n;vector<int> a(n + 1);for (int i = 1; i <= n; i ++ ){int x; cin >> x;a[i] = (x & 1);}vector<int> cnt(2);vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(2, vector<int>(2)));int ans = 0;for (int i = 1; i <= n; i ++ ){for (int j = 0; j < 2; j ++ ){for (int k = 0; k < 2; k ++ ){dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][k]) % mod;if ((j + k + a[i]) % 2 == 0){dp[i][j][a[i]] = (dp[i][j][a[i]] + dp[i - 1][k][j]) % mod;ans = (ans + dp[i - 1][k][j]) % mod;}}}for (int j = 0; j < 2; j ++ ) dp[i][j][a[i]] = (dp[i][j][a[i]] + cnt[j]) % mod;cnt[a[i]] ++ ;}cout << ans << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;// cin >> t;while (t -- ){solve();}
}

CF 161D Distance in Tree

题目链接

树形dp

做的少数几道树形dp来看，就是存储以每个点为根的子树信息，和 dfs 结合起来做

这一题的 dp[i][j] 就是以 i 为根的子树中，距离为 j 的点的个数

这个值就等于 i 的所有邻接点（除了父结点）的距离为 j - 1 的点数相加

得到这个信息之后，我们就可以计算出当前结点向下走符合条件的点数

还有一种情况是先向上走，走到其他的子树，再向下走

这个情况怎么计算呢？

可以用距离当前结点的父结点为 j - 1 的点数减去距离当前结点为 j - 2的点数，画图很好理解

#include <bits/stdc++.h>using namespace std;#define int long long
using i64 = long long;typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;const int N = 10;
const int mod = 998244353;
const int maxn = 1e6 + 10;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;void solve()
{int n, k;cin >> n >> k;vector<vector<int>> g(n + 1);for (int i = 0; i < n - 1; i ++ ){int u, v;cin >> u >> v;g[u].push_back(v);g[v].push_back(u);}vector<vector<int>> dp(n + 1, vector<int>(k + 1));function<void(int, int)> dfs1 = [&](int u, int fa){for (int i = 0; i < g[u].size(); i ++ ){int ver = g[u][i];if (ver == fa) continue;dfs1(ver, u);for (int j = 1; j <= k; j ++ ) dp[u][j] += dp[ver][j - 1];}};for (int i = 1; i <= n; i ++ ) dp[i][0] = 1;dfs1(1, -1);function<void(int, int)> dfs2 = [&](int u, int fa){for (int i = 0; i < g[u].size(); i ++ ){int ver = g[u][i];if (ver == fa) continue;for (int j = k; j >= 1; j -- ) // 因为更新大的需要用到小的 所以从大到小{dp[ver][j] += dp[u][j - 1];if (j > 1) dp[ver][j] -= dp[ver][j - 2];}dfs2(ver, u);}};dfs2(1, -1);int ans = 0;for (int i = 1; i <= n; i ++ ) ans += dp[i][k];cout << ans / 2 << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;// cin >> t;while (t -- ){solve();}
}

CF 1509C The Sports Festival

题目链接

第一次写出来区间dp（虽然很简单！开心ovo

dp[i][j] 就是 [i, j] 内的最佳答案

转移方程： dp[l][r] = min({dp[l][r], dp[l + 1][r] + a[r] - a[l], dp[l][r - 1] + a[r] - a[l]});

#include <bits/stdc++.h>using namespace std;#define int long long
using i64 = long long;typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;const int N = 10;
const int mod = 998244353;
const int maxn = 1e6 + 10;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;void solve()
{int n;cin >> n;vector<int> a(n + 1);for (int i = 1; i <= n; i ++ ) cin >> a[i];sort(a.begin() + 1, a.end());vector<vector<int>> dp(n + 1, vector<int>(n + 1, INF));for (int i = 1; i <= n; i ++ ) dp[i][i] = 0;for (int len = 2; len <= n; len ++ ){for (int l = 1; l + len - 1 <= n; l ++ ){int r = l + len - 1;dp[l][r] = min({dp[l][r], dp[l + 1][r] + a[r] - a[l], dp[l][r - 1] + a[r] - a[l]});}}cout << dp[1][n] << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;// cin >> t;while (t -- ){solve();}
}

CF 1398D Colored Rectangles

题目链接

又是dp。。。

以后可以注意一下数据范围，如果比较小的话可以考虑设计一下多维的dp

dp[i][j][k] 表示用 i 个 r ，j 个 g ，k 个 b 的最大面积和

具体怎么更新代码写的很清楚

#include <bits/stdc++.h>using namespace std;#define int long long
using i64 = long long;typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;const int N = 10;
const int mod = 998244353;
const int maxn = 1e6 + 10;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;void solve()
{int r, g, b;cin >> r >> g >> b;vector<int> rr(r + 1), gg(g + 1), bb(b + 1);for (int i = 1; i <= r; i ++ ) cin >> rr[i];for (int i = 1; i <= g; i ++ ) cin >> gg[i];for (int i = 1; i <= b; i ++ ) cin >> bb[i];sort(rr.begin() + 1, rr.end());sort(gg.begin() + 1, gg.end());sort(bb.begin() + 1, bb.end());vector<vector<vector<int>>> dp(r + 1, vector<vector<int>>(g + 1, vector<int>(b + 1)));for (int i = 0; i <= r; i ++ ){for (int j = 0; j <= g; j ++ ){for (int k = 0; k <= b; k ++ ){if (i > 0 && j > 0) dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - 1][k] + rr[i] * gg[j]);if (i > 0 && k > 0) dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j][k - 1] + rr[i] * bb[k]);if (j > 0 && k > 0) dp[i][j][k] = max(dp[i][j][k], dp[i][j - 1][k - 1] + gg[j] * bb[k]);}}}cout << dp[r][g][b] << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;// cin >> t;while (t -- ){solve();}
}