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