AtCoder Beginner Contest 369 题解

rgw2010 Lv1
  2024-09-13 2024-09-13 创建   2024-09-13 19:16:03 2024-09-13 19:16:03 更新      

AtCoder Beginner Contest 369 题解，by @rgw2010

[ABC369C] Count Arithmetic Subarrays

题意：

判断有多少个区间是等差数列（不能重排）。

。

思路：

赛时看错题了，以为这个区间可以重排，卡了 8min，小丑了。

首先容易注意到，对于一个区间 ，若其是等差数列，则这个区间的子区间 肯定也是子序列，造成的贡献是 。

那么考虑求出所有极长等差区间，设 ，若 能加入 的等差区间，当且仅当 ；否则就要新开一个等差子区间。

注意最后答案要加 。

时间复杂度为 。

完整代码：

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
#include<bits/stdc++.h>
#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)
#define lowbit(x) x&(-x)
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define iip pair<pair<ll,ll>,ll>
#define ppii pair<pair<ll,ll>,pair<ll,ll>>
#define fi first
#define se second
#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x
#define Full(A) memset(A,0,sizeof(A))
#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);
#define For(i,l,r) for(int i=l;i<=r;i++)
#define _For(i,l,r) for(int i=r;i>=l;i--)
using namespace std;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
bool Begin;
const int N=2e5+6;
inline ll read(){
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
          f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
inline void write(ll x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9)
	  write(x/10);
	putchar(x%10+'0');
}
ll n,s,ans;
ll a[N],d[N];
int main(){
	n=read();
	For(i,1,n)
	  a[i]=read();
	For(i,1,n)
	  d[i]=a[i+1]-a[i];
	For(i,1,n){
		if(d[i]!=d[i-1]){
			ans+=s*(s+1)/2;
			s=1;
		}
		else
		  s++;		
	}
	ans+=s*(s+1)/2;
	write(ans+n-1);
	return 0;
}

[ABC369D] Bonus EXP

题意：

有 个物品依次从你身边经过，第 个物品的贡献为 。

若你选择的第 个物品是 ：

  • 当 为偶数时：收益为 。

  • 否则收益为 。

问最大收益。

。

思路：

考虑动态规划算法。

注意到当前位置的取值只跟当前取的个数的奇偶性有关，则定义 表示对于前 个物品取的物品个数对 取余的结果为 的最大权值，则状态转移方程为：

最后的答案是 ，时间复杂度为 。

完整代码：

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
#include<bits/stdc++.h>
#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)
#define lowbit(x) x&(-x)
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define iip pair<pair<ll,ll>,ll>
#define ppii pair<pair<ll,ll>,pair<ll,ll>>
#define fi first
#define se second
#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x
#define Full(a) memset(a,0,sizeof(a))
#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);
#define For(i,l,r) for(int i=l;i<=r;i++)
#define _For(i,l,r) for(int i=r;i>=l;i--)
using namespace std;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
bool Begin;
const ll N=2e5+10;
inline ll read(){
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
          f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
inline void write(ll x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9)
	  write(x/10);
	putchar(x%10+'0');
}
ll n;
ll a[N],dp[N][2];
int main(){
	n=read();
	For(i,1,n)
	  a[i]=read();
	dp[1][1]=a[1],dp[1][0]=0;
	For(i,2,n){
		dp[i][0]=max(dp[i-1][1]+a[i]*2,dp[i-1][0]);
		dp[i][1]=max(dp[i-1][0]+a[i],dp[i-1][1]);
	}
	write(max(dp[n][0],dp[n][1]));
	return 0;
}

[ABC369E] Sightseeing Tour

题意：

给定一个 个节点的无向图，共 次询问，每次给定 个必须经过的边，问从 的最短路径是多少。

。

思路：

考虑先求出任意两点的最短路径 ，因为 ，可以使用 Floyd 算法 跑出。

然后对于每组询问，必须要经过编号为 的桥，定义编号为 的桥为 。

同时注意到 非常小，考虑全排列出依次经过哪些桥，同时爆搜是先到达这个桥的左端还是右端即可。

时间复杂度为 。

完整代码：

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
#include<bits/stdc++.h>
#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)
#define lowbit(x) x&(-x)
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define iip pair<pair<ll,ll>,ll>
#define ppii pair<pair<ll,ll>,pair<ll,ll>>
#define fi first
#define se second
#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x
#define Full(a) memset(a,0,sizeof(a))
#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);
#define For(i,l,r) for(int i=l;i<=r;i++)
#define _For(i,l,r) for(int i=r;i>=l;i--)
using namespace std;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
bool Begin;
const ll N=505,M=2e5+10;
inline ll read(){
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
          f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
inline void write(ll x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9)
	  write(x/10);
	putchar(x%10+'0');
}
ll n,m,q,k,x,y,w,ans;
ll a[N],p[N],A[M],B[M],W[M];
ll dis[N][N];
void dfs(ll pos,ll pre,ll sum){
	if(sum>ans)
	  return ;
	if(pos==k+1){
		ans=min(ans,sum+dis[pre][n]);
		return ;
	}
	dfs(pos+1,A[a[p[pos]]],sum+dis[pre][B[a[p[pos]]]]+W[a[p[pos]]]);
	dfs(pos+1,B[a[p[pos]]],sum+dis[pre][A[a[p[pos]]]]+W[a[p[pos]]]);
}
int main(){
	n=read(),m=read();
	For(i,1,n){
		For(j,1,n){
			if(i==j)
			  continue;
			dis[i][j]=1e18;
		}
	}
	For(i,1,m){
		x=read(),y=read(),w=read();
		dis[x][y]=min(dis[x][y],w);
		dis[y][x]=min(dis[y][x],w);
		A[i]=x,B[i]=y,W[i]=w;
	}
	for(int k=1;k<=n;k++)
	  for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		  dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
	q=read();
	while(q--){
		ans=1e18;
		k=read();
		For(i,1,k){
			a[i]=read();
			p[i]=i;
		}
		while(1){
			dfs(1,1,0);
			if(!next_permutation(p+1,p+k+1))
			  break;	
		}
		write(ans);
		putchar('\n');
	}
	return 0;
}

[ABC369F] Gather Coins

题意：

给定一个 的棋牌，有 个位置上有一个棋子，其它位置没有棋子，人每次可以往下或往左走，问从 走到 能收集到的最多的棋子数量。

。

思路：

考虑动态规划，令 表示到达第 个棋子最大权值，则状态转移方程为：

这是二维偏序优化动态规划问题，考虑先按 从小到大排序，若 相同则按 从小到大排序，那么这样对于 ，自然都满足 ，则状态转移方程降了一维：

相当于询问 区间内的最大值，因为需要输出路径，所以我们还需要记录一下最大值的位置，使用线段树维护即可。

时间复杂度为 。

完整代码：

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
#include<bits/stdc++.h>
#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)
#define lowbit(x) x&(-x)
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define iip pair<pair<ll,ll>,ll>
#define ppii pair<pair<ll,ll>,pair<ll,ll>>
#define fi first
#define se second
#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x
#define Full(a) memset(a,0,sizeof(a))
#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);
#define For(i,l,r) for(int i=l;i<=r;i++)
#define _For(i,l,r) for(int i=r;i>=l;i--)
using namespace std;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
bool Begin;
const ll N=2e5+10;
inline ll read(){
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
          f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
inline void write(ll x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9)
	  write(x/10);
	putchar(x%10+'0');
}
struct Node{
	ll x,y;
	bool operator<(const Node&rhs)const{
		if(x^rhs.x)
		  return x<rhs.x;
		return y<rhs.y;
	}
}a[N];
struct St{
	ll l,r;
	ll Max,id;
}X[N<<2];
ll h,w,n,id,cnt,ans;
ll dp[N],pre[N];
string S[N];
void pushup(ll k){
	X[k].Max=max(X[k<<1].Max,X[k<<1|1].Max);
	if(X[k].Max==X[k<<1].Max)
	  X[k].id=X[k<<1].id;
	else
	  X[k].id=X[k<<1|1].id;
}
void build(ll k,ll l,ll r){
	X[k].l=l,X[k].r=r;
	if(l==r)
	  return ;
	ll mid=(l+r)>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
}
void add(ll k,ll i,ll v,ll id){
	if(X[k].l==i&&i==X[k].r){
		if(v>X[k].Max){
			X[k].Max=v;
			X[k].id=id;
		}
		return ;
	}
	ll mid=(X[k].l+X[k].r)>>1;
	if(i<=mid)
	  add(k<<1,i,v,id);
	else
	  add(k<<1|1,i,v,id);
	pushup(k);
}
pi query(ll k,ll l,ll r){
	if(X[k].l==l&&r==X[k].r)
	  return {X[k].Max,X[k].id};
	ll mid=(X[k].l+X[k].r)>>1;
	if(r<=mid)
	  return query(k<<1,l,r);
	else if(l>mid)
	  return query(k<<1|1,l,r);
	else{
		auto x=query(k<<1,l,mid),y=query(k<<1|1,mid+1,r);
		pi ans;
		ans.fi=max(x.fi,y.fi);
		if(ans.fi==x.fi)
		  ans.se=x.se;
		else
		  ans.se=y.se;
		return ans;
	}
}
int main(){
	h=read(),w=read(),n=read();
	a[0]={1,1};
	a[n+1]={h,w};
	For(i,1,n)
	  a[i]={read(),read()};
	build(1,1,w);
	sort(a+1,a+n+1);
	dp[1]=ans=id=1;
	add(1,a[1].y,1,1);
	For(i,2,n){
		auto t=query(1,1,a[i].y);
		dp[i]=t.fi+1;
		pre[i]=t.se;
		add(1,a[i].y,dp[i],i);
		if(dp[i]>ans){
			ans=dp[i];
			id=i;
		}
	}
	pre[n+1]=id;
	id=n+1;
	while(1){
		ll x=pre[id];
		++cnt;
		ll sx=a[x].x,sy=a[x].y,tx=a[id].x,ty=a[id].y;
		For(i,1,tx-sx)
		  S[cnt]+='D';
		For(i,1,ty-sy)
		  S[cnt]+='R';
		id=x;
		if(!x)
		  break;
	}
	write(ans);
	putchar('\n');
	_For(i,1,cnt)
	  for(auto c:S[i])
		putchar(c);
	return 0;
}

[ABC369G] As far as possible

题意：

给定一个 个节点且有边权的树，对于每个 求：

  • 选取 条从根结点出发到叶子结点的简单路径，求这些路径的并集上所有结点的点权之和的最大值。

。

思路：

双倍经验。

明显有一个贪心的思路：

  • 每次取叶子到根的路径权值和最大的。

  • 清空该链上的点的点权。

模拟 次即可，但是复杂度不可取，考虑数据结构优化。

将叶子节点按 dfn 序从小到大编号，令 表示 子树内叶子节点的编号在 间。

每次找到路径权值和最大的那个叶子节点，可以直接暴力跳父亲清空路径上的点，每次清空就是将区间 内的叶子结点到根的权值和减去 。

若遇到一个点已经被清空了，故该点到根节点路径上的点肯定也被清空了，就可以直接退出了；这样每个点做多只会清空一次。

考虑使用线段树维护上述操作，时间复杂度均摊为 。

完整代码：

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
#include<bits/stdc++.h>
#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)
#define lowbit(x) x&(-x)
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define iip pair<pair<ll,ll>,ll>
#define ppii pair<pair<ll,ll>,pair<ll,ll>>
#define fi first
#define se second
#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x
#define Full(a) memset(a,0,sizeof(a))
#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);
#define For(i,l,r) for(int i=l;i<=r;i++)
#define _For(i,l,r) for(int i=r;i>=l;i--)
using namespace std;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
bool Begin;
const ll N=2e5+10;
inline ll read(){
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
          f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
inline void write(ll x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9)
	  write(x/10);
	putchar(x%10+'0');
}
struct Node{
	ll l,r;
	ll tag;
	ll Max;
	ll id;
}X[N<<2];
ll n,k,cnt,ans;
ll a[N],Ans[N],l[N],r[N],d[N],id[N],fa[N];
vector<pi> E[N];
map<pi,ll> F;
bool f[N];
void add(ll u,ll v,ll w){
	E[u].push_back({v,w});
	E[v].push_back({u,w});
}
void dfs(ll u,ll f){
	l[u]=n,r[u]=1;
	bool F=1;
	for(auto t:E[u]){
		ll v=t.fi,w=t.se;
		if(v==f)
		  continue;
		fa[v]=u;
		d[v]=d[u]+w;
		dfs(v,u);
		l[u]=min(l[u],l[v]);
		r[u]=max(r[u],r[v]);
		F=0;
	}
	if(F){
		id[++cnt]=u;
		l[u]=r[u]=cnt;
		a[cnt]=d[u];
	}
}
void pushup(ll k){
	X[k].Max=max(X[k<<1].Max,X[k<<1|1].Max);
	if(X[k].Max==X[k<<1].Max)
	  X[k].id=X[k<<1].id;
	else
	  X[k].id=X[k<<1|1].id;
}
void update(ll k,ll v){
	X[k].Max+=v;
	X[k].tag+=v;
}
void push_down(ll k){
	if(X[k].tag){
		update(k<<1,X[k].tag);
		update(k<<1|1,X[k].tag);
		X[k].tag=0;
	}
}
void build(ll k,ll l,ll r){
	X[k].l=l,X[k].r=r;
	if(l==r){
		X[k].Max=a[l];
		X[k].id=l;
		return ;
	}
	ll mid=(l+r)>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	pushup(k);
}
void update(ll k,ll l,ll r,ll v){
	if(X[k].l==l&&r==X[k].r){
		update(k,v);
		return ;
	}
	push_down(k);
	ll mid=(X[k].l+X[k].r)>>1;
	if(r<=mid)
	  update(k<<1,l,r,v);
	else if(l>mid)
	  update(k<<1|1,l,r,v);
	else{
		update(k<<1,l,mid,v);
		update(k<<1|1,mid+1,r,v);
	}
	pushup(k);
}
void solve(ll u){
	while(!f[u]&&fa[u]){
		f[u]=1;
		update(1,l[u],r[u],-F[{u,fa[u]}]);
		u=fa[u];
	}
}
int main(){
	n=read();
	for(int u,v,w,i=1;i<n;i++){
		u=read(),v=read(),w=read();
		F[{u,v}]=F[{v,u}]=w;
		add(u,v,w);
	}
	dfs(1,0);
	build(1,1,cnt);
	For(i,1,n){
		if(X[1].Max>0)
		  ans+=X[1].Max;
		if(X[1].Max>0)
		  solve(id[X[1].id]);
		write(ans*2);
		putchar('\n');
	}
	return 0;
}
  • 标题: AtCoder Beginner Contest 369 题解
  • 作者: rgw2010
  • 创建于 : 2024-09-13 00:00:00
  • 更新于 : 2024-09-13 19:16:03
  • 链接: https://rgw2010.github.io/2024/09/13/AtCoder Beginner Contest 369 题解/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
目录
AtCoder Beginner Contest 369 题解
  1. [ABC369C] Count Arithmetic Subarrays
  2. 完整代码：
  3. [ABC369D] Bonus EXP
  4. 完整代码：
  5. [ABC369E] Sightseeing Tour
  6. 完整代码：
  7. [ABC369F] Gather Coins
  8. 完整代码：
  9. [ABC369G] As far as possible
  10. 完整代码：