Educational Codeforces Round 58 (Rated for Div. 2) A,B,C,D,E,G

竞赛链接：http://codeforces.com/contest/1101
A:找到一个被d整除，但是不被[l,r]包含的最小的数
解法：按照d和l的大小关系，分类讨论一下

#include <bits/stdc++.h>
using namespace std;
int d, l, r, q;
int main(){
    scanf("%d", &q);
    while(q--){
        scanf("%d%d%d", &l,&r,&d);
        int ans;
        if(d == 1){
            if(l > 1) printf("1\n");
            else printf("%d\n", r+1);
            continue;
        }
        if(d < l){
            ans = d;
        }else{
            ans = (r / d + 1) * d;
        }
        printf("%d\n", ans);
    }
}

B:题意，让我找一个最长的目标串长得像[:|||:] 这个样子，求中|是可以多个或者0个的
解法：直接扫描整个串找最左和最右的是[和]的位置，记作l,r,然后在l,r，里面找:最左和最右并且位置不同的位置记作x,y,最后统计一下x,y中间s[i]=’|'的个数，就得到目标串了，输出长度，在这种如果存在找不到，就输出非法信息即可。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 500010;
char s[maxn];

int main(){
    scanf("%s", s);
    int len = strlen(s);
    int pos1 = -1, pos2 = -1;
    for(int i = 0; i < len; i++){
        if(s[i] == '['){
            pos1 = i;
            break;
        }
    }
    for(int i = len-1; i >= 0; i--){
        if(s[i] == ']'){
            pos2 = i;
            break;
        }
    }
    if(pos1 == -1 || pos2 == -1 || pos1 > pos2){
        puts("-1");
        exit(0);
    }
    int pos3 = -1, pos4 = -1;
    for(int i = pos1; i <= pos2; i++){
        if(s[i] == ':'){
            pos3 = i;
            break;
        }
    }
    for(int i = pos2; i >= pos1; i--){
        if(s[i] == ':'){
            pos4 = i;
            break;
        }
    }
    if(pos3 >= pos4){
        puts("-1");
        exit(0);
    }
    int ans = 4;
    for(int i = pos3; i <= pos4; i++){
        if(s[i] == '|'){
            ans++;
        }
    }
    printf("%d\n", ans);
    return 0;
}

C:题意：给一堆线段，问是否可以把所有线段放到2个集合，使得这2个集合中任意选一个线段出来，即是第一个集合选一个，第2个集合选一下。
解法：很自然的想到按照l排序，l相同的时候按照r从小到大排序，然后依次扫描线段的过程中记录扫描过的线段的右端点的最大值，看一下是否当前线段的左端点大于右端点的最大值，如果大于，就从这里分界拆出集合就可以了。

#include <bits/stdc++.h>
using namespace std;
int T, n;
const int maxn = 1e5+10;
struct node{
    int l, r, id;
    bool operator<(const node &rhs)const{
        if(l == rhs.l) return r < rhs.r;
        return l < rhs.l;
    }
}a[maxn];
int out[maxn];
int main(){
    scanf("%d", &T);
    while(T--){
        scanf("%d", &n);
        for(int i = 1; i <= n; i++){
            scanf("%d%d", &a[i].l, &a[i].r);
            a[i].id = i;
        }
        sort(a+1, a+n+1);
        int ans = -1;
        int mx = a[1].r;
        for(int i = 2; i <= n; i++){
            if(a[i].l > mx){
                ans = i;
                break;
            }else{
                mx = max(mx, a[i].r);
            }
        }
        if(ans == -1){
            printf("-1\n");
            continue;
        }
        for(int i = 1; i <= n; i++){
            if(i < ans){
                out[a[i].id] = 1;
            }else{
                out[a[i].id] = 2;
            }
        }
        for(int i = 1; i <= n; i++) printf("%d ", out[i]);
        printf("\n");
    }
    return 0;
}

D:https://blog.csdn.net/qq_38891827/article/details/86354057，树上dp，可以参考这个同学的题解。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+5;
//dp[i][j]表示为以i为起点的向i的子树延伸的gcd为a[i]的第j个质因子的最长链的长度
int a[maxn], dp[maxn][10];
//map[pair<i,j>]=k表示i在j中是第k个质因子
vector <int> G[maxn], vec[maxn];
map <pair<int, int>, int> mp;
int ans = 0;
void dfs(int rt, int fa){
    for(int i = 0; i < G[rt].size(); i++){
        dp[rt][i] = 1;
    }
    int mx1[10], mx2[10];
    for(int i = 0; i < 10; i++) mx1[i] = mx2[i] = 0;
    for(int i = 0; i < vec[rt].size(); i++){
        int to = vec[rt][i];
        if(to == fa) continue;
        dfs(to, rt);
        for(int j = 0; j < G[rt].size(); j++){
            if(a[to] % G[rt][j] == 0){
                int pos = mp[make_pair(G[rt][j], to)]; //rt的第j个质因子是to的第pos个质因子
                int tmp = dp[to][pos];
                if(mx1[j] < tmp){
                    mx2[j] = mx1[j];
                    mx1[j] = tmp;
                }else if(mx2[j] < tmp){
                    mx2[j] = tmp;
                }
            }
        }
    }
    for(int i = 0; i < G[rt].size(); i++){
        dp[rt][i] += mx1[i];
        ans = max(ans, mx1[i] + mx2[i] + 1);
    }
}
int main(){
    int n, u, v;
    scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%d", &a[i]);
    for(int i=1; i<=n; i++){
        int tmp = a[i];
        for(int j=2; j*j<=tmp; j++){
            if(tmp%j == 0){
                G[i].push_back(j);
                mp[make_pair(j, i)] = G[i].size()-1;
                while(tmp%j == 0) tmp /= j;
            }
        }
        if(tmp > 1){
            G[i].push_back(tmp);
            mp[make_pair(tmp, i)] = G[i].size() - 1;
        }
    }
    for(int i = 1; i <= n-1; i++){
        scanf("%d%d", &u, &v);
        vec[u].push_back(v);
        vec[v].push_back(u);
    }
    dfs(1, -1);
    printf("%d\n", ans);
    return 0;
}

E:题意，这个题比d的难度小很多，就是一个人可能可以产生xy的小矩形（无数个），然后也可能查询已经有的小矩形是否可以填满当前xy这个大矩形？
解法：由于每种类型可以产生无数个，我们只用关心拥有的小矩形的长宽坐标是否在当前输入的范围内，是就可以完全填满。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5+5;

int main(){
    int q;
    scanf("%d", &q);
    int mx1 = 0, mx2 = 0;
    while(q--){
        char op[2];
        int x, y, minn, maxx;
        scanf("%s%d%d", op, &x, &y);
        minn = min(x, y);
        maxx = max(x, y);
        if(op[0] == '+'){
            mx1 = max(mx1, maxx);
            mx2 = max(mx2, minn);
        }else{
            if((x >= mx1 && y >= mx2) || (x >= mx2 && y >= mx1)) puts("YES");
            else puts("NO");
        }
    }
    return 0;
}

G:题意：将一个序列分成尽量多的段，每段值为异或值，且使得不存在非空子集异或和为0。
解法：转为前缀和，然后就是选最多元素且不存在非空子集异或和为0。然后插入线性基，线性基的大小即是答案。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 200010;
int n, a[maxn], b[maxn];
int p[33];

int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
        b[i] = b[i-1]^a[i];
    }
    if(b[n] == 0){
        puts("-1");
        return 0;
    }
    int ans = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 29; j >= 0; j--){
            if(!(b[i]>>j)) continue;
            if(!p[j]) {
                p[j] = b[i];
                ans++;
                break;
            }
            b[i] ^= p[j];
        }
    }
    printf("%d\n", ans);
    return 0;
}