Znzryb's Blog
0%

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

Posted on Edited on

思路讲解

我的思路就是这个回文其实很适合双向广搜。

这某种程度上也算一种吧

【AtCoder 初学者竞赛 394比赛讲解（ABC394）】 【精准空降到 41:26】 https://www.bilibili.com/video/BV1E2ASeiE8b/?share_source=copy_web&vd_source=6ca0bc05e7d6f39b07c1afd464edae37&t=2486

image

通过分析，我们知道肯定要么在同一点结束，要么在不同点结束，这两点之间有边。

image

AC代码

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

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
// Problem: E - Palindromic Shortest Path
// Contest: AtCoder - KAJIMA CORPORATION CONTEST 2025 (AtCoder Beginner Contest 394)
// URL: https://atcoder.jp/contests/abc394/tasks/abc394_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 (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>(1e2)+10,INF=static_cast<ll>(1e18)+3;

ll N,T,A[MAXN][MAXN];
char maze[MAXN][MAXN];
// vector<pair<ll,char> > g[MAXN];

inline void solve(){
	cin>>N;
	for(int i=1;i<=N;++i){
		for(int j=1;j<=N;++j){
			cin>>maze[i][j];
			// if(maze[i][j]!='-'){
				// g[i].pb({j,maze[i][j]});
			// }
		}
	}
	FOR(i,1,N){
		FOR(j,1,N){
			A[i][j]=INF;
		}
	}
	queue<arr> q;
	FOR(i,1,N){
		FOR(j,1,N){
			if(i==j){
				q.push({i,j,0});
				A[i][j]=0;
			}else if(maze[i][j]!='-'){
				q.push({i,j,1});
				A[i][j]=1;
			}
		}
	}
	while(!q.empty()){
		ll x=q.front()[0],y=q.front()[1],dis=q.front()[2];
		q.pop();
		FOR(i,1,N){
			char c=maze[i][x];
			if(c=='-') continue;
			FOR(j,1,N){
				char cj=maze[y][j];
				if(cj==c && dis+2<A[i][j]){
					q.push({i,j,dis+2});
					A[i][j]=min(A[i][j],dis+2);
				}
			}
		}
		
	}
	FOR(i,1,N){
		FOR(j,1,N){
			cout<<(A[i][j]!=INF?A[i][j]:-1)<<" ";
		}
		cout<<"\n";
	}
}

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

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

Posted on Edited on

思路讲解

感觉这题真出的没什么意思，纯粹就是看你有没有把题目读懂，还有K==1的特殊情况有没有想到。

AC代码

https://codeforces.com/contest/2075/submission/311347701

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
// Problem: B. Array Recoloring
// Contest: Codeforces - Educational Codeforces Round 176 (Rated for Div. 2)
// URL: https://codeforces.com/contest/2075/problem/B
// Memory Limit: 256 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>(5e3)+10,INF=static_cast<ll>(5e18)+3;

ll N,K,T,A[MAXN],sortA[MAXN];
ll pos[MAXN];
bool vis[MAXN];

inline bool cmp(const ll &a,const ll &b){
	return A[a]>A[b];
}

inline void solve(){
	cin>>N>>K;
	FOR(i,1,N){
		cin>>A[i];
		sortA[i]=A[i];
	}
	sort(sortA+1,sortA+1+N);
	FOR(i,1,N){
		pos[i]=i;
	}
	sort(pos+1,pos+1+N,cmp);
	ll ansT=0;
	FOR(i,1,K){
		vis[pos[i]]=true;
		ansT+=A[pos[i]];
	}
	ll ans=ansT;
	if(K!=1){
		ans+=A[pos[K+1]];
		cout<<ans<<"\n";
	}else{
		ans=0;
		FOR(i,1,N){
			ll lans=0;
			if(i==1){
				lans+=A[1];
				lans+=A[N];
			}else if(i==N){
				lans+=A[N];
				lans+=A[1];
			}else{
				lans+=A[i];
				lans+=max(A[1],A[N]);
			}
			ans=max(ans,lans);
		}
		cout<<ans<<"\n";
	}
}

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

*/

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

Posted on Edited on

思路讲解

难点在于怎么把这个双循环搞成单循环

image

然后记得读题，那个栅栏仅能由两种颜色构成，多了，少了都不行。

AC代码

这个+2也是比较迷，但加了就AC了，我也不知道为什么。

可能是原来比16还要多减一次1，但其实和16一样。

https://codeforces.com/contest/2075/submission/311344453

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
// Problem: C. Two Colors
// Contest: Codeforces - Educational Codeforces Round 176 (Rated for Div. 2)
// URL: https://codeforces.com/contest/2075/problem/C
// Memory Limit: 256 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;

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

inline void solve(){
	cin>>N>>M;
	// ll maxA=0;
	FOR(i,1,M){
		cin>>A[i];
	}
	sort(A+1,A+1+M);
	
	sumA[0]=0;
	FOR(i,1,A[M]){
		ll idx=M-(lower_bound(A+1,A+1+M,N-i)-A)+1;
		if(i==N){
			idx=0;
		}
		sumA[i]=sumA[i-1]+idx;
	}
	ll ans=0;
	// FOR(i,1,M){	// 暴力法存档
		// FOR(j,1,A[i]){
			// ll idx=M-(lower_bound(A+1,A+1+M,N-j)-A)+1;
			// if(N-j<=A[i]){
				// idx-=1;
			// }
			// if(j==N){
				// idx=0;
			// }
			// ans+=idx;
		// }
	// }
	FOR(i,1,M){
		ans+=sumA[A[i]];
		// if(A[i]==N){
			// if((A[i]-(N-A[i])+1)>0){
				// ans-=(A[i]-(N-A[i])+1);
			// }			
		// }else{
		if((A[i]-(N-A[i])+1)>0){
			ans-=(A[i]-(N-A[i])+1);
		}			

		if(A[i]>=N){
			ans+=2;
		}
	}	
// #ifdef LOCAL
	// FOR(i,1,A[M]){
		// cerr<<sumA[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();
#ifdef LOCAL
    cerr <<  '\n';
#endif
	}
	return 0;
}
/*

*/

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