赛时过了 A-G,Ex 仿佛猜到了结论但是完全不懂多项式科技,就炸了。
大家好像都秒了 A,B,C 就不写了。
D.General Weighted Max Matching
题目描述:
给你一个加权无向完全图,图中有 \(N\) 个顶点,编号从 \(1\) 到 \(N\)。连接顶点 \(i\) 和 \(j\) 的 \((i < j)\)的权重为\(D_{i,j}\)。
在以下条件下选择若干条边时,请找出所选边的最大可能总权重。
- 所选边的端点是成对不同的。
\(2\leq N\leq 16\)
\(1\leq D_{i,j} \leq 10^9\)
所有输入值均为整数。
题目分析:
一眼看过去这是一般图的最大权独立集,根本没啥多项式做法。
所以就直接爆搜的就好了,也就是对于每一个点找它匹配的点,需要注意的是可以有点不匹配边。
这样的复杂度就是 \(O(N!!)\) 显然可以过。
代码:
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 20;
int n,match[N],d[N][N],ans,sum;
void dfs(int now){
if(now == n + 1){
ans = max(ans,sum);
return;
}
if(match[now]){
dfs(now+1);
return;
}
for(int i=now+1; i<=n; i++){
if(match[i]) continue;
match[now] = i,match[i] = now;
sum += d[now][i];
dfs(now+1);
match[now] = match[i] = 0;
sum -= d[now][i];
}
dfs(now+1);
}
signed main(){
scanf("%lld",&n);
for(int i=1; i<=n; i++){
for(int j=i+1; j<=n; j++){
scanf("%lld",&d[i][j]);
}
}
dfs(1);
printf("%lld\n",ans);
return 0;
}
E.Sandwiches
题目描述:
给你一个长度为 \(N\) 的正整数序列:\(A=(A_1,A_2,\ldots,A_N)\).求满足下列所有条件的正整数三元组 \((i,j,k)\)的个数:
- \(1\leq i < j < k\leq N\),
- \(A_i = A_k\),
- \(A_i \neq A_j\).
\(3 \le N \le 3 \times 10^5\)
\(1 \le A_i \le N\)
题目分析:
看上去我们可以考虑枚举 \(i,k\) 然后看看有多少符合条件的 \(j\)。
不妨假设 \(s_i\) 表示前 \(i\) 个数中有多少个等于 \(A_i\) 的数。
可以发现答案其实就是:
可以对于每一个 \(A_i\) 开一个桶维护位置,这样我们直接在每一个桶内维护就好了,这样 \(A_i = A_k\) 的限制就无了:
考虑每一个 \(s_i - i\) 会有 \(n - (i + 1)\) 个 \(k\) 使得 \(i\) 可以产生这个贡献,所以这一部分对答案的贡献就是:\(\sum_{i=1}^{len} (s_i-i) \times (n - i - 1)\)
考虑每一个 \(k - s_k\) 会有 \(k-1\) 个 \(i\) 使得 \(k\) 可以产生这个贡献,所以这一部分对答案的贡献就是:\(\sum_{k=1}^{len} (k - s_k) \times (k - 1)\)
两部分求和就好。
代码:
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6+5;
int a[N];
vector<int> v[N];
signed main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int n;scanf("%lld",&n);
for(int i=1; i<=n; i++) scanf("%lld",&a[i]);
for(int i=1; i<=n; i++){
v[a[i]].push_back(i);
}
int ans = 0;
for(int i=1; i<=n; i++){
int len = v[i].size();
for(int j=0; j<v[i].size(); j++){
ans += -v[i][j] * (len - (j + 1));
ans += v[i][j] * j;
ans += j * (len - (j + 1));
ans += -j * j;
}
}
printf("%lld\n",ans);
return 0;
}
F.Octopus
题目描述:
在一条数线上有一个章鱼形机器人和 \(N\)个宝物。第 \(i\)个宝物 \((1\leq i\leq N)\)位于坐标 \(X_i\)处。
机器人有一个头和\(N\)条腿,\(i\)条腿\((1\leq i\leq N)\)的长度为\(L_i\)。
求满足如下要求的整数 \(k\) 的个数:
- 将头部置于坐标 \(k\)处。
- 依次对 \(i=1,2,\ldots,N\)重复以下步骤:如果在距离头部 \(L_i\)的距离内,即在满足 \(k-L_i\leq x\leq k+L_i\)的坐标 \(x\)处,有一件宝物尚未被抓取,则选择其中一件宝物并抓取。
\(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\) 给怎么判断是否合法。
一个显然的贪心就是按与 \(k\) 的距离将宝藏排序,然后让第 \(i\) 长的腿去抓第 \(i\) 远的宝藏,若抓不到则无解。
类似扫描线的思想,我们会发现如果对于区间 \(k \in [l,r]\) 任何一条腿都没有恰好碰到某一个宝藏,则这一段的数是否可以作为 \(k\) 的结果是一样的,因为感性理解既然不存在其恰好碰到某一个宝藏的情况,也就是不存在某一个腿原来可以覆盖宝藏 \(i\) 但是现在不能覆盖了,或者原本不能覆盖了现在可以覆盖的情况,因为若出现这种情况必然存在恰好碰到这样的分界点。
所以可以直接钦定某一条腿碰到某一个宝藏,这样可以得到 \(O(n^2)\) 个 \(k\),并且它们将区间分成了 \(O(n^2)\) 段。
只需要对于每一个段里随便选一个数判断一下即可,然后再对于选出的 \(O(n^2)\) 个 \(k\) 判断一下即可。
代码:
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5+5;
int n,tot,a[N],b[N],x[N],l[N],c[N];
bool chk(int k){
for(int i=1; i<=n; i++) a[i] = abs(x[i] - k);
for(int i=1; i<=n; i++) b[i] = l[i];
sort(a+1,a+n+1);
sort(b+1,b+n+1);
for(int i=1; i<=n; i++){
if(a[i] > b[i]) return false;
}
return true;
}
signed main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
scanf("%lld",&n);
for(int i=1; i<=n; i++) scanf("%lld",&x[i]);
for(int i=1; i<=n; i++) scanf("%lld",&l[i]);
for(int j=1; j<=n; j++){
for(int i=1; i<=n; i++){
int k = x[i] + l[j];
c[++tot] = k;
k = x[i] - l[j];
c[++tot] = k;
}
}
sort(c+1,c+tot+1);
tot = unique(c+1,c+tot+1) - c - 1;
int ans = 0;
for(int i=1; i<tot; i++){
if(c[i] == c[i+1]) continue;
if(chk(c[i]+1)) ans += c[i+1] - c[i] - 1;
}
for(int i=1; i<=tot; i++) if(chk(c[i])) ++ans;
printf("%lld\n",ans);
return 0;
}
G.Typical Path Problem
题目描述:
问题陈述
给你一个简单连通的无向图\(G\),它有\(N\)个顶点和\(M\)条边。 \(G\)的顶点和边分别编号为顶点\(1\)、顶点\(2\)、\(\ldots\)、顶点\(N\)和边\(1\)、边\(2\)、\(\ldots\)、边\(M\),边\(i\)\((1\leq i\leq M)\)连接顶点\(U_i\)和\(V_i\)。
在\(G\)上还有不同的顶点\(A,B,C\)。请判断是否有一条简单路径通过顶点\(B\)连接顶点\(A\)和\(C\)。
什么是简单连通无向图?
当\(G\)是简单且连通的无向图时,图\(G\)被称为简单连通的无向图。
当 \(G\) 的边没有方向时,图 \(G\) 称为无向图。
当 \(G\)不包含重边和自环时,图 \(G\)是简单的。
当人们可以通过边在\(G\)的所有顶点之间移动时,图\(G\)是连通的。
什么是通过顶点\(Z\)的简单路径?
对于图\(G\)上的顶点\(X\)和\(Y\),连接\(X\)和\(Y\)的简单路径是一系列不同的顶点\((v_1,v_2,\ldots,v_k)\),使得\(v_1=X\) \(v_k=Y\),并且对于满足\(1\leq i\leq k-1\)的每一个整数\(i\),在\(G\)上有一条边连接顶点\(v_i\)和\(v_{i+1}\)。
当有一条 \(i\)\((2\leq i\leq k-1)\)满足 \(v_i=Z\)时,称一条简单路径 \((v_1,v_2,\ldots,v_k)\)经过顶点 \(Z\) \((2\leq i\leq k-1)\)满足 \(v_i=Z\)。
\(3 \le N \le 2\times 10^5,M \le 2 \times 10^5\)
题目分析:
(官解竟然是网络流,充分说明科技的重要性,感觉震撼)
路径(必须)经过某个点的问题,显然想到圆方树,因为圆方树完美地保留了原图的必经性。
这个意思就是说圆方树路径上的圆点为两点路径的必经点,路径上的方点下的圆点就是两点路径的可经过的点。
所以只需要建出圆方树然后判断 \(A,C\) 路径上的圆点或方点下的圆点是否含有 \(B\) 即可。
代码:
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int _ = 2e6 + 5;
int A,B,C,n, m, q, tp;
int cnt_node, cntn;
bool flag;
int dfn[_], low[_];
int dep[_], top[_], siz[_], hson[_], fa[_];
stack<int> s;
struct Graph
{
int tot, head[_], nxt[_ << 1], to[_ << 1];
void add(int u, int v)
{
nxt[++tot] = head[u];
to[tot] = v;
head[u] = tot;
nxt[++tot] = head[v];
to[tot] = u;
head[v] = tot;
}
} G, T;
void tarjan(int u)
{
dfn[u] = low[u] = ++cnt_node;
s.push(u);
for (int i = G.head[u], v; i; i = G.nxt[i])
{
v = G.to[i];
if (!dfn[v])
{
tarjan(v);
low[u] = min(low[u], low[v]);
if (low[v] >= dfn[u])
{
T.add(++cntn, u);
while (1)
{
int now = s.top();
s.pop();
T.add(cntn, now);
if (now == v)
break;
}
}
}
else
low[u] = min(low[u], dfn[v]);
}
}
void dfs1(int u, int d = 1)
{
siz[u] = 1;
dep[u] = d;
for (int i = T.head[u], v; i; i = T.nxt[i])
{
v = T.to[i];
if (dep[v])
continue;
fa[v] = u;
dfs1(v, d + 1);
siz[u] += siz[v];
if (siz[v] > siz[hson[u]])
hson[u] = v;
}
}
void chk(int now){
if(now <= n && now == B) flag = true;
else{
for(int i=T.head[now]; i; i=T.nxt[i]){
int to = T.to[i];
if(to == B) flag = true;
}
}
}
signed main()
{
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
scanf("%d%d",&n,&m);
scanf("%d%d%d",&A,&B,&C);
cntn = n;
for (int i = 1, u, v; i <= m; i++)
{
scanf("%d%d",&u,&v);
G.add(u, v);
}
tarjan(1);
dfs1(1);
flag = false;
while(A != C){
if(dep[A] < dep[C]) swap(A,C);
chk(A);
A = fa[A];
}
chk(A);
if(flag) printf("Yes\n");
else printf("No\n");
return 0;
}
Ex.Count Strong Test Cases
题目描述:
Snuke 遇到了以下问题。
给你\((1,2,\ldots,N)\)的排列组合\(P=(P_1,P_2,\ldots,P_N)\)和\(Q=(Q_1,Q_2,\ldots,Q_N)\)。让我们如下建立一个有 \(N\) 个顶点和 \(N\) 条边的图。
- 依次为\(i=1,2,\ldots,N\),画一条权重为\(Q_i\)的边,双向连接顶点\(i\)和\(P_i\)。
当删除一定数量的边以消除图中的循环时,求删除的边的总重量的最小值。
爱丽丝和鲍勃提出了以下解决方案。
爱丽丝: 初始化答案为\(0\)。对于按此顺序排列的 \(i=1,2,\ldots,N\),如果连接顶点 \(i\)和 \(P_i\)的边包含在一个循环中,则删除该边并将其权重添加到答案中。
鲍勃: 将答案初始化为 \(0\)。对于按此顺序排列的\(i=N,N-1,\ldots,1\),如果连接顶点\(i\)和\(P_i\)的边包含在一个循环中,则删除该边并将其权重添加到答案中。
Snuke 意识到他们的解法都不正确,他想知道他们的解法都没有给出正确答案的输入数。
在 \((N!)^2\) 个可能的输入中,求爱丽丝和鲍勃的解都没有给出正确答案的输入个数(模为 \(998244353\))。
题目分析:
(这个大概就是 Atcoder 网站上的解法)
考虑答案可以容斥转化为所有的概率 - 两个全部正确的概率 - 恰好一个正确的概率。
首先若对于一个环最小的 \(i\) 满足 \(i \to P_i\) 在环上不为这个环的最小值,则 Alice 会寄掉。
如果对于一个环最大的 \(i\) 满足 \(i \to P_i\) 在环上不为这个环的最小值,则 Bob 会寄掉。
两个全部正确的概率,设为 \(f_n\)
而因为权值一定是一个排列,也就是不存在相等的情况,所以只要环不为自环则必然会至少寄一个,则显然 \(f_n = \frac{1}{n!}\)
恰好一个正确的概率,设为 \(g_n\)
这个计算就可以考虑枚举 \(n\) 所在环的大小设为 \(i\),则就有如下的式子:
上面的这个首先要知道一个定理就是:长度为 \(n\) 的置换,点 \(n\) 所在环的长度在 \([1,n]\) 概率相等,所以上文的 \(\frac{2}{i}\) 的含义其实就是最小值在下标最大的/最小的位置,而后面的 \(\frac{1}{i}\) 相当于我们已经在 \(g_{n-i}\) 确定了谁寄,为了保证另一个不寄最小值只能在这一个位置。
对于 \(g\) 前面这一坨就是卷积,后面这一坨是半在线卷积,都是可以做的。
我们的答案显然就是 \((1 - f_n - g_n) \times (n!)^2\),然后就做完了。
- 题解 Beginner AtCoder Contest 318beginner atcoder contest 318 题解beginner atcoder contest contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 328 beginner atcoder contest 332 beginner atcoder contest 334