赛时过了 A-G，Ex 仿佛猜到了结论但是完全不懂多项式科技，就炸了。

大家好像都秒了 A,B,C 就不写了。

题目描述：

给你一个加权无向完全图，图中有 \(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;
} 

题目描述：

给你一个长度为 \(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\) 的数。

可以发现答案其实就是：

\[\sum_{i=1}^n \sum_{k=i+1}^n [A_i = A_k] (k - i - 1) - (s_k - s_i - 1)
\]

可以对于每一个 \(A_i\) 开一个桶维护位置，这样我们直接在每一个桶内维护就好了，这样 \(A_i = A_k\) 的限制就无了：

\[\begin{aligned}
&\sum_{i=1}^{len} \sum_{k=i+1}^{len}(k - i - 1) - (s_k - s_i - 1) \\
&= \sum_{i=1}^{len} \sum_{k=i+1}^{len}k - i - s_k + s_i \\
&= \sum_{i=1}^{len} (s_i - i + \sum_{k=i+1}^{len}k - s_k)
\end{aligned}
\]

考虑每一个 \(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;
} 

题目描述：

在一条数线上有一个章鱼形机器人和 \(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\)，它有\(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;
} 

题目描述：

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\)，则就有如下的式子：

\[g_n = \dfrac{\sum_{i=1}^n \frac{2}{i} \times f_{n-i} + \frac{1}{i} \times g_{n-i}}{n}
\]

上面的这个首先要知道一个定理就是：长度为 \(n\) 的置换，点 \(n\) 所在环的长度在 \([1,n]\) 概率相等，所以上文的 \(\frac{2}{i}\) 的含义其实就是最小值在下标最大的/最小的位置，而后面的 \(\frac{1}{i}\) 相当于我们已经在 \(g_{n-i}\) 确定了谁寄，为了保证另一个不寄最小值只能在这一个位置。

对于 \(g\) 前面这一坨就是卷积，后面这一坨是半在线卷积，都是可以做的。

我们的答案显然就是 \((1 - f_n - g_n) \times (n!)^2\)，然后就做完了。