2024/9/27刷题记录（cf1800 - 2000）

题目一：树形​​​​​​dp​​   ​​​​​​   https://codeforces.com/problemset/problem/1866/C

#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
#define endl '\n'
#define pq priority_queue
using namespace std;
typedef pair<int,int> pii;
const int mod = 998244353;void solve(){int n;cin >> n;vector<vector<pair<int,int>>>e(n + 1);for(int i = 0;i < n;i ++){int s;cin >> s;while(s --){int l, w;cin >> l >> w;e[i + 1].push_back({w, l});}}vector<array<int,3>>dp(n + 1);vector<int> st(n + 1);auto dfs =[&](auto self, int x){if(st[x]){return dp[x];}st[x] = true;for(auto [w, l] : e[x]){dp[x][2] = (dp[x][2] + dp[x][1] * (w == 0)) % mod;dp[x][w] += 1;auto g = self(self, l);dp[x][2] = ((dp[x][2] + g[0] * dp[x][1] % mod) % mod + g[2]) % mod;dp[x][1] += g[1];dp[x][1] %= mod;dp[x][0] += g[0];dp[x][0] %= mod;}return dp[x];};cout << dfs(dfs, 1)[2] << endl;}signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t = 1;while(t--){solve();}return 0;
}

题目二（树形背包）：https://codeforces.com/problemset/problem/1856/E1

#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
#define endl '\n'
#define pq priority_queue
using namespace std;
typedef pair<int,int> pii;void solve(){int n;cin >> n;vector<vector<int>>e(n + 1);for(int i = 2;i <= n;i ++){int p;cin >> p;e[p].push_back(i);}vector<int>sz(5050);int ans = 0;auto dfs =[&](auto self, int u) -> void{bitset<5050>dp;dp.set(0);for(auto j : e[u]){self(self, j);sz[u] += sz[j];dp |= dp << sz[j];}int t = 0;for(int i = 0;i <= n / 2;i ++){if(dp.test(i)){t = max(t, i * (sz[u] - i));}}ans += t;sz[u] += 1;};dfs(dfs, 1);cout << ans << endl;}signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t = 1;while(t--){solve();}return 0;
}

题目三(dp + 二分)：https://codeforces.com/problemset/problem/1862/F

#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
#define endl '\n'
#define pq priority_queue
using namespace std;
typedef pair<int,int> pii;void solve(){int w, f;cin >> w >> f;int n;cin >> n;vector<int>dp(1e6 + 10);int sum = 0;dp[0] = 1;for(int i = 1;i <= n;i ++){int x;cin >> x;sum += x;for(int i = 1e6;i >= x;i --)dp[i] |= dp[i - x];}auto check =[&](int mid) -> bool{int x = mid * w, y = mid * f;int ok = false;if(x >= sum || y >= sum)ok = true;for(int i = 0;i <= sum;i ++){if(dp[i] && x >= i && y >= (sum - i))ok = true;}return ok;};int l = 0, r = 1e9 + 1;while(l + 1 != r){int mid = l + r >> 1;if(check(mid))r = mid;elsel = mid;}cout << r << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t;cin>>t;while(t--){solve();}return 0;
}

题目四（暴力）：https://codeforces.com/problemset/problem/1808/C

#include <bits/stdc++.h>using i64 = long long;int luckiness(i64 x) {auto s = std::to_string(x);auto [pmin, pmax] = std::minmax_element(s.begin(), s.end());return *pmax - *pmin;
}void solve() {i64 l, r;std::cin >> l >> r;i64 ans = l;i64 p = 1;for (int i = 0; i <= 18; i++) {for (int x = 0; x < 10; x++) {i64 v = l / p * p + (p - 1) / 9 * x;if (l <= v && v <= r && luckiness(v) < luckiness(ans)) {ans = v;}v = r / p * p + (p - 1) / 9 * x;if (l <= v && v <= r && luckiness(v) < luckiness(ans)) {ans = v;}}p *= 10;}std::cout << ans << "\n";
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t;std::cin >> t;while (t--) {solve();}return 0;
}