Solved: 9/12
Rank: 5 (现场）/ 12（ucup）
A. 环状线
签到题。
#include<bits/stdc++.h>
using namespace std;
int main()
{int n, a, b;cin >> n >> a >> b;int x = 1;if (b < a) swap(a, b), x = 2;if (b-a < n-(b-a)) cout << x << '\n';else cout << 3-x << '\n';
}
J. 后鼻嘤
签到题。考点：getline（？
#include<bits/stdc++.h>
using namespace std;
int main()
{string s;getline(cin, s);s += '\n';string cur;vector <string> ans;for (char ch : s){if (ch >= 'a' && ch <= 'z') cur += ch;else{if (cur.back() == 'n') cur += 'g';ans.push_back(cur);cur = "";}}for (string s : ans) cout << s << ' ';cout << '\n';
}
G. 最大公约数
题意
在 \([1,n]\) 中选出 \(m\) 个整数，使它们两两互质。
题解
选出合数显然不优（会导致和它有公因子的数都选不了），故选择 1 和所有质数即可。
#include<bits/stdc++.h>
using namespace std;const int N = 3e5+5;
bool np[N];
int pri[N], cnt, pre[N];
void sieve(int n)
{for (int i=2; i<=n; ++i){if (!np[i]) pri[++cnt] = i;for (int j=1; j<=cnt && i*pri[j] <= n; ++j){np[i*pri[j]] = 1;if(!(i%pri[j])) break;}}for (int i=1; i<=n; ++i) pre[i] = pre[i-1] + !np[i];
}int main()
{int n, k; cin >> n >> k;sieve(n);if (pre[n] < k) cout << "NO\n";else{cout << "YES\n";int cnt = 0;for (int i=1; i<=n; ++i){if (!np[i]) cout << i << ' ', ++cnt;if (cnt == k) break;}cout << '\n';}
}
B. 爬山
题意
无向带权图，每个点有高度，从低到高走会积累疲劳值，从高到低会清空疲劳值，在疲劳值不超过 \(H\) 的前提下求最短路。
\(n\leq 10^4, m\leq 2\times 10^4, H\leq 100\)
题解
分层图最短路，复杂度 \(O(mH\log mH)\)。
点太多了所以最好不要把图建出来
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;struct node
{int p, h;ll d;node(int p, int h, ll d) : p(p), h(h), d(d) {}bool operator < (const node& t) const{return d > t.d;}
};const int N = 1e4+5;
int n, m, H, h[N];
vector <pii> e[N];
void adde(int x, int y, int z)
{e[x].emplace_back(y, z);
}
ll dis[N][105];int main()
{ios::sync_with_stdio(0); cin.tie(0);cin >> n >> m >> H;for (int i=1; i<=n; ++i) cin >> h[i];for (int i=1; i<=m; ++i){int x, y, z;cin >> x >> y >> z;adde(x, y, z), adde(y, x, z);}memset(dis, 0x3f, sizeof(dis));priority_queue <node> pq;dis[1][0] = 0;pq.push(node(1,0,0));while (!pq.empty()){node cur = pq.top(); pq.pop();int u = cur.p, r = cur.h; ll w = cur.d;if (w > dis[u][r]) continue;for (auto & [v, w] : e[u]){int s = h[v] >= h[u] ? r + h[v] - h[u] : 0;if (s <= H && dis[v][s] > dis[u][r] + w){dis[v][s] = dis[u][r] + w;pq.push(node(v, s, dis[v][s]));}}}for (int i=2; i<=n; ++i){ll ans = 1e18;for (int j=0; j<=H; ++j) ans = min(ans, dis[i][j]);if (ans > 1e17) cout << "-1 ";else cout << ans << ' ';}
}
C. 短视频
题意
\(n\) 个视频，按顺序看。在每一秒：
-
若当前看视频时间 \(x\leq T\)，则无论如何都继续看；
-
若当前看视频时间 \(x > T\)，如果这个视频的吸引值 \(k_i \geq x - T\)，则继续看，否则跳到下一个视频。
-
每个视频至少看 \(1\) 秒。
\(n\leq 10^5, T,t_i\leq 10^9\)。
题解
签到题。因为第三个条件藏在最后喜提+5
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;const int N = 1e5+5;
int n;
ll T, t[N], k[N];int main()
{ios::sync_with_stdio(0); cin.tie(0);cin >> n >> T;for (int i=1; i<=n; ++i) cin >> t[i] >> k[i];ll ans = 0;for (int i=1; i<=n; ++i){ans = max(ans + 1, min(ans + t[i], k[i] + T + 1));}cout << ans << '\n';
}
K. 左儿子右兄弟
题意
给一棵树，可以任意重排子树顺序，求左儿子右兄弟表示下的最小子树大小和，以及达到这个最小值的方案数。
\(n\leq 10^5\)。
题解
每个节点的子树重排对答案的贡献是独立的：都是 \(\sum_i i\times sz_{v_i}\)。
所以 dfs 一遍处理出所有子树大小后对每个点的儿子排序，然后统计答案即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;const int N = 1e5+5, mod = 998244353;
int n;
ll fac[N];
void init(int n)
{fac[0] = 1;for (int i=1; i<=n; ++i) fac[i] = fac[i-1] * i % mod;
}
vector <int> e[N];
void adde(int x, int y)
{e[x].push_back(y);
}
int sz[N];
void dfs(int u)
{sz[u] = 1;for (int v: e[u]){dfs(v);sz[u] += sz[v];}
}int main()
{ios::sync_with_stdio(0); cin.tie(0);cin >> n; init(n);for (int i=2; i<=n; ++i){int x; cin >> x;e[x].push_back(i);}dfs(1);ll ans1 = sz[1], ans2 = 1;for (int i=1; i<=n; ++i){vector <int> ss;for (int j : e[i]) ss.push_back(sz[j]);sort(ss.begin(), ss.end()); reverse(ss.begin(), ss.end());int len = 1;for (int i=0; i<ss.size(); ++i){if (ss[i] == ss[i-1]) ++len;else ans2 = ans2 * fac[len] % mod, len = 1;ans1 += (i+1) * ss[i];}ans2 = ans2 * fac[len] % mod;}cout << ans1 << '\n' << ans2 << '\n';
}
E. 购物计划
题意
有 \(n\) 个商品和 \(m\) 个满减计划，第 \(i\) 个商品原价 \(w_i\) 折扣 \(\frac {p_i}{q_i}\)，第 \(j\) 个计划满 \(a_j\) 减 \(b_j\)。
对每个商品，你可以选择将它的价格降为 \([\frac {p_i}{q_i}w_i, w_i]\) 后再参与任意一个满减计划。
求每个商品的最低购买价格。
\(n,m\leq 5\times 10^5, a_i, b_i, w_i\leq 10^6\)。
题解
最优策略一定是降到某个 \(a_i\) 的倍数，或是降到最低价，再参与满减。可以分别处理。
枚举倍数，预处理 \(g_x\) 表示价格 \(x\) 满减后能到达的最低价。这里得到的只是 \(x\) 恰为某个 \(a_j\) 的倍数时的最低价，但不降到 \(x\) 显然不如继续降。
对每个商品，用 st 表求出 \(g[\lceil \frac {p_i}{q_i}w_i\rceil]\) 的最小值。
枚举倍数，预处理 \(f_x\) 表示价格 \(x\) 满减后能减少的价格的最大值。
对每个商品，用 st 表求出 \(f[1, \lfloor \frac {p_i}{q_i}w_i\rfloor]\) 的最大值，再由 \(\frac {p_i}{q_i}w_i\) 减去即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;const int N = 5e5+5, M = 1e6+5;
int n, m;
int d[M], f[M], g[M];
int st1[20][M], st2[20][M];
int qry1(int l, int r)
{if (l>r) return 0;int o = __lg(r-l+1);return max(st1[o][l], st1[o][r-(1<<o)+1]);
}
int qry2(int l, int r)
{if (l>r) return 1e9;int o = __lg(r-l+1);return min(st2[o][l], st2[o][r-(1<<o)+1]);
}int main()
{ios::sync_with_stdio(0); cin.tie(0);cin >> n >> m;for (int i=1; i<=m; ++i){int x, y; cin >> x >> y;d[x] = max(d[x], y);}int lim = 1e6;for (int i=1; i<=lim; ++i) if (d[i])for (int j=1; i*j<=lim; ++j)f[i*j] = max(f[i*j], d[i]*j);for (int i=1; i<=lim; ++i) g[i] = i - f[i];for (int i=1; i<=lim; ++i) st1[0][i] = f[i], st2[0][i] = g[i];for (int i=1; i<=19; ++i)for (int j=1; j<=lim-(1<<i)+1; ++j){st1[i][j] = max(st1[i-1][j], st1[i-1][j + (1<<i-1)]);st2[i][j] = min(st2[i-1][j], st2[i-1][j + (1<<i-1)]);}for (int i=1; i<=n; ++i){int x, p, q; cin >> x >> p >> q;int l = 1ll * x * p / q, r = (1ll * x * p + q-1) / q;int L = l - qry1(1, l), R = qry2(r, x);if (R <= L) cout << R << ' ' << 1 << '\n';else{int u = 1ll * x * p - 1ll * l * q, v = q;int g = __gcd(u, v);u /= g, v /= g;cout << 1ll * L * v + u << ' ' << v << '\n';}}
}
F. 丝之歌
题意
-
\(n\leq 10^3\) 个关卡，\(m\leq 10^3\) 种敌人，满血 \(c\leq 10\)。
-
除最后一关外，每获得 \(a\) 枚钱会在过关时自动存储为一串，到最后一关后每串钱换 \(b\) 枚钱。
-
第 \(i\) 个关卡会依次出现 \(k_{i,j}\leq 10^9\) 个第 \(id_{i,j}\) 种敌人，\(j = 1\dots t_i, t_i\leq 100\)。
-
第 \(i\) 个敌人在你血量为 \(x\) 时有 \(p_{i,x,y}\) 的概率使你的血量变为 \(y\)，血量为 \(0\) 时你需要重打这一关同时失去所有未存储的钱。游戏无限重生且不存在死档，可以理解为只有一次通过和一次未通过两种情况。
-
求通过所有关卡后的期望钱数。
题解
矩乘 + 期望dp 二合一。
对关卡，我们关心的只是满血进关后死亡的概率。这个概率就是矩阵 \(\prod_{i,j} P_{id_{i,j}}^{k_{i,j}}\) 的第 \(c\) 行 \(0\) 列。矩阵快速幂复杂度太高会 T，加预处理 \(2^k\) 次幂的优化即可。
这部分时间复杂度为 \(O(mc^3\log k + ntc^2\log k)\)。（不优化是 \(O(ntc^3\log k)\) 可能也能卡过，没试）
设上面的死亡概率为 \(p_0\)，令 \(p_1 = 1-p_0\)，设 \(f(i,j)\) 和 \(g(i,j)\) 表示第 \(i\) 关通关、未存储的钱数为 \(j\) 时的概率和期望钱串数，则有转移
这部分时间复杂度 \(O(na)\)。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;const int N = 1e3+5, D = 11, mod = 998244353;
ll qpow(ll a, int b)
{ll r=1;for (; b; b>>=1){if (b&1) r = r * a % mod;a = a * a % mod;}return r;
}
ll inv(ll a)
{return qpow(a, mod-2);
}struct mat
{int n, m;ll a[D][D];mat(int n = 0, int m = 0, int o = 0) : n(n), m(m){memset(a, 0, sizeof(a));if (o){for (int i=0; i<n; ++i) a[i][i] = 1;}}const ll* operator [] (int i) const {return a[i];}ll* operator [] (int i) {return a[i];}mat operator * (const mat & b) const{mat c(n, b.m);for (int i=0; i<n; ++i)for (int j=0; j<b.m; ++j)for (int k=0; k<m; ++k)(c[i][j] += a[i][k] * b[k][j]) %= mod;return c;}
};int n, m, A, B, C, w[N];
mat p[N][30];
ll f[N][N], g[N][N];int main()
{ios::sync_with_stdio(0); cin.tie(0);cin >> n >> m >> A >> B >> C;for (int i=1; i<=m; ++i) cin >> w[i];for (int i=1; i<=m; ++i){p[i][0] = mat(C+1, C+1);p[i][0][0][0] = 1;for (int j=1; j<=C; ++j){ll sum = 0;for (int k=0; k<=j; ++k)cin >> p[i][0][j][k], sum += p[i][0][j][k];sum = inv(sum);for (int k=0; k<=j; ++k)p[i][0][j][k] = p[i][0][j][k] * sum % mod;}for (int j=1; j<30; ++j) p[i][j] = p[i][j-1] * p[i][j-1];}f[0][0] = 1;for (int i=1; i<=n; ++i){int k; cin >> k;mat v(1, C+1, 0); v[0][C] = 1;ll sw = 0;for (int j=1; j<=k; ++j){int id, num; cin >> id >> num;for (int l=0; l<30; ++l) if (num >> l & 1)v = v * p[id][l];sw += 1ll * w[id] * num;}ll q = (sw / A) % mod;int r = sw % A;ll p0 = v[0][0], p1 = (1 - p0 + mod) % mod;if (i < n){for (int j=0; j<A; ++j){f[i][r] = (f[i][r] + f[i-1][j] * p0) % mod;g[i][r] = (g[i][r] + f[i-1][j] * (g[i-1][j] + q) % mod * p0) % mod;f[i][(j+r)%A] = (f[i][(j+r)%A] + f[i-1][j] * p1) % mod;g[i][(j+r)%A] = (g[i][(j+r)%A] + f[i-1][j] * (g[i-1][j] + q + (j+r >= A)) % mod * p1) % mod;}for (int j=0; j<A; ++j) g[i][j] = g[i][j] * inv(f[i][j]) % mod;//for (int j=0; j<A; ++j) cout << f[i][j] << ',' << g[i][j] << ' ';//cout << '\n';}else{ll ans = sw % mod;for (int j=0; j<A; ++j){ans = (ans + f[i-1][j] * g[i-1][j] % mod * B % mod * p0) % mod;ans = (ans + f[i-1][j] * (g[i-1][j] * B % mod + j) % mod * p1) % mod;}cout << ans << '\n';}}
}
D. 网络改造
题意
有向图，第 \(i\) 条边可以用 \(a_i\) 的代价反向或用 \(b_i\) 的代价删除，第 \(i\) 个点可以用 \(c_i\) 的代价删除（同时会删除所有与之相连的边），求将图变为 DAG 的最小代价。
\(n\leq 22\)。
题解
看范围知状压。
设 \(f(S)\) 表示将点集 \(S\) 变为 DAG 的最小代价，按拓扑序转移，强制要求下一个点 \(x\) 没有连到 \(S\) 的边，则
其中 \(s(x, S)\) 表示处理 \(x\) 到 \(S\) 的边的代价和。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;const int N = 22;
int n, m, c[N], f[1<<N], s[N][1<<N];int main()
{ios::sync_with_stdio(0); cin.tie(0);cin >> n >> m;for (int i=0; i<n; ++i) cin >> c[i];for (int i=1; i<=m; ++i){int u, v, a, b;cin >> u >> v >> a >> b; --u, --v;s[u][1<<v] = min(a, b);}for (int i=0; i<n; ++i)for (int j=0; j<n; ++j)for (int S=0; S < (1<<j); ++S)s[i][S | (1<<j)] = s[i][S] + s[i][1<<j];memset(f, 0x3f, sizeof(f));f[0] = 0;for (int S=0; S<(1<<n); ++S)for (int j=0; j<n; ++j) if (!(S >> j & 1))f[S | (1<<j)] = min(f[S | (1<<j)], f[S] + min(c[j], s[j][S]));cout << f[(1<<n)-1] << '\n';
}