<head> <script src="https://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML" type="text/javascript"></script> <script type="text/x-mathjax-config"> MathJax.Hub.Config({ tex2jax: { skipTags: ['script', 'noscript', 'style', 'textarea', 'pre'], inlineMath: [['$','$']] } }); </script> </head>
08-02 题解
A
首先, 这题的 dp 不满足四边形不等式, 这告诉我们猜决策单调性的时候多打几个样例看看(不过这么着过了是真抽象)
朴素的想法
题意转化:
如果每份伤害为 \(i\), 你能打败 \(defeat_i\) 个怪物, 求选出 \(n\) 个 \(i\) 使得他们的和为 \(m\) , \(\sum_{i \in S} defeat_i\) 最大, 输出 \(n - \frac{\sum_{i \in S} defeat_i}{n}\)
设 \(f(x, y)\) 表示选了 \(x\) 个 \(i\), \(i\) 的和为 \(y\), \(\sum defeat\)的最大值为 \(f(x, y)\)
这样转移是 \(nm^2\) 的
考虑怎么优化
方法1: max+ 卷积
何为 max+ 卷积 ?
形如本题的转移式
dp[i][j] = max(dp[i - 1][k] + defeat[j - k]), 即外层为 max 操作, 内层为 + 操作
max+ 卷积有什么好的性质?
他是符合结合律的
感性理解一下, dp[i][j] 里面先加入了 2 个defeat, 再加了 1 个, 这和先 1 后 2 的最优答案是一样的
(上述内容可结合 01 背包理解 : 背包的最终答案和物品放入顺序无关)
这样的性质就让我们可以倍增的去做
类似快速幂地, defeat 数组相当于底数, dp 数组相当于 ans
然后就做完了, 代码实现不难
方法2: 剪枝
设当前加进去的攻击值为 \(x\)
如果把 \(x\) 从大往小加进去, 那么 当前已经选的份数 \(i \le \lfloor \frac{m}{i} \rfloor\)
所以对于 \(x \in [0, m]\) , \(i\) 的循环次数 \(\sum_i = \lfloor \frac{m}{1} \rfloor + \lfloor \frac{m}{2} \rfloor + ... + \lfloor \frac{m}{m} \rfloor\)
这是个调和级数, 所以枚举 \(i\) 一共 \(m\ log\ m\)次, 总复杂度是 \(O(m^2 + m\ log\ m)\) (我分析的对吗? 感觉有 bug)
然后就过了
代码
方法一
#include <bits/stdc++.h>
#define int long long
#define double long double
#pragma optimize(3)
using namespace std;
const int N = 1e3 + 10, M = 5e3 + 10;
int n, m;
int a[N];
double dp[M], defeat[M];
void Max_Plus(int ti){
while(ti){
if(ti & 1){
for(int i = m; i >= 0; i--){
dp[i] += defeat[0];
for(int j = 1; j <= i; j++){
dp[i] = max(dp[i], dp[i - j] + defeat[j]);
}
}
}
ti >>= 1;
for(int i = m; i >= 0; i--){
defeat[i] += defeat[0];
for(int j = 1; j < i; j++){ //每个 i 只能卷一次 0
defeat[i] = max(defeat[i], defeat[i - j] + defeat[j]);
}
}
}
}
signed main(){
cin >> n >> m;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
for(int i = 0; i <= m; i++){
for(int j = 1; j <= n; j++){
defeat[i] += (a[j] <= i);
}
}
Max_Plus(n);
double ans = n - 1.0 * dp[m] / n;
printf("%.10Lf\n", ans);
}
方法二
#include <bits/stdc++.h>
#pragma optimize(3)
using namespace std;
const int N = 1e3 + 10, M = 5e3 + 10;
int n, m;
int a[N];
int dp[M][N], defeat[M];
signed main(){
cin >> n >> m;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
for(int i = 0; i <= m; i++){
for(int j = 1; j <= n; j++){
defeat[i] += (a[j] <= i);
}
}
dp[0][0] = 0;
for(int i = m; i >= 0; i--){
for(int j = 0; j <= m; j++){
for(int k = 1; k <= ((i == 0) ? n : min(n, m / i)); k++){
if(j < i) continue;
dp[j][k] = max(dp[j][k], dp[j - i][k - 1] + defeat[i]);
}
}
}
double ans = n - 1.0 * dp[m][n] / n;
printf("%.10lf\n", ans);
}
B
这道题和前几天 HackerRank 的那个不同, 本题字典序最小的路径是唯一的, 因为点的编号各不相同
首先, 我们不可能把所有路径存下来, 最劣\(n^2m\) 的空间
因为路径唯一, 即 w 如果在 u, v 的路径上, 那么 (w, v) 是 (u, v) 的一部分, 这说明路径信息是可合并的
所以考虑倍增
设 \(f(i, j, k)\) 为以 \(i\) 为起点, \(j\) 为终点的路径上第 \(2^k\) 个点的编号
\(f(i, j, k) = f(f(i, j, k - 1), j, k - 1)\), 感性理解就好
发现终点 \(j\) 在转移式里是不变的
所以枚举终点 \(j\) , 对于每个 \(i\) , 保留他能到达 \(j\) 的字典序最小的出边, 建反图
这样做能保证走环的情况为-1, 因为在反图上两点根本不可达, 记录一下即可
然后就做完了
代码
#include <bits/stdc++.h>
#pragma optimize(3)
using namespace std;
const int N = 2e3 + 10;
int n, m, q, type;
int u, v, s, t, k;
vector <int> e[N], ee[N];
int f[N][N][12], dis[N][N];
bool vis[N][N];
void Dfs(int x, int id){
vis[id][x] = 1;
for(auto i : e[x]){
if(vis[id][i]) continue;
Dfs(i, id);
}
}
void Dfs2(int x, int id){
for(auto i : ee[x]){
if(i == id) continue;
dis[id][i] = dis[id][x] + 1;
Dfs2(i, id);
}
}
signed main(){
cin >> n >> m >> q >> type;
for(int i = 1; i <= m; i++){
cin >> u >> v;
e[u].push_back(v);
}
for(int i = 1; i <= n; i++){
Dfs(i, i);
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
ee[j].clear();
}
for(int j = 1; j <= n; j++){
int mini = n + 1;
for(auto k : e[j]){
if(vis[k][i]){
mini = min(mini, k);
}
}
if(vis[j][i]){
ee[mini].push_back(j);
f[j][i][0] = mini;
}
}
Dfs2(i, i);
for(int j = 1; j <= 11; j++){
for(int k = 1; k <= n; k++){
f[k][i][j] = f[f[k][i][j - 1]][i][j - 1];
}
}
}
int lstans = 1;
for(int i = 1; i <= q; i++){
cin >> s >> t >> k;
if(type){
s = (s ^ lstans) % n + 1;
t = (t ^ lstans) % n + 1;
k = (k ^ lstans) % n + 1;
}
if(s == t && k == 1){
cout << s << "\n";
lstans = s;
continue;
}
--k;
if(dis[t][s] < k || !dis[t][s]){
cout << "-1\n";
lstans = 1;
continue;
}
for(int j = 11; j >= 0; j--){
if((k >> j) & 1){
s = f[s][t][j];
}
}
lstans = s;
cout << s << "\n";
}
}
C
代码貌似非常麻烦, 不想写, 这里只说一下第一步转化
对于 \(l\), \(r\) 我们肯定要从 \(l\) 走到 \(r\), 在中间出现一些 \(i \to i-1\ \to i\) 的折返, 每一步这样的折返可以使 \(a_i\), \(a_{i + 1}\) 各减少 1
设折返步数数组 \(b_i\), 含义如上
首先对所有 \(a\) 减 1, 这是主线(\(l \to r\)) 的贡献
\(b_l = a_l\)
\(b_i = a_i - b_{i - 1}\)
如果 \(b_r\) 不为 0, 则无解
如果任意 \(i \in [l, r]\), \(b_i < 0\) , 那么也无解
然后你就得到了一种优秀的 \(n^2\) 做法哈哈哈(但是因为数据过水, 你能获得 60 pts 的好成绩)
代码
#include <bits/stdc++.h>
#define int long long
#define double long double
#pragma optimize(3)
using namespace std;
const int N = 1e6 + 10;
int n, q;
int a[N], opt, l, r, x;
int ca[N], b[N];
signed main(){
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
cin >> q;
for(int i = 1; i <= q; i++){
cin >> opt >> l >> r;
if(opt == 1){
cin >> x;
for(int j = l; j <= r; j++){
a[j] += x;
}
}else{
for(int j = l; j <= r; j++){
ca[j] = a[j] - 1;
}
b[l] = ca[l];
for(int j = l + 1; j <= r; j++){
b[j] = ca[j] - b[j - 1];
}
bool f = 1;
for(int j = l; j <= r; j++){
if(b[j] < 0){
f = 0;
break;
}
}
if(b[r] != 0){
f = 0;
}
if(f == 1){
cout << "Yes\n";
}else{
cout << "No\n";
}
}
}
}