山姆的競程日記

從綠牌開始的旅途

0%

TIOJ 2008, 2009 (北市賽 2017)

發表於 Disqus：

因為昨天在巴哈上看到

日音醬提到他在校內選拔無法解出這兩題

所以我就決定要來解解看這兩題

剛好也是以往北市賽的題目 就順便練一下吧

TIOJ 2008 - 格鬥大賽 (Fight)

這題的想法還滿簡單的 就是要去找每個編號最多能夠贏多少人

很直接的就是要去找所有編號勝場數最大的

不過如果我們直接暴搜 複雜度會是 $O(n^2)$

因此 我們需要想到別的方式來維護每個編號的最大值

我們可以很輕易的想到 如果一個人能夠贏過 $x$ 個人

那麼打贏這人的人一定能夠贏過 $x$ 個人以上

這裡用 $w$ 表示每個人的勝場數

我們可以知道若第 $i$ 個人贏過第 $j$ 個人 ($j$ < $i$)
且 $i$ 贏過 $i-1,i-2,…, j$個人

那麼 $w_i = w_j + (i-j-1)$

我們可以利用 stack 來維護這個值

或者不使用 stack 直接使用迴圈也可解出這題

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

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

using namespace std;

const int N = 1500000;
int ans[N];

signed main(){
	fastio
	int n;
	cin >> n;
	vector<pair<int,int>> v;
	for(int i = 0,x,y;i < n;i++){
		cin >> x >> y;
		v.push_back({x,y});
	}
	stack<int> s;
	for(int i = 0;i < n;i++){
		while(!s.empty()&&((v[i].first > v[s.top()].first&&v[i].second >= v[s.top()].second)||(v[i].second>v[s.top()].second&&v[i].first >= v[s.top()].first)))
			s.pop();
		if(s.empty())
			ans[i] += i;
		else ans[i] += i-s.top()-1;
		s.push(i);
	}
	while(!s.empty()) s.pop();
	for(int i = n-1;~i;i--){
		while(!s.empty()&&((v[i].first > v[s.top()].first&&v[i].second >= v[s.top()].second)||(v[i].second>v[s.top()].second&&v[i].first >= v[s.top()].first)))
			s.pop();
		if(s.empty())
			ans[i] += n-1-i;
		else ans[i] += s.top()-i-1;
		s.push(i);
	}
	cout << *max_element(ans,ans+N) << "\n";
}

TIOJ 2009 - 數字密碼鎖

這題感覺就是當年的送分題

這題沒什麼難度

我們先紀錄一開始陣列與最後目標的陣列的數字差

再貪心的由前而後將數字差變為零

當最後有一個或以上數字差不為零 則沒有答案

程式碼

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 int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

signed main(){
	fastio
	int n,k;
	cin >> n >> k;
	int arr[n];
	for(auto &x : arr) cin >> x;
	for(int i = 0,tmp;i < n;i++){
		cin >> tmp;
		if(tmp < arr[i]) arr[i] = tmp+9-arr[i];
		else arr[i] = tmp-arr[i];
	}
	int ans = 0;
	for(int i = 0;i <= n-k;i++){
		if(arr[i]==0) continue;
		int tmp = arr[i];
		ans += tmp;
		for(int j = 0;j < k;j++){
			arr[i+j] = (arr[i+j]-tmp+9)%9;
		}
	}
	for(int i = 0;i < n;i++){
		if(arr[i]!=0){
			cout << 0 << "\n";
			return 0;
		}
	}
	cout << ans << "\n";
}

心得

這兩題感覺難度都不太高

希望今年的題目不要太難 然後想進全國賽 QQ