---
title: TNHSPA_四月場
tags: TNHSPA,contest
description: View the slide with "Slide Mode".
---
# **TNHSPA_四月場**
## 公告
:::success
4/16 公告
TNHSPA_四月場 題解已上線
:::
:::success
4/16 公告
TNHSPA_四月場 已結束，感謝大家的參與
:::
:::danger
4/3 公告
本次比賽因與 2023成大高中生邀請賽 撞期，估將原訂 4/9 之比賽，延至 4/16
:::
---
## 比賽資訊
* 時間 ： 4 月 16 日 14:00 ~ 17:00
* 地點 ： [Codeforces Group](https://codeforces.com/group/vyc3POHHoZ/contests)
* 賽制 ： IOI 制
* 題數 ： 6 題
* 命題範圍 ： 大約比照能競南區賽、資奧初選（包含但不限於：貪心、DP、暴搜、基礎圖論、資結等）
* 程式語言使用限制 ： 無
---
## 比賽結果
### 最終排名
### 題解
#### 第一題
將所有金幣數量加起來，如果總和小於k就輸出0，否則輸出除以k的餘數，然後記得開long long就沒問題了。
:::spoiler AC code
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,k,a;
long long int sum=0;
cin>>n>>k;
for(int i=0;i<n;i++){
cin>>a;
sum+=a;
}
if(sum>=k)cout<<sum%k<<'\n';
else cout<<"0\n";
}
```
:::
#### 第二題
首先我們可以知道，先不考慮操作一的情況下，只需要執行一次操作二將字串排成升冪，就可以得到最小的字典序，也因此只會有以下兩種情況，執行m次操作一，該情況只需要從頭把非’a’字元替換成’a’就好；或者執行一次操作二與m-k次操作一，另外操作一需要由順序較後面的字母開始替換成’a’，才能確保最終排出來的字典序最小，若該部分沒注意到，可能只會拿subtask 1。最後再將以上兩種情況做比較，取字典序較小的，複雜度O(n log n)。
:::spoiler AC code
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,m,k;
string s,t;
cin>>n>>m>>k>>s;
t=s;
for(int i=0,j=m;i<n&&j>0;i++){
if(s[i]!='a')s[i]='a',j--;
}
sort(t.begin(),t.end());
for(int i=n-1,j=m-k;i>=0&&j>0;i--){
if(t[i]!='a')t[i]='a',j--;
}
sort(t.begin(),t.end());
if(k<=m)cout<<min(s,t)<<'\n';
else cout<<s<<'\n';
}
```
:::
#### 第三題
首先考慮對於每個位置，水可以淹到的最高高度(此處是指a_i+h_i，即水面相對於高度0)，必須滿足其左邊有一座高山大於等於此高度，右邊也是一樣。因此，事實上可以先對數列a做前綴最大值與後綴最大值，結果分別會是某個位置往左找的最高高度與往右找的最高高度，最後只要再將這兩個值較小的，再減掉a_i就是h_i了，複雜度O(n)。
:::spoiler AC code
```cpp=
#include<bits/stdc++.h>
using namespace std;
int a[(int)1e6+5],pre[(int)1e6+5],suf[(int)1e6+5];
int main(){
int n;
long long int ans=0;
cin>>n;
for(int i=0;i<n;i++)cin>>a[i];
for(int i=1;i<=n;i++)pre[i]=max(pre[i-1],a[i-1]);
for(int i=n;i>=1;i--)suf[i]=max(suf[i+1],a[i-1]);
for(int i=1;i<=n;i++)ans+=max(0,min(pre[i],suf[i])-a[i-1]);
cout<<ans<<'\n';
}
```
:::
#### 第四題
暫時不考慮跳躍高度的限制，只考慮往後跳躍的距離，我們可以利用dp解決該問題，利用以下轉移式，其中i為當前位置、j為跳躍距離。
dp[i+j]=min(dp[i+j],dp[i]+1)
接著我們只需要在dp過程中，對於每個位置i，迭代每個跳躍距離j的同時，將j由1到p，並沿途記錄途中高度最大值，倘若遇到最大高度大於起跳點的高度加上跳躍高度j/p，那麼可以直接開始下一個i，可以透過高度最大值向後會遞增，而跳躍高度會遞減來證明這件事。複雜度O(lp)。
:::spoiler AC code
```cpp=
#include<bits/stdc++.h>
using namespace std;
int a[(int)1e5+5],dp[(int)1e5+5];
int main(){
int l,p;
cin>>l>>p;
for(int i=0;i<=l;i++)cin>>a[i];
for(int i=1;i<=l;i++)dp[i]=1e9;
for(int i=0;i<l;i++){
int hi=0;
for(int j=1;j<=p&&i+j<=l;j++){
hi=max(hi,a[i+j]);
if(a[i]+p/j<hi)continue;
dp[i+j]=min(dp[i+j],dp[i]+1);
}
}
if(dp[l]==1e9)cout<<"-1\n";
else cout<<dp[l]<<'\n';
}
```
:::
#### 第五題
首先可以先計算出對於不同的字母數量n，其單字總量為多少，將其設為f[n]，透過題目中的造字規則我們可以知道，如果先任選其中一個字母當作第一位，那麼剩下n-1個字母可以湊出f[n-1]種單字，將其接在後面都是合法的，另外後面不接東西也是合法的，因此可以得到f[n]=(f[n-1]+1)*n，另外f[1]=1。
接下來，我們可以發現，對於目前有n個字母，第1到f[n-1]+1個單字會是由排列第一的字母開頭的，第(f[n-1]+1)+1到2(f[n-1]+1)個單字會由排列第二的字母開頭，往後以此類推，因此若我們要求出其中的第k個單字，可以由k/(f[n-1]+1)來計算其開頭的單字，接著將k對f[n-1]+1進行取模即可得到更後面的部分是剩下n-1個字母字典序第幾小的組合，另外由於我們知道若後面什麼都沒接的字典序會最小，因此須注意這種情況要跳出迴圈不繼續往後找。
:::spoiler AC code
```cpp=
#include<bits/stdc++.h>
using namespace std;
long long int a[25];
int main(){
a[0]=1;
for(int i=1;i<20;i++)a[i]=(a[i-1]+1)*(i+1);
int n,q;
long long int k;
string s,ans;
vector<char>v;
cin>>n>>q>>s;
while(q--){
cin>>k;
k--;
ans.clear();
v.clear();
for(char c:s)v.push_back(c);
for(int i=n-2;i>=0;i--){
int x=k/(a[i]+1);
ans+=v[x];
v.erase(v.begin()+x);
k%=(a[i]+1);
if(k==0)break;
k--;
if(i==0)ans.push_back(v[0]);
}
if(n==1)ans+=v[0];
cout<<ans<<'\n';
}
}
```
:::
#### 第六題
這題需要先注意到題目給的線索，由於有n個點與n-1條邊，因此圖的類型必為樹，因此任兩點間一定有唯一的路徑，所以使被感染城市盡量少的做法就是只直接從x走到y，不走多餘的路徑。
* Subtask1
可以直接對每筆查詢做dfs，複雜度O(nq)。
* Subtask2
應該是最好拿的子任務，由於圖的類型為鏈，且照點的編號相接，因此可以直接透過簡單的數學計算得到結果。
* Subtask3
可以允許整體複雜度O(n^2)，但沒有特別想到這樣的作法。
* Subtask4
要通過整題的做法，必須利用lca來確保每筆查詢在O(log n)的複雜度下，透過任取一點作為根，進行dfs以計算lca，利用lca可以求出任兩點間的一部分路徑資訊，若lca(x,z)與lca(y,z)皆不為z或者lca(x,y)深度大於z的深度，則z不在x到y的路徑上，若z在路徑上，則可以透過lca(x,z)與lca(y,z)計算出z在路徑上的哪個位置，藉以求出經過z後會感染多少城市。建表複雜度O(n log n)，單筆查詢複雜度O(log n)，整體複雜度O((n+q)log n)。
:::spoiler AC code
```cpp=
#include<bits/stdc++.h>
using namespace std;
vector<int>cnt[(int)1e5+5];
int lev[(int)1e5+5],up[(int)1e5+5][20];
void dfs(int x,int y){
up[x][0]=y;
for(int i=1;i<=17;i++)up[x][i]=up[up[x][i-1]][i-1];
for(int i:cnt[x]){
if(i==y)continue;
lev[i]=lev[x]+1;
dfs(i,x);
}
}
int lca(int x,int y){
if(lev[x]>lev[y])swap(x,y);
for(int i=17;i>=0;i--){
if(lev[x]<=lev[up[y][i]])y=up[y][i];
}
for(int i=17;i>=0;i--){
if(up[x][i]!=up[y][i])x=up[x][i],y=up[y][i];
}
if(x==y)return x;
else return up[x][0];
}
int main(){
int n,q,u,v,x,y,z;
cin>>n>>q;
for(int i=0;i<n-1;i++){
cin>>u>>v;
cnt[u].push_back(v);
cnt[v].push_back(u);
}
for(int i=1;i<=n;i++)lev[i]=1e9;
lev[1]=0;
dfs(1,1);
while(q--){
cin>>x>>y>>z;
if(lca(x,z)!=z&&lca(y,z)!=z||lca(lca(x,y),z)!=lca(x,y))cout<<"1\n";
else if(lca(y,z)==z)cout<<lev[y]-lev[z]+1<<'\n';
else cout<<lev[y]+lev[lca(x,z)]-lev[lca(x,y)]*2+1<<'\n';
}
}
```
:::
---
[DC群組 Join us](https://discord.gg/jpxZT9nZ5k)
[回到首頁](https://hackmd.io/@TNHSPA/intro)
[Codeforces使用教學](https://hackmd.io/@TNHSPA/cf_intro)
Sign in with Wallet
Connect another wallet