北市賽倒數12天

今天解了2017北市賽的題目

還有晚上打了AtCoder和Codeforces

不過Codeforces比較晚 所以晚點補

2017 北市賽

這一年的題目真的比較難(((ﾟДﾟ;)))

我預估只能拿到 $400$ 分左右 可能再更低 不像昨天解的 2018 那樣和藹可親

然後2017的北市賽的二、三題之前也寫過了 所以今天又重新解了一次

解法大致上滿相似的 所以我這裡一樣用之前的Code整理過來

第一題、編碼問題

這題我不太確定怎麼解 但是我用頗暴力的方式解決了

可能會有錯誤

不負責任程式碼

#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;
//A  B  C  D
//01 10 00 1
//1001 DCD, BA 
signed main(){
	fastio
	int n;
	cin >> n;
	vector<string> v;
	queue<string> q;
	int num = 1;
	for(int i = 0;i < n;i++){
		string s;
		cin >> s;
		num = lcm(num,s.size());
		v.push_back(s);
		q.push(s);
	}
	map<string,int> m;
	while(!q.empty()){
		string tmp = q.front(); q.pop();
		for(int i = 0; i < n;i++){
			if(tmp.size()+v[i].size() <= num*2){
				if(m[tmp+v[i]]){
					cout << 0 << "\n";
					return 0;
				}
				q.push(tmp+v[i]);
				m[tmp+v[i]]++;
			}
		}
	}
	cout << 1 << "\n";
}

第二題、格鬥大賽 (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 直接使用迴圈也可解出這題

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

第三題、數字密碼鎖

這題感覺就是當年的送分題（10/24號解了當年的題目 還真的是最簡單的==

這題沒什麼難度

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

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

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

程式碼

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

第四題、阿里巴巴與四十大盜（Thief）

$0/1$ 背包問題 但是多了一維的限制

這題我真的想不到比 $O(nxy)$ 更好的解法了

有想過$O(nv)$ ($v$ 為總價值) 但是最後解法還是會退化成 $O(2^nv)$

子題一、二、三

$O(nxy)$ 解

設 $dp[i][j][k]$ （$i$ 表示第幾個物品，$j$ 表示總重量, $k$ 表示總體積）

其中$j,k$可以任意換成重量、體積、價值 任選兩個來做$dp$

這樣就可以拿到 $51$ 分了

子題四

有沒有比 $O(nxy)$ 更快的解法阿 拜託救救我QQ

第五題、賞櫻（Sakura）

這題我真的想不到

而且這題我記得我有印象

tmw曾經三年前在Codeforces問過這題的解法說他也想不到這題的解法

子題一、二、特別測資

應該能暴力去做來拿到$20$ 或 $40$ 或 $63$ 分 但我不確定 QQ

子題三

我真的不會 會的人應該也很少吧…

AtCoder Regular Contest 106

這場我打的不怎麼樣 不過還是來打個 pA ~ pC 的解法好了

pA - 106

很直接 找到 $(A,B)$ 能使 $3^A+5^B=N$

就直接暴搜就好了 複雜度也不會很高

但是在解這題的時候沒看到 Positive Integers 砸了兩次WA (´;ω;`)

程式碼

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

pB - Values

這題一開始看到的時候以為要輸出次數 想了一下子

不過只要輸出是否能達成數值由 $a$ 變成 $b$

找出連通塊並看連通塊內的節點的數值在 $a$ 與 $b$ 中是否相等即可

程式碼

#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;
vector<int> adj[N];
int vis[N], a[N], b[N];
int add1, add2;

void dfs(int u){
	vis[u] = true;
	add1 += a[u], add2 += b[u];
	for(auto v : adj[u]){
		if(!vis[v]) dfs(v);
	}
}

signed main(){
	fastio
	int n,m;
	cin >> n >> m;
	for(int i = 1;i <= n;i++) cin >> a[i];
	for(int i = 1;i <= n;i++) cin >> b[i];
	while(m--){
		int u,v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	for(int i = 1;i <= n;i++){
		add1 = 0, add2 = 0;
		if(!vis[i]) dfs(i);
		if(add1!=add2){
			cout << "No\n";
			return 0;
		}
	}
	cout << "Yes\n";
}

pC - Solutions

時間安排問題 這個應該是每個人學到的前幾個 Greedy 題目

而這題給你正確作法與錯誤作法

問你能否輸出能使第一個作法比第二個作法找到的區間多 $M$ 個區間

題目上有寫 $-N \leq M \leq N$

但是我們可以想到下面的解法不可能得到比上面更優的答案

所以當 $M < 0$ 時 我們可以直接輸出 $-1$

接下來 我們該如何去構造呢

首先 如果我們能夠限制下面的解法最多只能有一個答案

那麼 我們就可以去構造使得上面獲得 $M+1$ 個答案

要限制下面的解法 其實非常簡單 只要輸出 $[1,10^9]$ 即可

但是題目同時限制了你要輸出 $N$ 個區間

所以我們可以額外輸出 $[2,10^9-1], [3,10^9-2]$ 這樣子沒有用的區間來限制答案

最後我們就能夠構造出答案了 （注意： $N=1, M=0$ 時是有解的）

程式碼

#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,m;
	cin >> n >> m;
	if(m < 0){
		cout << -1 << "\n";
		return 0;
	}
	if(n==1&&m==0){
		cout << 1 << " " << (int)1e9 << "\n";
		return 0;
	}
	//5 1 => [1,10^9], [2,10^9-1], [3,10^9-2], [4,5], [6,7]
	if(n < m+2){
		cout << -1 << "\n";
		return 0;
	}
	cout << 1 << " " << (int)1e9 << "\n";
	for(int i = 1;i <= n-(m+2);i++){
		cout << 1+i << " " << (int)1e9-i << "\n";
	}
	for(int i = 0; i <= m;i++){
		cout << n-m+2*i << " " << n-m+2*i+1 << "\n";
	}
}