D Choose Me

Description

Solution

记 $Takahashi$ 和 $Aoki$ 的选票数差为 $\Delta$ 。如果 $Takahashi$ 不在任何城市演讲，则 $\Delta = -\sum A_i$ 。假设 $Takahashi$ 在城市 $i$ 演讲，则 $\Delta$ 会增大 $2A_i+B_i$ 。题目要求选择最少的城市使 $\Delta>0$ ，因此只需要对城市按 $2A_i+B_i$ 降序排列即可。

Code

Choose Me

#include <bits/stdc++.h>

#define debug(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

const int MAXN = 2E5 + 5;
const int MOD = 1E9 + 7;
int n, m, T;
LL pre[MAXN], pos[MAXN];

struct City {
    LL a, b, c;
    friend bool operator<(const City& a, const City& b) {
        return 2 * a.a + a.b > 2 * b.a + b.b;
    }
} ct[MAXN];

template <class T>
void read(T& x) {
    x = 0;
    T f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : 1), ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
    x *= f;
}

template <class T, class... Args>
void read(T& x, Args&... args) {
    read(x), read(args...);
}

signed main() {
    read(n);
    for (int i = 1; i <= n; i++)
        read(ct[i].a, ct[i].b), ct[i].c = ct[i].a + ct[i].b;
    sort(ct + 1, ct + n + 1);
    for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + ct[i].c;
    for (int i = n; i >= 1; i--) pos[i] = pos[i + 1] + ct[i].a;
    for (int i = 1; i <= n; i++)
        if (pre[i] > pos[i + 1]) {
            cout << i;
            break;
        }
    return 0;
}

E Through Path

Description

题目链接

Solution

设节点 $a$ 深度大于节点 $b$ ，那么对于第二种操作，相当于对树上所有节点加上 $x$ ，将 $a$ 的子树中所有节点减去 $x$ ；对于第一种操作，只需要将 $a$ 的子树中所有节点加上 $x$ 即可。对于子树修改，可以考虑使用 $dfs$ 序加树状数组。由于本题无动态查询，因此只需要在树上进行差分，最后再跑一遍 $dfs$ 统计答案。

Code

Through Path

#include <bits/stdc++.h>

#define debug(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

const int MAXN = 2E5 + 5;
const int MOD = 1E9 + 7;
int n, m, q, T;
vector<int> G[MAXN];
array<int, MAXN> in, out, depth;
LL tot;

struct Edge {
    int a, b;
} e[MAXN];

template <class T>
void read(T& x) {
    x = 0;
    T f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : 1), ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
    x *= f;
}

template <class T, class... Args>
void read(T& x, Args&... args) {
    read(x), read(args...);
}

struct BIT {  // Binary Index Trees, 1based
    int lowbit(int x) { return x & (~x + 1); }
    /* O(n) build tree*/
    BIT() {
        for (int i = 1; i <= n; i++) c[i] = 0;
    }
    void build() {
        for (int i = 1; i <= n; i++) {
            int j = i + lowbit(i);  // j is father of i
            if (j <= n) c[j] += c[i];
        }
    }
    /*@param x the position to add val*/
    void add(int x, LL val) {
        while (x <= n) c[x] += val, x += lowbit(x);
    }
    /*range [1, x] sum query*/
    LL query(int x, LL res = 0) {
        while (x) res += c[x], x -= lowbit(x);
        return res;
    }
    array<LL, MAXN> c;
} bit[3];
/*range [l, r] add val*/
inline void add(int l, int r, LL val) {
    bit[1].add(l, val), bit[1].add(r + 1, -val);
    bit[2].add(l, val * l), bit[2].add(r + 1, -val * (r + 1));
}
/*range [l, r] sum query*/
inline LL query(int l, int r, LL res = 0) {
    res = bit[0].query(r) + bit[1].query(r) * (r + 1) - bit[2].query(r);
    res -= bit[0].query(l - 1) + bit[1].query(l - 1) * l - bit[2].query(l - 1);
    return res;
}

void dfs(int now, int fa) {
    static int times = 1;
    depth[now] = depth[fa] + 1, in[now] = times++;
    for (auto& to : G[now]) {
        if (to != fa) dfs(to, now);
    }
    out[now] = times;
}

signed main() {
    read(n);
    for (int i = 1; i <= n - 1; i++) {
        read(e[i].a, e[i].b);
        G[e[i].a].push_back(e[i].b);
        G[e[i].b].push_back(e[i].a);
    }
    dfs(1, 1);
    read(q);
    for (int i = 1; i <= q; i++) {
        int type, ei, x;
        read(type, ei, x);
        if (type == 1) {
            if (depth[e[ei].a] > depth[e[ei].b])
                add(in[e[ei].a], out[e[ei].a] - 1, x);
            else {
                tot += x;
                add(in[e[ei].b], out[e[ei].b] - 1, -x);
            }
        } else {
            if (depth[e[ei].a] < depth[e[ei].b])
                add(in[e[ei].b], out[e[ei].b] - 1, x);
            else {
                tot += x;
                add(in[e[ei].a], out[e[ei].a] - 1, -x);
            }
        }
    }
    for (int i = 1; i <= n; i++) printf("%lld\n", query(in[i], in[i]) + tot);
    return 0;
}

F Close Group

Description

题目链接

Solution

设 $dp[i]$ 表示点集为 $i$ 时的答案。设当前点集为 $S$ ，若这些点能构成完全图，那么答案显然为 $1$ ；否则，可以将点集 $S$ 可以分为两个非空真子集，于是有 $dp[S] = \min \limits_{T⊂S}{dp[T]+dp[S-T]}$ 。因此对于每个集合，二进制枚举其非空真子集即可。由二项式定理可证枚举非空真子集的时间复杂度为 $O(3^N)$ ，而对于每个点集，判断其能否构成完全图的时间复杂度为 $O(N^2)，$ 因此总的时间复杂度为 $O(N^22^N+3^N)$ 。

Code

Close Group

#include <bits/stdc++.h>

#define debug(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

const int MAXN = (1 << 18);
int n, m;
bool e[18][18], good[MAXN];
int dp[MAXN];

bool check(int x) {
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (j != i)
                if (((x >> i) & 1) && ((x >> j) & 1) && !e[i][j])
                    return false;
    return true;
}

signed main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        e[a][b] = e[b][a] = 1;
    }
    memset(dp, 0x3f3f3f3f, sizeof(dp));
    dp[0] = 0;
    for (int i = 1; i < (1 << n); i++)
        if (check(i)) good[i] = 1, dp[i] = 1;
    for (int i = 1; i < (1 << n); i++) {
        if (good[i]) continue;
        for (int j = i; j; j = (j - 1) & i)
            dp[i] = min(dp[i], dp[j] + dp[i ^ j]);
    }
    cout << dp[(1 << n) - 1];
    return 0;
}