Codeforces Round 1008 (Div. 2)（A-D）

题目链接：Dashboard - Codeforces Round 1008 (Div. 2) - Codeforces

A. Final Verdict

思路

我们每次选的k是能够整除数组a的长度的，可以发现最后每个数都要除以n，此时判断一下sum==n*x即可

代码

void solve(){
    int n,x;
    cin>>n>>x;
    vector<int> a(n+10);
    int sum=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum+=a[i];
    }
    if(sum==x*n){
        cout<<"YES\n";
    }else{
        cout<<"NO\n";
    }
}

B. Vicious Labyrinth

思路

贪心的想一下，最后我们肯定是尽可能要让所有人都在n这个牢房，这样总和是最小的，其中因为所以我们让且这样我们就能保证最后进行完k步之后所有的人在n或n-1，如果k是偶数的话我们让最后我们就让所有人在n牢房，如果k是奇数的话我们让最后除了原先在n牢房的哪个人在n-1牢房（这是不能避免的），其余人都在n牢房。这样就构造完成了

代码

void solve(){
    int n,k;
    cin>>n>>k;
    if(k%2){
        for(int i=1;i<=n;i++){
            if(i!=n){
                cout<<n<<" ";
            }else{
                cout<<n-1<<" ";
            }
        }
        cout<<"\n";
    }else{
        for(int i=1;i<=n;i++){
            if(i!=n){
                if(i==n-1){
                    cout<<n<<" ";
                }else{
                    cout<<n-1<<" ";
                }
                
            }else{
                cout<<n-1<<"\n";
            }
        }
    }
    
}

C. Breach of Faith

思路

构造，我们先来看给定数组a的条件，我们要构造出缺失的a

1. 首先a是个正数，其次不能大于1e18因为b<=2e5的所以可以忽视

2.a1,a2,…,a2n+1a1,a2,…,a2n+1 成对不相同。我们构造出的数不能再b中出现过

3.        用于构造的等式

要保证条件2我们可以想到要构造出不同的一个数，最简单的就是比最大值大，比最小值小的数，根据条件1我们只能构造一个比最大值大的数

那么我们就可以构造一个   新数 =（最大数-负数+某个正数）为什么这么构造呢？我们根据条件3这个等式，我们把最大值和某个正数拿出来，其余数根据等式构造一个负数即可，为了方便构造负数我们让某个正数=最小值即可

我们的等式加上新数就变成了

最大=（最大-负数+最小）- 最小 + 负数

这样就完成了构造

代码

#include<bits/stdc++.h>
using namespace std;

#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;

const int N=2e5+10;
const int inf=1e18;
const int mod=998244353;

void solve(){
    int n;
    cin>>n;
    n*=2;
    vi b(n+10);
    
    for(int i=1;i<=n;i++){
        cin>>b[i];
    }
    sort(b.begin()+1,b.begin()+1+n);
    int sum=0;
    for(int i=2;i<=n/2;i++){
        sum+=(b[i]-b[n-i+1]);
    }
    cout<<b[n]<<" ";
    sum=b[n]+b[1]-sum;
    cout<<sum<<" "<<b[1]<<" ";
    for(int i=2;i<=n/2;i++){
        cout<<b[i]<<" "<<b[n-i+1]<<" ";
    }
    cout<<"\n";
}
signed main() {
    vcoistnt
    cout<<fixed<<setprecision(2);
    int _=1;
    cin>>_;
    while(_--) solve();
    return 0;
}

D. Scammy Game Ad

思路

贪心，我们的最终目的就是让人数多，可以发现关于过的每道门来说，他新增的可分配的人数，后面无论是如何是影响不到的，选定了通过哪扇门新增的也就是可分配的人数是确定的，再由这些新增的人数去决定后面下一个的门选择哪一个

想明白了这个就知道了这是个贪心的题目

很明显+的那扇门无论是否分配人数是不会影响新增人数的

对于每扇门我们可以分为三种情况：

1.都是+。可分配人数无论此时选择的哪扇门新增的人数是不会收到影响的，我们要看后面的门让其分配到后面的第一个乘法门上

2.一个+，一个x。我们要把可分配人数放到x法上，这样可以使新增人数变多

3.都是x。如果后面的数是相等的与全是+等效。如果不同选择乘数大的；

至此便完成了对贪心的刨析

代码

#include<bits/stdc++.h>
using namespace std;

#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;

const int N=2e5+10;
const int inf=1e18;
const int mod=998244353;

void solve(){
    int n;cin>>n;
    vector<pair<char,int>> l(n+1),r(n+1);
    for(int i=1;i<=n;i++){
        cin>>l[i].first>>l[i].second>>r[i].first>>r[i].second;
    }
    int x=1,y=1;  //目前已经固定在某一条路上的人数
    int s=0;    //能够进行自由分配的人数

    for(int i=1;i<=n;i++){
        if(l[i].first=='+' && r[i].first=='+'){
            s += (l[i].second+r[i].second);
        }else if(l[i].first=='x' && r[i].first=='+'){
            x += s;
            s = (l[i].second - 1)*x + r[i].second;
        }else if(l[i].first=='+' && r[i].first=='x'){
            y += s;
            s = l[i].second + (r[i].second-1)*y;
        }else{
            if(l[i].second>r[i].second){
                x += s;
                s = (l[i].second-1)*x + (r[i].second-1)*y;
            }else if(l[i].second == r[i].second){
                s += (l[i].second-1)*(s+x+y);
            }else{
                y += s;
                s = (l[i].second-1)*x + (r[i].second-1)*y;
            }
        }
    }
    cout<<x+y+s<<"\n";
}
signed main() {
    vcoistnt
    cout<<fixed<<setprecision(2);
    int _=1;
    cin>>_;
    while(_--) solve();
    return 0;
}