2020-12-21 10:49 已编辑湖南师范大学附属中学算法工程师

关注

牛客练习赛 74 题解

$\rm NowCoder~Practice~Contest~74$

$\quad$

$\text{——}~The~~Solution~~Written~~by~~CCA~\text{——}$

$\rm Summary$

$\quad$ 首先要给大家道个歉， $B$ 题的子串和字符串界定并没有说清楚，当且仅当也给部分人带来了歧义，给大家带来了一些不好的体验，对不起【鞠躬】

$\quad$ 但是总的来说，本场题目质量还是很不错的，难度也比上次比赛控制得好，共有 $5$ 人 $AK$ 。他们分别是 $:$

$\quad$ 让我们恭喜他们！

$\quad$ 这是 $CCA$ 在牛客上出的第 $2$ 场比赛，他喜欢将自己的 $idea$ 用比赛的方式记录下来，也一直在努力将比赛出得更好，希望大家能够喜欢【呲牙】

$\rm A-Sequence$

$Description$

$\quad$ 判定一个长度为 $n$ 的序列 $A$ 是否满足给定的三个条件之一。

$\quad 3\leqslant n \leqslant 10^5~,~\forall i,a_i\leqslant 10^9$

$Solution$

$\quad$ 简单语法题。

$\quad$ 对于序列用第一项和第二项求出公差、公比和 “公模” ，对于每一个 $i\in [3,n]$ 判断第 $i-1$ 项和第 $i$ 项是否都满足条件即可。

$\quad$ 时间复杂度 $\mathcal{O}(N)$ 。

$Code$

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
const double eps = 1e-6;

int n, a[N], flag, tag;

int main () {

    //freopen("sequence.in", "r", stdin);
    //freopen("sequence.out", "w", stdout);

    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);

    tag = true;
    for(int i = 3; i <= n; i++)
        if(a[i] - a[i - 1] != a[i - 1] - a[i - 2]) tag = false;
    flag = max(flag, tag);

    tag = true;
    for(int i = 3; i <= n; i++)
        if(fabs(1.0 * a[i] / a[i - 1] - 1.0 * a[i - 1] / a[i - 2]) > eps) tag = false;
    flag = max(flag, tag);

    tag = true;
    for(int i = 3; i <= n; i++) 
        if(a[i] % a[i - 1] != a[i - 1] % a[i - 2]) tag = false;
    flag = max(flag, tag);

    puts(flag ? "YES" : "NO");

    return 0;
}

$\rm B-Find$

$Description$

$\quad$ 在一个长度为 $n$ 的母串中匹配一个较短的子序列，问能匹配多少次。

$\quad n \leqslant 10^5$

$Solution$

$\quad$ 简单容斥题。

$\quad$ 用一个指针记录当前已经匹配到了哪里，暴力匹配，运用乘法原理计算答案即可。

$\quad$ 时间复杂度 $\mathcal{O}(N)$ 。

$Code$

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10; 

int n, Last;
char s[N], pos[8] = {'N', 'o', 'w', 'C', 'o', 'd', 'e', 'r'};
long long ans;

int main () {

    //freopen("find.in", "r", stdin);
    //freopen("find.out", "w", stdout);

    scanf("%s", s + 1), n = strlen(s + 1);

    for(int i = 1; i <= n; i++) {
        bool flag = true;
        for(int j = 0; j < 8; j++)
            if(s[i + j] != pos[j]) { flag = false; break; }
        if(flag) ans += 1ll * (i - Last) * (n - i - 6), Last = i;
    }

    printf("%lld", ans);

    return 0;
}

$\rm C-Mouse$

$Description$

$\quad$ 问一个 $n\times n$ 的带权矩阵 $A$ 中一个斜着的 $k\times k$ 的子矩阵的最大权值和。

$\quad n \leqslant 10^3~,~k\leqslant 100~,~\forall i,j,a_{i,j}\leqslant 10^9$

$Solution$

$\quad$ 较简单的前缀和题，需要用到一点初中数学知识。

$\quad$ 先将矩阵 $A$ 旋转 $45^\circ$ 后存在一个新数组里，然后做前缀和即可。

$\quad$ 时间复杂度 $\mathcal{O}(N)$ 。

$Code$

//这道题的代码写得太丑了，于是就把验题人的代码搬过来了 【呲牙】
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mid ((l+r)>>1)
#define lson rt<<1, l, mid
#define rson rt<<1|1, mid+1, r
#define fors(i, a, b) for(int i = (a); i < (b); ++i)
using namespace std;
const int maxn = 5e3 + 50;
ll s[maxn][maxn];
int n, k;
int main()
{
    scanf("%d%d", &n, &k);
    assert(n <= 2000 && n > 0 && k <= n && k <= 100 && k > 0);
    fors(i,1,n+1){
        fors(j,1,n+1) scanf("%lld", &s[i+j][i-j+n]), assert(s[i+j][i-j+n] <= 1e9 && s[i+j][i-j+n] >= 0);
    }
    fors(i,1,maxn){
        fors(j,1,maxn) s[i][j] += s[i-1][j] + s[i][j-1] - s[i-1][j-1];
    }
    ll ans = 0;
    fors(l,1,2*n+1){
        fors(d,1,2*n+1){
            int r = l + 2*k-2;
            int u = d + 2*k-2;
            if((l+d-n)%2) continue;
            ans = max(ans, s[r][u] - s[l-1][u] - s[r][d-1] + s[l-1][d-1]);
        }
    }
    cout<<ans<<endl;
}

$\rm D-Trip$

$Description$

$\quad$ 在一张无向带权图中求一条从起点和终点的路径，在最大化最小边的同时最小化最大边。

$\quad n \leqslant 10^6~,~m \leqslant 3\times 10^6~,~\forall i,W_i\leqslant 10^9$

$Solution$

$\quad$ 较简单的并查集题。

$\quad$ 先按边权从大到小枚举边， $s$ 到 $t$ 的路径第一次连通时加入的边的边权就是 $L$ ，再按边权从 $L$ 开始往大枚举边， $s$ 到 $t$ 的路径再一次连通时加入的边的边权就是 $R$ 。

$\quad$ 时间复杂度 $\mathcal{O}(N\times log_2N)$ ，可以用路径压缩和按秩合并优化到 $\mathcal{O}[N\times \alpha(N)]$ 。

$Code$

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
const int M = 3e6 + 10;

struct Edge { int u, v, w; }E[M];

int n, m, s, t, fa[N], num[N], L, R;

int Find (int x) {
    if(x != fa[x]) fa[x] = Find(fa[x]);
    return fa[x];
}

void Link (int u, int v) {
    int x = Find(u), y = Find(v);
    if(num[x] < num[y]) fa[x] = y, num[y] += num[x];
    else fa[y] = x, num[x] += num[y];
}

bool cmp (Edge a, Edge b) { return a.w < b.w; }

int main () {

    //freopen("trip.in", "r", stdin);
    //freopen("trip.out", "w", stdout);

    scanf("%d%d%d%d", &n, &m, &s, &t);
    for(int i = 1; i <= m; i++)
        scanf("%d%d%d", &E[i].u, &E[i].v, &E[i].w);

    sort(E + 1, E + m + 1, cmp);

    for(int i = 1; i <= n; i++) fa[i] = i, num[i] = 1;

    for(int i = m; i >= 1; i--) {
        Link(E[i].u, E[i].v);
        if(Find(s) == Find(t)) { L = i; break; }
    }

    for(int i = 1; i <= n; i++) fa[i] = i, num[i] = 1;

    for(int i = L; i <= m; i++) {
        Link(E[i].u, E[i].v);
        if(Find(s) == Find(t)) { R = i; break; }
    }

    printf("%d %d", E[L].w, E[R].w);

    return 0;
}

$\rm E-Dyeing$

$Description$

$\quad$ 在一张无向带权图上进行 $k$ 次操作，每次等概率随机选择 $2$ 个点，将这两个点之间的所有最短路上的所有点染黑。问经过 $k$ 次操作后的图上期望黑点个数是多少。

$\quad n \leqslant 500~,~m \leqslant \frac{n(n-1)}{2}~,~\forall i,W_i\leqslant 10^9~,~k\leqslant 10^9$

$Solution$

$\quad$ 不难的概率题，需要用到 $Floyd(DP)$ 求最短路。

$\quad$ 考虑对每个点分别求贡献，容斥后就转化成求每个点经过 $k$ 次后不被染黑的概率，即为一次不被染黑的概率的 $k$ 次方。

$\quad$ 于是只需要用 $Floyd$ 算法求出多源最短路，然后计算每个点被多少条最短路经过即可。这个过程也可以用 $Dijkstra$ 算法优化到 $\mathcal{O}(N^2\times log_2N)$ ，但是良心出题人没有卡 ^_^

$\quad$ 时间复杂度 $\mathcal{O}(N^3)$ 。

$Code$

#include<bits/stdc++.h>
using namespace std;

const int N = 500 + 10;
const int M = N * N;
const int mod = 1023694381;

int n, m, k, col[N], cnt[N], ans;
long long dis[N][N];

int Pow (int a, int k) {
    if(k == 1) return a;
    int S = Pow(a, k >> 1);
    if(k & 1) return 1ll * S * S % mod * a % mod;
    else return 1ll * S * S % mod;
}

int main () {

    //freopen("dyeing.in", "r", stdin);
    //freopen("dyeing.out", "w", stdout);
    scanf("%d%d%d", &n, &m, &k);
    for(int i = 1; i <= n; i++) scanf("%d", &col[i]);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            dis[i][j] = dis[j][i] = 4e18 * (i != j);
    for(int u, v, w, i = 1; i <= m; i++)
        scanf("%d%d%d", &u, &v, &w), dis[u][v] = dis[v][u] = w;

    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);

    for(int i = 1; i <= n; i++)
        for(int j = i + 1; j <= n; j++)
            for(int k = 1; k <= n; k++)
                if(dis[i][j] == dis[i][k] + dis[k][j]) cnt[k]++;

    for(int i = 1; i <= n; i++)
        if(col[i]) ans++;
        else ans = (ans + 1 - Pow(1ll * (1ll * n * (n - 1) % mod - cnt[i] * 2)
          * Pow(1ll * n * (n - 1) % mod, mod - 2) % mod, k) + mod) % mod;

    printf("%d", ans);

    return 0;
}

$\rm F-Tree$

$Description$

$\quad$ 求满足给定条件的树的期望数量。

$\quad n,m \leqslant 10^7$

$Solution$

$\quad$ 有点意思的组合题。

$\quad\large{Part1}$

$\quad$ 手动计算【呲牙】

$\quad\large{Part2}$

$\quad$ 暴力模拟，找出所有形态的树和所有染色方案，判定是否合法。

$\quad$ 其实很快你就会发现，树的形态枚举错了也没关系，还是可以得到正确的答案。

$\quad\large{Part3}$

$\quad$ 状态压缩，搜索或 $DP$ 。

$\quad\large{Part4}$

$\quad$ 树形 $DP$ ，时间复杂度 $\mathcal{O}(N^3)$ 。

$\quad\large{Part5}$

$\quad$ 这是本题第一个巧妙的转化。

$\quad$ 先容斥，然后我们考虑将树拍平，放到 $dfs$ 序上考虑。

$\quad$ 令 $dp(i,j)$ 表示此时枚举到 $dfs$ 序的第 $i$ 位，已经用了 $j$ 种颜色的不合法方案数。

$\quad$ 选到当前这个点时，其父亲的颜色肯定已经确定了（这个结点父亲的 $dfs$ 序排在这个结点的前面），如果想让这种方式不合法，必须存在其任意一个非父非子结点颜色和其相同且整条路径颜色也相同，而若有这样一条路径，必须要与其父亲颜色相同，所以颜色已经唯一确定，直接继承前一个结点的方案数。如果选一种之前没有选过的颜色，则有 $(m-j+1)$ 种选择。

$\quad$ 转移方程很显然 $:$

$dp(i,j)=dp(i-1,j)+dp(i-1,j-1)*(m-j+1)$ $Ans=m^n-\sum_{k=1}^mdp(n,k)$

$\quad$ 时间复杂度 $\mathcal{O}(N^2)$ 。

$\quad\large{Part6}$

$\quad$ 可能会有一些奇怪的 $\mathcal{O}(N\times log_2N)$ 的算法？

$\quad\large{Part7}$

$\quad 70$ 分的那个 $DP$ 方程是不是很眼熟？我们考虑它的组合意义。

$\quad$ 如果你稍微有点数学直觉就可以发现，这个 $DP$ 可以用来求解如下问题：

$\quad$ 给定 $n$ 个带编号的小球和 $m$ 个带编号的盒子，将这些小球放入 $m$ 个盒子中的 $k$ 个里的方案数是多少？

$\quad$ 显然这个问题的答案是 $dp(n,k)$ 。

$\quad$ 而这个问题又可以通过组合数来算，所以 $:$

$dp(n,k)=m!\dbinom{m}{k}\dbinom{n-1}{k-1}$ $Ans=m^n-m·m!-\sum_{k=1}^m\dbinom{m}{k}\dbinom{n-1}{k-1}$

$Code$

#include<bits/stdc++.h>
using namespace std;

const int N = 1e7 + 10;
const int mod = 1023694381;

int n , m , fac[N] , inv[N] , Sum;

inline int Add(int a , int b){
    return a + b > mod ? a + b - mod : a + b;
}

inline int Mul(int a , int b){
    return 1ll * a * b % mod;
}

inline int Pow(int a , int k){
    if(k == 0) return 1;
    if(k == 1) return a;
    int S = Pow(a , k >> 1);
    if(k & 1) return Mul(Mul(S , S) , a);
    else return Mul(S , S);
}

inline int C(int n , int m){
    if(m > n) return 0;
    return Mul(fac[n] , Mul(inv[m] , inv[n - m]));
}

inline int A(int n , int m){
    if(m > n) return 0;
    return Mul(fac[n] , inv[n - m]);
}

int main(){
    //freopen("tree.in" , "r" , stdin);
    //freopen("tree.out" , "w" , stdout);
    scanf("%d %d" , &n , &m);
    fac[0] = 1 , inv[0] = 1;
    for(register int i = 1; i <= max(n, m); i++) fac[i] = Mul(fac[i - 1] , i);
    inv[max(n, m)] = Pow(fac[max(n, m)] , mod - 2);
    for(register int i = max(n, m) - 1; i >= 1; i--) inv[i] = Mul(inv[i + 1] , i + 1);
    for(register int i = 1; i <= m; i++) Sum = Add(Sum , Mul(A(m , i) , C(n - 1 , i - 1)));
    printf("%d" , Add(Pow(m , n) - Sum , mod));
    return 0;
}