2025.4.28考试总结 最后更新于 2025-05-01 22:16:03

### T1 U556432 暴力枚举 rt，暴力枚举 $a$ 和 $b$，$c$ 可以直接算出来，但是这样还是会超时，所有需要优化 $a$ 和 $b$ 的循环范围，显然 $a ^ 3 \leq n$，$a b ^ 2 \leq n$，这样就能拿到 100 分了。 ```cpp #include <bits/stdc++.h> using namespace std; long long n , cnt; int main() { cin >> n; for(long long i = 1;i * i * i <= n;i ++) { for(long long j = i;j * j * i <= n;j ++) { cnt += n / i / j - j + 1; } } cout << cnt; return 0; } ``` ### U558044 芒果分类 这题贪心是错的，正解是二分答案，考虑每一个芒果的贡献，是 $\max(a_i , x)$，其中 $x$ 是分的组数，只有$(\sum_{i = 1}^{n} \max(a_i , x)) \geq xk$ 时才可以分成 $x$ 组，而 $(\sum_{i = 1}^{n} \max(a_i , x))$ 显然是有单调性的，所有可以二分。 ```cpp #include <bits/stdc++.h> #define int long long using namespace std; int n , l , a[500005] , k; bool check(int x) { int sum = 0; for(int i = 1;i <= n;i ++) { sum += min(a[i] , x); } return sum >= x * k; } signed main() { cin >> n >> k; int l , r; for(int i = 1;i <= n;i ++) { cin >> a[i]; r += a[i]; } l = 1; while(l < r) { int mid = (l + r + 1) / 2; if(check(mid)) { l = mid; } else { r = mid - 1; } } cout << l; return 0; } ``` ### U558035 芒果配送 推一点式子： $$ \begin{aligned} dist(x_1 , y_1 , x_2 , y_2) &= |x_1 - x_2| + |y_1 - y_2| \\ &= \max\{(x_1 - x_2) + (y_1 - y_2) , (x_2 - x_1) + (y_1 - y_2) , (x_1 - x_2) + (y_2 - y_1) , (x_2 - x_1) + (y_2 - y_1)\} \\ &= \max\{x_1 - x_2 + y_1 - y_2 , x_2 - x_1 + y_1 - y_2 , x_1 - x_2 + y_2 - y_1 , x_2 - x_1 + y_2 - y_1\} \\ &= \max\{(x_1 \times dirx + y_1 \times diry) - (x_2 \times dirx + y_2 \times diry)\} \end{aligned} \\ \text{其中} dirx = \pm 1,diry = \pm 1 $$ 可以枚举 $dirx$ 和 $diry$，要求 $dist(x_1 , y_1 , x_2 , y_2)$ 的最大值，$(x_1 \times dirx + y_1 \times diry)$ 就要大，再枚举 $(x_2 , y_2)$，就能算出单个点到所有配送任务地点的距离最大值，再把所有的取最小就是答案了。 ~~公式好长。~~ ```cpp #include <bits/stdc++.h> #define int long long using namespace std; int t , n , m , x[1000005] , y[100005] , a[100005] , b[100005]; int dx[15] = {1 , -1 , 1 , -1}; int dy[15] = {1 , -1 , -1 , 1}; int maxx[15]; //dirx = dx[i] , diry = dy[i]时的最大（x * dirx + y * diry）。 void solve() { cin >> n >> m; for(int i = 1;i <= n;i ++) { cin >> x[i] >> y[i]; } for(int i = 1;i <= m;i ++) { cin >> a[i] >> b[i]; } for(int i= 0;i < 4;i ++) { maxx[i] = -2e9; } for(int i = 1;i <= n;i ++) { for(int j = 0;j < 4;j ++) { int tmp = x[i] * dx[j] + y[i] * dy[j]; maxx[j] = max(maxx[j] , tmp); } } int res = 2e9; for(int i = 1;i <= m;i ++) { int ans = 0; for(int j = 0;j < 4;j ++) { int tmp = maxx[j] - (a[i] * dx[j] + b[i] * dy[j]); ans = max(ans , tmp); } res = min(res , ans); } cout << res << endl; } signed main() { cin >> t; while(t --) { solve(); } return 0; } ``` ### U558032 芒果的收获季 考虑区间 $\text{dp}$。 将时间看成横坐标，将位置看成纵坐标。 （借鉴一下题解的图）  每次考虑一个区间 $[l , r]$，求出被 $[l , r]$ **完全包含** 的区间的最大距离 $d$ 和这个区间 $p$，因为跑到最大距离才能把前面的也全部摘到，然后转移。 $dp[i][j] = \min\{dp[i][k - 1] + dp[k + 1][j] + d\}$ 其中 $k$ 是枚举的 $p$ 中的一个点。 注意这题要离散化。 ```cpp #include <bits/stdc++.h> #define int long long using namespace std; int n , m , t; bool vis[600005]; int dp[3005][3005]; int id[100005]; struct node { int a , b , d; } a[100005]; void solve() { cin >> n; memset(vis , 0 , sizeof(vis)); memset(dp , 0 , sizeof(dp)); for(int i = 1;i <= n;i ++) { cin >> a[i].a >> a[i].b >> a[i].d; vis[a[i].a] = 1; vis[a[i].b] = 1; } int cnt = 0; for(int i = 1;i <= 10000;i ++) { if(vis[i]) { id[i] = ++cnt; } } for(int i = 1;i <= n;i ++) { a[i].a = id[a[i].a]; a[i].b = id[a[i].b]; } //离散化 for(int len = 1;len <= cnt;len ++) { for(int i = 1;i + len - 1 <= cnt;i ++) { int j = i + len - 1; int d = 0; int pos = -1; for(int k = 1;k <= n;k ++) { if(a[k].a >= i && a[k].b <= j) //完全包含 { if(a[k].d > d) { d = a[k].d; pos = k; } } } if(pos == -1) continue; dp[i][j] = 2e9; for(int k = a[pos].a;k <= a[pos].b;k ++) { dp[i][j] = min(dp[i][j] , dp[i][k - 1] + dp[k + 1][j] + d); } } } cout << dp[1][cnt] << endl; } signed main() { cin >> t; while(t --) { solve(); } return 0; } ```