一眼前缀DP+后缀DP，中间枚举之后用某种数据结构处理出来区间最值
然后选择了复杂度多了个log并常数非常大的线段树，写起来很麻烦，但debug时间不是很长，好在还是卡过去了
不知道是gym的机子太垃，还是我实现的太垃，但总之是过了
以下放置两个代码，一个我的，一个dls的
请越过我的答辩，欣赏dls的简洁的高手做法
下面是我的答辩
复制代码
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160#include<bits/stdc++.h> using namespace std; using ll=long long; const ll init_val=1e18; const int N=5e5+10; struct segment { struct Node { int l,r; ll val; bool is_dot(){return l==r;} int mid(){return l+r>>1;} bool in(int L,int R){return (L<=l)&&(r<=R);} }tr[N<<2]; void build(int u,int l,int r) { tr[u]={l,r,init_val}; if(l==r)return ; int mid=l+r>>1; build(u<<1,l,mid),build(u<<1|1,mid+1,r); } void pushup(int u) { if(tr[u].is_dot())return ; tr[u].val=min(tr[u<<1].val,tr[u<<1|1].val); } ll query(int u,int l,int r) { Node &rt=tr[u]; if(rt.in(l,r)){return tr[u].val;} int mid=rt.mid(); ll rs=init_val; if(l<=mid)rs=min(rs,query(u<<1,l,r)); if(r>mid)rs=min(rs,query(u<<1|1,l,r)); return rs; } void update(int u,int pos,ll val) { Node &rt=tr[u]; if(rt.is_dot()){rt.val=val;return ;} int mid=rt.mid(); if(pos<=mid)update(u<<1,pos,val); else update(u<<1|1,pos,val); pushup(u); } }pr_seg,sf_seg; ll pr_dp[N],sf_dp[N]; int a[N],pr[N],sf[N]; ll f[N][22],g[N][22]; char str[N]; int lg[N]; ll query2(int l,int r) { int p=lg[r-l+1]; return min(g[l][p],g[r-(1<<p)+1][p]); } ll calc(int l,int r,int p,int n,int k) { ll rs=1e18; for(int i=r;i>=l;--i) { if(sf[i]-i<=k){rs=min(pr_dp[i]+sf_dp[sf[i]],rs);} else if(p+1<=min(i+k,n)) rs=min(pr_dp[i]+query2(p+1,min(i+k,n)),rs); if(str[i]=='1')break; } return rs; } void solve() { int n,k;scanf("%d%d",&n,&k); n+=2; for(int i=2;i<n;++i)scanf("%d",&a[i]); a[1]=a[n]=0; scanf("%s",str+2);str[1]=str[n]='1';str[n+1]=0; // pre_DP pr[1]=1; for(int i=2;i<=n;++i) { if(str[i-1]=='1')pr[i]=i-1; else pr[i]=pr[i-1]; } pr_seg.build(1,1,n); pr_seg.update(1,1,0); pr_dp[1]=0; for(int i=2;i<=n;++i) { if(i-pr[i]<=k) { pr_dp[i]=pr_dp[pr[i]]+a[i]; } else { int l=max(i-k,1); pr_dp[i]=pr_seg.query(1,l,i-1)+a[i]; } pr_seg.update(1,i,pr_dp[i]); } //suf_DP sf[n]=n; for(int i=n-1;i;--i) { if(str[i+1]=='1')sf[i]=i+1; else sf[i]=sf[i+1]; } sf_seg.build(1,1,n); sf_dp[n]=0;sf_seg.update(1,n,0); for(int i=n-1;i;--i) { if(sf[i]-i<=k) { sf_dp[i]=sf_dp[sf[i]]+a[i]; } else { int r=min(n,i+k); sf_dp[i]=a[i]+sf_seg.query(1,i+1,r); } sf_seg.update(1,i,sf_dp[i]); } //st表 // init st for(int i=1;i<=n;++i)f[i][0]=pr_dp[i]; for(int j=1;j<=20;++j) for(int i=1;i+(1<<j)-1<=n;++i) f[i][j]=min(f[i][j-1],f[i+(1<<j-1)][j-1]); for(int i=1;i<=n;++i)g[i][0]=sf_dp[i]; for(int j=1;j<=20;++j) for(int i=1;i+(1<<j)-1<=n;++i) g[i][j]=min(g[i][j-1],g[i+(1<<j-1)][j-1]); int q;scanf("%d",&q); while(q--) { int p,v;scanf("%d%d",&p,&v);++p; if(str[p]=='1'){printf("%lldn",pr_dp[n]+v-a[p]);continue;} ll rs=v; if(p-pr[p]<=k)rs+=pr_dp[pr[p]]; else { rs+=pr_seg.query(1,p-k,p-1); } if(sf[p]-p<=k)rs+=sf_dp[sf[p]]; else { rs+=sf_seg.query(1,p+1,p+k); } printf("%lldn",min(calc(max(1,p-k+1),p-1,p,n,k),rs)); } } int main() { lg[0]=-1; for(int i=1;i<N;i++)lg[i]=lg[i/2]+1; int T;scanf("%d",&T); while(T--)solve(); }
以下是dls的优秀做法
复制代码
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
78
79
80
81
82
83
84
85
86
87#include <bits/stdc++.h> using namespace std; #define rep(i,a,n) for (int i=a;i<n;i++) #define per(i,a,n) for (int i=n-1;i>=a;i--) #define pb push_back #define eb emplace_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define fi first #define se second #define SZ(x) ((int)(x).size()) typedef vector<int> VI; typedef basic_string<int> BI; typedef long long ll; typedef pair<int,int> PII; typedef double db; mt19937 mrand(random_device{}()); const ll mod=1000000007; int rnd(int x) { return mrand() % x;} ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;} // head const int N=501000; ll dp[N],dpr[N],tmp[N]; char s[N]; int n,k,a[N],q[N]; void solve() { scanf("%d%d",&n,&k); for (int i=1;i<=n;i++) scanf("%d",&a[i]); scanf("%s",s+1); int h=0,t=-1; dp[0]=0; q[++t]=0; a[0]=a[n+1]=0; rep(i,1,n+2) { while (h<=t&&i-q[h]>k) ++h; dp[i]=a[i]+dp[q[h]]; if (s[i]=='1') while (h<=t) ++h; while (h<=t&&dp[i]<dp[q[t]]) --t; q[++t]=i; //printf("%d %lldn",i,dp[i]); } dpr[n+1]=0; h=0; t=-1; q[++t]=n+1; per(i,0,n+1) { while (h<=t&&q[h]-i>k) ++h; dpr[i]=a[i]+dpr[q[h]]; if (s[i]=='1') while (h<=t) ++h; while (h<=t&&dpr[i]<dpr[q[t]]) --t; q[++t]=i; //printf("val %d %lldn",i,dpr[i]); //rep(c,h,t+1) printf("%d ",q[c]); puts(""); } int Q; scanf("%d",&Q); rep(_,0,Q) { int p,v; scanf("%d%d",&p,&v); int L=max(p-k,0); h=0; t=-1; rep(j,L,p) { tmp[j]=dp[j]; if (s[j]=='1') while (h<=t) ++h; while (h<=t&&tmp[j]<tmp[q[t]]) --t; q[++t]=j; } int R=min(p+k,n+1); ll ans=1ll<<60; rep(j,p,R+1) { while (h<=t&&j-q[h]>k) ++h; tmp[j]=(j==p?v:a[j])+tmp[q[h]]; ans=min(ans,tmp[j]+dpr[j]-a[j]); if (s[j]=='1') while (h<=t) ++h; while (h<=t&&tmp[j]<tmp[q[t]]) --t; q[++t]=j; } printf("%lldn",ans); } } int _; int main() { for (scanf("%d",&_);_;_--) { solve(); } }
最后
以上就是迅速火龙果最近收集整理的关于2022 ICPC南京 B的全部内容，更多相关2022内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复