---
# System prepended metadata

title: 2023/03/31 NYCU 2023 PCCA Week 07題單
tags: [競技程式設計一]

---

---
title: '2023/03/31 NYCU 2023 PCCA Week 07題單'
disqus: hackmd
---
###### tags:`競技程式設計一` 
2023/03/31 NYCU 2023 PCCA Week 07題單
===
[TOC]

## Problem B Expeditious Cubing
### 解題關鍵 1. 浮點數運算
* 本題重點在於處理浮點數運算
* 由於浮點數判斷大於等於小於超級麻煩，加上本題有說明數字範圍都落在 20 內，所以採用「先以浮點數讀入，再轉以整數」的方式進行判斷大於等於小於的操作
* 假設現在給定浮點數 1.00 ，那我們在把 1.00 改成整數的時候只要寫 translate_num = 1.00*100 就好了嘛 ?
* 注意到電腦儲存浮點數 1.00 的方式可能是 1.00000001 或是 0.99999999999 之類的，後者很明顯跟我們想要的不同，那該怎麼做呢?
* 把 1.00 + 極小的 $eps$ 就可以解決問題啦 
### 解題關鍵 2. 判斷解的情況
#### 無解
* 假設給定 $t_1, t_2, t_3, t_4$為由小到大排列的數字
* 加入 $t_4$ 後，最佳解的時間為 $\frac{t_1+t_2+t_3}{3}~$麻
* 如果這個解比給定的 $target$ 還要大，那就無解拉
#### 輸出無限大
* 假設給定 $t_1, t_2, t_3, t_4$ 為由小到大排列的數字
* 加入 $t_4$ 後，最爛解的時間為 $\frac{t_2+t_3+t_4}{3}~$麻
* 如果這個最爛解的時間比 target 還好，那顯然 $t_5$ 愛多大有多大麻
#### 輸出有限解 
* 假設給定 $t_1, t_2, t_3, t_4$ 為由小到大排列的數字
* 觀察到 $t_5 \leq t_1$，因為比 $t_1$大也沒有意義(會被去除)
* 且 $t_5 > t_4$，因為比 $t_1$小也沒有意義(會被去除)
* 所以解題時間的平均必為 $\frac{t_2+t_3+t_5}{3}~$
### AC code
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fastio ios::sync_with_stdio(false),cin.tie(0);
#define pll pair<ll,ll>
#define F first
#define S second
#define eb emplace_back
#define mkp make_pair

const ll MAXN=1e6+5;
const ll INF=1e18;
const ll MOD=998244353;
const double eps=1e-6;

vector<ll> vec;
ll target;
double x;

void init(){
	for(ll i=0;i<4;i++){
		cin>>x;
		x+=eps;
		vec.push_back(x*100);
	}
	cin>>x;
	x+=eps;
	//存1.00可能被存成0.9999999或是1.00000001，加上eps可以避免這存取上的問題
	target=x*100;//因為判斷整數相等比較容易，所以先轉成整數
	sort(vec.begin(),vec.end());	
}

void solve(){
	if(vec[0]+vec[1]+vec[2]-3*target>0){
		cout<<"impossible\n";
	}
	else if(vec[1]+vec[2]+vec[3]-3*target<=0){
		cout<<"infinite\n";
	}
	else{
		double ans=(double((3*target-vec[1]-vec[2]))+eps)/100;
		cout<<fixed<<setprecision(2)<<ans<<'\n';
	}
}

int main(){
	fastio	
	// ll T;
	// cin>>T;
	// while(T--){
		init();
		solve();
	// }
	return 0;
}
```
## Problem DKayaking Trip
### 解題關鍵 1. 思考做法
* 這題看起來總船數 $m=\frac{b+n+e}{2}$ 很大，枚舉顯然 TLE
* 那要怎麼做會比較好呢 ?
* 觀察題目答案性質，ㄟ有單調性ㄟ
* 你問為啥答案有單調性?
* 因為假設最慢船隻可以達到船速 $v$ 好了，那真正最慢船隻的速度一定 $\geq v$麻
* 那就來試試看對答案二分搜阿
### 解題關鍵 2. 判斷二分搜的值是否合法
* 怎麼判斷當前的值 $val$，是否滿足會讓所有船速都 $\geq val$ 呢 ?
* 使用貪心的想法，我每次當前船隻配上划最慢的兩個人，但要滿足船速 $\geq val$ 這個限制
* 這個解會是最佳解
* 然後二分搜不要寫 $L,~R$ 的扣，用跳最大 $2$ 進位數字的扣，不用判斷左右界，超級好用
### 解題關鍵 3. 實作細節
* 在判斷兩個同為新手, 中手, 或老手的人是否可以一起組隊的時候，需要判斷新手, 中手, 或老手的人的數量是否 $\geq 2$，不能只有判斷 $>0$
### AC code
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fastio ios::sync_with_stdio(false),cin.tie(0);
#define pll pair<ll,ll>
#define F first
#define S second
#define eb emplace_back
#define mkp make_pair

const ll MAXN=1e6+5;

ll cnt[3],v[3],sum,c[MAXN],num[MAXN];
vector<pair<ll,pll>> vec;

void init(){
	cin>>cnt[0]>>cnt[1]>>cnt[2];
	cin>>v[0]>>v[1]>>v[2];
	sum=(cnt[0]+cnt[1]+cnt[2])/2;
	for(ll i=0;i<sum;i++)	cin>>c[i];
	sort(c,c+sum);
	for(ll i=0;i<3;i++){
		for(ll j=i;j<3;j++){
			vec.eb(mkp(v[i]+v[j],mkp(i,j)));
		}
	}
	sort(vec.begin(),vec.end());
}

void init2(){
	for(ll i=0;i<3;i++){
		num[i]=cnt[i];
	}
}

bool ok(ll i,ll j,ll k,ll val){
	if(k*(v[i]+v[j])>=val){
		if(i==j){
			if(num[i]>=2) return true;
		}
		else{
			if(num[i]>0 && num[j]>0) return true;
		}
	}
	return false;
}

bool isValid(ll val){
	init2();
	for(ll i=0;i<sum;i++){
		bool flag=false;
		for(auto it:vec){
			if(ok(it.S.F,it.S.S,c[i],val)){
				num[it.S.F]--;
				num[it.S.S]--;
				flag=true;
				break;
			}
		}
		if(!flag){
			return false;
		}
	}
	return true;
}

void solve(){
	ll ans=0,step=pow(2,60);
	while(step){
		if(isValid(ans+step)){
			ans+=step;
		}
		else{
			step/=2;
		}
	}
	cout<<ans<<'\n';
}
int main(){
	fastio
	init();
	solve();
}
```
## Problem E Counting Subsequences (Hard)
### 解題關鍵 1. 計算區間和
* 怎麼計算 $S_{i,j}=a_i+a_{i+1}+\cdots+a_j$ 呢?
* 可以利用 $pre[i]$ 紀錄 $S_k=a_0+a_1+\cdots+a_k$ 的值
* 接著我們有 $S_{i,j}=a_i+a_{i+1}+\cdots+a_j=(a_0+a_1+\cdots+a_j)-(a_0+a_1+\cdots+a_{i-1})$
* 得到$S_{i,j}=S_j-S_{i-1}$，這個我們可以利用 $pre[j]-pre[i-1]$，$O(1)$時間查詢麻

### 解題關鍵 2. 觀察題目性質
* 當我們固定連續區間和的結尾在 $a[k]$ 時，我們想問有多少個這樣的連續區間和為 47 ，相當於問有多少個 $i$ 使得 $a_i+a_{i+1}+\cdots+a_k=pre[k]-pre[i-1]=47$ 麻
* 移項後我們想問有多少個 $i$ 滿足 $pre[i-1]=pre[k]-47$ 麻
* 那就用 STL 中的 $map$ 去紀錄 $pre[i-1]$ 就好了啊

### 解題關鍵 3. 注意題目邊界 case
* 注意到 0 0 47 這筆測資會讓上面的解不能過
* 這是為什麼呢 ? ~~因為我在假解~~
* 因為我們在記錄 $pre[i-1]$ 的時候，是用 for loop 從 $i$ 跑到 $N-1$ 麻
* 接著注意到在算 $mp[pre[k]-47]$，相當於問我在前面可以從索引 $0$ 的位置開始，要連續丟掉多少個 $arr[i]$ ，才可以讓區間和變成 47 的可行解有多少個 ，但這忽略了什麼都不丟掉的 case 啊 !
* 那怎麼做 ? 就把 $mp[0]+=1$ 啊
* 因為沒有東西相加的總和 = 0 麻

### AC code
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fastio ios::sync_with_stdio(false),cin.tie(0);
#define pll pair<ll,ll>
#define F first
#define S second
#define eb emplace_back
#define mkp make_pair

const ll MAXN=1e6+5;
const ll INF=1e18;
const ll MOD=998244353;

ll N,ans,arr[MAXN];
ll pre[MAXN];
map<ll,ll> mp;

void init(){
	mp.clear();
	mp[0]=1;
	//要使得可以出現長度為1的子序列和，所以要設為1
	//什麼都不加的總和是0麻
	ans=0;
	cin>>N;
	for(ll i=0;i<N;i++){
		cin>>arr[i];
		if(i==0){
			pre[i]=arr[i];
		}
		else{
			pre[i]=arr[i]+pre[i-1];
		}
	}	
}

void solve(){
	for(ll i=0;i<N;i++){
		mp[pre[i]]++;
		ans+=mp[pre[i]-47];
	}	
	cout<<ans<<'\n';
}

int main(){
	fastio	
	ll T;
	cin>>T;
	while(T--){
		init();
		solve();
	}
	return 0;
}
```
## Problem F Fenwick Tree
### 解題關鍵 1. 選擇使用的資料結構
* 題目都說這是 $Fenwick Tree$
* 操作又是單點修改、區間查詢
* 那就直接 $BIT$ 砸下去啊
* ~~不要跟我一樣模板抄錯就好~~
### AC code
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fastio ios::sync_with_stdio(false),cin.tie(0);
#define pll pair<ll,ll>
#define F first
#define S second
#define eb emplace_back
#define mkp make_pair

const ll MAXN=1e7+5;

ll N,Q;
char c;
ll a,b,arr[MAXN];

void upd(ll id,ll x){
    for(ll i=id;i<=N;i+=i&-i) arr[i]+=x;
}

ll sum(ll id){
    ll res=0;
    for(ll i=id;i>0;i-=i&-i) res+=arr[i];
    return res;
}

void init(){
    cin>>N>>Q;
}

void solve(){
    while(Q--){
        cin>>c;
        if(c=='+'){
            cin>>a>>b;
            upd(a+1,b);
        }
        else{
            cin>>a;
            cout<<sum(a)<<'\n';
        }
    }
}

int main(){
    fastio  
    // ll T;
    // cin>>T;
    // while(T--){
        init();
        solve();
    // }
    return 0;
}
```
## Problem G Supercomputer
### 解題關鍵 1. 抓取題目重點
* 題目有兩種操作
* 第一種操作 $F$ $i$
* 代表如果 $a[i]=1$，要把 $a[i]$ 設成 0
* 如果 $a[i]=0$，要把 $a[i]$ 設成 1
* 第二種操作 $F$ $l$ $r$
* 詢問 $[l,r]$ 間 1 的數量
* 第二種操作相當於詢問 $[l,r]$ 區間和
* 總結下來，第一種操作為單點改值，第二種操作為區間查詢
* 那就開 $BIT$ 阿

### 解題關鍵 2. 判斷 a[i] 是否 = 1
* $a[i]=S_i-S_{i-1}=query(i)-query(i-1)$
* 這個操作可以在 $O(log~n)$ 時間內完成

### AC code

```cpp=
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fastio ios::sync_with_stdio(false),cin.tie(0);
#define pll pair<ll,ll>
#define F first
#define S second
#define eb emplace_back
#define mkp make_pair

const ll MAXN=1e7+5;

ll N,Q;
char c;
ll a,b,arr[MAXN];

void upd(ll id,ll x){
    for(ll i=id;i<=N;i+=i&-i) arr[i]+=x;
}

ll sum(ll id){
    ll res=0;
    for(ll i=id;i>0;i-=i&-i) res+=arr[i];
    return res;
}

void init(){
    cin>>N>>Q;
}

void solve(){
    while(Q--){
        cin>>c;
        if(c=='F'){
            cin>>a;
            if(sum(a)-sum(a-1)==0)
	            upd(a,1);
	        else
	        	upd(a,-1);
        }
        else{
            cin>>a>>b;
            cout<<sum(b)-sum(a-1)<<'\n';
        }
    }
}

int main(){
    fastio  
    // ll T;
    // cin>>T;
    // while(T--){
        init();
        solve();
    // }
    return 0;
}
```
## Problem H Just for Sidekicks
### 解題關鍵 1. 觀察題目性質
* 第一筆操作等價於單點改值
* 第三筆操作等價於區間查詢
* 那感覺就要用 $BIT$ 了阿
* 可是只開一顆 $BIT$ 紀錄當前節點是哪種寶石，第二筆操作就會爛掉阿
* 簡單，那就開六棵 $BIT$ 去紀錄每種寶石的數量

### AC code
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fastio ios::sync_with_stdio(false),cin.tie(0);
#define pll pair<ll,ll>
#define F first
#define S second
#define eb emplace_back
#define mkp make_pair

const ll MAXN=1e7+5;

ll N,Q,c;
ll a,b,bit[MAXN][7],v[7],arr[MAXN];

void upd(ll id,ll x,ll k){
    for(ll i=id;i<=N;i+=i&-i) bit[i][k]+=x;
}

ll query(ll id,ll k){
    ll res=0;
    for(ll i=id;i>0;i-=i&-i) res+=bit[i][k];
    return res;
}

void init(){
    cin>>N>>Q;
    for(ll i=1;i<=6;i++) cin>>v[i];
    string s;
    cin>>s;
    for(ll i=1;i<=N;i++){
    	arr[i]=int(s[i-1]-'0');
    	upd(i,1,arr[i]);
    }
}

void solve(){
    while(Q--){
        cin>>a>>b>>c;
        if(a==1){
        	ll now=arr[b];
        	upd(b,-1,now);
        	upd(b,1,c);
        	arr[b]=c;
        }
        else if(a==2){
        	v[b]=c;
        }
        else{
        	ll ans=0;
        	for(ll i=1;i<=6;i++){
        		ans+=v[i]*(query(c,i)-query(b-1,i));	
        	}
        	cout<<ans<<'\n';
        }
    }
}

int main(){
    fastio  
    // ll T;
    // cin>>T;
    // while(T--){
        init();
        solve();
    // }
    return 0;
}
```