AtCoder ABC187

本期题比较简单，但是如果不懂套路就难以想到

C - 1-SAT

检查!****类字符串是否在集合中出现

D - Choose Me

稍微需要想一下：
每次选第i项后，两边的差增加了$a_i+a_i+b_i$
按照这个差排序即可

#include <cstring>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;
typedef pair<int, int> pii;
typedef long long LL;
typedef pair<LL, LL> pll;


int n;
pll vote[200020];

bool cmp(pll a, pll b) {
    return a.first * 2 + a.second > b.first * 2 + b.second;
}


int main() {
    //freopen("in.txt", "r", stdin);
    scanf("%d", &n);
    for(int i = 0; i < n; ++ i) {
        scanf("%lld%lld", &vote[i].first, &vote[i].second);
    }
    sort(vote, vote + n, cmp);
    LL va = 0, vb = 0;
    for(int i = 0; i < n; ++ i) {
        va += vote[i].first;
    }
    int ans = 0;
    for(int i = 0; i < n; ++ i) {
        va -= vote[i].first;
        vb += vote[i].second + vote[i].first;
        if (vb > va) {
            ans = i + 1;
            break;
        }
    }
    printf("%d\n", ans);
    return 0;
}

E - Through Path

类似差分的做法
设$t_i$是可以访问的那一边，$e_i$是不能访问的一边
检查两个点$t_i,e_i$的相对位置
如果$t_i$在树中高，则整棵树的值加val，然后$e_i$为根的树里每个值需要减val
为了维护这个运算，可以标记一个数组add，在根节点记录val，在遍历的时候加入计算
反之如果$e_i$高，则将$e_i$为根的树里每个值加上val

#include <cstring>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;
typedef pair<int, int> pii;
typedef long long LL;
typedef pair<LL, LL> pll;


int n, q;
vector<int> g[200020];
LL add[200020];
int lev[200020];
pii edge[200020];
LL ans[200020];

void dfs(int u, int fa) {
    lev[u] = lev[fa] + 1;
    for(int v: g[u]) {
        if (v != fa)
            dfs(v, u);
    }
}


void dfs2(int u, int fa, LL cur) {
    cur += add[u];
    ans[u] = cur;
    for(int v: g[u]) {
        if(fa == v) continue;
        dfs2(v, u, cur);
    }
}


int main() {
    //freopen("in.txt", "r", stdin);
    
    scanf("%d", &n);
    for (int i = 1; i < n; ++ i) {
        int x, y;
        scanf("%d%d", &x, &y);
        g[x].push_back(y);
        g[y].push_back(x);
        edge[i] = {x, y};
    }
    dfs(1, 0);

    scanf("%d", &q);
    for(int i = 0; i < q; ++ i) {
        int op, x, val;
        scanf("%d%d%d", &op, &x, &val);
        int u, v;
        if (op == 1) {
            u = edge[x].first, v = edge[x].second;
        } else {
            u = edge[x].second, v = edge[x].first;
        }
        if (lev[u] < lev[v]) {
            add[1] += val;
            add[v] -= val;
        } else {
            add[u] += val;
        }
    }
    dfs2(1, 0, 0);
    for(int i = 1; i <= n; ++ i){
        printf("%lld\n", ans[i]);
    }
}

F - Close Group

N=18状态压缩暴力求解
当然需要一点技巧：
记录mask为当前取到的位码
遍历mask的子集（非0非本身）的方法是

for (int u = mask - 1; u; u = (u - 1) & mask)

判断完全子图可以压缩一下每个点所连边的状态，见代码

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <string>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <algorithm>
#define LT(x) (x * 2)
#define RT(x) (x * 2 + 1)

using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef vector<int> vi;


int n, m;
int dp[300000];
vi g[20];
int em[20];


int main() { 
    //freopen("in.txt", "r", stdin);
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        u--, v--;
        // g[u].push_back(v);
        // g[v].push_back(u);
        em[u] |= 1 << v;
        em[v] |= 1 << u;
    }
    for (int i = 0; i < n; ++i)
        em[i] |= 1 << i;
    set<int> single;
    for (int i = 1; i < (1 << n); i *= 2)
        single.insert(i);
    for (int i = 1; i < (1 << n); ++i) {
        if (single.count(i)) {
            dp[i] = 1;
            continue;
        }
        dp[i] = n;
        for (int v = (i - 1) & i; v; v = (v - 1) & i) {
            int u = i - v;
            dp[i] = min(dp[u] + dp[v], dp[i]);
        }
        bool flag = 1;
        for (int j = 0; j < n; ++j) {
            if ((i >> j) & 1) {
                if ((em[j] & i) != i) {
                    flag = 0;
                }
            }
        }
        if (flag)
            dp[i] = 1;
    }
    printf("%d\n", dp[(1 << n) - 1]);
    return 0;
}