Codeforces Round 912 (Div. 2)

Codeforces Round 912 (Div. 2)

A

大等于2依据冒泡排序即可排序，因此判断下1即可

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
int a[N];

void solve()
{
    int n , m;
    cin >> n >> m;
    for(int i = 1 ; i <= n ; i ++){
        cin >> a[i];
    }
    if(m < 2){
        for(int i = 2 ; i <= n ; i ++)
            if(a[i] < a[i - 1]){
                cout << "NO\n";
                return ;
            }
    }
    cout << "YES\n";
    return ;
}


int main()
{
    int T;
    cin >> T;
    while(T --){
        solve();
    }
    return 0;
}

B

对每一个数字找哪一位肯定为0填0其他的填1

#include <bits/stdc++.h>

using namespace std;

const int N = 1e3 + 10;
int a[N] , m[N][N];

void solve()
{
    int n;
    cin >> n;
    for(int i=1;i<=n;i++){
        a[i]=(1<<30)-1;
        for(int j=1;j<=n;j++){
            cin>>m[i][j];
            if(i!=j)a[i]&=m[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if((i!=j)&&((a[i]|a[j])!=m[i][j])){
                cout << "NO\n";
                return ;
            }
        }
    }

    cout << "YES\n";
    for(int i=1;i<=n;i++){
        cout << a[i] << " ";
    }    
    cout << endl;
    return ;
}


int main()
{
    int T;
    cin >> T;
    while(T --){
        solve();
    }
    return 0;
}

C

从后往前考虑加到当前集合或新立一个集合

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
long long a[N] , f[N];
int n;

void solve()
{
    cin >> n;
    for(int i = 1 ; i <= n ; i ++){
        cin >> a[i];
        f[i]= -(1ll<<60);
    }
    f[n]=a[n];
    long long s=a[n];
    //加/不加
    for(int i=n-1;i;i--)f[i]=max(f[i+1]+a[i],f[i+1]+s+a[i]),s+=a[i];
    cout<<f[1]<<'\n';
    return ;
}


int main()
{
    int T;
    cin >> T;
    while(T --){
        solve();
    }
    return 0;
}

D

从最高位开始考虑能否为1，计算能否时每个数当前位为1

#include<bits/stdc++.h>
#define ll long long
#define int long long
using namespace std;
const int N=2e6+1;
const int mo=998244353;
int a[N];
int x,y,n,sum,m,k,z,p,b[N],c[N];
void sovel()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
    cin>>a[i];
    b[i]=a[i];
}
while(m--)
{
    cin>>y;
    int manx=0;
    for(int i=62;i>=0;i--)
    {
        int x=(1LL<<i),sum=0;
        for(int j=1;j<=n;j++)
        {
            if(((a[j]>>i)&1)==0)
            {
                sum+=x-(a[j]%x);
                if(sum>y)
                {
                    break;
                }
            }
        }
        if(y>=sum)
        {
            manx|=x;
            y-=sum;
            for(int j=1;j<=n;j++)
            {
                if(((a[j]>>i)&1)==0)
                {
                    a[j]+=x-(a[j]%x);
                }
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        a[i]=b[i];
    }
    cout<<manx<<endl;
}
}
signed main()
{
int t=1;
while(t--)
{
    sovel();
}
return 0;
}