Znzryb's Blog
0%

Posted on Edited on

image

L2-1 种树

https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/

以先序 [1, 2, 4, 5, 3, 6]、中序 [4, 2, 5, 1, 3, 6] 为例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
先序第一个 = 1（根）
在中序中找到 1 的位置，左边 [4,2,5]（3个），右边 [3,6]（2个）

          1
         / \
  左子树    右子树
  先序[2,4,5] 先序[3,6]
  中序[4,2,5] 中序[3,6]

继续递归左子树：根=2，中序中 2 左边[4]，右边[5]
继续递归右子树：根=3，中序中 3 左边空，右边[6]

最终：
          1
         / \
        2   3
       / \   \
      4   5   6

红色代表第一次（递归），蓝色代表第二次，黄色代表第三次。

image

应该算是一道典题了，但是问题在于我上次做这道题目还是在上次~~（刚学的时候，还是在用python那）~~

总体来讲，就是利用先序的root->left->right，中序的left->root->right，递归求解二叉树结构。

应该是没有太大问题的，比标程还多在我的电脑上过了一个

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
// http://120.55.170.42/contest/1001/problem/L2-1
#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>(2e5)+10,INF=static_cast<ll>(5e18)+3;

ll N,M,T,Pre[MAXN],Mid[MAXN];
map<ll,ll> posP,posM;
pll ans[MAXN];
// 根以及区域(在先序遍历上的范围)（因为只有在这个范围内先序root才是对的）
// ml,mr就是中序排列范围
bool flag=false;
void dfs(ll root,ll l,ll r,ll ml,ll mr){
	if(r<=l){
		return;
	}
	if(mr<=ml){
		return;
	}
	if(flag) return;
	ll rootm=posM[root];
	if(rootm<ml || rootm>mr){
		flag=true;
		return;
	}
	ll weiL=rootm-ml,weiR=mr-rootm;
	ll rootl=0,rootr=0;
// #ifdef LOCAL
    // cerr << root << " "<< l<<" "<<r<<" "<<weiL<<" "<<weiR << '\n';
// #endif
	if(/*l+1<=r &&*/ weiL>1){
		rootl=Pre[l+1];
		dfs(rootl,l+1,l+weiL,ml,rootm-1);
	}else if(weiL==1){
		rootl=Pre[l+1];
	}
	if(/*l+weiL+1<=r &&*/ weiR>1){
		rootr=Pre[l+weiL+1];
		dfs(rootr,l+weiL+1,r,rootm+1,mr);
	}else if(weiR==1){
		rootr=Pre[l+weiL+1];
	}
	ans[root].fi=rootl;
	ans[root].se=rootr;
}

inline void solve(){
	cin>>N;
	for(int i=1;i<=N;++i){
		cin>>Pre[i];
		posP[Pre[i]]=i;
	}
	for(int i=1;i<=N;++i){
		cin>>Mid[i];
		posM[Mid[i]]=i;
	}
	for(int i=1;i<=N;++i){	// 初始化
		ans[i].fi=0;
		ans[i].se=0;	
	}
	flag=false;
	dfs(1,1,N,1,N);
	if(flag){
		cout<<-1<<"\n";
		return;
	}
	for(int i=1;i<=N;++i){
		cout<<ans[i].fi<<" "<<ans[i].se<<"\n";
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	solve();
	return 0;
}
/*
6
1 3 5 6 4 2
3 5 1 4 6 2

*/

Posted on Edited on

思路讲解

稍微看了眼样例，还是发现有点难度呀，这1600好像还真开始上强度了。

这狗洛谷竟然一个标签都没有，佛了。这个codeforces倒是有几个标签，什么dp，二分，什么的。但老实说我不太敢信他的tag。

哈哈，我懂了，其实是这样，正推比较难，但可以倒推（毕竟都二分答案了）。就是说这个opA[i]=x（x类似于答案，就是我假设的二分答案），那么需要多少个操作？或者永远无法达成？

AC代码

https://codeforces.com/problemset/submission/1856/310565408

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
// Problem: CF1856C To Become Max
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1856C
// Memory Limit: 250 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>(1e6)+10,INF=static_cast<ll>(5e18)+3;

ll N,K,T,A[MAXN],opA[MAXN];

inline void init(){
	for(int i=1;i<=N;++i){
		opA[i]=A[i];
	}
}

inline bool check(ll x){
	for(int i=1;i<=N;++i){
		init();
		if(A[i]>=x){
			return true;
		}
		if(i==N){
			continue;
		}
		bool isAbNormal=false;
		ll opNum=0;
		opNum+=x-opA[i];
		opA[i]=x;
		for(int j=i+1;j<=N;++j){
			if(j!=N){
				if(opA[j]>=opA[j-1]-1){
					break;
				}else{
					opNum+=opA[j-1]-1-opA[j];
					opA[j]=opA[j-1]-1;
				}
			}else{
				if(opA[j]>=opA[j-1]-1){
					break;
				}				
				isAbNormal=true;
			}
		}
		
// #ifdef LOCAL
	// cerr<<x<<"\n";
	// for(int i=1;i<=N;++i){
		// cerr<<opA[i]<<" ";
	// }
	// cerr<<"\n";
	// cerr<<isAbNormal<<" "<<opNum<<"\n";
    // cerr << '\n';
// #endif
		if(!isAbNormal && opNum<=K) return true;
	}
	return false;
}

inline void solve(){
	cin>>N>>K;
	ll maxA=0;
	for(int i=1;i<=N;++i){
		cin>>A[i];
		maxA=max(A[i],maxA);
	}
	ll l=maxA,r=N+maxA+5;
	while(l<r){
		ll mid=l+r+1>>1;
		if(check(mid)){
			l=mid;
		}else{
			r=mid-1;
		}
	}
	cout<<l<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();
	}
	return 0;
}
/*
AC
https://codeforces.com/problemset/submission/1856/310565408
*/

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

Posted on Edited on

思路讲解

哥德巴赫猜想是吧

image

image

哈哈，我们只管用这个结论就对了

AC代码

https://codeforces.com/problemset/submission/735/310500929

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
// Problem: CF735D Taxes
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF735D
// Memory Limit: 250 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>(1e6)+10,INF=static_cast<ll>(5e18)+3;

ll N,M,T,A[MAXN];

inline void solve(){
	cin>>N;
	if(N==2){
		cout<<1<<"\n";
		return;
	}
	if(N%2==0){
		cout<<2<<"\n";
	}else{
		bool isPrime=true;
		for(int i=2;i<=floor(sqrt(N));++i){
			if(N%i==0){
				isPrime=false;
				break;
			}
		}
		if(isPrime){
			cout<<1<<"\n";
			return;
		}
		bool isPrime2=true;
		for(int i=2;i<=floor(sqrt(N-2));++i){
			if((N-2)%i==0){
				isPrime2=false;
				break;
			}
		}
		if(isPrime2){
			cout<<2<<"\n";
			return;
		}
		cout<<3<<"\n";
		return;
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	solve();
	return 0;
}
/*
AC
https://codeforces.com/problemset/submission/735/310500929
*/

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

Posted on Edited on

思路讲解

当发现裸的暴搜和状压不行了，这个时候就要开始想贪心了。（我怎么感觉这道题目的数据范围在误导我那）

参考以下题解，竟然是个贪心，佛了。

【Codeforces Round 1008 (Div. 2) 题目讲解 ABCDEF (CF2078)】 【精准空降到 19:54】 https://www.bilibili.com/video/BV13WQVYxEPC/?share_source=copy_web&vd_source=6ca0bc05e7d6f39b07c1afd464edae37&t=1194

主要思路就是可以通过贪心，+和x相比，肯定x划算，x2和x3相比，肯定x3划算，然后就可以了。注意是一段一段，因为每次增加的可以重新分配。每次增加的多了，经过重新分配，总量也就多了。

AC代码

https://codeforces.com/contest/2078/submission/310089733

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
// Problem: D. Scammy Game Ad
// Contest: Codeforces - Codeforces Round 1008 (Div. 2)
// URL: https://codeforces.com/contest/2078/problem/D
// Memory Limit: 256 MB
// Time Limit: 3000 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,4> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
constexpr ll MAXN=static_cast<ll>(1e3)+10,INF=static_cast<ll>(5e18)+3;

ll N,M,T;
// ll sum1[MAXN],mul1[MAXN],sum2[MAXN],mul2[MAXN];
struct OPER{
	char op1,op2;ll num1,num2;
}oper[MAXN];

inline void solve(){
	cin>>N;
	// sum1[0]=0;
	// mul1[0]=1;
	// sum2[0]=0;
	// mul2[0]=1;
	for(int i=1;i<=N;++i){
		cin>>oper[i].op1>>oper[i].num1>>oper[i].op2>>oper[i].num2;
	}
	ll lans=1,rans=1;
	for(int i=1;i<=N;++i){
		bool goLeft=true;
		for(int j=i+1;j<=N;++j){
			char op1=oper[j].op1,op2=oper[j].op2;
			ll num1=oper[j].num1,num2=oper[j].num2;
			if(op1=='+' && op2=='x'){
				goLeft=false;
				break;
			}else if(op1=='x' && op2=='x' && num2>num1){
				goLeft=false;
				break;
			}else if(op1=='x' && op2=='+'){
				goLeft=true;
				break;
			}else if(op1=='x' && op2=='x' && num2<num1){
				goLeft=true;
				break;
			}
		}
		char op1=oper[i].op1,op2=oper[i].op2;
		ll num1=oper[i].num1,num2=oper[i].num2;
		ll t1=0,t2=0;
		if(op1=='x') t1=num1*lans-lans;
		else t1=num1;
		if(op2=='x') t2=num2*rans-rans;
		else t2=num2;
		if(goLeft){
			lans+=(t1+t2);
		}else{
			rans+=(t1+t2);
		}
// #ifdef LOCAL
    // cerr << lans<<" "<<rans << '\n';
// #endif
	}
	cout<<lans+rans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();
	}
	return 0;
}
/*
AC
https://codeforces.com/contest/2078/submission/310089733
*/

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

注意，不仅遇到goRight的要停，goLeft的也要停。

这个算法其实问题在于虽然说后面乘数越多，你这个人的贡献就越大。但是问题在于如果一个人可以在比较早的时候变为多个人，然后再反哺回去，可能贡献更大？（如样例的第二个测试数据）

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
// Problem: D. Scammy Game Ad
// Contest: Codeforces - Codeforces Round 1008 (Div. 2)
// URL: https://codeforces.com/contest/2078/problem/D
// Memory Limit: 256 MB
// Time Limit: 3000 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,4> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
constexpr ll MAXN=static_cast<ll>(1e3)+10,INF=static_cast<ll>(5e18)+3;

ll N,M,T,A[MAXN];
ll sum1[MAXN],mul1[MAXN],sum2[MAXN],mul2[MAXN];
struct OPER{
	char op1,op2;ll num1,num2;
}oper[MAXN];

inline void solve(){
	cin>>N;
	// sum1[0]=0;
	// mul1[0]=1;
	// sum2[0]=0;
	// mul2[0]=1;
	for(int i=1;i<=N;++i){
		cin>>oper[i].op1>>oper[i].num1>>oper[i].op2>>oper[i].num2;
	}
	mul1[N+1]=1;
	mul2[N+1]=1;
	for(int i=N;i>=1;--i){
		if(oper[i].op1=='x'){
			mul1[i]=mul1[i+1]*oper[i].num1;
		}else{
			mul1[i]=mul1[i+1];
		}
		if(oper[i].op2=='x'){
			mul2[i]=mul2[i+1]*oper[i].num2;
		}else{
			mul2[i]=mul2[i+1];
		}
	}
	ll lans=1,rans=1;
	for(int i=1;i<=N;++i){
		ll num1=oper[i].num1,num2=oper[i].num2;
		ll lres=0,rres=0;	// 本次l和r需要增加的次数
		if(oper[i].op1=='x'){
			ll t=lans*num1-lans;
			if(mul1[i+1]>=mul2[i+1]){
				lres+=t;
			}else{
				rres+=t;
			}
		}else{
			ll t=num1;
			if(mul1[i+1]>=mul2[i+1]){
				lres+=t;
			}else{
				rres+=t;
			}		
		}
		
		if(oper[i].op2=='x'){
			ll t=rans*num2-rans;
			if(mul1[i+1]>=mul2[i+1]){
				lres+=t;
			}else{
				rres+=t;
			}			
		}else{
			ll t=num2;
			if(mul1[i+1]>=mul2[i+1]){
				lres+=t;
			}else{
				rres+=t;
			}		
		}
		lans+=lres;
		rans+=rres;
	}
	cout<<lans+rans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();
	}
	return 0;
}
/*

*/

Posted on Edited on

思路讲解

题意还是比较简单的，告诉你两数之和以及两数之积，问你在A数组中有几个对满足这个条件。

感觉是数据结构，但没想到要对题目条件进行转化。

看了一眼题解，好像是要转化题目条件。有点像下面这道题目，但没有那么明显。

2072E. Do You Love Your Hero and His Two-Hit Multi-Target Attacks?

又看了一眼，竟然是韦达定理？

image

离谱，我是完全没想到啊，这个我都已经不太记得了。

韦达定理+求根公式

image

AC代码

https://codeforces.com/problemset/submission/1857/310498477

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
// Problem: F. Sum and Product
// Contest: Codeforces - Codeforces Round 891 (Div. 3)
// URL: https://codeforces.com/problemset/problem/1857/F
// Memory Limit: 256 MB
// Time Limit: 4000 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,4> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
constexpr ll MAXN=static_cast<ll>(2e5)+10,INF=static_cast<ll>(5e18)+3;
constexpr double eps=1e-10;

ll N,T,A[MAXN];

inline void solve(){
	cin>>N;
	for(int i=1;i<=N;++i){
		cin>>A[i];
	}
	sort(A+1,A+1+N);
	ll Q;
	cin>>Q;
	for(int i=1;i<=Q;++i){
		ll b,c;
		cin>>b>>c;
		b=-b;
		ll D=b*b-4*1*c;
		if(D<0){
			cout<<0<<" ";
			continue;
		}
		long double sqD=sqrt(D);
// #ifdef LOCAL
	// cerr<<D<<"\n";
    // cerr <<setprecision(15)<< sqD << '\n';
// #endif
		// if(fabs(sqD-floor(sqD))>eps){	// 判断D是不是平方数
			// cout<<0<<" ";
			// continue;
		// }
		ll fsqD=floor(sqD);
		if(fsqD*fsqD!=D){
			cout<<0<<" ";
			continue;
		}
		if(D!=0){
			if((-b+fsqD)%2!=0 || (-b-fsqD)%2!=0){
				cout<<0<<" ";
				continue;
			}
			ll x1=(-b+fsqD)/(2);
			ll x2=(-b-fsqD)/(2);
			ll num1=upper_bound(A+1,A+1+N,x1)-lower_bound(A+1,A+1+N,x1);
			ll num2=upper_bound(A+1,A+1+N,x2)-lower_bound(A+1,A+1+N,x2);
			cout<<num1*num2<<" ";
// #ifdef LOCAL
    // cerr << num1<<" "<<num2<<" "<<x1<<" "<<x2 << '\n';
// #endif
		}else{
			ll needFind=(-b)/(2);
			ll num=upper_bound(A+1,A+1+N,needFind)-lower_bound(A+1,A+1+N,needFind);
			cout<<num*(num-1)/2<<" ";
		}
	}
	cout<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();
	}
	return 0;
}
/*
AC
https://codeforces.com/problemset/submission/1857/310498477
*/

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

WA

https://codeforces.com/problemset/submission/1857/310497474

被卡了精度，无视精度，直接用整数比较好。

1
2
3
4
5
ll fsqD=floor(sqD);
if(fsqD*fsqD!=D){
	cout<<0<<" ";
	continue;
}