打 * 号表示没有写的题，基本上是暂时没来得及写。
A. とてもたのしい家庭菜園 4
难度：$\bigstar$
题目大意：
给定长度为 $n$ 的序列 $a_1,\ldots,a_n$，每次操作可以给一个区间加上 $1$，求最少要多少次操作可以使得 $a$ 变为严格单峰的。
$2\leq n\leq 2\times 10^5$
题目解法：
严格单峰等价于差分序列 $c_1,\ldots,c_{n-1}$前一部分为正，后一部分为负。
一次操作可以将差分序列中一个靠前的位置加 $1$，靠后的位置减 $1$，因此我们可以枚举峰的位置，将差分序列两边需要加/减的次数取最大值即可，这可以通过统计 $\max(0,1-c_i)$ 的前缀和以及 $\max(0,c_i+1)$ 的后缀和求出。
时间复杂度为 $O(n)$。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| #include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=200010;
ll n,ans,a[MAXN],pre[MAXN],suf[MAXN];
int main () {
scanf("%lld",&n);
for (int i=1;i<=n;i++) {scanf("%lld",&a[i]);}
for (int i=1;i<=n-1;i++) {a[i]=a[i+1]-a[i];}
for (int i=1;i<=n-1;i++) {pre[i]=pre[i-1]+max(0ll,1-a[i]);}
for (int i=n-1;i>=1;i--) {suf[i]=suf[i+1]+max(0ll,a[i]+1);}
ans=1e18;
for (int i=1;i<=n;i++) {ans=min(ans,max(pre[i-1],suf[i]));}
printf("%lld\n",ans);
return 0;
}
|
B. 雪玉
难度：$\bigstar$
题目大意：
数轴上有 $n$ 个雪球，初始位置为 $x_1<\ldots<x_n$，接下来依次进行 $q$ 个操作，第 $i$ 个操作为将所有雪球同时向左/向右移动 $w_i$ 距离。
每一个单位长度上有一单位质量的雪，雪球滚过这一单位长度后就会带走其上的雪，求每个雪球在全过程中的质量增加量。
$1\leq n,q\leq 2\times 10^5$
题目解法：
显然每个雪球滚过的雪是一段区间，只要求出其左右端点即可。
执行前 $i$ 个操作后初始位置为 $x$ 的雪球曾经经过的位置设为 $[x-l_i,x+r_i]$，那么我们对于每个 $i$ 找到最大的 $j$ 使得 $x_i+r_j<x_{i+1}-l_j$，这说明前 $j$ 个操作中 $i$ 和 $i+1$ 两个雪球没有到达公共的区域，但第 $j+1$ 次操作时它们经过的区域就有交了，我们可以通过 $j$ 来算出 $i$ 滚过的雪的右端点和 $i+1$ 滚过的雪的左端点。
而这个 $j$ 是可以二分的，时间复杂度为 $O(n\log q+q)$。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| #include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=200010;
ll n,q,x[MAXN],s[MAXN],mx[MAXN],mn[MAXN],xl[MAXN],xr[MAXN];
int main () {
scanf("%lld%lld",&n,&q);
for (int i=1;i<=n;i++) {scanf("%lld",&x[i]);}
for (int i=1;i<=q;i++) {
scanf("%lld",&s[i]);
s[i]+=s[i-1];
mx[i]=max(mx[i-1],s[i]);
mn[i]=min(mn[i-1],s[i]);
}
xl[1]=x[1]+mn[q],xr[n]=x[n]+mx[q];
for (int i=1;i<=n-1;i++) {
if (x[i]+mx[q]<x[i+1]+mn[q]) {
xr[i]=x[i]+mx[q],xl[i+1]=x[i+1]+mn[q];
continue;
}
int l=0,r=q;
while (l<r) {
int mid=(l+r+1)>>1;
if (x[i]+mx[mid]<x[i+1]+mn[mid]) {l=mid;}
else {r=mid-1;}
}
if (s[l+1]-s[l]>0) {xr[i]=xl[i+1]=x[i+1]+mn[l];}
else {xr[i]=xl[i+1]=x[i]+mx[l];}
}
for (int i=1;i<=n;i++) {printf("%lld\n",xr[i]-xl[i]);}
return 0;
}
|
C. 集合写真
难度：$\bigstar$
题目大意：
给定 $1,\ldots,n$ 的排列 $p_1,\ldots,p_n$，每次操作可以交换相邻两个元素，问最少要多少次操作可以使得 $p_i<p_{i+1}+2$。
$3\leq n\leq 5000$
题目解法：
显然操作次数就是前后相对的逆序对数，同时不难发现最后的排列是首先把 $1,\ldots,n$ 划分成若干连续段，再把每一段反序。
设 $dp(i)$ 表示将 $1,\ldots,i$ 分段，只考虑这些段中数的逆序对数量最小值，那么考虑加入 $[l,r]$ 这一段造成的贡献，也就是：
- 原排列中某个 $x\in [l,r]$ 在 $y\in [1,l-1]$ 之前：暴力求出 $f(i,j)$ 表示原排列排在 $i$ 后面的 $<j$ 的数有多少个即可；
- 原排列中某个 $x\in [l,r]$ 在 $y\in [l,r], y>x$ 之前：求出原排列所有顺序对再二维前缀和。
时间复杂度为 $O(n^2)$。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| #include <bits/stdc++.h>
using namespace std;
const int MAXN=5010;
int n,a[MAXN],nw[MAXN],dp[MAXN],sum[MAXN][MAXN],cnt[MAXN][MAXN];
int main () {
scanf("%d",&n);
for (int i=1;i<=n;i++) {scanf("%d",&a[i]);}
for (int i=n;i>=1;i--) {
for (int j=1;j<=a[i]-1;j++) {cnt[a[i]][j]=nw[j];}
for (int j=a[i];j<=n;j++) {nw[j]++;}
for (int j=i-1;j>=1;j--) {
if (a[j]<a[i]) {sum[a[j]][a[i]]++;}
}
}
for (int i=n;i>=1;i--) {
for (int j=i+2;j<=n;j++) {sum[i][j]+=sum[i][j-1]+sum[i+1][j]-sum[i+1][j-1];}
}
memset(dp,0x3f,sizeof(dp));
dp[0]=0;
for (int i=0;i<=n;i++) {
int w=0;
for (int j=i+1;j<=n;j++) {
w+=cnt[j][i];
dp[j]=min(dp[j],dp[i]+w+sum[i+1][j]);
}
}
printf("%d\n",dp[n]);
return 0;
}
|
D. ロボット
难度：$\bigstar\bigstar$
题目大意：
给定 $n$ 个点 $m$ 条边，边有权值和颜色的无向图，改变一条边需要一定的代价，求最少要付出多少代价，使得存在一条 $1\to n$ 的路径 $1=x_1\to \ldots\to x_m=n$ 使得对于任意 $x_i$ 都不存在一条不同于 $x_i\to x_{i+1}$ 的邻边与 $x_i\to x_{i+1}$ 同色。
$2\leq n\leq 10^5, 1\leq m\leq 2\times 10^5$
题目解法：
设某个点的所有邻边有 $k$ 种不同的颜色 $t_1,\ldots,t_k$，将该点拆成 $k+1$ 个点 $p_1,\ldots,p_{k+1}$，其中 $p_i (i\leq k)$ 表示要选择一条颜色为 $t_i$ 的出边且不改变其颜色，而 $p_{k+1}$ 表示选择的出边改变了颜色，根据上述定义建图求最短路即可。
注意对于 $p_1,\ldots,p_k$ 需要建立一个汇聚点 $P_i$ 以压缩边数。
时间复杂度为 $O(m\log n+n)$。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| #include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=600010;
int n,m,tot,x[MAXN],y[MAXN],w[MAXN],z[MAXN],vis[MAXN];
ll sum[MAXN],dis[MAXN];
vector < pair<int,ll> > v[MAXN];
vector <int> cl[MAXN];
map < pair<int,int>,int > mp;
priority_queue < pair<ll,int> > q;
int main () {
scanf("%d%d",&n,&m);
tot=2*n;
for (int i=1;i<=m;i++) {
scanf("%d%d%d%d",&x[i],&y[i],&w[i],&z[i]);
v[x[i]].push_back(make_pair(y[i],z[i]));
v[x[i]].push_back(make_pair(y[i]+n,z[i]));
v[y[i]].push_back(make_pair(x[i],z[i]));
v[y[i]].push_back(make_pair(x[i]+n,z[i]));
if (mp.find(make_pair(y[i],w[i]))==mp.end()) {
mp[make_pair(y[i],w[i])]=++tot;cl[y[i]].push_back(tot);
}
if (mp.find(make_pair(x[i],w[i]))==mp.end()) {
mp[make_pair(x[i],w[i])]=++tot;cl[x[i]].push_back(tot);
}
sum[mp[make_pair(y[i],w[i])]]+=z[i];
sum[mp[make_pair(x[i],w[i])]]+=z[i];
}
for (int i=1;i<=m;i++) {
int tmp=mp[make_pair(y[i],w[i])];
v[x[i]].push_back(make_pair(tmp,0));
v[tmp].push_back(make_pair(x[i],sum[tmp]-z[i]));
v[tmp].push_back(make_pair(x[i]+n,sum[tmp]-z[i]));
tmp=mp[make_pair(x[i],w[i])];
v[y[i]].push_back(make_pair(tmp,0));
v[tmp].push_back(make_pair(y[i],sum[tmp]-z[i]));
v[tmp].push_back(make_pair(y[i]+n,sum[tmp]-z[i]));
}
for (int i=1;i<=n;i++) {
int len=cl[i].size();
for (int j=0;j<len;j++) {v[i+n].push_back(make_pair(cl[i][j],0));}
}
memset(dis,0x3f,sizeof(dis));
dis[1]=dis[n+1]=0;
q.push(make_pair(0,1)),q.push(make_pair(0,n+1));
while (q.size()) {
pair <ll,int> a=q.top();
q.pop();
if (vis[a.second]) {continue;}
vis[a.second]=1;
int len=v[a.second].size();
for (int i=0;i<len;i++) {
if (dis[v[a.second][i].first]>dis[a.second]+v[a.second][i].second) {
dis[v[a.second][i].first]=dis[a.second]+v[a.second][i].second;
q.push(make_pair(-dis[v[a.second][i].first],v[a.second][i].first));
}
}
}
if (dis[n]==0x3f3f3f3f3f3f3f3f) {printf("-1\n");}
else {printf("%lld\n",dis[n]);}
return 0;
}
|
*E. ダンジョン 3
难度：$\bigstar\bigstar\bigstar$
题目大意：
地牢有 $n+1$ 层，第 $i$ 层到第 $i+1$ 层需要付出 $a_i$ 能量，第 $i$ 层中可以花费 $b_i$ 金币恢复 $1$ 能量（可以同一层多次恢复），有 $m$ 个询问，每个询问给定 $s,t,u$，求能力上限为 $u$ 的情况下从第 $s$ 层走到第 $t$ 层所需要的最小金币数量（或报告无解）。
$1\leq n,m\leq 2\times 10^5$
题目解法：
首先考虑 $t=n+1$ 的情况，这是比较简单的，对于某个 $s\leq i\leq t$，设 $j$ 是满足 $s\leq j<i$ 且 $b_j\leq b_i$ 的最大数，$k$ 是满足 $i<k\leq t$ 且 $b_k<b_i$ 的最小数，再设 $D_1,D_2$ 分别为 $j\to i, i\to k$ 需要付出的能量之和，那么：
- 假如要从 $i$ 恢复能量，那么在 $j$ 处时能量必须是满的（否则可以在 $j$ 处恢复），所以 $i$ 处恢复能量不会超过 $D_1$；
- 经过 $i$ 后到达 $k$ 时能量一定为零（否则可以少恢复一点），所以 $i$ 处恢复能量不会超过 $D_2$，也不会超过 $D_1+D_2-u$；
- 不能超过能量上限，所以 $i$ 处恢复能量不会超过 $u$。
综上，$i$ 处恢复能量的值是关于 $u$ 的线性分段函数。
于是我们考虑倒序扫描 $s$，计算每个 $u$ 的答案，在维护单调栈的基础上，根据上面的分析可以通过区间加等差数列的线段树进行维护。
再考虑 $t<n+1$ 的情况，感觉这才是真正的难点：我们可以找到距离 $t$ 不超过 $u$ 的 $b$ 最小的位置 $x$，则到达 $t$ 时最后一部分能量一定是在 $x$ 这里恢复的，那么 $s\to t$ 的答案就相当于 $s\to n+1$ 减去 $x\to n+1$ 再加上 $x\to t$ 这部分只用 $x$ 的代价。
时间复杂度为 $O((n+m)\log n)$。