山姆的競程日記

從綠牌開始的旅途

0%

Educational Codeforces Round 96

發表於 更新於 Disqus：

Educational Codeforces Round 96

上週因為忙段考都沒po文 ・゜・(PД`q｡)・゜・

這場是連續掉分之後的第一場上分 真感動ヽ(✿ﾟ▽ﾟ)ノ

總共解出了 $5$ 題 分別是pABCDE

Problem A - Number of Apartments

給予一個數字 問是否能用 $3,5,7$表示

這題一看到確實會猶豫該怎麼去做這題

不過實際上這題可以利用暴搜的方式來找到解答 因為 $n$ 的值並不大

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;
	for(int i = 0;i <= 1000/3+1;i++){
		if(i*3>n) break;
		for(int j = 0;j <= 1000/5;j++){
			if(i*3+j*5>n) break;
			for(int k = 0;k <= 1000/7+1;k++){
				if(i*3+j*5+k*7>n) break;
				if(i*3+j*5+k*7==n){
					cout << i << " " << j << " " << k << "\n";
					return;
				}
			}
		}
	}
	cout << -1 << "\n";
}

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

Problem B - Barrels

這題也是一題滿經典的問題

如果有 $n$ 個水桶 你可以做 $k$ 次

每次可以將一個水桶的水倒進另外一個水桶

問裝最多水的水桶有多少水

這題只要排序然後挑最大的 $k$ 個水桶就可以了

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,k;
	cin >> n >> k;
	vector<int> v;
	for(int i = 0, tmp;i < n;i++){
		cin >> tmp;
		v.push_back(tmp);
	}
	sort(v.begin(),v.end());
	int val = v.back(); v.pop_back();
	while(k--&&!v.empty()){
		val += v.back(); v.pop_back();
	}
	cout << val << "\n";
}

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

Problem C - Number on Whiteboard

這題其實我不知道要說些什麼 因為我是觀察規律觀察出來的

不論 $n$ 多大 最後得到的答案都會是 $2$

先挑選 $n$ 和 $n-2$ 合併會得到 $n-1$

之後再一路往前合併就會得到 $2$ 了

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
#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;
	cout << 2 << "\n";
	if(n==2){
		cout << 1 << " " << 2 << "\n";
		return;
	}
	vector<int> v;
	for(int i = 1;i < n;i++){
		if(i!=n-2) v.push_back(i);
	}
	cout << n-2 << " " << n << "\n";
	int num = n-1;
	while(!v.empty()){
		cout << num << " " << v.back() << "\n"; 
		num = (num+v.back()+1)/2;
		v.pop_back(); 
	}
}

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

Problem D - String Deletion

這題的話剛看到的時候想了一下

他是給予一個由 $0,1$ 構成的字串 每次都會將最前面的連續字串刪除

問最多能做幾次操作

藉由觀察 我們可以知道每次最好的選擇是拿最前面 $>1$ 的連續字串的字元

然後最後剩下的再去用 $\lceil \frac{剩下的單個字元數量}{2} \rceil$ 就會是答案了

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

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

using namespace std;

void solve(){
	int n;
	string s;
	cin >> n >> s;
	deque<int> v;
	s = '#' + s + '#';
	for(int i = 1;i <= n;i++){
		if(s[i]!=s[i-1]) v.push_back(1);
		else v.back()++;
	}
	int ans = 0, idx = 0;
	while(!v.empty()&&idx<(int)v.size()){
		idx = max(0,idx);
		if(v[idx]==1) idx++;
		else if(v[idx]>=1){
			v[idx--]--;
			ans++;
			v.pop_front();
		}
	}
	cout << ans + (v.size()+1)/2 << "\n";
}

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

Problem E - String Reversal

這題我的作法是先將原本的字串用反轉後的字串變為一個整數陣列

然後我們都知道

一個陣列要被Bubble Sort排序好的次數為逆序對數量

因此我們可以用 BIT 去找逆序對數量

複雜度：$O(nlogn)$

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
#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;

const int N = 2e5+5;
int bit[N];
 
void modify(int pos, int val){
	while(pos<N){
		bit[pos] += val;
		pos += pos&-pos;
	}
}
 
int query(int pos){
	int res = 0;
	while(pos){
		res += bit[pos];
		pos -= pos&-pos;
	}
	return res;
}
int arr[N];
vector<int> v[26];
signed main(){
	fastio
	int n;
	cin >> n;
	string s;
	cin >> s;
	for(int i = 0;i < 26;i++) v[i].reserve(N);
	reverse(s.begin(),s.end());
	for(int i = 0;i < n;i++){
		v[s[i]-'a'].push_back(i);
	}
	reverse(s.begin(),s.end());
	for(int i = 0;i < 26;i++) reverse(v[i].begin(), v[i].end());
	for(int i = 0;i < n;i++){
		assert(!v[s[i]-'a'].empty());
		arr[i] = v[s[i]-'a'].back()+1; v[s[i]-'a'].pop_back();
	}
	int ans = 0;
	for(int i = 0;i < n;i++){
		ans += query(N-1)-query(arr[i]);
		modify(arr[i],1);
	}
	cout << ans << "\n";	
}