A. Penchick and Modern Monument
翻译：
在繁华大都市马尼拉的摩天大楼中，菲律宾最新的 Noiph 购物中心刚刚竣工！建筑管理方 Penchick 订购了一座由 n 根支柱组成的先进纪念碑。
纪念碑支柱的高度可以用一个由 n 个正整数组成的数组 h 来表示，其中
表示 1 到 n 之间所有 i 的第 i 根支柱的高度。
彭契克希望石柱的高度不递减，即 1 到 n-1 之间所有 i 的高度为
。然而，由于混淆不清，纪念碑的高度反而是非递增的，即对于 1 到 n-1 之间的所有 i，
。
幸运的是，彭奇克可以修改石碑，并根据需要多次对石柱进行以下操作：
- 将支柱的高度修改为任意正整数。形式上，选择一个下标
和一个正整数 x，然后赋值
。
帮助彭奇克确定使纪念碑支柱的高度不递减所需的最少操作次数 .
思路：
变为同一高度最好，选择同一高度最多的柱子为标准。
实现：
#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);// 中间填保留几位小数，不填默认// cout.precision();ll t;cin>>t;while (t--) solve();}B. Penchick and Satay Sticks
翻译：
Penchick 和他的朋友 Kohane 正在印度尼西亚旅游，他们的下一站是泗水！
在泗水熙熙攘攘的小吃摊上，Kohane 买了 n 根沙爹，把它们排成一行，其中第 i 根沙爹的长度为
。已知 p 是长度为 n 的排列。
彭奇克想把沙爹棒按长度递增的顺序排列，这样，每
。为了好玩，他们制定了一条规则：只能交换长度相差 1 的相邻沙爹棒。从形式上看，他们可以执行以下操作任意多次（包括零次）：
- 选择一个下标（
），使得
；
- 交换
。
判断是否可以通过执行上述操作对排列 p 进行排序，从而对嗲嗲棒进行排序。
思路：
当左边比当前数大2即以上的数时，那个数必定换不到当前数的右边。遍历时维护左边最大值即可。
实现：
#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);// 中间填保留几位小数，不填默认// cout.precision();ll t;cin>>t;while (t--) solve();
}C. Penchick and BBQ Buns
翻译：
Penchick 喜欢两样东西：方块数字和港式烧腊包！在 Penchick 生日的时候，Kohane 想送他一份礼物：n 个从左到右排列的烧腊包。烧腊包有
种馅料可供选择，从 1 到
- 每种馅料都不能使用一次；也就是说，每种馅料要么完全不出现，要么至少出现两次。
- 对于具有相同馅料的两个包子 i 和 j，它们之间的距离
必须是完全平方。
帮助 Kohane 找到选择包子馅的有效方法，或者确定是否不可能满足她的目标！如果有多个解决方案，请打印其中任何一个。
思路：
对于n为偶数，相同馅料间隔为i,i+1；
n为奇数时，由于存在
，即可以有三个相同的馅料位置为1,10,26，10到26间为奇数有一个没配对，而11+16=27，即11可以与27配对。那么结论即为n>=27，位置1,10,26填相同馅，11,27填相同馅料，剩下的为偶数可以通过偶数情况求解。
实现：
#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);// 中间填保留几位小数，不填默认// cout.precision();ll t;cin>>t;while (t--) solve();}D. Penchick and Desert Rabbit
翻译：
Penchick 致力于挑战自己的极限，在阿拉伯沙漠的正午阳光下，他向自己发起了挑战！
当彭奇克沿着一片线状绿洲跋涉时，他发现一只沙漠兔正准备沿着一排棕榈树跳跃。一共有 n 棵棕榈树，每棵树的高度用
表示。
如果以下条件之一完全为真，兔子就能从第 i 棵树跳到第 j 棵树：
- j<i 且
：兔子可以向后跳到更高的树上。
- j>i 且
：兔子可以向前跳到较矮的树上。
对于 1 到 n 中的每个 i，确定兔子从第 i 棵树开始所能到达的所有树的最大高度。
思路：
对于每个可跳的位置，可以任意往来，构成连通块。从左到右，维护每个连通块最大值，当前值小于连通块时，合并连通块，并更新连通块最大值。
每个位置的答案就是所属连通块的最大值。
代码：
#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);// 中间填保留几位小数，不填默认// cout.precision();ll t;cin>>t;while (t--) solve();}
