Codeforces Round #619 (Div. 2)

A題：

題解：

開始沒看懂，後來發現c和a，b交換的操作是強制的。那麼就很白給了。

#include <bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e5+7;
int t, n, a[N];
int main()
{
    int n; cin>>n;
    for(int i=1;i<=n;i++){
        string a,b,c; cin>>a>>b>>c;
        int flag=0;
        for(int i=0;i<a.size();i++){
            if(a[i]==c[i]||b[i]==c[i]) continue;
            flag=1;
        }
        if(flag) cout<<"NO"<<endl;
        else cout<<"YES"<<endl;
    }
}
           

B題：

題解：

讓最大的最小，寫二分一直炸，無奈換了一種寫法。結果無非4種情況。把位置想成三個。左中右某一個miss，或者全部miss。如果相鄰的兩個沒有miss那麼直接記錄答案。對結果造成影響的隻有miss的值會造成影響。我們都知道到兩個數距離最小的就是這兩個數的中位數值。是以我們記錄答案。找中位數值。最後答案取最大值就可以了。

#include <bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e5+7;
int t, n, a[N];
int main()
{
    int t; scanf("%d",&t);
    while(t--){
        vector<int> g;
        int n; scanf("%d",&n);
        int res=0;
        for(int i=1;i<=n;i++) scanf("%d",a+i);
        for(int i=1;i<n;i++){
            if(a[i]!=-1&&a[i+1]==-1) g.push_back(a[i]);
            else if(a[i]==-1&&a[i+1]!=-1) g.push_back(a[i+1]);
            else res=max(res,abs(a[i]-a[i+1]));
        }
        if(!g.size()) cout<<0<<' '<<0<<endl;
        else{
            sort(g.begin(),g.end());
            int k=(g.back()+g[0])/2;
            cout<<max({res,g.back()-k,k-g[0]})<<' '<<k<<endl;
        }
    }
}
           

C題：

題解：

正難則反，我們利用容斥原理，先把所有的方案都找出來。然後把所有不合理的方案再減去。這裡不合理的方案就是連續的０作為的字串。我們要讓我們的含有１的字串盡可能多，那麼就是将０分散在１之中，那麼就成了插空了。最後看下多出來的０分别插空就行了。

#include <bits/stdc++.h>
#define int long long
using namespace std;
int t, n;
 
signed main()
{
    scanf("%lld",&t);
    while(t--){
        int n,m; scanf("%lld%lld",&n,&m);
        int sum=n*(n+1)/2;
        int group_num=(n-m)/(m+1);//0
        int mod=(n-m)%(m+1);//多餘0
        sum-=(group_num+1)*(2+group_num)*mod/2;
        sum-=group_num*(1+group_num)*(m+1-mod)/2;
        cout<<sum<<endl;
    }
}
           

Ｄ題：

題解：

我們構造出一個最長路，如果最長路都不能把我們的步數走完，那麼就一定走不完了。

#include <bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e5+7;
vector<pair<int,string>> g,res;
int main()
{
    int n,m,k; scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n-1;i++){
        if(m-1!=0){
            g.push_back({m-1,"R"});
            g.push_back({m-1,"L"});
        }
        g.push_back({1,"D"});
    }
    if(m-1!=0) g.push_back({m-1,"R"});
    for(int i=1;i<=m-1;i++){
        if(n-1!=0) {
            g.push_back({n-1, "U"});
            g.push_back({n-1, "D"});
        }
        g.push_back({1,"L"});
    }
    if(n-1!=0){
        g.push_back({n-1,"U"});
    }
    for(int i=0;i<g.size();i++){
        if(k>=g[i].first){
            k-=g[i].first;
            res.push_back({g[i].first,g[i].second});
        }else{
            if(k!=0&&g[i].first>k)
            res.push_back({k,g[i].second});
            k=0;
            break;
        }
    }
    if(k>0) cout<<"NO"<<endl;
    else{
        cout<<"YES"<<endl;
        cout<<res.size()<<endl;
        for(int i=0;i<res.size();i++){
            cout<<res[i].first<<' '<<res[i].second<<endl;
        }
    }
}