---
# System prepended metadata

title: 'Codeforces Round #938 (div.3) 紀錄'

---

# Codeforces Round #938 (div.3) 紀錄

*比賽日期: 04/09*

### 比賽連結 : https://codeforces.com/contest/1955

## 賽中作答
> 賽中答題數:2/8 賽後答題數:7/8

以結果來說，這場比賽實在慘不忍睹ˊnˋ，雖然主要原因是我跑去先寫後面幾題，導致後來沒時間把前面的題目做完，不過比賽計算分數的方式就是答越多題越高分，這麼做是必須冒著很大的風險的，下次應該確實先把前幾題做完，再來思考後面的題目該怎麼做。

### 第一題

考慮是否一次就買兩個，如果不超出需求並且比購買一個還划算的話，那麼就盡可能買兩個。 

#### 程式碼
``` cpp=
#include<bits/stdc++.h>
#define ll long long
#define pii pair<ll,ll>
#define F first
#define S second
#define mkp(a,b) make_pair(a,b)
#define runrun ios_base::sync_with_stdio(false);cin.tie(0);
using namespace std;

void solve(){
	int n,a,b;
	cin>>n>>a>>b;
	cout<<min((n/2)*b+(n%2)*a,n*a)<<"\n";
}

int main(){
	int t;
	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}
```

### 第四題
給定兩個陣列a跟b (|a|>|b|)，題目要求對於陣列a，找到至少k個數字跟b相同的子序列有幾個。這題要先存下b裡面的數字，再來用雙指針維護a的子序列裡面的數字，就可以達成了，時間複雜度O(n+m)=O(n)。


#### 程式碼
``` cpp=
#include<bits/stdc++.h>
#define ll long long
#define pii pair<ll,ll>
#define F first
#define S second
#define mkp(a,b) make_pair(a,b)
#define runrun ios_base::sync_with_stdio(false);cin.tie(0);
using namespace std;

void solve(){
	int n,m,k,in;
	cin>>n>>m>>k;
	map<int,int> disc;
	vector<int> cnt,vec,U;
	for(int i=0;i<n;i++){
		cin>>in;
		vec.push_back(in);
	}
	int sz=0;
	for(int i=0;i<m;i++){
		cin>>in;
		if(disc.find(in)==disc.end()){
			cnt.push_back(0);
			U.push_back(0);
			disc[in]=sz++;
		}
		U[disc[in]]++;
	}
	int C=0,ans=0;
	for(int i=0;i<n;i++){
		if(i-m>=0&&disc.find(vec[i-m])!=disc.end()){
			if(U[disc[vec[i-m]]]>--cnt[disc[vec[i-m]]]) C--;
		}
		if(disc.find(vec[i])!=disc.end()){
			if(U[disc[vec[i]]]>= ++cnt[disc[vec[i]]]) C++;
		}
		
		if(i>=m-1&&C>=k) ans++;
	}
	cout<<ans<<"\n";
}

int main(){
	runrun
	int t;
	cin>>t;
	while(t--){
		solve();
	}
	
	return 0;
}
```


## 賽後補題
> 賽中答題數:2/8 賽後答題數:6/8


### 第二題
給定n^2^個數字 (注意n<=500)，判斷這些數字可不可以構成向下遞增c，向右遞增d的矩陣。
由於最左上角的數字必為最小，若以這個數字為基準，就能確認其右方和下方的數字是否符合遞增條件，進一步判斷整個矩陣是否符合題目要求。
若採用了枚舉的方式，時間複雜度會高達O(n^4^)，這不是我們想要的結果；若先對數字做排列，那麼就可以用二分搜快速找到需要的數字，時間複雜度降為O(n^2^logn)。

#### 程式碼
``` cpp=
#include<bits/stdc++.h>
#define ll long long
#define pii pair<ll,ll>
#define F first
#define S second
#define mkp(a,b) make_pair(a,b)
#define runrun ios_base::sync_with_stdio(false);cin.tie(0);
using namespace std;
vector<int> vec,check;
int bsearch(int tar){
	int l=0,r=vec.size()-1,mid;
	while(l<=r){
		mid=(l+r)/2;
		if(vec[mid]<tar){
			l=mid+1;
		}
		else{
			r=mid-1;
		}
	}
	return l;
}

void solve(){
	int n,a,b,in;
	cin>>n>>a>>b;
	vec.clear();
	check.clear();
	for(int i=0;i<n*n;i++){
		cin>>in;
		vec.push_back(in);
		check.push_back(0);
	}
	sort(vec.begin(),vec.end());
	bool f=1;
	int tm=vec[0];
	for(int i=0;i<n;i++){
		int p2=bsearch(tm)-1;
		if(vec[p2+1]==tm){
			while(p2<n*n-1&&check[++p2]);
			if(p2>=n*n||vec[p2]!=tm) {f=0;break;}
		} else {f=0;break;}
		check[p2]=1;
		for(int j=1;j<n;j++){
			int p3=bsearch(tm+j*b)-1;
			if(vec[p3+1]==tm+j*b){
				while(p3<n*n-1&&check[++p3]);
				if(p3>=n*n||vec[p3]!=tm+j*b) {f=0;break;}
			} else {f=0;break;}
			check[p3]=1;
		if(!f) break;
		tm+=a; 
	}
	if(f) cout<<"Yes\n";
	else cout<<"No\n";
}

int main(){
	int t;
	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}
```


### 第三題
注意！！有海怪襲擊！
有一列總數n艘戰艦的轟炸戰隊，每艘戰艦有各自的耐久度ai，海怪會攻擊輪流攻擊最靠左/右的戰艦，每次攻擊會讓一艘戰艦減少1點耐久度，若耐久度降至0，那麼那艘戰艦就會沉入海底。
給定海怪總共攻擊的次數k，目標是記錄總共有幾艘戰艦被擊沉。
為了加快計算的速度，我們要在O(1)的時間計算一艘戰艦被擊沉需要花費的攻擊，總時間複雜度便是O(n)。

#### 程式碼

``` cpp=
#include<bits/stdc++.h>
#define ll long long
#define pii pair<ll,ll>
#define F first
#define S second
#define mkp(a,b) make_pair(a,b)
#define runrun ios_base::sync_with_stdio(false);cin.tie(0);
using namespace std;

ll ans;
vector<ll> vec;
void Check(ll &l,ll &r){
	if(vec[l]==0){
		++l;
		++ans;
	}
	if(vec[r]==0){
		--r;
		++ans;
	}
}

void solve(){
	ll n,k,in;
	cin>>n>>k;
	vec.clear();
	for(int i=0;i<n;i++){
		cin>>in;
		vec.push_back(in);
	}
	ll l=0,r=n-1,cnt=1;
	ans=0;
	while(1){
		if(l>r) break;
		else if(l==r){
			if(vec[l]<=k){
				ans++;
			}
			break;
		}
		ll m=min(vec[l],vec[r]);
		if(2*m<=k){
			k-=2*m;
			vec[l]-=m;
			vec[r]-=m;
			Check(l,r);
		}
		else{
			ll m1=k/2;
			if(k%2){
				vec[l]-=m1+1;
				vec[r]-=m1;
			}
			else{
				vec[l]-=m1;
				vec[r]-=m1;
			}
			Check(l,r);
			break;
		}
	}
	cout<<ans<<"\n";
}

int main(){
	runrun
	int t;
	cin>>t;
	while(t--){
		solve();
	}
	
	return 0;
}
```

### 第五題
一道Greedy題加上一點變數的應用，其實寫這題時原本有用到線段樹~~蠻毒瘤的~~，結果剛好被測資的範圍卡住了，吃了TLE。稍微參考官方的Solution後，才改成現在這種樣式。

#### 程式碼

``` cpp=
#include<bits/stdc++.h>
#define ll long long
#define pii pair<ll,ll>
#define F first
#define S second
#define mkp(a,b) make_pair(a,b)
#define runrun ios_base::sync_with_stdio(false);cin.tie(0);
using namespace std;

int n;
bool func(vector<bool> b,int l){
	int cnt=0;
	int p=0;
	vector<int> paper;
	for(int i=0;i<n;i++){
		if(p<paper.size()&&paper[p]==i) {cnt--;p++;}
		if(!(b[i]^(cnt%2))&&i<=n-l){
			cnt++;
			paper.push_back(i+l);
		}
		b[i]=b[i]^(cnt%2);
	}
	bool t=1;
	for(int i=0;i<n;i++){
		t=t&b[i];
	}
	return t;
}

void solve(){
	char ch;
	cin>>n;
	vector<bool> N;
	for(int i=0;i<n;i++){
		cin>>ch;
		N.push_back((ch=='1')? 1:0);
	}
	
	int L=0,R=n-1,M,ans=1;
	for(int i=1;i<=n;i++){
		if(func(N,i)) ans=i;
	}
	
	cout<<ans<<"\n";
	
}

int main(){
	int t;
	cin>>t;
	while(t--){
		solve();
	}
	
	return 0;
}
```
### 第六題
\\\\英文閱讀能力大爆炸//
這題我真的卡了很久，從比賽時就看不懂這題在幹嘛，一直到寫這題心得前還是不懂，後來我跑去看有人寫的中文題解後，才總算搞懂這題在做什麼，而且感覺還挺簡單的?
要讓計算的結果為零，我們可以知道，每種數字剩餘的數量無非都是偶數，不然就是123都得是奇數，所以我們只要想辦法找到可以獲勝最多次的貪心策略，就可以得到答案了。


#### 程式碼
``` cpp=
#include<bits/stdc++.h>
#define ll long long
#define pii pair<ll,ll>
#define F first
#define S second
#define mkp(a,b) make_pair(a,b)
#define runrun ios_base::sync_with_stdio(false);cin.tie(0);
using namespace std;

int ar[5];

void solve(){
	int cnt=0,tail=0;
	for(int i=1;i<=4;++i){
		cin>>ar[i];
		if(ar[i]>0&&tail==0) tail=i;
		cnt+=ar[i];
	}
	int s=0,ans=0;
	for(int i=1;i<=4;++i){
		if(ar[i]%2){
			s=s^i;
		}
	}
	while(cnt){
		if(s==0) ++ans;
		for(int i=4;i>=1;--i){
			if(i==tail){
				s=s^i;
				--ar[i];
				break;
			}
			else if(ar[i]>0&&(s^i)==0){
				s=s^i;
				--ar[i];
				break;
			}
			else if(i==4&&ar[i]%2){
				s=s^i;
				--ar[i];
				break;
			}
			else if(ar[i]>0&&s==0){
				s=s^i;
				--ar[i];
				break;
			}
		}
		--cnt;
	}
	
	cout<<ans<<"\n";	
}

int main(){
	int t;
	cin>>t;
	while(t--){
		solve();
	}
	
	return 0;
}
```


### 第七題
這題就是二維DP和GCD實作結合在一起的題目，以DP來說算是比較基本的題型。我覺得比較困難地方是執行時間的評估。
這題的我的作法時間複雜度是O(nmk)，k是初始值的因數數量，其實蠻難判斷是否合理(至少對我來說)，不過就結果來說，這樣的作法被允許的。
這題還有一個我沒有注意到的點，我做狀態轉移的時候，是紀錄當下可以延伸最遠的最大公因數，如果這麼做，還要花更多時間在找最大公因數，對已經緊繃的執行時間又上了一道枷鎖。
換一個想法，只記錄當前選擇的數字能否繼續延伸，這樣不但意圖更明確，又避免了不必要的計算，執行速度更是比前面的作法快了四倍。

#### 程式碼

```cpp=
#include<bits/stdc++.h>
#define ll long long
#define pii pair<ll,ll>
#define F first
#define S second
#define mkp(a,b) make_pair(a,b)
#define runrun ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;

int n,m;
bool dp[101][101];
vector<vector<int> > road;

bool func(int pre){
	for(int i=0;i<=n;++i){
		for(int j=0;j<=m;j++){
			dp[i][j]=0;
		}
	}
	dp[1][1]=1;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			if(i+j==2) continue; 
			if(road[i][j]%pre==0) dp[i][j]=dp[i][j-1]|dp[i-1][j];
		}
	}
	return dp[n][m];
}

void solve(){
	cin>>n>>m;
	road.assign(n+1,vector<int>(m+1));
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>road[i][j];
		}
	}
	vector<int> vec;
	for(int i=1;i*i<=road[1][1];i++){
		if(road[1][1]%i==0){
			vec.push_back(i);
			vec.push_back(road[1][1]/i);
		}
	}
	sort(vec.begin(),vec.end());
	
	int p=vec.size(),ans;
	while(!(func(vec[--p])));
	ans=vec[p];
	
	cout<<ans<<"\n";
}

int main(){
	runrun
	int t;
	cin>>t;
	while(t--){
		solve();
	}
	
	return 0;
}
```

*截稿日期 : 04/30*