好不容易的一次CF阳间赛，这次题目普遍较长。
A-Penchick and Modern Monument
题目大意
将一个非递增的序列通过操作某些数（可增大可减小），最终使得序列变成一个非递减的序列，求出最少要操作多少次？
解题思路
这个题也是想了不断时间，而且还提交错误一次，原因就是调试的代码没有修改。
我们可以通过找到出现次数最多的那个数，然后操作其他所有数，这就是最少得操作次数。
Accepted
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
const int N = 50 + 10;
ll n,m,k;
ll a[N],b[N];
void solve () {
memset(a,0,sizeof a);
memset(b,0,sizeof b);
cin>>n;
for(int i = 0;i < n;i++) {
cin>>a[i];
b[a[i]] ++;
}
int maxLen = 0;
int index = 0;;
for(int i = 0;i < n;i++) {
if(maxLen < b[a[i]]) {
maxLen = b[a[i]];
}
}
int res = n - maxLen;
cout<<res<<endl;
}
int main () {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--) {
solve();
}
return 0;
}
B - Penchick and Satay Sticks
题目大意
给定一个长度为n的序列，这个序列在CF中有特性，就是1~n之间的所有数的任意排列。然后判断是否可以通过交换相邻的两个值，并且这两个值相差为1，最后是否能够得到升序的序列？
解题思路
可以直接通过双指针的一个操作，依次判断是否能交换，如果出现不能交换的情况直接返回错误。
当时想的有点多了，考虑了这些那些的情况，还想了某种排序算法能不能实现，最后以失败告终；还有依次思路正确但是 TLE ，因为我在外层还加了一层循环；但是基于这个序列的特性，就不需要在外层添加一次循环，直接一次遍历即可。
Accepted
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
ll n,m,k;
ll a[N];
void solve () {
cin>>n;
for(int i = 0; i < n; i++) {
cin>>a[i];
}
for(int j = 1; j < n; j++) {
if(a[j-1] > a[j]) {
if(abs(a[j-1] - a[j]) == 1) {
swap(a[j-1],a[j]);
} else {
cout<<"No"<<endl;
return ;
}
}
}
cout<<"Yes"<<endl;
}
int main () {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--) {
solve();
}
return 0;
}
C - Penchick and BBQ Buns
题目大意
这是一道构造排列的题，要求是：
- 每个数字如果出现必须是两个以上；
- 两个相同数之间的距离一定是一个完全数。
解题思路
这道题属实有点观察规律了，但是想一想还是有技巧的。
序列长度分为奇数和偶数：
- 偶数：直接然两个相同的数挨着，并且出现次数恰好为 2 满足第一个条件，这时距离值也是 1 满足第二个条件。
- 奇数：偶数情况是恰好出现两次的时候，如果为奇数，那么要想能够排列，一定要存在三个完全数 r1、r2、r3，还应满足 r1 = r2 + r3，那么就可以分别为9 、 16 、 25，所以说，要想奇数次数能够排列的时候必须满足 n > 25 ，先思考能否取到 27 ，那么先将 1 填到 位置1 、 10 、 26，然后再两个两个填充其他值，肯定是可以构造的。那么对于大于27的奇数，都可以将其前27进行排列，然后以偶数的方式进行排列即可构造。
Accepted
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
ll n,m,k;
int a[N];
void solve () {
int n;
cin>>n;
if(n%2 != 0) {
if(n >= 27) {
cout<<"1 2 2 3 3 4 4 5 5 1 6 6 7 7 8 8 9 9 10 10 11 11 12 13 13 1 12 ";
for(int i = 14;i*2+1 <= n;i++) {
cout<<i<<" "<<i<<" ";
}
cout<<endl;
} else {
cout<<-1<<endl;
}
} else {
for(int i = 1; i <= n/2; i++) {
cout<<i<<" "<<i<<" ";
}
cout<<endl;
}
}
int main () {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--) {
solve();
}
return 0;
}
D - Penchick and Desert Rabbit
题目大意
有一排树，兔子现在可以按照规则来跳跃：
- 向前（下标增大的方向），可以跳跃到任意比当前树低的那一颗；
- 向后（下标减小的方向），可以跳跃到任意比当前树高的那一颗。
现在要找出从每一颗树出发，判断可以跳到的最高的树的高度。
解题思路
根据规则可以建立前缀最大数组和后缀最小数组，方便兔子跳到那个可以跳跃的位置；
然后通过遍历前缀和后缀数组，每次比较的都是前缀当前下标的值（a）和后缀下一个下标的值（b），如果 a > b,那就可以接着跳，直到遇见 a <= b 的情况，然后更新当前下标之前的所有下标值为当前位置对应的前缀数组中的值。
Accepted
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
const int N = 5e5+10;
int n,m,k;
int a[N];
void solve () {
cin>>n;
for(int i = 1; i <= n; i++) {
cin>>a[i];
}
vector<int> mx(n+1,0),mi(n+2,1e9);
for(int i = 1; i <= n; i++) mx[i] = max(mx[i-1],a[i]);
for(int i = n; i >= 0; i--) mi[i] = min(mi[i+1],a[i]);
for(int i = 1,j = 1; i <= n; i++) {
if(mx[i] <= mi[i+1]) {
while(j <= i) {
cout<<mx[i]<<" ";
j++;
}
}
}
cout<<endl;
}
int main () {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--) {
solve();
}
return 0;
}
E 题好像用到了树形DP，但是我题目还没有看懂
标签：cout,int,ll,Codeforces,cin,long,987,tie,Div From： https://blog.csdn.net/2301_76605150/article/details/143821819