山姆的競程日記

從綠牌開始的旅途

0%

寒假競程訓練第二天

發表於 更新於 Disqus：

今天混了滿久都沒在練習的

一樣是持續戳 2100 ~ 2500 的題目

不過我覺得感覺一直解這些題目好像沒什麼進步

就只是猜梗的速度以及實作的速度變快了一點

我覺得要開始解一些照主題分的題目了

順便解一些經典題 畢竟聽說入營考常常會考裸題

像去年的最後一題也是 AC 自動機 （不過我去年根本連DP都還不會就去參加了（¯﹃¯）

解題

今天一共解了 1 題 + 前一天的寒假練題計畫 5 題

Codeforces 992E - Nastya and King-Shamans

題意：

給一個 $n$ 項的陣列，以及 $q$ 個操作，每次操作完要輸出任一個 $i$ 使得 $\displaystyle \sum_{k < i} a_k = a_i$ ，亦即在這個元素以前的和要等於這個元素本身

若是找不到這樣的元素，則輸出 $-1$

想法：

要找一個陣列某一項前面的和，不就是「前綴和」嗎？

解法：

我們可以先建一個前綴和陣列

然後我們所要找的是 前綴和 $= a_i$ 的位置

因此我們可以使用線段樹存 $a_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
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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#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;

struct SegT{
	int d[4*N];
	int lazy_tag[4*N];
	int combine(int a, int b){
		return max(a,b);
	}
	void build(int a[], int ind = 1, int l = 0, int r = N-1){
		if(l==r){
			d[ind]=a[l];
		}else{
			int mid = (l+r)/2;
			build(a,ind<<1,l,mid);
			build(a,ind<<1|1,mid+1,r);
			d[ind] = combine(d[ind<<1],d[ind<<1|1]);
		}
	}

	void apply(int ind, int val, int l, int r){
		if(ind>=0&&ind<4*N){
			d[ind] += val;
			lazy_tag[ind] += val;
		}
	}

	void range_modify(int ml, int mr, int val, int ind = 1, int l = 0, int r = N-1){
		if(ml>r||mr<l) return;
		if(ml<=l&&mr>=r){
			lazy_tag[ind] += val;
			d[ind] += val;
			return;
		}
		int mid = (l+r)/2;
		if(lazy_tag[ind]){
			apply(ind<<1, lazy_tag[ind], l, mid);
			apply(ind<<1|1, lazy_tag[ind], mid+1, r);
			d[ind] = combine(d[ind<<1],d[ind<<1|1]);
			lazy_tag[ind] = 0;
		}
		range_modify(ml,mr,val,ind<<1,l,mid);
		range_modify(ml,mr,val,ind<<1|1,mid+1,r);
		d[ind] = combine(d[ind<<1],d[ind<<1|1]);
	}
	
	int query(int ind = 1, int l = 0, int r = N-1){
		if(d[ind] < 0) return -1;
		if(l==r) return d[ind] ? -1 : l+1;
		int mid = l+r>>1;
		if(lazy_tag[ind]){
			apply(ind<<1, lazy_tag[ind], l, mid);
			apply(ind<<1|1, lazy_tag[ind], mid+1, r);
			d[ind] = combine(d[ind<<1],d[ind<<1|1]);
			lazy_tag[ind] = 0;
		}
		int tmp = query(ind<<1,l,mid);
		if(tmp > 0) return tmp;
		else return query(ind<<1|1,mid+1,r);
	}
} st;

signed main(){
	fastio
	int n,q;
	cin >> n >> q;
	int arr[n], pref[n+1] = {}, arr2[n];
	for(int i = 0;i < n;i++){
		cin >> arr[i];
		pref[i+1] = pref[i]+arr[i];
		arr2[i] = arr[i]-pref[i];
	}
	st.build(arr2,1,0,n-1);
	while(q--){
		int p,x;
		cin >> p >> x;
		p--;
		int tmp = x; x = x - arr[p]; arr[p] = tmp; 
		st.range_modify(p,p,x,1,0,n-1);
		st.range_modify(p+1,n-1,-x,1,0,n-1);
		cout << st.query(1,0,n-1) << "\n";
	}
}

寒假練題計畫 1/22

一開始忘記打了 也打的不怎麼樣

第一題、k-factorization (Codeforces 797A)

題意：

給兩個數字 $n$ 以及 $k$

問 $n$ 能不能分成 $k$ 個大於 $2$ 的數字的乘積

若可以 則輸出一組解

想法：

$n \leq 10^5$ 因此，我們直接使用一個 for 迴圈解決

程式碼：

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
#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;
	vector<int> v;
	for(int i = 2;i <= n;i++){
		if(v.size()==k-1&&n!=1){
			for(auto x : v) cout << x << " ";
			cout << n << "\n";
			return 0;
		}
		while(n%i==0){
			v.push_back(i), n/=i;
			if(v.size()==k-1&&n!=1){
				for(auto x : v) cout << x << " ";
				cout << n << "\n";
				return 0;
			}
		}
	}
	if(v.size()==k){
		for(auto x : v) cout << x << " ";
		return 0;
	}
	cout << -1 << "\n";
}

第二題、New Year and Buggy Bot (Codeforces 908B)

題意：

給一個盤面包含了起點與終點

以及一個操作指令的字串（由 $0~3$ 組成）

問有幾種數字與上下左右的對應能使我們走到終點

解法：

C++ STL 的 next_permutation

程式碼：

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
#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
	map<char,pair<int,int>> ma;
	ma['U'] = {-1,0};
	ma['R'] = {0,1};
	ma['D'] = {1,0};
	ma['L'] = {0,-1};
	char d[4] = {'U','L','R','D'};
	int n,m;
	cin >> n >> m;
	int grid[n][m] = {};
	int sx, sy, ex, ey;
	for(int i = 0;i < n;i++){
		for(int j = 0;j < m;j++){
			char c;
			cin >> c;
			if(c=='S') sx = i, sy = j;
			else if(c=='#') grid[i][j] = 1;
			else if(c=='E') ex = i, ey = j;
		}
	}

	string s;
	cin >> s;
	int ans = 0;
	sort(d,d+4);
	do{
		int nx = sx, ny = sy;
		for(int i = 0;i < s.size();i++){
			auto [dx,dy] = ma[d[s[i]-'0']];
			if(nx+dx >= 0 && nx + dx < n && ny + dy >= 0 && ny + dy < m && grid[nx+dx][ny+dy]==0){
				nx += dx, ny += dy;
			}else{
				break;
			}
			if(nx==ex&&ny==ey){
				ans++;
				break;
			}
		}
		
	}while(next_permutation(d,d+4));
	cout << ans << "\n";
}

第三題、Driving Test (Codeforces 845D)

題意：

有一個人在開車 有六種他會遇到的事件

（一）改變車子的速度為 $s$

（二）超車

（三）遇到「限速 $s$」 的牌子

（四）遇到「可以超車」的牌子

（五）遇到「不限速」的牌子

（六）遇到「不可超車」的牌子

問最少要無視幾個牌子 才能遵守交通規則

想法：

會發現（一）（三）（五）和（二）（四）（六）可以分開思考

是否能超車只要用一個變數來維護就好了 而限速則是能用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
39
40
#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;
	cin >> n;
	int ans = 0;
	stack<int> s; //For speed;
	int nowspeed = 0, sign = 0;
	for(int i = 0;i < n;i++){
		int a,b;
		cin >> a;
		if(a==1||a==3){
			cin >> b;
		}
		if(a==1){
			nowspeed = b;
			while(!s.empty()&&b > s.top())
				s.pop(), ans++;
		}else if(a==2){
			ans += sign;
			sign = 0;
		}else if(a==3){
			if(nowspeed > b) ans++;
			else s.push(b);
		}else if(a==4){
			sign = 0;
		}else if(a==5){
			while(!s.empty()) s.pop();
		}else if(a==6){
			sign++;
		}
	}
	cout << ans << "\n";
}

第四題、The Intriguing Obsession (Codeforces 869C)

題意：

有三種顏色的島嶼，分別有 $a$, $b$, $c$ 個這三種顏色的島嶼。

給予兩個條件：

（一）同色的島嶼不能互相相鄰

（二）同色的島嶼之間的最短距離要是 $3$ 以上

想法：

不能相鄰這點還算好像，那最短距離為 $3$ 以上呢？

我們會發現如果每個同色島嶼之間的最短距離要是 $3$

那麼一定要是 $1-2-3-1-2-3$ 這樣的排法

因此，每個島嶼只會和一種顏色的島嶼做連接

我們還能發現由於這個性質，兩兩顏色之間是互相獨立的事件

因此最後只要相乘就好

至於要怎麼維護兩兩之間的連接呢？

解法：

如果我們使用 DP 的方式來思考

那麼這個問題就沒有很難了

如果我們今天考慮 dp 式

$dp[i][j]$ 為 $i$ 個顏色 $1$ 與 $j$ 個顏色 $2$ 的接法

那我們就可以思考轉移式

如果我們新加入一種顏色 $1$

那麼轉移式就可以列成

$dp[i][j] = dp[i-1][j]$ （代表不連）$+ dp[i-1][j-1] * j$ （代表可以和任一個顏色 $2$ 相連）

程式碼：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#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 = 5e3+5, MOD = 998244353;
int dp[N][N];

signed main(){
	fastio
	int a,b,c;
	cin >> a >> b >> c;
	for(int i = 0;i < N;i++) dp[i][0] = 1, dp[0][i] = 1;
	for(int i = 1;i < N;i++){
		for(int j = 1;j < N;j++){
			dp[i][j] = (dp[i-1][j]+dp[i-1][j-1]*j%MOD)%MOD;
		}
	}
	cout << dp[a][b]*dp[b][c]%MOD*dp[c][a]%MOD << "\n";
}

第五題、Square Subsets (Codeforces 895C)

題意：

給一個 $n$ 項的陣列 $a$ ($a_i \leq 70$)，問有幾種選法使得選到的數字乘積為完全平方數？

想法：

首先，我們可以注意到 $a_i \leq 70$

$70$ 這個數字有什麼特別的呢？

我們可以將小於 $70$ 的質數列出來，會發現只有 $19$ 個！

而要怎麼判斷是完全平方數呢

完全平方數的特性是他在質因數分解後，質數的次方一定是偶數！

$19$ 個代表著我們可以使用位元dp，枚舉 $1$ 到 $2^{18}$

兩個數字的位元狀態做 XOR 即為相乘

解法：

因為值域只有到 $70$，我們可以先紀錄 $1~70$ 在陣列中出現了幾次

然後每次去加入這些數字，去判斷有幾種選法

程式碼：

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
#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 MOD = 1e9+7;
vector<int> primes = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67};

int cnt[71], num[71], dp[71][1<<18];

int fastpow(int n, int p){
	int res = 1;
	while(p){
		if(p&1) res = (res * n) % MOD;
		n = (n * n) % MOD;
		p>>=1;
	}
	return res;
}

signed main(){
	fastio
	//cout << primes.size() << "\n";
	for(int i = 1;i <= 70;i++){
		int tmp = i;
		for(int j = 0;j < primes.size();j++){
			while(tmp%primes[j]==0) num[i]^=(1<<j), tmp/=primes[j];
		}
	}
	int n;
	cin >> n;
	for(int i = 0;i < n;i++){
		int tmp;
		cin >> tmp;
		cnt[tmp]++;
	}

	dp[0][0] = 1;
	for(int i = 1;i <= 70;i++){
		for(int j = 0;j < (1<<18);j++){
			if(!cnt[i]) dp[i][j] = dp[i-1][j];
			else dp[i][j] = (dp[i][j] + dp[i-1][j] + dp[i-1][j^num[i]])%MOD * fastpow(2,cnt[i]-1)%MOD;
		}
	}
	cout << (dp[70][0]-1+MOD)%MOD << "\n";
}