Znzryb's Blog
0%

Posted on Edited on

思路讲解

和这道leetcode很像

https://leetcode.cn/problems/shortest-palindrome/solutions/392676/shou-hua-tu-jie-cong-jian-dan-de-bao-li-fa-xiang-d/

其实思路也很简单，暴力方法时间复杂度最大的部分其实是一个一个判断字符串是不是回文（一样），那么我们直接用字符串哈希加速这个过程就行。

这个下面的讲的很详细

P10469 后缀数组(如何算子串哈希值)

唉，前面怎么样都不太对，结果发现其实是我的哈希递推式子错了。

hash[i]=hash[i−1]∗base+s[i]hash[i]=hash[i-1]*base+s[i]

正确的哈希递推式子长这样，相当于我们把第一位看成最高位，和我们的数字写法一样。

AC代码

https://atcoder.jp/contests/abc398/submissions/64119843

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
// Problem: F - ABCBA
// Contest: AtCoder - UNIQUE VISION Programming Contest 2025 Spring (AtCoder Beginner Contest 398)
// URL: https://atcoder.jp/contests/abc398/tasks/abc398_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;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(5e5)+10,INF=static_cast<ll>(5e18)+3;
constexpr ll base=131;

ll N,M,T,A[MAXN];
ull hashe[MAXN],hashrs[MAXN];
ull powBase[MAXN];


inline void solve(){
	string s;
	cin>>s;
	string rs(s.rbegin(),s.rend());
	rs='0'+rs;
	N=SZ(s);
	if(N==1){
		cout<<s<<"\n";
		return;
	}
	powBase[0]=1;
	FOR(i,1,N){
		powBase[i]=powBase[i-1]*base;
	}
	s='0'+s;
	FOR(i,1,N){
		hashe[i]=hashe[i-1]*base+s[i];
	}
	FOR(i,1,N){
		hashrs[i]=hashrs[i-1]*base+rs[i];
	}
	FOR(i,N/2+1,N){
		ull len,suf,pre;
		// 以i的前面作为对称中心
		len=N-i+1;
		suf=hashrs[len]-hashrs[0]*powBase[len];
		pre=hashe[i-1]-hashe[i-len-1]*powBase[len];
// #ifdef LOCAL
    // cerr<<len<<" " <<i<<" "<< suf<<" "<<pre << '\n';
// #endif
		if(suf==pre){	
			FOR(i,1,N){
				cout<<s[i];
			}
			FOR(i,len*2+1,N){
				cout<<rs[i];
			}
			cout<<"\n";
			return;
		}
		// 以i作为对称中心
		len=N-i;
		suf=hashrs[len]-hashrs[0]*powBase[len];
		pre=hashe[i-1]-hashe[i-len-1]*powBase[len];
		if(suf==pre){	
			FOR(i,1,N){
				cout<<s[i];
			}
			FOR(i,len*2+2,N){
				cout<<rs[i];
			}
			cout<<"\n";
			return;
		}

	}
	FOR(i,1,N){
		cout<<s[i];
	}
	FOR(i,1,N){
		cout<<rs[i];
	}
	cout<<"\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/abc398/submissions/64119843
*/

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

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
*/