A. Penchick and Modern Monument

翻譯：

????????在繁華大都市馬尼拉的摩天大樓中，菲律賓最新的 Noiph 購(gòu)物中心剛剛竣工！建筑管理方 Penchick 訂購(gòu)了一座由 n 根支柱組成的先進(jìn)紀(jì)念碑。

????????紀(jì)念碑支柱的高度可以用一個(gè)由 n 個(gè)正整數(shù)組成的數(shù)組 h 來(lái)表示，其中 表示 1 到 n 之間所有 i 的第 i 根支柱的高度。

????????彭契克希望石柱的高度不遞減，即 1 到 n-1 之間所有 i 的高度為。然而，由于混淆不清，紀(jì)念碑的高度反而是非遞增的，即對(duì)于 1 到 n-1 之間的所有 i，。

幸運(yùn)的是，彭奇克可以修改石碑，并根據(jù)需要多次對(duì)石柱進(jìn)行以下操作：

• 將支柱的高度修改為任意正整數(shù)。形式上，選擇一個(gè)下標(biāo) 和一個(gè)正整數(shù) x，然后賦值 。

????????幫助彭奇克確定使紀(jì)念碑支柱的高度不遞減所需的最少操作次數(shù) .

思路：

? 變?yōu)橥桓叨茸詈?#xff0c;選擇同一高度最多的柱子為標(biāo)準(zhǔn)。

實(shí)現(xiàn)：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
// using pll = pair<ll,ll>;void solve(){int n;int maxx = 0;  vector<int> nums(100,0);cin>>n;for (int i=0,num;i<n;i++){cin>>num;nums[num]++;maxx = max(maxx,nums[num]);}  cout<<n-maxx<<endl;
}
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 中間填保留幾位小數(shù)，不填默認(rèn)// cout.precision();ll t;cin>>t;while (t--) solve();}

B. Penchick and Satay Sticks

?翻譯：

????????Penchick 和他的朋友 Kohane 正在印度尼西亞旅游，他們的下一站是泗水！

????????在泗水熙熙攘攘的小吃攤上，Kohane 買了 n 根沙爹，把它們排成一行，其中第 i 根沙爹的長(zhǎng)度為 。已知 p 是長(zhǎng)度為 n 的排列。

????????彭奇克想把沙爹棒按長(zhǎng)度遞增的順序排列，這樣，每 時(shí)，。為了好玩，他們制定了一條規(guī)則：只能交換長(zhǎng)度相差 1 的相鄰沙爹棒。從形式上看，他們可以執(zhí)行以下操作任意多次（包括零次）：

• 選擇一個(gè)下標(biāo)（），使得 ；
• 交換 和 。

判斷是否可以通過執(zhí)行上述操作對(duì)排列 p 進(jìn)行排序，從而對(duì)嗲嗲棒進(jìn)行排序。

思路：

當(dāng)左邊比當(dāng)前數(shù)大2即以上的數(shù)時(shí)，那個(gè)數(shù)必定換不到當(dāng)前數(shù)的右邊。遍歷時(shí)維護(hù)左邊最大值即可。

實(shí)現(xiàn)：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
// using pll = pair<ll,ll>;void solve(){int n;    cin>>n;vector<int> a(n);for (int i=0;i<n;i++) cin>>a[i];if (n==2||n==1){cout<<"YES"<<endl;return;}else{int maxx = a[0];for (int i=1;i<n;i++){if (maxx>a[i]+1){cout<<"NO"<<endl;return;}maxx = max(a[i],maxx);}cout<<"YES"<<endl;}
}
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 中間填保留幾位小數(shù)，不填默認(rèn)// cout.precision();ll t;cin>>t;while (t--) solve();
}

C. Penchick and BBQ Buns

?翻譯：

????????Penchick 喜歡兩樣?xùn)|西：方塊數(shù)字和港式燒臘包！在 Penchick 生日的時(shí)候，Kohane 想送他一份禮物：n 個(gè)從左到右排列的燒臘包。燒臘包有 種餡料可供選擇，從 1 到 。為了確保彭奇克會(huì)喜歡這份禮物，科哈尼有幾個(gè)目標(biāo)：

• 每種餡料都不能使用一次；也就是說，每種餡料要么完全不出現(xiàn)，要么至少出現(xiàn)兩次。
• 對(duì)于具有相同餡料的兩個(gè)包子 i 和 j，它們之間的距離 必須是完全平方。

????????幫助 Kohane 找到選擇包子餡的有效方法，或者確定是否不可能滿足她的目標(biāo)！如果有多個(gè)解決方案，請(qǐng)打印其中任何一個(gè)。

思路：

對(duì)于n為偶數(shù)，相同餡料間隔為i,i+1；

????????n為奇數(shù)時(shí)，由于存在，即可以有三個(gè)相同的餡料位置為1,10,26，10到26間為奇數(shù)有一個(gè)沒配對(duì)，而11+16=27，即11可以與27配對(duì)。那么結(jié)論即為n>=27，位置1,10,26填相同餡，11,27填相同餡料，剩下的為偶數(shù)可以通過偶數(shù)情況求解。

實(shí)現(xiàn)：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
// using pll = pair<ll,ll>;void solve(){int n;  cin>>n;vector<int> a(n+1,0);if (n%2==1){if (n>=27){a[1] = 1;a[10] = 1;a[26] = 1;a[11] = 2;a[27] = 2;int cnt = 3,f = 0;for (int i=1;i<=n;i++){if (a[i]==0){a[i] = cnt;f++;}if (f==2){f = 0;cnt++;}}}else{cout<<-1<<endl;return;}}else{int cnt = 1;for (int i=1;i<=n;i+=2){a[i] = cnt;a[i+1] = cnt;cnt++;}}for (int i=1;i<n;i++){cout<<a[i]<<" ";}cout<<a[n]<<endl;
}
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 中間填保留幾位小數(shù)，不填默認(rèn)// cout.precision();ll t;cin>>t;while (t--) solve();}

D. Penchick and Desert Rabbit

翻譯：

????????Penchick 致力于挑戰(zhàn)自己的極限，在阿拉伯沙漠的正午陽(yáng)光下，他向自己發(fā)起了挑戰(zhàn)！

????????當(dāng)彭奇克沿著一片線狀綠洲跋涉時(shí)，他發(fā)現(xiàn)一只沙漠兔正準(zhǔn)備沿著一排棕櫚樹跳躍。一共有 n 棵棕櫚樹，每棵樹的高度用 表示。

????????如果以下條件之一完全為真，兔子就能從第 i 棵樹跳到第 j 棵樹：

• j<i 且 ：兔子可以向后跳到更高的樹上。
• j>i 且 ：兔子可以向前跳到較矮的樹上。

對(duì)于 1 到 n 中的每個(gè) i，確定兔子從第 i 棵樹開始所能到達(dá)的所有樹的最大高度。

思路：

????????對(duì)于每個(gè)可跳的位置，可以任意往來(lái)，構(gòu)成連通塊。從左到右，維護(hù)每個(gè)連通塊最大值，當(dāng)前值小于連通塊時(shí)，合并連通塊，并更新連通塊最大值。

? ? ? ? 每個(gè)位置的答案就是所屬連通塊的最大值。

代碼：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
// using pll = pair<ll,ll>;
const int N = 5e5+10;
vector<int> f(N),sz(N);
int find(int k){return f[k]==k ? f[k] : f[k] = find(f[k]);
}
void add(int x,int y){x = find(x);y = find(y);if (x==y) return;if (sz[x]<sz[y]) swap(x,y);f[y] = x;sz[x] += sz[y];
}int n;
vector<int> nums(N);void solve(){int n;cin>>n;for (int i=1;i<=n;i++){cin>>nums[i];sz[i] = 1;f[i] = i;}priority_queue<pair<int,int>> piece1;for (int i=1;i<=n;i++){int temp = nums[i];while (!piece1.empty()){int x = piece1.top().first, y = piece1.top().second;if (x>nums[i]){temp = max(x,temp);add(y,i);piece1.pop();}else{break;}}piece1.push(make_pair(temp,find(i)));}map<int,int> mp;while (!piece1.empty()){int x = piece1.top().first, y = piece1.top().second;piece1.pop();mp[find(y)] = x;}for (int i=1;i<n;i++){cout<<mp[find(i)]<<" ";}cout<<mp[find(n)]<<endl;
}
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 中間填保留幾位小數(shù)，不填默認(rèn)// cout.precision();ll t;cin>>t;while (t--) solve();}