D 位运算之谜

链接：https://ac.nowcoder.com/acm/contest/7412/D
来源：牛客网

输入

1
2 1

输出

0

输入

1
2 2

输出

-1

思路

结论:x + y = x ^ y + (x & y) << 1
将x + y = a, x & y = b, 代入
x ^ y = a - (b << 1)

代码

#include<iostream>

using namespace std;

typedef long long LL;

int main(){
    int T;
    scanf("%d", &T);
    while(T --){
        LL x, y;
        scanf("%lld%lld", &x, &y);
        LL ans = x - (y << 1);
        if(ans < 0 || ans & y) cout << -1 << endl;
        else cout << ans << endl;
    }

    return 0;
}

G 牛牛和字符串的日常

思路

字符串匹配问题, KMP模板题

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 100010;

char p[N], s[N];
int ne[N];
int main(){
    scanf("%s", p + 1);
    int n = strlen(p + 1);
    for(int i = 2, j = 0; i <= n; i ++){
        while(j && p[j + 1] != p[i]) j = ne[j];
        if(p[i] == p[j + 1]) j ++;
        ne[i] = j;
    }

    int T;
    int ans = 0;
    scanf("%d", &T);
    while(T --){
        scanf("%s", s + 1);
        int m = strlen(s + 1);
        int res = 0;
        for(int i = 1, j = 0; i <= m; i ++){
            while(j && s[i] != p[j + 1]) j = ne[j];
            if(s[i] == p[j + 1]) j ++;
            res = max(res, j);
        }
        ans += res;
    }

    printf("%d\n", ans);

    return 0;
}

J树上行走

思路

找连通块元素个数最大值，可以用dfs, 也可以并查集

#include<iostream>
#include<cstring>
#include<algorithm>
#define rep(a, b) for(int i = a; i <= b; i ++)
using namespace std;

const int N = 200100;

int p[N];
int w[N];
int Size[N];
int n;
int ans[N];

int find(int x){
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main(){
    scanf("%d", &n);
    rep(1, n){
        int x;
        scanf("%d", &x);
        w[i] = x;
        p[i] = i;
        Size[i] = 1;
    }

    rep(1, n - 1){
        int a, b;
        scanf("%d%d", &a, &b);
        if(w[a] == w[b]) {
            int pa = find(a), pb = find(b);
            if(pa == pb) continue;
            Size[pb] += Size[pa];
            p[pa] = pb;
        }
    }
    int maxv = 0;
    rep(1, n){
        maxv = max(maxv, Size[find(p[i])]);
    }

    int cnt = 0;
    rep(1, n){
        if(Size[find(p[i])] == maxv) ans[cnt ++] = i;
    }

    sort(ans, ans + cnt);
    printf("%d\n", cnt);
    rep(0, cnt - 1){
        printf("%d ", ans[i]);
    }
    cout << endl;
}