AtCoder Beginner Contest 318

D General Weighted Max Matching

题目大意

有一个无向图，$i$ 到 $j$ 的距离为 $D_{i,j}$。你可以选择一些边，使得这些边连接的所有顶点互不相同。求这些边总长度的最大值。

限制： $2 \leq n \leq 16$，$1 \leq D_{i, j} \leq 10^9$。

题解

直接状压 $\text{dp}$ 暴力枚举转移即可。

代码

/********************************************************************
    > File Name: d.cpp
    > Author: winter2020
    > Created Time: Tue Oct  3 13:40:56 2023
 ************************************************************************/

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <set>

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 17;
int n;
int a[N][N];
LL f[(1 << N)];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i ++ ) 
        for (int j = i + 1; j <= n; j ++ )
            cin >> a[i][j];
    for (int i = 1; i < (1 << n); i ++ ) {
        vector<int> pos;
        for (int j = 0; j < n; j ++ )
            if (i >> j & 1) pos.push_back(j);
        if (pos.size() % 2) continue;
        for (int j = 0; j < pos.size(); j ++ )
            for (int k = j + 1; k < pos.size(); k ++ )
                f[i] = max(f[i], f[i - (1 << pos[j]) - (1 << pos[k])] + a[pos[j] + 1][pos[k] + 1]);
    }
    if (n & 1) {
        LL ans = 0;
        for (int i = 0; i < n; i ++ )
            ans = max(ans, f[(1 << n) - 1 - (1 << i)]);
        cout << ans << endl;
    }
    else cout << f[(1 << n) - 1] << endl;
    return 0;
}

E Sandwiches

题目大意

给定一个长度为 $N$ 的序列 $A$。求满足以下条件的三元组 $(i,j,k)$ 的个数。

• $1 \le i < j < k \le N$
• $A_i = A_k$
• $A_i \ne A_j$

限制：$3 \le N \le 3 \times 10^5$，$1 \le A_i \le N$。

题解

枚举 $i$，假设满足 $i < k$ 的 $a_k = a_i$ 的 $k$ 分别为 $pos_1,\ pos_2,\ pos_3 \cdots$，那么当前 $i$ 对答案的贡献为 ：$(pos_1 - i - 1) + (pos_2 - i - 1 - 1) + (pos_3 - i - 1 - 2) \cdots$。

每个 $pos_i$ 的最后一项是个等差数列，可以直接预处理。$pos$ 的和可以预处理后缀和或者先算总和后递推中更改。最后还要减去 $cnt * i$，vector（ $v_i$ 里面存所有 $a_j=i$ 的 $j$ ）+ 二分做。

代码

/********************************************************************
    > File Name: e.cpp
    > Author: winter2020
    > Created Time: Tue Oct  3 13:54:05 2023
 ************************************************************************/

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <set>

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 3e5 + 10;
int n;
int a[N];
vector<int> pos[N];
LL sum[N], cot[N];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) {
        scanf("%d", &a[i]);
        pos[a[i]].push_back(i);
        sum[a[i]] += i;
    }
    for (int i = 1; i <= n; i ++ ) cot[i] = cot[i - 1] + i;
    LL ans = 0;
    for (int i = 1; i <= n; i ++ ) {
        sum[a[i]] -= i;
        int cnt = lower_bound(pos[a[i]].begin(), pos[a[i]].end(), i) - pos[a[i]].begin();
        cnt = pos[a[i]].size() - cnt - 1;
        LL ct = sum[a[i]] - 1ll * cnt * i - cot[cnt];
        ans += ct;
    }
    cout << ans << endl;
    return 0;
}

F Octopus

题目大意

有个机器人，它有 $N$ 个手臂，第 $i$ 个手臂长度为 $L_i$。同时有 $N$ 个宝藏，第 $i$ 个宝藏的坐标是 $X_i$。

当机器人位于 $k$ 时，它的第 $i$ 条手臂可以够到 $[k-L_i,k+L_i]$ 范围内的宝藏。

机器人的每条手臂只能选择一个宝藏。请问总共有多少个整数坐标，能够让机器人在这个坐标能够拿到所有宝藏？

限制：$1\ \leq\ N\leq\ 200$，$-10^{18}\ \leq\ X_1\ <\ X_2\ <\ \cdots\ <\ X_N\leq\ 10^{18}$，$1\leq\ L_1\leq\ L_2\leq\cdots\leq\ L_N\leq\ 10^{18}$，输入都是整数。

题解

没想出来，好像是因为没读对题，但应该读对了也做不出来。

首先考虑如何判断当头部位于 $k_0$ 时是否可以抓住所有 $n$ 个宝物，可以排序后贪心将触手与宝藏配对。

然后考虑怎样的 $k_0$ 作为分界点，即头部位于 $k_0$ 满足条件而头部位于 $k_0+1$ 不满足条件和头部位于 $k_0$ 不满足条件而头部位于 $k_0+1$ 满足条件的所有 $k_0$。

• 头部位于 $k_0$ 满足条件而头部位于 $k_0+1$ 不满足条件

在这种情况下，一定有这样的 $i,j$ 满足 $k_0-L_j\le x_i \le k_0+L_j$ 且 $k_0+1-L_j >x_i$ 或 $k_0+1+L_j < x_i$。

解不等式得 $k_0=x_i+L_j$。

• 头部位于 $k_0$ 不满足条件而头部位于 $k_0+1$ 满足条件

在这种情况下，一定有这样的 $i,j$ 满足 $k_0+1-L_j\le x_i \le k_0+1+L_j$ 且 $k_0-L_j >x_i$ 或 $k_0+L_j < x_i$。

解不等式得 $k_0=x_i-L_j-1$。

至此，我们找出了所有分界点，所以相邻分界点内的点一定相同，即将所有分界点按升序排序后放入 $S$ 后，当 $k_0=S_i$ 满足条件时，所有 $S_{i-1}+1\le k_0 \le S_i$ 的 $k_0$ 均满足条件。

时间复杂度 $\mathcal O(N^3 \log n)$。

题解参考了 https://www.luogu.com.cn/blog/cqwe/solution-at-abc318-g。

代码

/********************************************************************
    > File Name: f.cpp
    > Author: winter2020
    > Created Time: Tue Oct  3 16:58:40 2023
 ************************************************************************/

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <set>

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 210;
int n;
LL x[N], l[N];
LL pos[N * N * 2];

bool check(LL ps) {
    priority_queue<LL, vector<LL>, greater<LL> > q;
    for (int i = 1; i <= n; i ++ ) q.push(abs(ps - x[i]));
    for (int i = 1; i <= n; i ++ ) {
        if (q.top() > l[i]) return false;
        q.pop();
    }
    return true;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%lld", &x[i]);
    for (int i = 1; i <= n; i ++ ) scanf("%lld", &l[i]);
    int cnt = 0;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ ) {
            pos[ ++ cnt] = x[i] + l[j];
            pos[ ++ cnt] = x[i] - l[j] - 1;
        }
    sort(pos + 1, pos + cnt + 1);
    LL ans = 0;
    for (int i = 2; i <= cnt; i ++ ) 
        if (check(pos[i])) ans += pos[i] - pos[i - 1];
    cout << ans << endl;
    return 0;
}

G Typical Path Problem

题目大意

给出一个有 $n$ 个顶点和 $m$ 条边的无向连通图 $G$，没有重边和自环。

顶点的编号为 $1 \sim n$，边的编号为 $1 \sim m$，第 $i$ 条边连接顶点 $u_i$ 和 $v_i$。

给出图上三个不同的顶点 $A,B,C$。判断是否有从点 $A$ 经过点 $B$ 到点 $C$ 的简单路径。

简单路径指路径上的点互不相同，即不重复经过同一个点。

限制：$3 \le n \le 2 \times 10^5$，$n-1 \le m \le \min(\frac{n(n-1)}{2}, 2 \times 10^5)$，$1 \le A,B,C \le n$，$1 \le u_i < v_i \le n$。

题解

考虑网络流建图+拆点，把每个点拆成入点和出点，两个之间连一条流量为 $1$ 的边，从 $S$ 向 $B$ 连一条流量为 $2$ 的边，从 $A$、$C$ 分别向 $T$ 连一条流量为 $1$ 的边。原图的边就是 $u_{出点} \rightarrow v_{入点}$，$v_{出点} \rightarrow u_{入点}$。

然后跑一下 $\text{Dinic}$，如果最大流是 $2$ 那么输出 Yes，否则是 No。

代码

/********************************************************************
    > File Name: g.cpp
    > Author: winter2020
    > Created Time: Tue Oct  3 23:34:48 2023
 ************************************************************************/

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <set>

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 4e5 + 10, M = 2e6 + 10, INF = 0x3f3f3f3f;
int n, m;
int h[N], e[M], f[M], ne[M], idx;
int q[N], d[N], cur[N];
int A, B, C, S, T;

void add(int a, int b, int c) {
    e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx ++;
    e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx ++;
}


bool bfs() {
    int hh = 0, tt = 0;
    memset(d, -1, sizeof d);
    q[0] = S, d[S] = 0, cur[S] = h[S];
    while (hh <= tt) {
        int t = q[hh ++ ];
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (d[j] == -1 && f[i]) {
                d[j] = d[t] + 1;
                cur[j] = h[j];
                if (j == T) return true;
                q[ ++ tt] = j; 
            }
        }
    }
    return false;
}

int find(int u, int limit) {
    if (u == T) return limit;
    int flow = 0;
    for (int i = cur[u]; ~i && flow < limit; i = ne[i]) {
        cur[u] = i;
        int j = e[i];
        if (d[j] == d[u] + 1 && f[i]) {
            int t = find(j, min(f[i], limit - flow));
            if (!t) d[j] = -1;
            f[i] -= t, f[i ^ 1] += t, flow += t;
        }
    }
    return flow;
}

int dinic() {
    int flow, r = 0;
    while (bfs()) while (flow = find(S, INF)) r += flow;
    return r;
}

int main() {
    memset(h, -1, sizeof h);
    scanf("%d%d", &n, &m);
    scanf("%d%d%d", &A, &B, &C);
    for (int i = 1; i <= m; i ++ ) {
        int u, v;
        scanf("%d%d", &u, &v);
        add(u + n, v, 1), add(v + n, u, 1);
    }
    for (int i = 1; i <= n; i ++ ) 
        if (i != B) add(i, i + n, 1);
        else add(i, i + n, 2);
    add(S, B, 2), T = n * 2 + 1, add(A + n, T, 1), add(C + n, T, 1);
    int res = dinic();
    if (res == 2) puts("Yes");
    else puts("No");
    return 0;
}