這場又打的不太好了｡ﾟヽ(ﾟ´Д`)ﾉﾟ｡
明明題目沒很難 卻解了很久==
可能是開學後解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
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
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
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
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
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();
}