Codeforces Round 987 (Div. 2) ABCD

链接：

Codeforces Round 987 (Div. 2)

A:Penchick and Modern Monument

大意：

单调非增序列操作多少步变成单调非减

思路：

最后的数一定是相同的，为出现次数最多的那个数，结果就是n减去出现次数最多的数

代码：

#include <bits/stdc++.h>using namespace std;
#define int long long
const int N = 2e5 + 10, INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
#define pb push_back
#define  vi vector<int>
#define  vvi vector<vector<int>>
#define  vii vector<pair<int, int>>
#define ff first 
#define ss second 
// ++   ~!    */+-    <<>>    <>  ==   &^|   &&|| =void solve()
{int n;cin >> n;vi a(n + 1);for (int i = 1; i <= n; i++)cin >> a[i];int mx = 0;for (int i = 1; i <= n; i++){int j = i;while (i <= n && a[i] == a[j])i++;mx = max(i - j, mx);i--;}cout << n - mx << endl;
}signed main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--) solve();return 0;
}
/*   /\_/\
*   (= ._.)
*   / >  \>
*/

B：Penchick and Satay Sticks

大意：

一个排列转换成123456...n的最小字典序排列，每次转换只能相邻1个并且数值不能相差超过1，求是否能转换

思路：

相差不能超过1，则只能与位置相邻的数进行交换，即如果i不在位置i上，必然就在位置i-1或者i + 1上，如果都没有，就不能转换

那么可以从左到右遍历，如果 i !=a[i] 并且跟后边差1,就跟右边交换即可，换完还不等，就不能转换

代码：

#include <bits/stdc++.h>using namespace std;
#define int long long
const int N = 2e5 + 10, INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
#define pb push_back
#define  vi vector<int>
#define  vvi vector<vector<int>>
#define  vii vector<pair<int, int>>
#define ff first 
#define ss second 
// ++   ~!    */+-    <<>>    <>  ==   &^|   &&|| =void solve()
{int n;cin >> n;vi a(n + 1);for (int i = 1; i <= n; i++)cin >> a[i];for (int i = 1; i <= n; i++){if (a[i] != i){if(i + 1 <= n && a[i + 1] == i && abs(a[i + 1] - a[i])==1)swap(a[i], a[i + 1]);else{cout << "NO" << endl;return;}}}cout << "YES" << endl;
}signed main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t = 1; cin >> t;while (t--) solve();return 0;
}
/*   /\_/\
*   (= ._.)
*   / >  \>
*/

C：Penchick and BBQ Buns

大意：

给一个长度n的每个点上都赋一个值，如果赋了相同的值，任意两个相同的值之间要满足距离之差等于某个整数的平方和，求赋值方案，没有则输出-1

思路：

先对n进行奇偶分析，如果偶数的话就好了，直接两两相邻，距离差为1

奇数的话可以转换成偶数的情况，我们需要一个三个点的那就是距离为9和距离为16的，最小的情况下给1，10，26同种，发现1-10之间可以填偶数个，直接填就行，10到26之间填奇数个，可以多一个距离差为4的一个在10-26之内，一个在之外，这样距离差为4的里面再塞一对，前面的几对也塞一下就行了，所以27是最小的奇数合法情况

代码：

#include <bits/stdc++.h>using namespace std;
#define int long long
const int N = 2e5 + 10, INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
#define pb push_back
#define  vi vector<int>
#define  vvi vector<vector<int>>
#define  vii vector<pair<int, int>>
#define ff first 
#define ss second 
// ++   ~!    */+-    <<>>    <>  ==   &^|   &&|| =void solve()
{int n;cin >> n;if (n & 1){if (n < 27)cout << -1 << endl;else{vi ans(n + 1);int cnt = 2;int num = 0;for (int i = 1; i <= n; i++){if (i == 1 || i == 10 || i == 26)ans[i] = 1e6;else if (i == 23 || i == 27)ans[i] = 1e6-1;else{ans[i] = cnt;num++;if (num == 2){num = 0;cnt++;}}}for (int i = 1; i <= n; i++)cout << ans[i] << ' ';}}else{int num = n / 2;for (int i = 1; i <= num; i++)cout << i << " " << i << " ";cout << endl;}}signed main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--) solve();return 0;
}
/*   /\_/\
*   (= ._.)
*   / >  \>
*/

D：Penchick and Desert Rabbit

大意：

一个数组，位于i的数可以跳到右边比他小的数，可以跳到左边比他大的数，求从每一位开始最后可以跳到的最大数

思路：

有一个性质就是，一个数如果能跳到另一个数上，那么这两个位置的答案会一样

首先要想的是要跳到最大，应该是先往右跳，跳到最靠右的，然后往左跳才会有最大的，但是从左到右找最靠右的不太好找，pass

从右往左找的话，可以知道最靠右的就是自己，然后这个的答案就是前n个取最大，并且可知右边的能跳的肯定大于等于左边的能跳到的数，对于位置i，直接取i后面数的最小值，看看i是否大于后面最小值，如果大于，那么，那么i肯定直接或间接能到i + 1，那么i的答案跟i + 1的答案是相同的；如果小于等于，那么i到不了右边任何一个，只能取前面的最大值。

所以求一下前缀最大值和后缀最小值依次从右往左即可。

代码：

#include <bits/stdc++.h>using namespace std;
#define int long long
const int N = 2e5 + 10, INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
#define pb push_back
#define  vi vector<int>
#define  vvi vector<vector<int>>
#define  vii vector<pair<int, int>>
#define ff first 
#define ss second 
// ++   ~!    */+-    <<>>    <>  ==   &^|   &&|| =void solve()
{int n;cin >> n;vi a(n + 1);for (int i = 1; i <= n; i++)cin >> a[i];vi ans(n + 1), p(n + 1), s(n + 1);p[1] = a[1], s[n] = a[n];for (int i = 2; i <= n; i++)p[i] = max(p[i - 1], a[i]);for (int i = n - 1; i > 0; i--)s[i] = min(a[i], s[i + 1]);ans[n] = p[n];for (int i = n - 1; i; i--){if (p[i] > s[i + 1])ans[i] = ans[i + 1];else ans[i] = p[i];}for (int i = 1; i <= n; i++)cout << ans[i] << ' ';cout << endl;
}signed main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--) solve();return 0;
}
/*   /\_/\
*   (= ._.)
*   / >  \>
*/