---
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;
}
```
Sign in with Wallet
Connect another wallet