Codeforces Round 987 (Div. 2)（前四道）

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();}