0%

Educational Codeforces Round 80

這場又打的不太好了。゚ヽ(゚´Д`)ノ゚。

明明題目沒很難 卻解了很久==

可能是開學後解CF題目的時間少很多吧 等北市賽比完再繼續瘋狂刷CF題好了

pA - Marketing Scheme

這題很明顯當 $2l > r$ 的時候

答案就會是對的 所以就一行解決

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>

#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

void solve(){
int a,b;
cin >> a >> b;
cout << (b < 2*a ? "YES\n" : "NO\n");
}

signed main(){
fastio
int t = 1;
cin >> t;
while(t--) solve();
}

pB - Reverse Binary Strings

我們可以把一些字串列出來看看

然後就能觀察出答案會是

程式碼

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
#include <bits/stdc++.h>

#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

void solve(){
int n;
cin >> n;
string s;
cin >> s;
int num1 = 0, num2 = 0;
for(int i = 1;i < s.size();i++){
if(s[i]=='1'&&s[i]==s[i-1]) num1++;
if(s[i]=='0'&&s[i]==s[i-1]) num2++;
}
cout << max(num1,num2) << "\n";
}

signed main(){
fastio
int t = 1;
cin >> t;
while(t--) solve();
}

pC - Chef Monocarp

這題在賽中我沒看到值域只有到$200$

想了好久都沒有想法

如果值域那麼小的話 那可以使用 dp 來得到解

使 $dp[i][j]$ 為第 $j$ 個元素在第 $i$ 的時間拿出來的最小值

轉移式:

程式碼:

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
#include <bits/stdc++.h>

#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

void solve(){
int n;
cin >> n;
vector<int> arr(n + 1);
int dp[2*n+1][n+1];
memset(dp,0x3f3f3f,sizeof dp);
for(int i = 1; i <= n; i++)
cin >> arr[i];
sort(arr.begin() + 1, arr.end());
dp[0][0] = 0;
for(int i = 1; i <= n * 2; i++)
for(int j = 0; j <= n; j++)
dp[i][j] = min(dp[i - 1][j], j ? (dp[i - 1][j - 1] + abs(arr[j] - i)) : (int)1e18);
cout << dp[n * 2][n] << '\n';
}

signed main(){
fastio
int t = 1;
cin >> t;
while(t--) solve();
}

pD - Minimal Height Tree

考慮 BFS 的走法

由深度低的一路往深度高的做搜尋

要做這題的話 我們會發現當後面輸入的數字比前面小的時候

我們就一定會放在下一層

但是下一層有幾個位置可以放呢 就是前一層的節點數量

我的程式碼

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
#include <bits/stdc++.h>

#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

void solve(){
int n;
cin >> n;
int tmp1 = 0, tmp2 = 0, ans = 0;
int arr[n];
for(auto &x : arr) cin >> x;
for(int i = 1;i < n;i++){
if(i==1||arr[i] < arr[i-1]){
if(tmp1) tmp1--,tmp2++;
else{
tmp1 = tmp2, tmp2 = 0, ans++;
}
}else{
tmp2++;
}
}
cout << ans << "\n";
}

signed main(){
fastio
int t = 1;
cin >> t;
while(t--) solve();
}

更好理解的寫法

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
#include <bits/stdc++.h>

#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

void solve(){
int n;
cin >> n;
queue<int> q;
q.push(0);
int arr[n];
for(auto &x : arr) cin >> x;
int ans = 0;
for(int i = 1;i < n;i++){
if(arr[i] < arr[i-1])
q.pop();
q.push(q.front()+1), ans = max(q.front()+1,ans);
}
cout << ans << "\n";
}

signed main(){
fastio
int t;
cin >> t;
while(t--) solve();
}