# 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*
Sign in with Wallet
Connect another wallet