【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^{n-2}\sum_{i=1}^{n}(i-1)=2^{n-3}\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;    
}