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;
}