Codeforces Round #827 (Div. 4)

A：给定三个数字，问是否存在1个数字是另外两个的和

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

B：给定一个数组，能否存在一个组合是单调上升的 

思路：显然只要没有相同的两个数即可

void solve(){
    int n;  cin >> n;
    set<int> s;
    rep(i, 0, n){
        int x;  cin >> x;
        s.insert(x);
    }
    cout << (s.size() == n ? "YES" : "NO") << endl;
}

C：给定一个 8×8 的网格，其中 . 符号表示空，'R' 符号表示红色，'B' 符号表示蓝色。 每次可能水平地画一道红色，或者垂直地画一道蓝色，后面画的会覆盖前面画的，给出最终结果，问最后画的是什么颜色。

思路：很简单，只要行内有完整的一行，说明这一行是最后画的，如果行内没有那就是列了

void solve(){
    string s[8];
    int R = false;
    for(int i = 0; i < 8; i++) {
        cin >> s[i];
        if(s[i] == "RRRRRRRR") R = true;
    }
    if(R) cout << "R\n";
    else cout << "B\n";
}

D：给定一个长度为 n <= 2e5 的数组，数字大小不超过 1000。求最大的 i + j 满足 a[i] 与 a[j] 互质。

思路：考虑到数字大小不超过1000，且i显然越大越好，所以最后一次出现的位置我们才记录。然后暴力枚举这1000个数即可！

const int N = 1010;
int g[N][N];
 
//n^2 枚举所有可能不可取，但我们发现数字大小不超过 1000，这也就意味着这个数组会有很多的重复元素，把这些重复的元素只保留下标最大的即可，这样就可以 1000^2 枚举了。
inline void solve(){
    int n;  cin >> n;
    int v[1020] = {0};
    repn(i, 1, n){
        int x;  cin >> x;   v[x] = i;
    }
    int res = -1;
    for (int i = 1; i <= 1000; i ++ )
        for (int j = 1; j <= 1000; j ++ ){
            if(g[i][j] && v[i] && v[j]) res = max(res, v[i] + v[j]);
        }
    cout << res << endl;
 
}
 
int main(){
 
    IOS;
    int t;  cin >> t;
    for(int i = 1; i <= 1000; i++) //打表看互质
        for(int j = 1; j <= 1000; j++)
            g[i][j] = (__gcd(i, j) == 1);
 
    while(t -- ){
        solve();
    }
    
    
    return 0;
}

 

E：给定一个长度为 n <= 2e5 的数组 a[i]，表示每级台阶的高度。

给定 q<=2e5 个询问，每个询问给出 k 表示一次最多能跨越的高度，问从 0 开始最多能爬多高。

思路：显然只要小于k的位置我们是肯定都能跨越的，所以我们用一个数组维护当前位置前的最大高度，那么这个数组显然是单调不降的！那么就可以二分出位置了。然后直接计算一下前缀和即可

inline void solve(){
    int n, q;   cin >> n >> q;
    repn(i, 1, n){
        cin >> s[i];
        mx[i] = max(s[i], 1ll * mx[i - 1]);//维护当前位置前最大的高度
        s[i] += s[i - 1];//前缀和
    }
    while(q -- ){
        int k;  cin >> k;
        auto t = upper_bound(mx + 1, mx + n + 1, k) - mx - 1;
        cout << s[t] << ' ';
    }
    cout << endl;
 
}

 

 F：给定两个字符串 s, t，初始时全为空。

有 q<=2e5 次操作，每次操作选择其中一个串，给定 k <= 2e5，str，往后添加 k 个 str。并询问是否存在一种方式重排 s，t 的字符，使得 s 的字典序严格小于 t 的字典序。

 

思路：显然只要有s中加入了不是'a'的字符，就肯定比t小了，否则就得比较字符串长度大小了

inline void solve(){
    int n;
    cin >> n;
    ll aa = 0, bb = 0, sz1 = 0, sz2 = 0;
    while(n -- ) {
        int op, k;
        string s;
        cin >> op >> k >> s;
        if(op == 1) sz1 += k * s.size();
        else sz2 += k * s.size();
        for(int i = 0 ; s[i] ; i ++ )
            if(s[i] != 'a') {
                if(op == 1) aa = 1;//给s加上了， s输了
                else bb = 1;//t输了
            }
        if(bb) {
            puts("YES");
            continue;
        } else if(aa) {
            puts("NO");
            continue;
        } else {
            if(sz1 >= sz2) puts("NO");
            else puts("YES");
        }
    }
}