---
title: TNHSPA_五月場
tags: TNHSPA,contest
description: View the slide with "Slide Mode".
---
# **TNHSPA_五月場**
## 公告
:::success
5/28 公告
TNHSPA_五月場 題解已上線
:::
:::success
5/21 公告
TNHSPA_五月場 已結束，感謝大家的參與
:::
:::danger
4/18 公告
因部分協辦校期中考與原定 5/14 之比賽同週，估將原比賽延至 5/21
:::
---
## 比賽資訊
* 時間 ： 5 月 21 日 14:00 ~ 17:00
* 地點 ： [Codeforces Group](https://codeforces.com/group/vyc3POHHoZ/contests)
* 賽制 ： IOI 制
* 題數 ： 6 題
* 命題範圍 ： 大約比照能競南區賽、資奧初選（包含但不限於：貪心、DP、暴搜、基礎圖論、資結等）
* 程式語言使用限制 ： 無
---
## 比賽結果
### 最終排名
### 題解
#### 第一題
先利用陣列或STL紀錄每個字母的數量。很顯然的，對於長度為偶數的回文，每個字母皆會出現偶數次，而對於長度為奇數的回文，除了一個被放在正中間的字母出現奇數次，其餘字母也是出現偶數次。因此我們可以直接將每個字母的數量檢查，如果某個字母數量是偶數，就將其全部用以產生回文；如果數量是奇數，就將其中一個保留下來，剩下的數量即是偶數，也全部用以產生回文，最後再判斷，若有多出來的將其放在回文的中間，並且答案加一。
:::spoiler AC code
```cpp=
#include<bits/stdc++.h>
using namespace std;
int cnt[30];
int main(){
int n,ans=0;
bool odd=0;
char c;
cin>>n;
while(n--){
cin>>c;
cnt[c-'A']++;
}
for(int i=0;i<26;i++){
if(cnt[i]%2){
odd=1;
ans+=cnt[i]-1;
}else{
ans+=cnt[i];
}
}
if(odd)ans++;
cout<<ans;
}
```
:::
#### 第二題
該題可以透過觀察，發現重要性質，例如可以將原先就連續的塗黑正方形視為一體，而不必再將其裁剪成很多小正方形，另外，對於正方形數量眾多時，為了把塗黑的正方形獨立拿出來連在一起，大部分的塗黑正方形會需要裁剪兩刀(左邊界、又邊界)才能拿出來排，不過可以有兩段可以只有剪一刀，以其作為最後連續塗黑正方形的左邊界與右邊界。綜合以上所述，我們可以得出我們可以拿k/2+1段連續的塗黑正方形串起來，接著只需要將原本的字串把連續的1數量先給記錄下來，進行排序後取最大的k/2+1個即是答案。
由於以上文字可以不夠清楚，以實際測資解釋一次，以範測2為例，s為1110010011，若k=0或1，事實上我們無法進行任何增長連續塗黑正方形的裁剪，因此答案是最長的段等於3；若k=2或3，我們可以將其剪成…111、00100、11…，並重排成…11111…00100，答案為最長的兩段也就是3+2=5；若k=4或更大的情況，就是範測2說明的狀況，可以將所有塗黑正方形接起來。
:::spoiler AC code
```cpp=
#include<bits/stdc++.h>
using namespace std;
vector<int>v;
int main(){
int n,k,cnt=0,ans=0;
string s;
cin>>n>>k>>s;
for(int i=0;i<n;i++){
if(s[i]=='1')cnt++;
else{
if(cnt)v.push_back(cnt);
cnt=0;
}
}
if(cnt)v.push_back(cnt);
sort(v.begin(),v.end(),greater<int>());
for(int i=0;i<min((int)v.size(),k/2+1);i++)ans+=v[i];
cout<<ans;
}
```
:::
#### 第三題
* Subtask1
在輸入糖果時，只記錄xy在[-1000,1000]的糖果，接著每步移動都記錄會經過哪些格子，最後再把有經過的格子上的滿足感加總起來，時間複雜度O(n+總路徑長)，空間複雜度O(2000^2)。
* Subtask2
由於只有+x、-x方向的移動，因此可以只記錄y=0的糖果，接著可以利用STL的map，以及內建二分搜函式，再進行迭代器的遍歷來查找會經過哪些糖果，然後吃過的糖果再把它刪掉就好，時間複雜度O((n+k)log n)。
* Subtask3
因為該子任務的範圍xy座標會到10^9，因此必須進行離散化或利用其他方式記錄，方法之一是利用二維的STL map，宣告兩個map<int,map<int,int>>為xy與yx，xy是先記錄x座標再紀錄y座標，yx同理，接著每次的移動，若是平行x軸方向，則因為y座標固定，可以利用yx[y座標]再結合Subtask2的方法來求得會經過哪些糖果，將滿足感加至答案上後，接著再把xy與yx中的這些糖果給刪除，時間複雜度O((n+k)log^2 n)。
:::spoiler AC code
```cpp=
#include<bits/stdc++.h>
using namespace std;
map<int,map<int,int>>xy,yx;
vector<pair<int,int>>v;
int main(){
int n,k,a,x,y,d;
long long int ans=0;
string dir;
cin>>n>>k;
for(int i=0;i<n;i++){
cin>>a>>x>>y;
xy[x][y]=a,yx[y][x]=a;
}
x=y=0;
while(k--){
cin>>dir>>d;
if(dir=="+x"){
for(auto it=yx[y].lower_bound(x);it!=yx[y].end()&&it->first<=x+d;it++){
ans+=it->second;
v.push_back({it->first,y});
}
x+=d;
}else if(dir=="-x"){
auto it=yx[y].upper_bound(x);
while(it!=yx[y].begin()&&prev(it)->first>=x-d){
it--;
ans+=it->second;
v.push_back({it->first,y});
}
x-=d;
}else if(dir=="+y"){
for(auto it=xy[x].lower_bound(y);it!=xy[x].end()&&it->first<=y+d;it++){
ans+=it->second;
v.push_back({x,it->first});
}
y+=d;
}else{
auto it=xy[x].upper_bound(y);
while(it!=xy[x].begin()&&prev(it)->first>=y-d){
it--;
ans+=it->second;
v.push_back({x,it->first});
}
y-=d;
}
for(auto p:v){
xy[p.first].erase(p.second);
yx[p.second].erase(p.first);
}
v.clear();
cout<<ans<<'\n';
}
}
```
:::
#### 第四題
經典的爬樓梯DP的變形，其實少加跨一階的情況就好，複雜度O(n(k-1))。
:::spoiler AC code
```cpp=
#include<bits/stdc++.h>
using namespace std;
long long int dp[(int)1e5+5];
int main(){
int n,k;
cin>>n>>k;
dp[0]=1;
for(int i=2;i<=n;i++){
for(int j=2;i-j>=0&&j<=k;j++)dp[i]+=dp[i-j];
dp[i]%=(int)1e9+7;
}
cout<<dp[n];
}
```
:::
#### 第五題
應該是這次最難的一題，會用到最短路徑、DSU、backtracking等概念。
* Subtask1
由於c_i=10k，又我們可以知道，使用最多8次操作二就可以將「Elizabeth」的排列變回「Elizabeth」，只需要花費8k，因此該子任務只需要檢查需要進行幾次交換才可以完成排列，該問題可以利用DSU解決，或者在圖上找循環的數量亦可。
* Subtask2
與子任務1一樣的，只需要用到其中一種操作，因為給出的25組操作一可以將a-z所有字母進行轉換，因此一定可以變成「Elizabeth」。另外由於最壞的情況為從a變成z，需要花費∑c_i，而假如進行一次操作二的交換，最好可以直接使兩個字元歸位，因此只利用操作一使兩個字元變成正確的，最壞需要花費2∑c_i，而只利用操作二，最理想的情況也需花費k，因此該子任務的約束2∑c_i≤k，可以證明只使用操作一必然較好。於是該問題只需要利用最短路徑演算法(建議Floyd-Warshall演算法)先建表兩個字元要轉換的花費，再逐字把花費加總即可，時間複雜度為建表的O(26^3)。
* Subtask3
其實並沒有特別的解法，就只是可以少判大寫的位置，詳細解法請參考子任務4。
* Subtask4
要過整題的做法必須結合子任務1與2。我們可以知道透過多次操作一可以把其中一個字元直接或間接轉換成另一個，並且可以利用子任務2的做法建表，而操作二則可以把字母的排序改變。而其實可以發現，先改變字元再排序或先排序好再改字元，花費與最後的結果會是一樣的，因此我們不妨先將字串s透過操作一變換成「Elizabeth」的排列，然後再透過操作二將其還原。而我們將該步驟反過來看，改為遍歷所有「Elizabeth」的排列，該部分可利用backtracking或內建next_permutation函式做到，並且為了知道最少需要進行幾次交換可以還原回「Elizabeth」，我們可以利用DSU計算其連通塊的數量，接著再逐位判斷由s變成該狀況需要花費多少。不過須注意要判斷大寫字母的位置與s不同的情況，因為我們要直接將s變為該排列後再使用操作二，因此該情況可以跳過，另外透過操作一無法轉換的字母也應一併判斷。總複雜度O(26^3+9!*9)。
:::spoiler AC code
```cpp=
#include<bits/stdc++.h>
using namespace std;
int dis[30][30];
map<char,char>dsu;
set<char>cnt;
char search(char c){
if(dsu[c]==c)return c;
else return dsu[c]=search(dsu[c]);
}
void u(char x,char y){
x=search(x),y=search(y);
dsu[y]=x;
}
int main(){
int n,k,c,ans=1e9,cost;
char a,b;
string name="Elizabeth",goal,s;
goal=name;
for(int i=0;i<26;i++)for(int j=0;j<26;j++)dis[i][j]=(i==j?0:1e9);
cin>>n>>k>>s;
while(n--){
cin>>a>>b>>c;
dis[a-'a'][b-'a']=dis[b-'a'][a-'a']=c;
}
for(int k=0;k<26;k++)for(int i=0;i<26;i++)for(int j=0;j<26;j++)dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
sort(name.begin(),name.end());
do{
bool flag=0;
for(int i=0;i<9;i++)if(name[i]>='A'&&name[i]<='Z'&&s[i]>='a'&&s[i]<='z')flag=1;
if(flag)continue;
for(int i=0;i<9;i++){
if(s[i]>='A'&&s[i]<='Z'){
if(dis[name[i]-'A'][s[i]-'A']==1e9)flag=1;
}else{
if(dis[name[i]-'a'][s[i]-'a']==1e9)flag=1;
}
}
if(flag)continue;
dsu.clear();
cnt.clear();
for(char cc:goal)dsu[cc]=cc;
for(int i=0;i<9;i++)u(goal[i],name[i]);
for(char cc:goal)cnt.insert(search(cc));
cost=(9-(int)cnt.size())*k;
for(int i=0;i<9;i++){
if(s[i]>='A'&&s[i]<='Z')cost+=dis[name[i]-'A'][s[i]-'A'];
else cost+=dis[name[i]-'a'][s[i]-'a'];
}
ans=min(ans,cost);
}while(next_permutation(name.begin(),name.end()));
cout<<(ans==1e9?-1:ans)<<'\n';
}
```
:::
#### 第六題
* Subtask1
可以暴力。
* Subtask2
由於開始詢問後不再更新，因此可以用一般前綴和記錄。
* Subtask3
可用int紀錄。
* Subtask4
使用BIT紀錄做單點更新與區間和查詢而已，不過由於是要檢查能否整除2，因此使用bool值進行記錄或用位元運算會是比較理想的做法。
:::spoiler AC code
```cpp=
#include<bits/stdc++.h>
using namespace std;
bool BIT[(int)5e6+5];
void update(int x,bool y){
for(int i=x;i<=5000000;i+=i&(-i))BIT[i]^=y;
}
bool query(int x){
bool res=0;
for(int i=x;i>0;i-=i&(-i))res^=BIT[i];
return res;
}
int main(){
int n,q,com,x,y,a,b;
long long int z;
cin>>n>>q;
while(q--){
cin>>com;
if(com==1){
cin>>x>>z;
if(z&1)update(x,1);
}else{
cin>>x>>y;
cout<<(query(x-1)^query(y)?"NO\n":"YES\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