---
# System prepended metadata

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

---

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

*(補) 比賽日期: 03/11*

## 賽中作答
> 賽中答題數:3/7 賽後答題數:6/7
> 賽中作答順序: 1->4->5->2->3


### 第一題
第一題是很簡單的枚舉題，只要一一計算所有b[i]+c[j]小於等於k的數即可。

不過在提交的時候發生了一點意外
傳送的結果是Compilation error
一開始還以為是程式碼出狀況
稍微修改後結果還是一樣
最後才發現是編譯器選錯
再次提交後就AC了

#### 程式碼
```cpp=
#include<iostream>
#include<vector>
#define F first
#define S second
#define ll long long
#define pii pair<int,int>
#define mkp(a,b) make_pair(a,b)
#define runrun ios_base::sync_with_stdio(false);cin.tie(0);
using namespace std;
 
int n,m,k,in;
void solve(){
    cin>>n>>m>>k;
	vector<int> b,c;
	for(int i=0;i<n;i++){
	  cin>>in;
		b.push_back(in);
	}
	for(int i=0;i<m;i++){
		cin>>in;
		c.push_back(in);
	}
	ll ans=0;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;++j){
			if(b[i]+c[j]<=k){
				++ans;
			}
		}
	}
	
	cout<<ans<<"\n";
}
 
int main(){
	int t;
	cin>>t;
	while(t--){
		solve();
	}
	
	return 0;
}
```

### 第四題
#### 題目敘述：
有編號1到n總共n個人，他們圍繞在一起。編號x的人有一顆球
接下來有m行輸入，其中包含數字r和字元c
如果c== '0'，那麼拿著球的人就會往順時針方向投擲，投給(x+r)%n編號的人
如果c== '1'，那麼拿著球的人就會往逆時針方向投擲，投給(x-r+n)%n編號的人
如果c== '?'，那麼拿著球的人就有可能往順時針或逆時針方向投擲。更仔細的說，拿到球的人可能是編號(x+r)%n或編號(x-r+n)%n的人，
試問最後可能拿到球的人共有幾人，並輸出他們的編號

由於題目有給一個n×m不會超過2e5的條件，所以可以很快速的想到應該是複雜度O(nm)的做法
知道這個條件後，我們就可以這樣做：用陣列記錄每個當下可能拿到球的人，判斷他們可以投到的位置，將處於這個位置的人設為下一個拿到球的人

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

int n,m,x;
void solve(){
	cin>>n>>m>>x;
	vector<int> dp(n,0);
	vector<int> memo,memo2;
	dp[x-1]=1;
	memo.push_back(x-1);
	char c;
	for(int i=0,d;i<m;i++){
		cin>>d>>c;
		for(int j=0;j<n;j++){
			int r=(j-d+n)%n,l=(j+d)%n;
			if((c=='0'||c=='?')&&dp[r]==1){
				memo2.push_back(j);
			}
			if((c=='1'||c=='?')&&dp[l]==1){
				memo2.push_back(j);
			}
		}
		for(auto v:memo){
			dp[v]=0;
		}
		for(auto v:memo2){
			dp[v]=1;
		}
		swap(memo,memo2);
		memo2.clear();
	}
	int cnt=0;
	for(int i=0;i<n;i++){
		if(dp[i]==1) cnt++;
	} 
	cout<<cnt<<"\n";
	for(int i=0;i<n;i++){
		if(dp[i]==1) cout<<i+1<<" ";
	}
	cout<<"\n";
	
}

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

### 第五題
賽中寫這題時完全卡住了==，剩二十分鐘才回去前面補題

### 第二題
滿直覺的greedy題，從左到右計算，如果遇到大於0的數字，那麼就分別對ak,ak+1,ak+2減去1,2,1；如果遇到等於0的數字，那就跳到下一個數字；如果遇到小於0的數字或者n-2或n-1的數字是正數的時候，那麼這個序列就是不成立的

#### 程式碼

```cpp=
#include<iostream>
#include<vector>
#define F first
#define S second
#define ll long long
#define pii pair<int,int>
#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;
	cin>>n;
	vector<int> vec(n);
	for(int i=0;i<n;i++) cin>>vec[i];
	
	bool f=true;
	int p=0;
	
	while(p<n){
		if(vec[p]==0) p++;
		else if(vec[p]>0&&p<n-2){
			vec[p+1]-=vec[p]*2;
			vec[p+2]-=vec[p];
			vec[p]=0;
		}
		else{
			f=false;
			break;
		}
	}
	if(f){
		cout<<"YES\n";
	}
	else{
		cout<<"NO\n";
	}
}
 
int main(){
	runrun
	int t;
	cin>>t;
	while(t--) solve();
	
	return 0;
}
```


### 第三題
這題條件判斷比較複雜，而且我在寫這題時已經剩不到十分鐘了，所以最後我是沒有做出來的 :(

## 賽後補題
> 賽中答題數:3/7 賽後答題數:6/7
> 賽後補題順序: 3->5->6

### 第三題
這題真的不難，可惜最後時間緊湊，腦子一時間轉不過來。題目要求字串總共有幾個完整的map跟pie。除了記錄這兩個單字之外，還要考慮出現mapie的情況，所以只要用五個字元記錄，然後做出對應的判斷就行

#### 程式碼
```cpp=
#include<bits/stdc++.h>
#define pii pair<int,int>
#define F first
#define S second
#define mkp(a,b) make_pair(a,b)
using namespace std;
 
void solve(){
	int n,ans=0;
	string S;
	cin>>n>>S;
	char c[5]={'0','0','0','0','0'};
	for(int i=0;i<n;i++){
		for(int j=0;j<4;j++){
			c[j]=c[j+1];
		}
		c[4]=S[i];
		if(c[2]=='p'&&c[3]=='i'&&c[4]=='e'){
			ans++;
		}
		if(c[2]=='m'&&c[3]=='a'&&c[4]=='p'){
			ans++;
		}
		if(c[0]=='m'&&c[1]=='a'&&c[2]=='p'&&c[3]=='i'&&c[4]=='e'){
			ans--;
		}
	}
	
	cout<<ans<<"\n";
}
int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);
	int t;
	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}
```

### 第五題
仔細閱讀題目敘述之後，我才發現我比賽時理解錯題意了。題目要求製造連續k座橋最小所需花費的成本。製作一座橋所需的最小成本可以用單調序列得到，而計算連續的成本只要簡單的用陣列記錄就行了

#### 程式碼
```cpp=
#include<bits/stdc++.h>
#define F first
#define S second
#define ll long long
#define pii pair<ll,ll>
#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,d;
	cin>>n>>m>>k>>d;
	vector<vector<ll> > road(n,vector<ll>(m));
	vector<pii> A;
	for(int i=0;i<n;i++){
		deque<pii> deq;
		for(int j=0;j<m;j++){
			cin>>road[i][j];
			if(j==0){
				deq.push_back(mkp(1,0));
				continue;
			}
			
			while(!deq.empty()&&deq.front().S<j-d-1){
				deq.pop_front();
			}
			ll cnt=road[i][j]+deq.front().F+1;
			while(!deq.empty()&&deq.back().F>=cnt){
				deq.pop_back();
			}
			deq.push_back(mkp(cnt,j));
		}
		A.push_back(deq.back());
	}
	ll ans=2e18,tmp=0,cnt=0;
	for(int i=0;i<n;i++){
		cnt++;
		tmp+=A[i].F;
		if(cnt>=k){
			if(ans>tmp) ans=tmp;
			tmp-=A[i-k+1].F;
		}
	}
	cout<<ans<<"\n";
}

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

### 第六題
這題想法單純，實作卻有很多細節，以下是我的想法:
* 紀錄a陣列數字間距離最大d1和次大d2，還有最大距離旁的兩個數字nex跟pre
* 如果d1==d2的話，那麼答案必定為d1
* 否則，對陣列f進行排序
* 完成排序後，我們就可以對陣列f進行二分搜
* 那要搜什麼呢？
* 我們的目標是找到d[i]+f[j]放入陣列a，使陣列間的數字間距離最小
* 同時我們知道：如果在陣列a放入一個(nex+pre)/2的數字，其命名為tar，那麼tar就會落在nex跟pre之間，並且d1的距離必定減少最多
* 知道這些後，我們就可以用二分搜尋找有沒有符和或靠近tar的組合，得到這兩個數字間可分割成的距離
* 最後，這些計算後的距離還要跟d2比較，答案就是這些數字中的最大值
#### 程式碼
```cpp=
#include<bits/stdc++.h>
#define F first
#define S second
#define int long long
#define pii pair<int,int>
#define mkp(a,b) make_pair(a,b)
#define runrun ios_base::sync_with_stdio(false);cin.tie(0);
using namespace std;

int v,n,m,dis=0,pre,nex,sec;
vector<int> a,d,k; 
int bsearch(int v,int tar){
	int l=0,r=m-1,mid;
	while(l<=r){
		mid=(l+r)/2;
		if(v+k[mid]>tar){
			r=mid-1;
		}
		else if(v+k[mid]<=tar){
			l=mid+1;
		}
	}
	int ans=dis;
	if(l<m) ans=min(ans,max(v+k[l]-pre,nex-(v+k[l]) ));
	if(r>=0) ans=min(ans,max(v+k[r]-pre,nex-(v+k[r]) ));
	if(ans<sec) ans=sec;
	return ans;
}

int solve(){
	int in;
	cin>>v>>n>>m;
	dis=0;
	sec=0;
	a.clear();
	d.clear();
	k.clear();
	for(int i=0;i<v;i++){
		cin>>in;
		a.push_back(in);
		if(i>0){
			if(dis<=a[i]-a[i-1]){
				pre=a[i-1]; nex=a[i];
				sec=dis;
				dis=a[i]-a[i-1];
			}
			else if(sec<a[i]-a[i-1]){
				sec=a[i]-a[i-1];
			}
		}
	}
	for(int i=0;i<n;i++){
		cin>>in;
		d.push_back(in);
	}
	for(int i=0;i<m;i++){
		cin>>in;
		k.push_back(in);
	}
	if(dis==sec) return dis;
	sort(k.begin(),k.end());
	int ave=(pre+nex)/2;
	int ans=2e9+5;
	for(int i=0;i<n;i++){
		ans=min(ans,bsearch(d[i],ave));
	}
	
	return ans;
}

signed main(){
	runrun
	int t;
	cin>>t;
	while(t--){
		cout<<solve()<<"\n";
	}
	
	return 0;
}
```

*(補) 截稿日期:03/21*
