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;    
}

🎈 本文由eriktse原創，創作不易，如果對您有幫助，歡迎小夥伴們點贊👍、收藏⭐、留言💬