E. GCD VS XOR(位运算)

时间复杂度：$O(n)$

题意

    $t$组数据，每组给定一个$x$，求出严格小于$x$的正整数$y$，使得$gcd(x,y)=x \oplus y$；若不存在，则输出“-1”.

数据范围

  • $1 \le t \le 10^4$
  • $1 \le x \le 10^{18}$

思路

    签到题，结论就是$y=x-lowbit(x)$或者更为直接的写法$y=x \& (x-1)$,当$x$恰为2的幂次方时，也就是x二进制(从低位往高位)的第一个1就是其本身，即$x=lowbit(x)$，此时答案无解。
    从结论出发，不难发现，当$y=x-lowbit(x)$时，即y等于x减去二进制的第一个1时，$lowbit(x)$与$x$一定成倍数，恰好满足gcd的要求，同时两者异或值等于$lowbit(x)$。如二进制数$(1011100)_2$，其$lowbit(x)=(100)_2$,显然，$(1011100)_2=(1000000)_2 +(10000)_2+(1000)_2+(100)_2$，也就是$(100)_2 \cdot (2^4+2^2+2^1+2^0)$;$(1011100)_2 \oplus (1011000)_2=(100)_2$,故$gcd(x,y)=x \oplus y=lowbit(x)$.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
#define endl '\n' 
using i64 = long long;
using namespace std;
signed main(){
    std::ios::sync_with_stdio(false);cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        i64 x, ans;
        cin >> x;
        i64 res = x & (x-1);
        ans = (res ? res : -1);
        cout << ans << endl;
    }
    return 0;
}

C. Red Walking on Grid（贪心/动态规划）

时间复杂度：$O(2n)$

题意

    有一个$2 \cdot n$的方格，颜色为红$(‘R’)$或者白$(‘W’)$。Red 起始可以选择任意一个红方格，他每次可以选择上、下、左、右四个方位前进到相邻的红方格，每走一步，原来的红方格将被染成白色（不能返回），请问 Red 最远能走的步数。

数据范围

  • $1 \le n \le 10^6$

思路

    本题与最大连通块不同的是，它的路径是连续不断的，所以不能使用DFS或并查集求解。从贪心的角度考虑，最大步数显然与奇偶和选择的起点有关，形成的路径也会存在重叠，所以若干个子问题重叠应该考虑 动态规划 求解。
    设$dp[1/2][i]$表示到达第$1/2$行第$j$列的最大步数，起始将所有值赋为0，显然，当$s[i][j]$等于$’W’$时,$dp[i][j]=0$。从左往右循环遍历，每次对上下两格进行转移操作，当$s[i][j]=’R’$时，分为两种转移方式——

  1. 从左边转移，$dp[1/2][j]=max(dp[1/2][j], \colorbox{Yellow}{dp[1/2][j-1]+1})$
  2. 从斜对角转移，以第一行为例，当$s[2][i]=’R$时，$\colorbox{Yellow}{dp[1][i]=dp[2][i-1]+2}$;注意，不能直接从下方转移，因为其可能还没有进行转移.

    最后的答案就是取所有方格的 ${dp}$最大值减去1 ,因为起始取到的方格是不算步数的；注意当全为$’W’$时，最后的结果会变成-1，所以需要特判最小步数为0。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
#define endl '\n' 
using i64 = long long;
using namespace std;
char s[3][1000010];
int dx[] = {1, 0, 0, -1}, dy[] = {0, 1, -1, 0};
signed main(){
    std::ios::sync_with_stdio(false);cin.tie(0);
    int n;
    cin >> n;
    vector<vector<int>> dp(3, vector<int>(n + 1));
    for (int i = 1; i <= 2;i++)
        cin >> s[i] + 1;
    int ans;
    for (int i = 1; i <= n;i++){
        if(s[1][i]=='R'){
            dp[1][i] = max(dp[1][i], dp[1][i - 1] + 1);
            if(s[2][i]=='R')
                dp[1][i] = max(dp[1][i], dp[2][i - 1] + 2);
        }
        if(s[2][i]=='R'){
            dp[2][i] = max(dp[2][i], dp[2][i - 1] + 1);
            if (s[1][i] == 'R')
                dp[2][i] = max(dp[2][i], dp[1][i - 1] + 2);
        } 
    }
    ans = max(*max_element(dp[1].begin(), dp[1].end()), *max_element(dp[2].begin(), dp[2].end()))-1;
    ans = max(ans, 0);
    cout << ans << endl;
    return 0;
}

H. Instructions Substring(前缀和+map映射)

时间复杂度：$O(n)$

题意

    Red 起始站在坐标(0,0)点，可以接受四种字符指令$c$：$’W’$(向上),$’S’$(向下),$’A’$(向左)和$’D’$(向右)。现在给定一个长度为$n$的仅有四种字符指令构成的字符串和目标坐标$(x,y)$，请问能够使得 Red 成功 经过 坐标$(x,y)$的连续子串的数量。

数据范围

  • $1 \le n \le 2 \times 10^5$
  • $-10^5 \le x,y \le 10^5$
  • $c \in \{‘W’,’S’,’A’,’D’\}$

思路

    由于求的是连续子串，我们可以枚举连续子串的 左端点 ，当往后取到第一个右端点能够满足该区间产生的位移值，其恰好能够使坐标移动到目标点，则此后任意的端点都能满足”经过“，所以问题就转化为了找到每个左端点$i$的 右边第一个 满足条件的下标值$j$！
    维护区间值的经典思路显然是 前缀和 ，设$pre[1][i]$为前i个字符的横向位移值，$pre[2][i]$为前i个字符的纵向位移值；维护每个坐标的信息和对应的下标，显然应该使用 map容器 进行映射。
    当枚举到左端点$i$和对应的右端点$j$时，满足等式$pre[1][i-1]+dx=pre[1][j]$和$pre[2][i-1]+dy=pre[2][j]$，其中$dx$和$dy$分别等于原点到坐标的差值，数值上等于$x$与$y$，该左端点对答案的 贡献值 显然为$n-j+1$.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<bits/stdc++.h>
#define endl '\n' 
using i64 = long long;
using namespace std;
typedef pair<int, int> PII;
char s[200010];
signed main(){
    std::ios::sync_with_stdio(false);cin.tie(0);
    int n, x, y;
    cin >> n >> x >> y;
    cin >> s + 1;
    i64 ans = 0;
    if (x == 0 && y == 0){
        ans = n * (n + 1) / 2;
        cout << ans << endl;
        return 0;
    }
    vector<vector<int>> pre(n+1, vector<int>(3));
    map<pair<int, int>, vector<int>> pos;
    for (int i = 1; i <= n;i++){
        pre[i][1] = pre[i - 1][1];
        pre[i][2] = pre[i - 1][2];
        if(s[i]=='W')
            pre[i][2]++;
        else if(s[i]=='S')  
            pre[i][2]--; //往下就是往上走-1步
        else if(s[i]=='A')
            pre[i][1]--; //往左同理
        else
            pre[i][1]++;
    }
    for (int i = n; i;i--)
        pos[{pre[i][1], pre[i][2]}].emplace_back(i); //存放每一个坐标值的下标
    for (int i = 1; i <= n; i++){
        PII temp = {pre[i - 1][1] + x, pre[i - 1][2] + y};
        while (!pos[temp].empty()) //由于每个下标只会被访问一次，所以不会影响复杂度
        {
            if (pos[temp].back() < i){ //找到右边第一个满足坐标值的下标
                pos[temp].pop_back();
                continue;
            }
            ans += n - pos[temp].back() + 1;
            break;
        }
    }
    cout << ans << endl;
    /*for (int i = 1; i <= n; i++)
        cout << pre[i][1] << ' ' << pre[i][2] << endl;*/
    return 0;
}

B.MST(根号分治+最小生成树)

时间复杂度：$O(n \sqrt{n} +\sqrt{n}\:m)$

题意

    给定一张$n$个节点和$m$条边的无向图，$m$条边含有起点$u_i$，终点$v_i$和权值$w_i$;给定现在有$q$次询问，每次询问会先给出一个$k_i$，随后给出$k_i$个不同的正整数，这些正整数组成一个新的点集$S$，请问这些S组成的最小生成树的边权和是多少，若不能组成，则输出”-1”.

数据范围

  • $2 \le n \le 10^5,1 \le m,q \le 10^5$
  • $1 \le u_i,v_i \le n,u_i \neq v_i$
  • $1 \le w_i \le 10^9$
  • $1 \le k_i \le n,1 \le s_{i,j} \le n$
  • $\sum {k_i} \le 10^5$

思路

    由于本题$\: q \in [1,10^5]$,而离线算法计算各个点集是不现实的，在线算法无论枚举点还是边复杂度都不够……本题的正解是 根号分治 。
    我们考虑分成两部分考虑，即$k_i <= \sqrt n$和$k_i>\sqrt n$（等号取任意一边即可）————

  • 当$ k_i<=\sqrt n $时，此时点集数量较少，我们考虑直接暴力枚举点，如果两个点之间有边，那么我们就将其记录，枚举各点的复杂度为$ \dfrac{k_i \times (k_i-1)}{2} $，因为$ k_i \le \sqrt n $，所以复杂度不超过$ O(n) $;不难想到，暴力枚举的各边形成的是 稠密图 ，所以可以选择$Prim$法跑最小生成树，复杂度为$ k_i*k_i $,与之前枚举点的复杂度几乎相同，又因为题中给定了$\sum {k_i} \le 10^5$,也就是说$k_i$的总和范围等于$n$的范围，所以最坏情况下$(k_i=\sqrt n)$的轮数仅为$\dfrac {n}{\sqrt n}=\sqrt n$，所以总体复杂度为$O(\sqrt n \cdot n )$.
  • 当$k_i>\sqrt n$时,此时我们直接通过题中所给的 $m$条边 进行遍历，如果边的两个端点都隶属于该次询问的点集中，那么将这条边保存下来，最后我们对满足条件的边进行排序和并查集操作，跑$Kruskal$法最小生成树，复杂度为$O(m\;log_2m)$,同时可以继续优化，我们可以在询问前就对所有边数进行预处理排序，这样每次选出的边也一定是升序的，进行的轮数同样也是不超过$\sqrt n$的，所以总复杂度就是$O(\sqrt n \cdot m)$.

    故总复杂度为 $O(n\sqrt{n} +\sqrt{n}\:m)$ ，能够通过此题！

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <bits/stdc++.h>
#define endl '\n'
#define inf 1e12
using i64 = long long;
using namespace std;
struct node{
    int u, v, w;
    bool operator<(const node x) const{
        return w < x.w; //按边权值升序
    }
} e[100010], edge[100010];
signed main(){
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m, q, k;
    cin >> n >> m >> q;
    vector<int> u(m + 1), v(m + 1), w(m + 1), s(n + 1);
    map<pair<int,int>, int> g; //邻接矩阵
    int tot = 0;
    for (int i = 1; i <= m; i++)
    {
        cin >> u[i] >> v[i] >> w[i];
        e[++tot] = {u[i], v[i], w[i]};
        g[{u[i], v[i]}] = g[{v[i], u[i]}] = w[i];
    }
    sort(e + 1, e + tot + 1); //排序预处理
    auto Kruskal = [&]() -> i64
    {
        vector<int> fa(n + 1);
        for (int i = 1; i <= n; i++)
            fa[i] = i;
        auto find = [&](auto find, int x) -> int
        {
            return x == fa[x] ? x : fa[x] = find(find, fa[x]);
        };
        int cnt = 0;
        i64 ans = 0;
        for (int i = 1; i <= tot; i++){
            int rx = find(find, edge[i].u), ry = find(find, edge[i].v);
            if (rx != ry){
                fa[rx] = ry, cnt++;
                ans += edge[i].w;
            }
            if (cnt == k - 1)
                break;
        }
        return (cnt == k - 1 ? ans : -1);
    };
    auto Prim = [&]() -> i64
    {
        vector<vector<i64>> G(k + 1, vector<i64>(k + 1, inf));
        vector<i64> dist(n + 1, inf);
        vector<bool> vis(n + 1);
        for (int i = 1; i <= k;i++)
            for (int j = i; j <= k;j++)
                if(g.count({s[i],s[j]}))
                    G[i][j] = G[j][i] = g[{s[i],s[j]}]; //将s[1]-s[k]设为点1-k
                else
                    G[i][j] = inf;
        vis[1] = 1, dist[1] = 0;
        for (int i = 2; i <= k;i++)
            dist[i] = min(dist[i], G[1][i]);
        i64 res = 0;
        for (int i = 2; i <= k;i++)
        {
            i64 temp = inf, idx = -1;
            for (int j = 1; j <= k;j++)
                if (!vis[j] && dist[j] < temp)
                    temp = dist[j], idx = j;
            if (idx == -1)
                return -1;
            vis[idx] = 1, res += temp;
            for (int j = 1; j <= k;j++)
                if (!vis[j] && dist[j] > G[idx][j])
                    dist[j] = min(dist[j], G[idx][j]);
        }
        return res;
    };
    int temp;
    temp = (int)sqrt(n + 0.5);
    while (q--){
        cin >> k;
        map<int, bool> mp;
        for (int i = 1; i <= k; i++)
            cin >> s[i], mp[s[i]] = 1;
        if (k <= temp) // 暴力枚举点集跑Prim O(√n n)
            cout << Prim() << endl;
        else{ // 暴力遍历所有的边跑Kruskal O(√n m)
            tot = 0;
            for (int i = 1; i <= m; i++)
                if (mp.count(e[i].u) && mp.count(e[i].v))
                    edge[++tot] = {e[i].u, e[i].v, e[i].w};
            cout << Kruskal() << endl;
        }
        /*for (int i = 1; i <= tot;i++)
            cout << edge[i].u << ' ' << edge[i].v << ' ' << edge[i].w << endl;*/
    }
    return 0;
}