Codeforces Round #759 (Div. 2) A B C D

A. Life of a Flower(水题，模拟)：

思路：
$1:$前面是$0$现在是$1$那么$+1$
$2:$前面是$1$现在是$1$那么$+5$
$3:$前面是$0$现在是$0$那么花直接死亡，直接输出$-1$结束

• 参考代码：

#include<bits/stdc++.h>
using namespace std;
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define re register int
#define int long long 
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define lowbit(x) (x&-x)
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
const int N=1100;
int a[N];
signed main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        int sum=1;
        for(int i=1;i<=n;i++)cin>>a[i];
        if(a[1]==1)sum+=1;
        for(int i=2;i<=n;i++){
            if(a[i]==1&&a[i-1]==1)sum+=5;
            if(a[i]==1&&a[i-1]==0)sum+=1;
            if(a[i]==0&&a[i-1]==0){
                cout<<"-1"<<endl;
                goto GG;
            }
        }
        cout<<sum<<endl;
        GG:;
    }
    return 0;
}

B. Array Eversion(思维)：

思路： 先找到数组中最大的数的下标，从后往前扫描直到碰到最大值停止，并且初始化一个数等于初始的最后一个数，如果遇到更大的更新这个数并且操作数$++$。

• 参考代码：

#include<bits/stdc++.h>
using namespace std;
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define re register int
#define int long long 
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define lowbit(x) (x&-x)
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
const int N=2e5+10;
int a[N];
signed main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        int MA=-1;
        for(int i=1;i<=n;i++){cin>>a[i];MA=max(MA,a[i]);}
        int sum=0;
        int MI=-1;
        for(int i=n;i>=1;i--){
            if(a[i]==MA)break;
                if(a[i]>MI){
                    MI=a[i];
                    sum++;
                }
        }
        cout<<sum<<endl;
    }
    return 0;
}

C. Minimize Distance(贪心)：

思路： 我觉得本题很容易就发现是贪心，奈何我太菜硬生生撸了120行才勉强在最后两分中过掉，这里有个从佬那里学到的20行做法，简单易懂。

• 参考代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
#define int long long 
int a[N];
signed main(){
    int t;
    long long n, k;
    cin>>t;
    while(t--)
    {
        cin>>n>>k;
        for(int i=0;i<n;i++) cin >> a[i];
        sort(a,a+n);
        long long ans=0;
        for(int i=n-1;i>=0 && a[i]>=0;i-=k)ans+=a[i];
        for(int i=0;i<n && a[i]<0;i+=k) ans-=a[i];
        cout<<2*ans-max(abs(a[0]), a[n-1])<<endl;
    }
    return 0;
} 

D. Yet Another Sorting Problem(置换的奇偶性问题和逆序对处理)

思路： $dls$言：两个数置换会改变奇偶性，三个数置换等于两个数置换，奇偶性不变。所以本题可以从逆序对着手，如果目标数组是一个上升序列那么逆序对的数量为$0$(偶数)，因为三个数置换永远不会改变奇偶性，所以初始数组的逆序对必须是偶数个才能最终置换成逆序对为$0$的数组，其中如果一个数出现两次及以上那么奇偶性就可以随意更改，那么最终也可以变成逆序对为$0$的数组，其余的逆序对为奇数情况全部是不能的所以输出$NO$

• 参考代码

#include<bits/stdc++.h>
using namespace std;
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define re register int
#define int long long 
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define lowbit(x) (x&-x)
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
const int N=5e5+10;
int q[N];
int n,tmp[N];
int res;
int merge_sort(int q[N],int l,int r){
    if(l>=r)return 0;
    int mid=l+r>>1;
    res=merge_sort(q,l,mid)+merge_sort(q,mid+1,r);
    int k=0,i=l,j=mid+1;
    while(i<=mid&&j<=r)if(q[i]<=q[j])tmp[k++]=q[i++];
    else{
        res+=mid-i+1;
        tmp[k++]=q[j++];
    }
    while(i<=mid)tmp[k++]=q[i++];while(j<=r)tmp[k++]=q[j++];
    for(int i=l,j=0;i<=r;j++,i++)q[i]=tmp[j];
    return res;
}
signed main(){
    int t;
    cin>>t;
    while(t--){
        cin>>n;
        set<int>S;
        for(int i=0;i<n;i++){cin>>q[i];S.insert(q[i]);}
        if(S.size()!=n){
            cout<<"YES"<<endl;
            continue;
        }
        merge_sort(q,0,n-1);
        if(res%2)cout<<"NO"<<endl;
        else cout<<"YES"<<endl;
    }
    return 0;
}