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;
}
/* /\_/\
* (= ._.)
* / > \>
*/