Codeforces Round #827 (Div. 4)

A

水题

#include<bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
#define rep(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
typedef long long ll;
const int N = 2e6 + 7;
const int mod = 1e9 + 7;


void solve() {
    int a,b,c;
    cin>>a>>b>>c;
    if(a+b==c||a+c==b||b+c==a)cout<<"YES"<<endl;
    else cout<<"NO"<<endl;

}
signed main(){
    int t=1;
    cin>>t;
    while (t--) solve();
    
    return 0;
}

B

水题

#include<bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
#define rep(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
typedef long long ll;
const int N = 2e6 + 7;
const int mod = 1e9 + 7;


void solve() {
    int n;
    cin>>n;
    vector<int> a(n);
    for(int i=0;i<n;i++) cin>>a[i];
    sort(a.begin(),a.end());
    for(int i=0;i<n-1;i++){
        if(a[i]==a[i+1]){
            cout<<"NO"<<endl;
            return;
        }
    }
    cout<<"YES"<<endl;

}
signed main(){
    int t=1;
    cin>>t;
    while (t--) solve();
    
    return 0;
}

C

如果有一整行或者一整列为同一个字母，说明肯定是最后一次画的。

#include<bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
#define rep(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
typedef long long ll;
const int N = 2e6 + 7;
const int mod = 1e9 + 7;

char g[20][20];

void solve() {
    for(int i=0;i<8;i++){
        for(int j=0;j<8;j++){
            cin>>g[i][j];
        }
    }
    for(int i=0;i<8;i++){
        int cnt=0;
        for(int j=0;j<8;j++){
            if(g[i][j]=='R') cnt++;
        }
        if(cnt==8){
            cout<<"R"<<endl;
            return;
        }
    }
    for(int i=0;i<8;i++){
        int cnt=0;
        for(int j=0;j<8;j++){
            if(g[j][i]=='B') cnt++;
        }
        if(cnt==8){
            cout<<"B"<<endl;
            return;
        }
    }
}
signed main(){
    int t=1;
    cin>>t;
    while (t--) solve();
    
    return 0;
}

D

桶计数，暴力找,两个数互质，gcd为1

#include<bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
#define rep(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
typedef long long ll;
const int N = 2e6 + 7;
const int mod = 1e9 + 7;


void solve() {
    int n;
    cin>>n;
    vector<int> a(n+1);
    vector<int> pos(1001,-1);
    for(int i=1;i<=n;i++) {
        cin>>a[i];
        pos[a[i]]=i;
    }
    int ans=0;
    int ok=0;
    for(int i=1;i<=1000;i++){
        for(int j=1;j<=1000;j++){
            if(__gcd(i,j)==1&&pos[i]!=-1&&pos[j]!=-1){
                ans=max(ans,pos[i]+pos[j]);
                ok=1;
            }
        }
    }
    if(!ok) cout<<-1<<endl;
    else cout<<ans<<endl;

}
signed main(){
    int t=1;
    cin>>t;
    while (t--) solve();
    
    return 0;
}

E

预处理，前缀和，二分

#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
#define rep(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
typedef long long ll;
const int N = 2e6 + 7;
const int mod = 1e9 + 7;
#define int long long
void solve()
{
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    vector<int> sum(n);
    sum[0] = a[0];
    for (int i = 1; i < n; i++) {
        sum[i] = sum[i - 1] + a[i];
    }
    for (int i = 1; i < n; i++) {
        a[i] = max(a[i], a[i - 1]);
    }

    // for (auto& x : a)
    //     cout << x << " ";
    // cout << endl;
    // for (auto& x : sum)
    //     cout << x << " ";
    // cout << endl;
    while (q--) {
        int x;
        cin >> x;
        int l = 0, r = n - 1;
        int ans = 0;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (x >= a[mid]) {
                ans = sum[mid];
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        cout << ans << " ";
    }
    cout << endl;
}
signed main()
{
    int t = 1;
    cin >> t;
    while (t--)
        solve();

    return 0;
}

F

注意开始的时候

S,T

字符串都是有一个a的，可以发现如果

T

字符串存在比

a

字符大，我们就可以让S的

a

字符放在第一个，

T

的大于

a

的字符放在第一个，这样肯定

S

<

T

。

如果

T

全是

a

没有比

a

大的，就看

S

有没有比

a

大的，如果有，则无法构造。如果没有，

S

也完全是

a

字符，则比较

a

字符的数量。

#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
#define rep(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
typedef long long ll;
const int N = 2e6 + 7;
const int mod = 1e9 + 7;
#define int ll
void solve()
{
    int q;
    cin >> q;
    int hs = 0, ht = 0, cs = 0, ct = 0;
    while (q--) {
        int op, k;
        string x;
        cin >> op >> k >> x;

        if (op == 1) {
            for (auto& c : x) {
                if (c > 'a') {
                    hs = 1;
                } else {
                    cs += k;
                }
            }
        } else {
            for (auto& c : x) {
                if (c > 'a') {
                    ht = 1;
                } else {
                    ct += k;
                }
            }
        }
        // cout << hs << " " << ht << endl;
        if (ht) {
            cout << "YES" << endl;
        } else if (!hs) {
            if (cs < ct)
                cout << "YES" << endl;
            else
                cout << "NO" << endl;
        } else if (hs) {
            cout << "NO" << endl;
        }
    }
}
signed main()
{
    int t = 1;
    cin >> t;
    while (t--)
        solve();

    return 0;
}
/*
s:aabb
t:aaaaa
*/

G

观察可以发现，第一个数肯定是a数组中最大的那个数，那么接下来就找和前面或最大的数，可以遍历一遍没有用过的数，找到最大的那个，由于最多有31位，所以最多遍历31次或的结果就是最大的,遍历31次之后，剩下就可以随便输出了。

#include<bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
#define rep(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
typedef long long ll;
const int N = 2e6 + 7;
const int mod = 1e9 + 7;


void solve() {
    int n;
    cin>>n;
    vector<int> a(n);
    for(int i=0;i<n;i++) {
        cin>>a[i];
    }
    vector<int> vis(n+1,0);
    int ans=0;
    for(int i=0;i<min(31,n);i++){
        int maxOr=0,idx=-1;
        for(int j=0;j<n;j++){
            if(vis[j]) continue;
            if((a[j]|ans)>maxOr){
                maxOr=a[j]|ans;
                idx=j;
            }
        }
        vis[idx]=1;
        cout<<a[idx]<<" ";
        ans|=a[idx];
    }
    for(int i=0;i<n;i++){
        if(!vis[i]) cout<<a[i]<<" ";
    }
    cout<<endl;
}
signed main(){
    int t=1;
    cin>>t;
    while (t--) solve();
    
    return 0;
}