Znzryb's Blog
0%

Posted on Edited on

思路讲解

类似于最短路问题。但这题真的难度只有977吗？这个1400多的树上dp我都有点思路。这个是看完一点思路都没有呀。

不过图论嘛有什么难的那？我很快想到了分层图。这个其实把这张图分为两层就可以了，一层正图，一层反图，正图到反图或者反图到正图都有代价X。

其实dijsktra的关键在于是去找点，就是说目前为止找到的不确定点（dist=INF）中与原点最近的点，改为确定点就（dist=dis）好了。

AC代码

https://atcoder.jp/contests/abc395/submissions/64132524

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
// Problem: E - Flip Edge
// Contest: AtCoder - AtCoder Beginner Contest 395
// URL: https://atcoder.jp/contests/abc395/tasks/abc395_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,2> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(5e18)+3;

ll N,M,X,T,A[MAXN];
vector<ll> g[MAXN];
ll dist[MAXN];

struct cmp{
	bool operator()(const arr &a,const arr &b)const{
		return a[1]>b[1];
	}
};

inline void solve(){
	cin>>N>>M>>X;
	FOR(i,1,2*N){
		dist[i]=INF;
	}
	FOR(i,1,M){
		ll u,v;
		cin>>u>>v;
		g[u].pb(v);
		g[v+N].pb(u+N);
	}
	priority_queue<arr,vector<arr>,cmp> pq;
	pq.push({1,0});
	while(!pq.empty()){
		ll node=pq.top()[0],dis=pq.top()[1];
		pq.pop();
		if(dist[node]==INF){
			dist[node]=dis;
			FOR(i,0,SZ(g[node])-1 ){
				ll toNode=g[node][i];
				pq.push({toNode,dis+1});
			}
			if(node>N){
				pq.push({node-N,dis+X});
			}else{
				pq.push({node+N,dis+X});
			}
		}
	}
	cout<<min(dist[N],dist[2*N])<<"\n";
// #ifdef LOCAL
    // FOR(i,1,2*N){
    	// cerr<<dist[i]<<" ";
    // }
    // cerr<<"\n";
// #endif
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	// cin>>T;
	// while(T--){
		// solve();
	// }
	solve();
	return 0;
}
/*
AC
https://atcoder.jp/contests/abc395/submissions/64132524
*/

心路历程（WA，TLE，MLE……）

Posted on Edited on

思路讲解

将问题通过转化，Ui‘的取值范围是

max(H−Di，0)<=Ui′<=Uimax(H-D_i，0)<=U_i'<=U_i

那么我们其实就是要在这个范围内实现题目要求

Ui−1′−X<=Ui′<=Ui−1′+XU_{i-1}'-X<=U_i'<=U_{i-1}'+X

然后问这个H最大是多少。

其实这是一个比较经典的差分约束系统https://oi-wiki.org/graph/diff-constraints/

【算法讲解142【扩展】负环和差分约束】 https://www.bilibili.com/video/BV1iNH9eREG3/?share_source=copy_web&vd_source=6ca0bc05e7d6f39b07c1afd464edae37

差分约束做法参考以下题解

https://www.luogu.com.cn/article/xxqmcpr3

image

怎么去记这个连边的方向那（判断负环的话）

这个小于等于号像不像一个箭头，这就是连边方向！

这个小于等于号像不像一个箭头，这就是连边方向！（奇淫巧技）

然后判断负环的话总归是小于号（不是小于嘛就变成小于，两边加符号嘛）。

然后其实这道题目默认是没有负环的（因为X是正值嘛），所以不用判断负环。

https://www.luogu.com.cn/article/hm6gtuo1

其实这两种方法殊途同归，因为他们得到的都是最靠近0的点，只不过一个是从左边接近，一个从右边接近，说白了这两个解的转化无非就是+d的事情。

但是好像这两种办法对这题其实没什么帮助。我们需要的解其实是最靠近原来的长度的解，这样可以保证Ui被磨的最少，这样子H自然会更大。

所以我们把距离初始值设定为Ui，然后只往小里面更新，不往大里面更新（因为是小于号系统，不往小里面更新会不满足系统约束）

官解以及视频题解都是二分答案做法，但是我总归还是想学一点新的东西嘛。

参考以下视频题解

【AtCoder 初学者竞赛 395比赛讲解（ABC395）】 【精准空降到 1:37:59】 https://www.bilibili.com/video/BV1vE98YDEXA/?share_source=copy_web&vd_source=6ca0bc05e7d6f39b07c1afd464edae37&t=5879

image

AC代码

https://atcoder.jp/contests/abc395/submissions/64194370

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
// Problem: F - Smooth Occlusion
// Contest: AtCoder - AtCoder Beginner Contest 395
// URL: https://atcoder.jp/contests/abc395/tasks/abc395_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,2> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(5e18)+3;

ll N,X,T;
arr ud[MAXN];

struct cmp{
	bool operator()(const arr &a,const arr &b)const{
		return a[1]>b[1];
	}
};

inline void solve(){
	cin>>N>>X;
	ll minH=0,maxH=INF,sumUd=0;
	vector<ll> dist(N+5,INF);
	vector<vector<ll> > g(N+5);
	vector<bool> vis(N+5,false);
	priority_queue<arr,vector<arr>,cmp> q;
	FOR(i,1,N){
		cin>>ud[i][0]>>ud[i][1];
		maxH=min(maxH,(ud[i][0]+ud[i][1]));
		sumUd+=(ud[i][0]+ud[i][1]);
		if(i!=N) g[i+1].pb(i),g[i].pb(i+1);
		dist[i]=ud[i][0];
		q.push({i,dist[i]});
	}
	// 在这个差分约束上走最短路（Dijsktra）
	while(!q.empty()){
		ll u=q.top()[0],dis=q.top()[1];
		q.pop();
		if(vis[u]) continue;
		vis[u]=true;
		dist[u]=dis;
		FOR(i,0,SZ(g[u])-1){
			ll v=g[u][i];
			if(!vis[v]){
				q.push({v,dis+X});
			}
		}
	}
// #ifdef LOCAL
    // FOR(i,1,N){
    	// cerr<<dist[i]<<' ';
    // }
    // cerr<<"\n";
// #endif
	ll H=INF;
	FOR(i,1,N){
		H=min(H,dist[i]+ud[i][1]);
	}
	cout<<sumUd-N*H<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	// cin>>T;
	// while(T--){
		// solve();
	// }
	solve();
	return 0;
}
/*
AC
https://atcoder.jp/contests/abc395/submissions/64194370
*/

心路历程（WA，TLE，MLE……）

Posted on Edited on

思路讲解

洛谷很明确的告诉我这道题目就是并查集。但是我不太会就是说这个并查集怎么把单个元素剥离出来的？

哈哈，事实证明他只是借用了一下并查集的思想，并不是真的并查集（不需要find函数和merge函数）

nestTofa的意思就是指nest号码对应到的fa的号码，faTonest的意思就是fa的号码对应到的nest的号码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
if(op==1){
	ll a,b;
	cin>>a>>b;
	fa[a]=nestTofa[b];
}else if(op==2){
	ll a,b;
	cin>>a>>b;
	swap(faTonest[nestTofa[a]],faTonest[nestTofa[b]]);
	swap(nestTofa[a],nestTofa[b]);
}else{
	ll a;
	cin>>a;
	cout<<faTonest[fa[a]]<<"\n";
}

AC代码

https://atcoder.jp/contests/abc395/submissions/64014199

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
// Problem: D - Pigeon Swap
// Contest: AtCoder - AtCoder Beginner Contest 395
// URL: https://atcoder.jp/contests/abc395/tasks/abc395_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(5e18)+3;

ll N,Q,T,A[MAXN];
ll fa[MAXN];
ll faTonest[MAXN];
ll nestTofa[MAXN];

inline void solve(){
	cin>>N>>Q;
	FOR(i,1,N){
		fa[i]=i;
		faTonest[i]=i;
		nestTofa[i]=i;
	}
	FOR(i,1,Q){
		ll op;
		cin>>op;
		if(op==1){
			ll a,b;
			cin>>a>>b;
			fa[a]=nestTofa[b];
		}else if(op==2){
			ll a,b;
			cin>>a>>b;
			swap(faTonest[nestTofa[a]],faTonest[nestTofa[b]]);
			swap(nestTofa[a],nestTofa[b]);
		}else{
			ll a;
			cin>>a;
			cout<<faTonest[fa[a]]<<"\n";
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	solve();
	return 0;
}
/*
AC
https://atcoder.jp/contests/abc395/submissions/64014199
*/

心路历程（WA，TLE，MLE……）

Posted on Edited on

思路讲解

这个下面的题目好像是问怎么把一个图转化为雪花树

ABC-385-E - Snowflake Tree

这个是要问Alkane的最大子图（边数最多）

给的无向图是一颗树。

“烷烃”的定义是这颗树上，顶点的入度为4或者为1，而且必须有一个点的入度为4

其实我感觉这种题目，这种比较简单的树上dp没什么难的，就是要分类讨论，每种情况都要想清楚。

AC代码

https://atcoder.jp/contests/abc394/submissions/64007396

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
// Problem: F - Alkane
// Contest: AtCoder - KAJIMA CORPORATION CONTEST 2025 (AtCoder Beginner Contest 394)
// URL: https://atcoder.jp/contests/abc394/tasks/abc394_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
constexpr ll MAXN=static_cast<ll>(2e5)+10,INF=static_cast<ll>(5e18)+3;
typedef pair<ll,bool> plb;

ll N,M,T,A[MAXN];
vector<ll> g[MAXN];
ll ans=0;
bool vis[MAXN];
ll dp[MAXN];

pair<ll,bool> dfs(ll x){
	ll lans=0;
	bool flag=false;
	vector<ll> rett;
	FOR(i,0,SZ(g[x])-1){
		ll node=g[x][i];
		if(!vis[node]){
			vis[node]=true;
			plb ret=dfs(node);
			if(ret.se) flag=true;
			lans+=ret.fi;
			rett.pb(ret.fi);
		}
	}
	if(SZ(g[x])==4){
		lans+=1;
		ans=max(lans,ans);
		return (plb){lans,true};
	}else if(SZ(g[x])==1){
		lans+=1;
		if(flag) ans=max(lans,ans);
		return (plb){lans,flag};
	}else if(SZ(g[x])<4){
		if(flag){
			sort(all(rett));
			ans=max(ans,1+rett[SZ(rett)-1]);
		} 
		return (plb){1,false};
	}else{
		sort(all(rett));
		lans=0;
		ROF(i,SZ(rett)-1,SZ(rett)-3){
			lans+=rett[i];
		}
		lans+=1;
		ans=max(ans,lans+rett[SZ(rett)-4]);
		return (plb){lans,true};
	}
}

inline void solve(){
	cin>>N;
	ans=0;
	FOR(i,1,N-1){
		ll a,b;
		cin>>a>>b;
		g[a].pb(b);
		g[b].pb(a);
	}
	vis[1]=true;
	dfs(1);
	cout<<(ans==0?-1:ans)<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	solve();
	return 0;
}
/*
WA
http://atcoder.jp/contests/abc394/submissions/64001178
AC
https://atcoder.jp/contests/abc394/submissions/64007396
*/

心路历程（WA，TLE，MLE……）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
7
1 2
2 3
3 4
3 5
3 6
3 7

ans: 5

8
1 2
2 3
3 4
3 5
5 6
5 7
5 8

ans:5
hack: https://atcoder.jp/contests/abc394/submissions/64007220
该提交在入度为2or3的处理上有一点问题

hack数据以上

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
// Problem: F - Alkane
// Contest: AtCoder - KAJIMA CORPORATION CONTEST 2025 (AtCoder Beginner Contest 394)
// URL: https://atcoder.jp/contests/abc394/tasks/abc394_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
constexpr ll MAXN=static_cast<ll>(2e5)+10,INF=static_cast<ll>(5e18)+3;
typedef pair<ll,bool> plb;

ll N,M,T,A[MAXN];
vector<ll> g[MAXN];
ll ans=0;
bool vis[MAXN];

pair<ll,bool> dfs(ll x){
	ll lans=0;
	bool flag=false;
	FOR(i,0,SZ(g[x])-1){
		ll node=g[x][i];
		if(!vis[node]){
			vis[node]=true;
			plb ret=dfs(node);
			if(ret.se) flag=true;
			lans+=ret.fi;
		}
	}
	if(SZ(g[x])==4){
		lans+=1;
#ifdef LOCAL
    cerr << x<<" "<<lans << '\n';
#endif
		ans=max(lans,ans);
		return (plb){lans,true};
	}else if(SZ(g[x])==1){
		lans+=1;
#ifdef LOCAL
    cerr << x<<" "<<lans << '\n';
#endif
		if(flag) ans=max(lans,ans);
		return (plb){lans,flag};
	}else{
		return (plb){1,false};
	}
}

inline void solve(){
	cin>>N;
	ans=0;
	FOR(i,1,N-1){
		ll a,b;
		cin>>a>>b;
		g[a].pb(b);
		g[b].pb(a);
	}
	vis[1]=true;
	dfs(1);
	cout<<(ans==0?-1:ans)<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	solve();
	return 0;
}
/*
WA
http://atcoder.jp/contests/abc394/submissions/64001178
*/

Posted on Edited on

思路讲解

其实也是临门一脚，已经是想到二分答案了，但是我想到的组织二分答案的方式有问题，比较困难，基本搞不定。（我想枚举的是选择的R连续段的个数，看了题解以后恍然大悟，他枚举的是这个颜色不匹配的的最大允许值）

当然题目也暗示的很明显了，最大值最小，这个算是很明显的暗示了。

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
## C. Limited Repainting
其实也是临门一脚，已经是想到二分答案了，但是我想到的组织二分答案的方式有问题，比较困难，基本搞不定。（我想枚举的是选择的R连续段的个数，看了题解以后恍然大悟，他枚举的是这个颜色不匹配的的最大允许值）

当然题目也暗示的很明显了，最大值最小，这个算是很明显的暗示了。

```cpp
// Problem: C. Limited Repainting
// Contest: Codeforces - Educational Codeforces Round 175 (Rated for Div. 2)
// URL: https://codeforces.com/contest/2070/problem/C
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (long long i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (long long i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
constexpr ll MAXN=static_cast<ll>(3e5)+10,INF=static_cast<ll>(5e18)+3;

ll N,K,T,A[MAXN];
char col[MAXN];
ll ans=0;

inline bool check(ll x){
	bool isConti=false;
	ll cntop=0;
	A[N+1]=INF,col[N+1]='R';
	FOR(i,1,N+1){
		if(col[i]=='R'){
			if(A[i]>x && isConti){
				isConti=false;
				++cntop;
			}
		}else{
			if(A[i]>x && !isConti){
				isConti=true;
			}
		}
	}
	if(cntop>K) return false;
	return true;
}

inline void solve(){
	cin>>N>>K;
	ll cntr=0;
	FOR(i,1,N){
		cin>>col[i];
		if(col[i]=='R') ++cntr;
	}
	ll maxr=0,maxb=0;
	FOR(i,1,N){
		cin>>A[i];
		if(col[i]=='R') maxr=max(maxr,A[i]);
		else maxb=max(maxb,A[i]);
	}
	if(K==0){
		cout<<maxb<<"\n";
		return;
	}
	ll l=0,r=max(maxr,maxb);
	ans=INF;
	while(l<r){
		ll mid=l+r>>1;
		if(check(mid)){
			r=mid;
		}else{
			l=mid+1;
		}
	}
	cout<<l<<"\n";
}


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();
#ifdef LOCAL
    cerr <<  '\n';
#endif
	}
	return 0;
}
/*
AC
https://mirror.codeforces.com/contest/2070/submission/308459133
1
32 5
BBBRRBBRBBRBBRBRBBBRRBRBRBBRBRBB
12 13 671 12 1277 13872 112 1381 1213 1918 12 121389 65427 435 21 128 1263 16797 1283974 1268 283738435738 21289738 217123 362182 18189 217 17834 18923 121 4378 642173 847356

*/

## AC代码

## 心路历程（WA，TLE，MLE……）