2020-2021:teams:die_java:front_page_springtraining7
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:die_java:front_page_springtraining7 [2020/05/30 08:51] fyhssgss 创建 |
2020-2021:teams:die_java:front_page_springtraining7 [2020/05/30 08:54] (当前版本) fyhssgss |
||
|---|---|---|---|
| 行 6: | 行 6: | ||
| * 时间:2020-5-24 13:00~18:00 | * 时间:2020-5-24 13:00~18:00 | ||
| - | * rank:2/30 | + | * rank:''%%2/30%%'' |
| - | * 完成情况：10/10/12 | + | * 完成情况：''%%10/10/12%%'' |
| ===== 题解 ===== | ===== 题解 ===== | ||
| 行 26: | 行 26: | ||
| 线段树维护最大独立点集合的和，维护信息为$mx[o][0/1][0/1]$表示$o$节点的答案，端点的数值选或者没选。 | 线段树维护最大独立点集合的和，维护信息为$mx[o][0/1][0/1]$表示$o$节点的答案，端点的数值选或者没选。 | ||
| + | <hidden 代码> | ||
| <code cpp> | <code cpp> | ||
| #include<iostream> | #include<iostream> | ||
| 行 83: | 行 84: | ||
| } | } | ||
| </code> | </code> | ||
| + | </hidden> | ||
| + | |||
| ===== ===== | ===== ===== | ||
| 行 97: | 行 100: | ||
| 路径一定是起始点到指定点再到终点，对 $k$ 个点跑最短路即可，询问的时候枚举到哪个指定点算最小值。 | 路径一定是起始点到指定点再到终点，对 $k$ 个点跑最短路即可，询问的时候枚举到哪个指定点算最小值。 | ||
| + | <hidden 代码> | ||
| <code cpp> | <code cpp> | ||
| #include<iostream> | #include<iostream> | ||
| 行 177: | 行 181: | ||
| } | } | ||
| </code> | </code> | ||
| + | </hidden> | ||
| ===== F. Combination Lock ===== | ===== F. Combination Lock ===== | ||
| 行 192: | 行 197: | ||
| $dp[i][j]$表示从$i$转移$j$的最佳收益，正常DP的话还需要枚举一个$k$，复杂度是$O(n^3)$。根据转移方程$dp[i][j]=max\{dp[k][i]\}+a[j],x[i]-x[k]\leq x[j]-x[i]$，发现$dp[k][i]$可以用单调队列维护最大值，所以复杂度降为$O(n^2)$ | $dp[i][j]$表示从$i$转移$j$的最佳收益，正常DP的话还需要枚举一个$k$，复杂度是$O(n^3)$。根据转移方程$dp[i][j]=max\{dp[k][i]\}+a[j],x[i]-x[k]\leq x[j]-x[i]$，发现$dp[k][i]$可以用单调队列维护最大值，所以复杂度降为$O(n^2)$ | ||
| + | <hidden 代码> | ||
| <code cpp> | <code cpp> | ||
| #include<bits/stdc++.h> | #include<bits/stdc++.h> | ||
| 行 251: | 行 257: | ||
| } | } | ||
| </code> | </code> | ||
| + | </hidden> | ||
| + | |||
| ===== H. Crowded Cows ===== | ===== H. Crowded Cows ===== | ||
| 行 263: | 行 271: | ||
| 讲所有奶牛按坐标排序，然后预处理一下RMQ维护一下区间奶牛的最大值，在统计时直接查询两端区间最大值是否满足大于二倍关系即可。 | 讲所有奶牛按坐标排序，然后预处理一下RMQ维护一下区间奶牛的最大值，在统计时直接查询两端区间最大值是否满足大于二倍关系即可。 | ||
| + | <hidden 代码> | ||
| <code cpp> | <code cpp> | ||
| #include<bits/stdc++.h> | #include<bits/stdc++.h> | ||
| 行 307: | 行 316: | ||
| } | } | ||
| </code> | </code> | ||
| + | </hidden> | ||
| ===== J. No Change ===== | ===== J. No Change ===== | ||
| 行 318: | 行 328: | ||
| 状压dp，$f[S]$ 表示用集合 $S$ 最多能买到的位置，转移的时候枚举用哪个硬币，在前缀和序列上二分即可 | 状压dp，$f[S]$ 表示用集合 $S$ 最多能买到的位置，转移的时候枚举用哪个硬币，在前缀和序列上二分即可 | ||
| + | <hidden 代码> | ||
| <code cpp> | <code cpp> | ||
| // luogu-judger-enable-o2 | // luogu-judger-enable-o2 | ||
| 行 356: | 行 367: | ||
| } | } | ||
| </code> | </code> | ||
| + | </hidden> | ||
| + | |||
| ===== ===== | ===== ===== | ||
| 行 381: | 行 394: | ||
| 模拟，直接从头开始走，转两圈就可以了 | 模拟，直接从头开始走，转两圈就可以了 | ||
| + | <hidden 代码> | ||
| <code cpp> | <code cpp> | ||
| #include<iostream> | #include<iostream> | ||
| 行 437: | 行 451: | ||
| } | } | ||
| </code> | </code> | ||
| + | </hidden> | ||
| ===== 训练实况 ===== | ===== 训练实况 ===== | ||
2020-2021/teams/die_java/front_page_springtraining7.1590799886.txt.gz · 最后更改: 2020/05/30 08:51 由 fyhssgss
