Codeforces Round 987 (Div. 2)

A. Penchick and Modern Monument

因为 $n$ 很小，可以直接暴力$O(n^2)$ 判断每个位置不变的情况下，左右需要变几次

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38


#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N=1e5+7, mod=1e9+7;
int n;
int h[N];
void solve(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>h[i];
    int ans=INT_MAX;
    for(int i=1;i<=n;i++){
        int cnt=0;
        int lst=h[i];
        for(int j=i-1;j>0;j--){
            if(h[j]>lst)cnt++;
            else lst=h[j];
        }
        lst=h[i];
        for(int j=i+1;j<=n;j++){
            if(h[j]<lst)cnt++;
            else lst=h[j];
        }
        ans=min(ans,cnt);
    }
    cout<<ans<<endl;
}
int 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

易发现，每个数字最多交换一次到位，即它只可能在正确位置的左右，那我们只需要对每个位置判断即可，如果左右交换后为正确的就交换，反之就说明是 No

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37


#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N=2e5+7, mod=1e9+7;
int n;
int p[N];
void solve(){
    cin>>n;
    bool flag=0;
    for(int i=1;i<=n;i++)cin>>p[i];
    for(int i=1;i<n;i++){
        if(p[i]==i)continue;
        else {
            if(p[i]==i+1&&p[i+1]==i){
                swap(p[i],p[i+1]);
                continue;
            }
            else {
                cout<<"No\n";
                return;
            }
        }
    }
    cout<<"Yes\n";
}
int 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

首先可以发现，偶数时只需要两个两个填即可，但是奇数情况不确定
研究完全平方数后，可以发现 $9, 16, 25$ 三个数可以满足 3 个数填上后，相互之间的距离为完全平方数，即对应位置 $1, 10, 26$ 但是这样还是无法满足其他位置的需求，因为 $10 \sim 26$ 和 $26 \sim n$ 之间的个数都是奇数个，没法按偶数的直接填，那么就需要在这两个片段中各填一个使其变为偶数长度，同时最好不要影响后面填的数，可以发现是 $11, 27$ 是最优的那么只要是大于等于 $27$ 的奇数都是有解的

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40


#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N=2e5+7, mod=1e9+7;
int n;
int a[N]={0, 1,3,3,4,4,5,5,6,6,1,2,7,7,8,8,9,9,10,10,11,11,12,12,13,13,1,2};
void solve(){
    cin>>n;
    if(n&1){
        if(n>26){
            for(int i=1;i<=27;i++)cout<<a[i]<<" ";
            n-=27;
            int cnt=14;
            for(int i=1;i<=n/2;i++){
                cout<<cnt<<" "<<cnt<<" ";
                cnt++;
            }
            cout<<endl;
        }
        else cout<<"-1\n";
    }
    else{
        for(int i=1;i<=n/2;i++){
            cout<<i<<" "<<i<<" ";
        }
        cout<<endl;
    }
}
int 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

易想到，每个位置对应的最大值就是向后跳之后位置的前方的最大置
所以记录每个位置前方的最大值，后方的最小值
问题是如何处理每个位置上的跳跃：

如果 $pre[i] > suf[i+1]$ 那么 $i$ 一定能跳到 $i+1$ 对应的最大值 $i$ 可以先向前跳到 $pre[i]$ 对应位置，再跳到 $suf[i+1]$ 对应的位置，此时就能跳到 $i+1$ 对应的最大值
反之，即跳不到 $i+1$ 对应的最大值，此时的答案就是 $pre[i]$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38


#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N=5e5+7, mod=1e9+7;
int n;
int a[N],suf[N],pre[N],ans[N];
void solve(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    pre[0]=-1;
    suf[n+1]=INT_MAX;
    for(int i=1;i<=n;i++){
        pre[i]=max(pre[i-1],a[i]);
    }
    for(int i=n;i>0;i--){
        suf[i]=min(suf[i+1],a[i]);
    }
    for(int i=n;i>0;i--){
        if(pre[i]>suf[i+1])ans[i]=ans[i+1];
        else ans[i]=pre[i];
    }
    for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
    cout<<endl;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t=1;
    cin>>t;
    while(t--)solve();
    return 0;
}