山姆的競程日記

從綠牌開始的旅途

0%

2020 APCS 十月場

發表於 Disqus：

這次是第二次考APCS

這次觀念題難度感覺比去年高

然後實作題我認為難度差不多（而且亂砸資結也能過）

這次的目標是 $5$ $5$ 希望能達成

觀念題上半節

這次難度好高哦

我每一題都看好久(其實是一直理解錯

不知道有沒有機會 $5$ 或甚至滿分

觀念題下半節

完全送分欸 滿滿的遞迴 而且都是簡單的

上半節是怎樣R

下半節直接提早半小時交==

希望能 $5$ 吧

實作題

今天來考的重點(上次只拿 $4$)

順便練一下比賽的感覺 畢竟十一月有北市賽

目前覺得應該有 $5$ 分 剛剛丟了 Zerojudge 也都全對

希望這次有 $5$ $5$

第一題、人力分配

有打這次APCS的人應該都知道這題有點小狀況

這題明明只有兩個範測

卻莫名多出了一個沒人過得了的第三個範測

很多人因為這題的狀況卡第一題

我也是一樣 在這題卡了十分鐘-_-

這題數字很小 亂做就可以過了

我的程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#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 arr[2][3];
	for(int i = 0; i < 2;i++) for(int j = 0;j < 3;j++) cin >> arr[i][j];
	int n;
	cin >> n;
	int ans = -1e9;
	for(int i = 0;i <= n;i++){
		int a = i, b = n-i;
		ans = max(ans,a*a*arr[0][0]+a*arr[0][1]+arr[0][2]+b*b*arr[1][0]+b*arr[1][1]+arr[1][2]);
	}
	cout << ans << "\n";
}

第二題、人口遷移

這題就直接照著題目的方式去模擬

我自己是每一次都多開一個 $tmp$ 陣列來紀錄每個位置要增加的值

程式碼

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
#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 r,c,k,m;
	cin >> r >> c >> k >> m;
	int grid[r][c];
	for(int i = 0;i < r;i++) for(int j = 0;j < c;j++) cin >> grid[i][j];
	
	for(int t = 0; t < m;t++){
		int tmp[r][c] = {};
		for(int i = 0;i < r;i++){
			for(int j = 0;j < c;j++){
				if(grid[i][j]==-1) continue;
				int tt = grid[i][j]/k;
				for(int dx : {-1,0,1})
					for(int dy : {-1,0,1}){
						if(abs(dx)==abs(dy)) continue;
						if(i+dx < 0|| i+dx >= r || j+dy < 0 || j+dy >= c) continue;
						if(grid[i+dx][j+dy]!=-1) tmp[i+dx][j+dy] += tt, grid[i][j]-=tt;
					}
			}
		}
		for(int i = 0;i < r;i++){
			for(int j = 0;j < c;j++){
				grid[i][j] = grid[i][j]+tmp[i][j]; //<< " ";
			}
		}
	}
	int mi = INT_MAX, ma = INT_MIN;
	for(int i = 0;i < r;i++){
		for(int j = 0;j < c;j++){
			if(grid[i][j]!=-1){
				mi = min(grid[i][j],mi);
				ma = max(grid[i][j],ma);
			}
		}
	}
	cout << mi << "\n" << ma << "\n";
}

第三題、勇者訓練

這題我點開題目想了好久 不知道該怎麼做就先跑去做第四題了

不過後來還是回來做這題

暴力解法

首先 我的思路是用這題的答案會是每一行的各種前綴和相加的最大值

因此 我先用了暴力法做了 $O(mn^2)$ 的解法（應該能拿到50分以上）

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
O(mn^2) 
#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 = 1e4+5;
int grid[55][N];
int pref[55][N];
int dp[55][N];

signed main(){
	fastio
	int n,m;
	cin >> n >> m;
	for(int i = 1;i <= n;i++) for(int j = 1;j <= m;j++) cin >> grid[i][j];
	for(int i = 1;i <= n;i++) for(int j = 1;j <= m;j++){
		pref[i][j] = (j!=0 ? pref[i][j-1] : 0) + grid[i][j];
	}
	for(int i = 1;i <= n+1;i++){
		for(int j = 1;j <= m;j++){
			int ma = 0;
			for(int k = 1;k <= m;k++){
				ma = max(ma,(k > j ? pref[i-1][k] - pref[i-1][j-1] : pref[i-1][j]-pref[i-1][k-1]) + dp[i-1][k]);
			}
			dp[i][j] = ma;
		}
	}
	cout << *max_element(dp[n+1]+1,dp[n+1]+m+1) << "\n";
}

毒瘤解法

然後想了要如何去將複雜度降為 $O(mnlogn)$

以我的方法來說 我是找到前一個連續的前綴和的最小值並加上到前一個的最大總和

我腦中浮現的是使用線段樹來達到這一點

而我將每一行都開了兩棵線段樹來做到（我總共開了110棵）

雖然很毒瘤 但意外的過了 所以我也放一下程式碼吧

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
#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 = 1e4+5;
int grid[55][N];
int pref[55][N];
int dp[55][N];

struct segT{
	int d[4*N];
	int combine(int a, int b){
		return max(a,b);
	}
	void modify(int pos, int val, int ind = 1, int l = 0, int r = N-1){
		if(l==r){
			d[ind] += val;
		}else{
			int mid = (l+r)/2;
			if(pos<=mid) modify(pos,val,ind<<1,l,mid);
			else modify(pos,val,ind<<1|1,mid+1,r);
			d[ind] = combine(d[ind<<1],d[ind<<1|1]);
		}
	}
	int query(int ql, int qr, int ind = 1, int l = 0, int r = N-1){
		if(ql>r||qr<l) return -1e18;
		if(ql<=l&&qr>=r) return d[ind];
		int mid = (l+r)/2;
		return combine(query(ql,qr,ind<<1,l,mid),query(ql,qr,ind<<1|1,mid+1,r));
	}
} tree[110];

signed main(){
	fastio
	int n,m;
	cin >> n >> m;
	for(int i = 1;i <= n;i++) for(int j = 1;j <= m;j++){
		cin >> grid[i][j];
	}
	for(int i = 1;i <= n;i++) for(int j = 1;j <= m;j++){
		pref[i][j] = (j!=0 ? pref[i][j-1] : 0) + grid[i][j];
		tree[i].modify(j,pref[i][j],1,1,m);
		tree[i+55].modify(j,-pref[i][j-1],1,1,m);
	}
	for(int i = 1;i <= n+1;i++){
		for(int j = 1;j <= m;j++){
			int ma = 0;
			ma = max(tree[i-1].query(j,m,1,1,m) - pref[i-1][j-1], pref[i-1][j] + tree[i+55-1].query(0,j,1,1,m));
			dp[i][j] = ma;
			tree[i].modify(j,dp[i][j],1,1,m);
			tree[i+55].modify(j,dp[i][j],1,1,m);
		}
	}
	cout << *max_element(dp[n+1]+1,dp[n+1]+m+1) << "\n";
}

第四題、低地距離

不會解第三題之後跑來看這題

題目的pdf上有個提示（很酷 我也不知道為什麼有提示）

反正反正這題就是 BIT 裸題（不過在APCS 出現資結真的很神奇）

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
#pragma GCC optimize(3)
#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;
}

signed main(){
	fastio
	int n;
	cin >> n;
	int pos[n+1];
	for(int i = 0; i <= n;i++) pos[i] = -1;
	int arr[2*n];
	ll ans = 0;
	for(int i = 0, tmp; i < 2*n;i++){
		cin >> tmp;
		arr[i] = query(tmp-1);
		if(pos[tmp]==-1){
			pos[tmp] = i;
		}else{
			ans += arr[i]-arr[pos[tmp]];
		}
		modify(tmp,1);
	}
	cout << ans << "\n";
}