山姆的競程日記

從綠牌開始的旅途

0%

寒假競程訓練第一天

發表於 Disqus：

決定重新開始寫Blog （昨天忘記寫了 ==)

紀錄一下每天所解的題目以及新學到的演算法等等

而寒假過後不久 就將迎來TOI初選

因此在這個寒假要更加努力勤奮的練習

解題

今天解了 1 題

CodeForces 612E - Square Root of Permutation

題意

給予一個 Permutation （$1$ ~ $n$ 數字的排列）$q$ ，定義一個 Permutation 的平方 $q^2 = p = q[q[i]]$

現在給予一個 Permutation 的平方 $p$，問是否能夠造出一個 Permutation $q$ 使得 $q^2 = p$ ？

想法

其實這題在戳題的時候的 tag 是戳圖論 不過看到題目的 $p[i] = q[q[i]] $

我們可以直接猜測他會是變成圖 然後找環

我們可以試著將一個 Permutation 放到圖上來觀察平方後會變成什麼樣子

就用第一個範測來看 $q = [3,4,2,1]$

對 $(i,q[i])$ 建邊

會發現我們得到了一個偶環

接著試著將 $q$ 平方做出 $p = [2,1,4,3]$ 的圖

發現這個大小為 $4$ 的偶環斷成兩個大小為 $2$ 的偶環了

接著我們再試試看第三個範測 $q = [4,5,1,2,3]$

會發現他是一個奇環

平方之後得到 $p = [2,3,4,5,1]$

同樣還是一個奇環

因此，我們可以觀察到

當有偶環時 他會斷成兩個相同大小的偶環

而奇環仍為奇環，但是指向的順序會改變

解法

（一）先對測資建圖

（二）找環

（三）將奇數環改變順序 偶數環兩兩合併（注意：不可以出現奇數個偶環 否則無答案）

程式碼:

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
#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 = 1e6+5;
int adj[N];
int visited[N];
vector<vector<int>> cycle[N];

vector<int> tmp;
void dfs(int u){
	visited[u] = 1;
	tmp.push_back(u);
	int v = adj[u];
	if(!visited[v]) dfs(v);
}

signed main(){
	fastio
	int n;
	cin >> n;
	for(int i = 1;i <= n;i++){
		int v;
		cin >> v;
		adj[i] = v;
	}
	for(int i = 1;i <= n;i++){
		if(!visited[i]){
			tmp.clear();
			dfs(i);
			cycle[tmp.size()].push_back(tmp);
		}
	}
	int ans[n+1];
	for(int i = 1;i <= n;i++){
		if(i&1){
			for(int j = 0;j < cycle[i].size();j++){
				for(int k = 0;k < i;k++) ans[cycle[i][j][k]] = adj[cycle[i][j][(k+(i-1)/2)%i]];
			}
		}else{
			if(cycle[i].size()&1){
				cout << -1 << "\n";
				return 0;
			}
			for(int j = 0;j < cycle[i].size();j += 2){
				for(int k = 0;k < i;k++){
					ans[cycle[i][j][k]] = adj[cycle[i][j+1][(i+k-1)%i]];
					ans[cycle[i][j+1][k]] = adj[cycle[i][j][k]];
				}
			}
		}
	}
	for(int i = 1;i <= n;i++) cout << ans[i] << " ";
}

Virtual Contest

共 Virtual Contest 1 場

Educational Codeforces Round 17

覺得應該要來解一些Educational Codeforces Round的題目

所以就隨便找了一場來練習

Problem A - k-th Divisor

題意：

給予一個數字 $n$ 以及 $k$

問 $n$ 的第 $k$ 個因數為何？

解法：

由於 $n \leq 10^{15}$ ，我們會發現 $\sqrt{n} \leq 3.16 \times 10^7$

因此我們可以考慮用暴搜的方式去搜到 $\sqrt{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
#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;

vector<int> v, v2;

void finddiv(int n){
	for(int i = 1;i*i <= n;i++){
		if(n%i==0) v.push_back(i);
		if(n%i==0&&i*i!=n) v2.push_back(n/i);
	}
}

signed main(){
	fastio
	int n,k;
	cin >> n >> k;
	finddiv(n);
	for(int i = v2.size()-1;~i;i--) v.push_back(v2[i]);
	if(v.size() < k) cout << -1 << '\n';
	else cout << v[k-1] << "\n";
}

Problem B - USB vs. PS/2

題意：

一台電腦有三種可能

一種是USB 一種是 PS/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
#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 a,b,c;
	cin >> a >> b >> c;
	int m;
	cin >> m;
	vector<pair<int,int>> v; //cost, type
	for(int i = 0;i < m;i++){
		int a;
		string b;
		cin >> a >> b;
		v.push_back({a,b[0]=='P'});
	}
	sort(v.begin(),v.end());
	int ans = 0, num = 0;
	for(auto x : v){
		if(x.second==0){
			if(a) a--, num++, ans += x.first;
			else if(c) c--, num++, ans += x.first;
		}else{
			if(b) b--, num++, ans += x.first;
			else if(c) c--, num++, ans += x.first;
		}
	}
	cout << num << " " << ans << "\n";
}

Problem C - Two strings

題意：

給予兩個字串 $a,b$

問最少要刪除幾個 $b$ 當中連續的子字串

才能使得 $b$ 成為 $a$ 的子序列

想法：

我們可以注意到最後的答案 一定是 $b$ 的前綴+後綴

因此 我們可以維護 $b$ 的前綴與後綴需要的 $a$ 的前綴與後綴的長度

進而得到答案

解法：

使用二分搜

難點：

這題容易因為小細節導致WA

程式碼：

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
#pragma optimize("O2");
#pragma optimize("unroll-loops")
#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
	string a,b;
	cin >> a >> b;
	int n = a.size(), m = b.size();
	int pref[m] = {}, suff[m] = {};
	//Two pointers to find the maximum pos that the pref or suff of b is subsequence of a
	fill(pref,pref+m,n);
	fill(suff,suff+m,-1);
	int i = 0, j = 0;
	while(i < n&&j < m){
		if(a[i]!=b[j]) i++;
		else if(a[i]==b[j]){
			pref[j] = i;
			i++, j++;
		}
	}
	i = n-1, j = m-1;
	while(~i&&~j){
		if(a[i]!=b[j]) i--;
		else if(a[i]==b[j]){
			suff[j] = i;
			i--,j--;
		}
	}
	string ans="";
	ans = b.substr(upper_bound(suff,suff+m,-1)-suff);
	for(int i = 0;i < m;i++){
		if(pref[i]==n) break;
		int num = upper_bound(suff,suff+m,pref[i])-suff;
		if(num <= i) continue; 
		string aa = b.substr(0,i+1), bb = b.substr(num);
		string cc = aa+bb;
		if(cc.size() > ans.size()) ans = cc;
		if(i==num-1) break;
	}
	if(ans.size()==0) cout << '-' << "\n";
	else cout << ans << "\n";
}

Problem D - Maximum Path

題意：

給予一個 $3 \times n $ 的版面以及每個格子的數字

問你能夠只經過每個格子一次的路徑 從 $(1,1)$ 走到 $(3,n)$ 的最大路徑和

想法：

這題的難處在於我們可以從右邊走到左邊

不過仔細想想 會發現其實每一條路徑 最多只會往左邊連續走一次

如果往左邊走連續兩次 那麼我們一定能找到另外一個路徑使得走過的格子相同

解法：

設 $dp[i][j]$ 為走完第 $i$ 列時 停在第 $j$ 行時所走過的最大路徑和

而 $dp[i][3]$ 為回頭走一次走完第 $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
#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 = 1e5+5;
int grid[3][N], dp[N][4];

signed main(){
	fastio
	int n;
	cin >> n;
	for(int i = 0;i < 3;i++){
		for(int j = 1;j <= n;j++){
			cin >> grid[i][j];
		}
	}
	fill(&dp[0][0],&dp[n][3],-1e18);
	dp[0][0] = 0;
	auto sum = [&](int j, int l, int r){
		int res = 0;
		if(l > r) swap(l,r);
		for(int i = l;i <= r;i++){
			res += grid[i][j];
		}
		return res;
	};
	for(int i = 1;i <= n;i++){
		for(int j = 0;j < 3;j++){
			for(int k = 0;k < 3;k++){
				dp[i][j] = max(dp[i][j],dp[i-1][k] + sum(i,j,k));
			}
		}
		dp[i][0] = max(dp[i][0], dp[i-1][3] + sum(i,0,2)); 
		dp[i][2] = max(dp[i][2], dp[i-1][3] + sum(i,0,2));
		dp[i][3] = max(dp[i][3], max(dp[i-1][0],dp[i-1][2]) + sum(i,0,2));
	}
	cout << dp[n][2] << "\n";
}