【ACM算法竞赛日常训练】DAY1题解与分析

DAY1 共四题：

月月查华华的手机：https://ac.nowcoder.com/acm/problem/23053
Rinne Loves Edges：https://ac.nowcoder.com/acm/problem/22598
逆序对：https://ac.nowcoder.com/acm/problem/14731
Xorto：https://ac.nowcoder.com/acm/problem/14247

视频教程：https://www.bilibili.com/video/BV1JX4y1d7LC

作者：Eriktse

简介：19岁，211计算机在读，现役ACM银牌选手力争以通俗易懂的方式讲解算法！️欢迎关注我，一起交流C++/Python算法。（优质好文持续更新中……）

个人博客：www.eriktse.com

月月查华华的手机

tag:动态规划

注意：子序列是可以分隔开的，请区别子串和子序列。

我们定义dp[i][j]表示在母串中第i位右边最近的字符j的位置，如果不存在则为-1，初始值为-1。

倒序处理出dp数组后，对每一个子串进行判断。

判断的思路是：当前在母串的位置j，当前子串字符为k，那么我找dp[j][k]看看是否存在，如果有就让j跳过去，如果没有就说明母串中不存在这个子序列。

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int maxn = 1e6 + 9;

char s[maxn];

int dp[maxn][30], now[30];//dp[i][j]表示母串中第i位右边最近的字符j的位置

signed main()

{

    memset(dp, -1, sizeof dp);

    memset(now, -1, sizeof now);

    scanf("%s", s + 1);

    int n = strlen(s + 1);

    for(int i = n;i >= 0; -- i)

    {

        for(int j = 0;j < 26; ++ j)dp[i][j] = now[j];

        if(i > 0)now[s[i] - 'a'] = i;

    }

    int T;scanf("%lld", &T);

    while(T --)

    {

        scanf("%s", s + 1);

        int m = strlen(s + 1);

        bool ans = true;

        for(int i = 1, j = 0;i <= m; ++ i)

        {

            int k = s[i] - 'a';

            if(dp[j][k] == -1)

            {

                ans = false;

                break;

            }

            else j = dp[j][k];

        }

        printf("%s\n", ans ? "Yes" : "No");

    }

    return 0;

}

Rinne Loves Edges

tag:简单图论，树

首先以s作为根构造一棵树，fa[x]表示x的父亲。

不难发现，假如我要使得点x为根的子树的所有叶子到不了s，那么可以通过删除x - fa[x]这条边或删除x与所有儿子节点的边，那么对于x的儿子亦是如此。

所以我们就有了dp方程, w[x]为x与fa[x]的边权，dp[x]表示删除点x的最小代价（代码中的dp用dfs表示）：

$$dp[x] = min(w[x], \sum_{y \in g[x] y \neq fa[x]}w[y])$$

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int maxn = 1e5 + 9, inf = 1e18;

int w[maxn];//w[i]表示点i的父亲这条边的边权

vector<pair<int, int> > g[maxn];

int n, m, s;

int dfs(int x, int pre)//pre是x的父节点，返回删除节点x和父亲这条边的最小代价

{

    //有可能是根

    if(g[x].size() == 1 and x != s)return w[x];

    int res = 0;//res表示子节点的代价之和

    for(auto &i : g[x])

    {

        int y = i.first, dw = i.second;

        //x -> y, cost = dw

        if(y == pre)continue;//如果下一个点是当前的父节点，就不进入

        w[y] = dw;

        res += dfs(y, x);

    }

    return min(w[x], res);

}

signed main()

{

    scanf("%lld %lld %lld", &n, &m, &s);

    for(int i = 1;i <= m; ++ i)

    {

        int x, y, w;scanf("%lld %lld %lld", &x, &y, &w);

        g[x].push_back({y, w});

        g[y].push_back({x, w});

    }

    w[s] = inf;

    printf("%lld\n", dfs(s, 0));

    return 0;

}

逆序对

tag:组合数学

我们知道只有(1, 0)这样的二元组会对答案产生贡献，那么我们枚举第二位，然后找左边有多少个1即可。

对于第i位，左边有$2^{i - 1}$种情况，每种情况平均都是$\frac{i-1}{2}$个1，然后右边有$2^{n - i}$种情况，会使得区间[0, i]的情况重复多次。

所以第i位的贡献$a_i = 2^{n-1} \times \frac{i-1}{2} = 2 ^ {n-2} \times (i - 1) $。

答案是：

$$ ans=\sum_{i=1}^{n}a_i=2\sum_{i=1}^{n}(i-1)=2\times n\times (n-1) $$

#include "bits/stdc++.h"

#define int long long

const int mod = 1e9 + 7;

int ksm(int a, int b) {

	int res = 1;

	while (b > 0) {

		if (b & 1) res = res * a % mod;

		b >>= 1;

		a = a * a % mod;

	}

	return res;

}

int mo(int x){return (x % mod + mod) % mod;}

signed main() {

	int n; std::cin >> n;

	if (n == 1) {

		std::cout << 0 << "\n";

	} else if (n == 2) {

		std::cout << 1 << "\n";

	} else {

        int m = n % mod;

		std::cout << mo(m * m % mod - m) * ksm(2, n - 3) % mod;

	}

    return 0;

}

Xorto

tag: map, vector, 异或xor

将所有的异或和结果存到一个map里，每一个异或和结果对应一个vector，里面存下了所有的异或和相同的区间，且按照左端点为第一关键字，右端点为第二关键字的顺序排列好。

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int maxn = 1e5 + 9;

int a[maxn];

unordered_map<int, vector<pair<int, int>> > mp;

signed main()

{

    int n;scanf("%lld", &n);

    for(int i = 1;i <= n; ++ i)scanf("%lld", a + i);

    for(int i = 1;i <= n; ++ i)

    {

        int xorsum = 0;

        for(int j = i;j <= n; ++ j)

        {

            xorsum ^= a[j];

            if(!mp.count(a[j]))mp[a[j]] = vector<pair<int, int> >();

            mp[xorsum].push_back({i, j});

        }

    }

    int ans = 0;

    for(auto &it : mp)

    {

        vector<pair<int, int> >& v = it.second;

        //v中的所有区间，异或和都相同

        for(int i = 0;i < v.size(); ++ i)

        {

            int j = upper_bound(v.begin(), v.end(), v[i].second,

                                [](const int &x, const pair<int, int>& p)

                                {

                                    return x < p.first;

                                }) - v.begin();

            ans += v.size() - j;

        }

    }

    printf("%lld\n", ans);

    return 0;

}

本文由eriktse原创，创作不易，如果对您有帮助，欢迎小伙伴们点赞、收藏、留言

【ACM算法竞赛日常训练】DAY1题解与分析

月月查华华的手机

Rinne Loves Edges

逆序对

Xorto