也较简单的养老场，纯粹当做把这几个题补上来打的。
A. ストーブ
难度：$\bigstar$
题目大意：
给定 $n$ 个递增的数 $T_1,\ldots,T_n$，你需要选择至多 $k$ 个区间使得它们的并包含所有 $[T_i,T_i+1]$，求区间长度和的最小值。
$1\leq n\leq 10^5$
题目解法：
先选所有 $[T_i,T_i+1]$，如果 $n>k$ 则再按照 $T_i-T_{i-1}$ 排序合并一些区间。
时间复杂度为 $O(n\log n)$。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| #include <bits/stdc++.h>
using namespace std;
const int MAXN=100010;
int n,k,ans,t[MAXN],x[MAXN];
int main () {
scanf("%d%d",&n,&k);
for (int i=1;i<=n;i++) {
scanf("%d",&t[i]);
if (i>1) {x[i-1]=t[i]-t[i-1]-1;}
}
sort(x+1,x+n);
ans=n;
for (int i=1;i<=n-k;i++) {ans+=x[i];}
printf("%d\n",ans);
return 0;
}
|
B. 美術展
难度：$\bigstar$
题目大意：
有 $n$ 个美术品，每个美术品有价值 $B_i$ 和尺寸 $A_i$，你需要选择一个美术品的集合 $S$ 使得其中价值之和减去尺寸极差最大。
$2\leq n\leq 5\times 10^5$
题目解法：
将美术品按照 $A$ 排序，设 $C_i=\sum\limits_{j\leq i} B_j-A_i, D_i=A_i-\sum\limits_{j<i}B_j$，那么我们就是要选择 $l\leq r$ 使得 $C_r+D_l$ 最大，直接做即可。
时间复杂度为 $O(n\log 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
| #include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=500010;
struct P {
ll a,b;
}p[MAXN];
int n;
ll mx,ans,sm[MAXN],sa[MAXN],sb[MAXN];
bool cmp (P a,P b) {return a.a<b.a;}
int main () {
scanf("%d",&n);
for (int i=1;i<=n;i++) {scanf("%lld%lld",&p[i].a,&p[i].b);}
sort(p+1,p+n+1,cmp);
mx=ans=-1e18;
for (int i=1;i<=n;i++) {
sm[i]=sm[i-1]+p[i].b;
sa[i]=p[i].a-sm[i-1],sb[i]=sm[i]-p[i].a;
mx=max(mx,sa[i]);
ans=max(ans,mx+sb[i]);
}
printf("%lld\n",ans);
return 0;
}
|
C. 団子職人
难度：$\bigstar\bigstar$
题目大意：
给定 $n\times m$ 的由 $\texttt{R,G,W}$ 构成的矩阵，你每次可以取走从上到下连续或从左到右连续且分别为 $\texttt{R,G,W}$ 的三个元素，一个位置不能重复取，求最多能取几次。
$1\leq n,m\leq 3000$
题目解法：
将贡献都算在中间的 $\texttt{G}$ 上，我们预处理每个 $\texttt{G}$ 上下和左右分别是否符合可以取的条件。
我们发现，两个可以取的三元组不能同时取，仅当它们对应的两个 $\texttt{G}$ 是在同一条平行副对角线的直线上，所以对每个这样的直线 DP，再把结果相加即可。
时间复杂度为 $O(nm)$。
代码
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
| #include <bits/stdc++.h>
using namespace std;
const int MAXN=6010;
int n,m,ans,mp[MAXN][MAXN],ud[MAXN][MAXN],lr[MAXN][MAXN],dp[MAXN][3];
char c[MAXN];
int calc (int x) {
memset(dp,0,sizeof(dp));
for (int i=1;i<=x;i++) {
dp[i][0]=max(dp[i-1][0],max(dp[i-1][1],dp[i-1][2]));
if (ud[i][x-i+1]) {dp[i][1]=max(dp[i-1][0],dp[i-1][1])+1;}
if (lr[i][x-i+1]) {dp[i][2]=max(dp[i-1][0],dp[i-1][2])+1;}
}
return max(dp[x][0],max(dp[x][1],dp[x][2]));
}
int main () {
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++) {
scanf("%s",c+1);
for (int j=1;j<=m;j++) {mp[i][j]=(c[j]=='R'?0:(c[j]=='G'?1:2));}
}
for (int i=1;i<=n;i++) {
for (int j=1;j<=m;j++) {
if (i>=2&&i<=n-1&&mp[i][j]==1&&mp[i-1][j]==0&&mp[i+1][j]==2) {ud[i][j]=1;}
if (j>=2&&j<=m-1&&mp[i][j]==1&&mp[i][j-1]==0&&mp[i][j+1]==2) {lr[i][j]=1;}
}
}
for (int i=1;i<=n+m-1;i++) {ans+=calc(i);}
printf("%d\n",ans);
return 0;
}
|
D. 定期券
难度：$\bigstar\bigstar$
题目大意：
给定 $n$ 个点 $m$ 条边的边带权无向图和其中四个点 $s,t,u,v$，你可以选择一条 $s\to t$ 的带权最短路，把其上所有边权改为 $0$，求修改后 $u\to v$ 带权最短路的最小值。
$2\leq n\leq 10^5, 1\leq m\leq 2\times 10^5$
题目解法：
求出 $s$ 出发的最短路 DAG，我们可以选择这个 DAG 上一条 $s\to t$ 的路径将边权改为 $0$。
考虑新图中 $u\to v$ 的最短路，一种情况是没有经过边权改为 $0$ 的边，也就是说等于原图中 $u\to v$ 的最短路；另一种情况是经过了边权改为 $0$ 的边，那么显然经过的边权为 $0$ 的边在 $u\to v$ 最短路以及 $s\to t$ 最短路上都是连续一段，我们只要知道段端点就可以确定答案。
而这可以在 DAG 上拓扑排序 DP 得到，对于点 $a,b$，如果在 DAG 上 $a\to b\to t$ 可达，那么 $dis(u,a)+dis(v,b)$ 和 $dis(v,a)+dis(u,b)$ 就是候选答案。
时间复杂度为 $O(m\log 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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
| #include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=100010;
int n,m,s,t,u,v,x,y,z,in[MAXN],vis[MAXN];
ll ans,dis[MAXN],d1[MAXN],d2[MAXN],d3[MAXN],d4[MAXN],dp[MAXN][4];
vector < pair<int,int> > e[MAXN];
vector <int> ou[MAXN];
void dijk (int x) {
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
dis[x]=0;
priority_queue < pair<ll,int> > q;
q.push(make_pair(0,x));
while (q.size()) {
pair<ll,int> a=q.top();
q.pop();
if (vis[a.second]) {continue;}
vis[a.second]=1;
int len=e[a.second].size();
for (int i=0;i<len;i++) {
if (dis[e[a.second][i].first]>dis[a.second]+e[a.second][i].second) {
dis[e[a.second][i].first]=dis[a.second]+e[a.second][i].second;
q.push(make_pair(-dis[e[a.second][i].first],e[a.second][i].first));
}
}
}
return;
}
int main () {
scanf("%d%d%d%d%d%d",&n,&m,&s,&t,&u,&v);
for (int i=1;i<=m;i++) {
scanf("%d%d%d",&x,&y,&z);
e[x].push_back(make_pair(y,z));
e[y].push_back(make_pair(x,z));
}
dijk(s);
for (int i=1;i<=n;i++) {d1[i]=dis[i];}
dijk(t);
for (int i=1;i<=n;i++) {d2[i]=dis[i];}
dijk(u);
for (int i=1;i<=n;i++) {d3[i]=dis[i];}
dijk(v);
for (int i=1;i<=n;i++) {d4[i]=dis[i];}
for (int i=1;i<=n;i++) {
int len=e[i].size();
for (int j=0;j<len;j++) {
if (d1[e[i][j].first]==d1[i]+e[i][j].second) {
ou[i].push_back(e[i][j].first);
in[e[i][j].first]++;
}
}
}
queue <int> q;
for (int i=1;i<=n;i++) {
if (in[i]==0) {q.push(i);}
}
memset(dp,0x3f,sizeof(dp));
ans=d3[v];
while (q.size()) {
int a=q.front();
q.pop();
dp[a][0]=0,dp[a][1]=min(dp[a][1],d3[a]),dp[a][2]=min(dp[a][2],d4[a]);
dp[a][3]=min(dp[a][3],min(dp[a][1]+d4[a],dp[a][2]+d3[a]));
int len=ou[a].size();
for (int i=0;i<len;i++) {
dp[ou[a][i]][1]=min(dp[ou[a][i]][1],dp[a][1]);
dp[ou[a][i]][2]=min(dp[ou[a][i]][2],dp[a][2]);
dp[ou[a][i]][3]=min(dp[ou[a][i]][3],dp[a][3]);
if (--in[ou[a][i]]==0) {q.push(ou[a][i]);}
}
}
printf("%lld\n",min(ans,dp[t][3]));
return 0;
}
|
E. 毒蛇の脱走
难度：$\bigstar\bigstar$
题目大意：
给定 $n$ 和序列 $a_0,\ldots,a_{2^n-1}$，还有 $q$ 次询问，每次给定包含 $0,1,\texttt{?}$ 的字符串 $S$，问将 $S$ 中的 $\texttt{?}$ 换成 $0,1$ 中的任何一个，将其看作二进制数 $x$，对所有可能的结果对应的 $a_x$ 求和。
$1\leq n\leq 20, 1\leq q\leq 10^6$
题目解法：
这题目太老了，见过好多次。
设 $S$ 中 $0,1,\texttt{?}$ 的个数分别为 $a,b,c$。
算法一：暴力将每个 $\texttt{?}$ 换成 $0$ 或 $1$ 求和，时间复杂度 $O(2^c)$。
算法二：对 $0$ 容斥，也就是写成 $s(0)=s(\texttt{?})-s(1)$ 的形式，将每个 $0$ 换成 $\texttt{?}$ 和 $1$，而对于只有 $\texttt{?}$ 和 $1$ 的情况可以直接预处理高维后缀和后计算，时间复杂度 $O(2^a)$。
算法三：对 $1$ 容斥，过程同上，用高维前缀和计算，时间复杂度 $O(2^b)$。
选取最优的算法，单次询问时间复杂度 $O(\min(2^a,2^b,2^c))$，而由于 $a+b+c=n$ 所以我们有 $\min(a,b,c)\leq \dfrac{n}{3}$，加上高维前后缀和的复杂度，总的时间复杂度为 $O(q2^{\frac{n}{3}}+n\times 2^n)$。
Bonus：https://www.luogu.com.cn/problem/P6562
代码
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
| #include <bits/stdc++.h>
using namespace std;
const int MAXN=1200010;
int l,q,ans,cnt0,cnt1,cntq,sz0,sz1,cq[30],c0[30],c1[30],a[MAXN],b[MAXN],c[MAXN];
char t[30],s[MAXN];
void dfsq (int x,int msk) {
if (x==cntq+1) {ans+=a[msk];return;}
dfsq(x+1,msk);
dfsq(x+1,msk|(1<<cq[x]));
return;
}
void dfs0 (int x,int flg,int msk) {
if (x==cnt0+1) {ans+=c[msk]*flg;return;}
dfs0(x+1,flg,msk);
dfs0(x+1,-flg,msk|(1<<c0[x]));
return;
}
void dfs1 (int x,int flg,int msk) {
if (x==cnt1+1) {ans+=b[msk]*flg;return;}
dfs1(x+1,flg,msk|(1<<c1[x]));
dfs1(x+1,-flg,msk);
return;
}
int main () {
scanf("%d%d%s",&l,&q,s+1);
for (int i=0;i<(1<<l);i++) {a[i]=b[i]=c[i]=s[i+1]-'0';}
for (int i=1;i<(1<<l);i<<=1) {
for (int j=0;j<(1<<l);j+=(i<<1)) {
for (int k=0;k<i;k++) {b[i+j+k]+=b[j+k];}
}
}
for (int i=1;i<(1<<l);i<<=1) {
for (int j=0;j<(1<<l);j+=(i<<1)) {
for (int k=0;k<i;k++) {c[j+k]+=c[i+j+k];}
}
}
for (int i=1;i<=q;i++) {
scanf("%s",t+1);
for (int i=1;i<=l/2;i++) {swap(t[i],t[l-i+1]);}
cnt0=0,cnt1=0,cntq=0,sz0=0,sz1=0;
for (int i=0;i<l;i++) {
if (t[i+1]=='0') {c0[++cnt0]=i;}
else if (t[i+1]=='1') {c1[++cnt1]=i,sz1|=(1<<i);}
else {cq[++cntq]=i,sz0|=(1<<i);}
}
ans=0;
if (cntq<=6) {dfsq(1,sz1);}
else if (cnt0<=6) {dfs0(1,1,sz1);}
else {dfs1(1,1,sz0);}
printf("%d\n",ans);
}
return 0;
}
|