Znzryb's Blog
0%

Posted on Edited on

思路讲解

二分答案+树状数组

其实这个二分答案还是挺难想的，主要还是因为这个东西具有单调性，所以就可以搞二分答案。二分答案还是能节省很多时间。

AC代码

https://codeforces.com/problemset/submission/1843/310708365

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
// Problem: CF1843E Tracking Segments
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1843E
// 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 (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>(1e5)+10,INF=static_cast<ll>(5e18)+3;

ll N,M,T,A[MAXN];
arr lr[MAXN];
ll modify[MAXN];
ll fiOcc[MAXN];	// 该值第一次出现的位置
ll tr[MAXN];
bool isHave[MAXN];
inline ll lowbit(ll x){
	return x&(-x);
}
inline void add(ll p){
	while(p<=N){
		tr[p]+=1;
		p+=lowbit(p);
	}
}
inline ll query(ll l,ll r){
	ll lres=0,rres=0;
	l-=1;
	while(l>0){
		lres+=tr[l];
		l-=lowbit(l);
	}
	while(r>0){
		rres+=tr[r];
		r-=lowbit(r);
	}	
	return rres-lres;
}
inline bool check(ll x){
	if(x==N+1) return true;
	FOR(i,1,N){
		tr[i]=0;
		isHave[i]=false;
	}
	FOR(i,1,x){	// 保证不重复加
		if(isHave[modify[i]]) continue;
		isHave[modify[i]]=true;
		add(modify[i]);
	}
	FOR(i,1,M){
		ll len=lr[i][1]-lr[i][0]+1;
		ll res=query(lr[i][0],lr[i][1]);
		if(res>len-res){
			return true;
		}
	}
	return false;
}
inline void solve(){
	cin>>N>>M;
	FOR(i,1,M){
		cin>>lr[i][0]>>lr[i][1];
	}
	ll Q;
	cin>>Q;
	FOR(i,1,Q){
		ll x;
		cin>>modify[i];
	}
	ll l=1,r=Q+1;
	while(l<r){
		ll mid=l+r>>1;
		if(check(mid)){
			r=mid;
		}else{
			l=mid+1;
		}
	}
	cout<<(l!=Q+1?l:-1)<<"\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/1843/310708365
*/

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

Posted on Edited on

思路讲解

思路其实比较简单，但没那么容易想到，只需要看队尾连续的一即可。

这乍听起来有点奇怪，但其实是因为a ≥ 1，所以说这个在 j 时刻（这个j是指离结束时刻的距离）的操作无法完成 j-1的这个指标，那么就没人帮他完成了。

AC代码

https://codeforces.com/problemset/submission/2059/310691802

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
// Problem: CF2059C Customer Service
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF2059C
// 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 (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>(3e2)+10,INF=static_cast<ll>(5e18)+3;

ll N,M,T,A[MAXN][MAXN];
// ll cur[MAXN];
// ll sumA[MAXN][MAXN];
ll suffix1[MAXN];

inline void solve(){
	cin>>N;
	for(int i=1;i<=N;++i){
		for(int j=1;j<=N;++j){
			cin>>A[i][j];
		}
	}
	FOR(i,1,N){
		ll cnt=0;
		ROF(j,N,0){
			if(A[i][j]!=1){
				suffix1[i]=cnt;
				break;
			}
			++cnt;
		}
	}
	sort(suffix1+1,suffix1+1+N);
	ll ans=0;
	FOR(i,1,N){
		if(suffix1[i]>=ans){
			++ans;
		}
	}
// #ifdef LOCAL
   	// FOR(i,1,N){
   		// cerr<<suffix1[i]<<" ";
   	// }
   	// cerr<<"\n";
// #endif
	cout<<ans<<"\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/2059/310691802
*/

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

https://codeforces.com/problemset/submission/2059/310691236

这个的问题在于

1
2
3
4
1
2
1 1
1 1
1
2
3
4
5
6
7
8
9
10
FOR(i,1,N){
	ll cnt=0;
	ROF(j,N,0){
		if(A[i][j]!=1){
			suffix1[i]=cnt;
			break;
		}
		++cnt;
	}
}

这种break式样的，做赋值的，一定要想到如果一直满足情况怎么办？

Posted on Edited on

思路讲解

image

这个是动态规划还是很明显的，但是是需要不等式优化的dp，因为裸的dp想到达到这道题目的O（n）时间复杂度还是有点困难的。

具体的来说，我们需要对机子进行排序，以让我们不需要考虑机子的顺序，按照排序顺序即可。

满足以下式子说明a1要排在前面。

a1(a2x+b2)+b1<a2(a1x+b1)+b2a1a2x+a1b2+b1<a1a2x+a2b1+b2a1b2+b1<a2b1+b2a1b2−b2<a2b1−b1a1−1b1<a2−1b2a_1(a_2x+b_2)+b_1 < a_2(a_1x+b_1) + b_2 \\a_1a_2x + a_1b_2 + b_1 < a_1a_2x + a_2b_1 + b_2 \\a_1b_2 + b_1 <a_2b_1 + b_2 \\a_1b_2 - b_2 < a_2b_1 - b_1 \\\cfrac{a_1 - 1}{b_1} < \cfrac{a_2 - 1}{b_2}

很明显，根据推导，该不等式具有传递性，因为a1，b1在一边，a2，b2在一边

然后动态规划部分其实就是从上面一个状态推下来，dp[i][j]表示考虑到第i个物品，选j个物品所能达到的最大值

这就是不考虑顺序（顺序已经是最优的情况）下，选K个物品时动态规划的套路

或者你还是理解不了，背包总理解吧？选K个物品不就是背包容量为K，每个物品重量为1吗？然后背包不也不用考虑顺序或者要求顺序已经最优吗？（其实是笔者自己不理解）

AC代码

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
// http://120.55.170.42/contest/1001/problem/L2-2
#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,K,T;
pll ab[MAXN];
ll dp[MAXN][15];

inline bool cmp(const pll &a,const pll &b){
	ll a1=a.fi,b1=a.se,a2=b.fi,b2=b.se;
	long double t2=(a2-1)*1.0l/b2,t1=(a1-1)*1.0l/b1;
	return t1<t2;
}

inline void solve(){
	cin>>N>>K;
	for(int i=1;i<=N;++i){
		cin>>ab[i].fi>>ab[i].se;
	}
	sort(ab+1,ab+1+N,cmp);
	for(int i=0;i<=K;++i){
		dp[0][i]=1;
	}
	for(int i=0;i<=N;++i){
		dp[i][0]=1;
	}
	// 注意到，其实k是很小的
	for(int i=1;i<=N;++i){
		ll a=ab[i].fi,b=ab[i].se;
		for(int j=1;j<=K;++j){
			dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]*a+b);
		}
	}
	cout<<dp[N][K]<<"\n";
}

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

*/

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

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……）