🫟2024牛客暑假多校训练营Day2||补题

A-Floor Tiles

题意

存在A型、B型两种砖：

现用这两种砖拼成 $N\times M$ 的矩形，提问是否有恰好存在 $K$ 条曲线的平铺方式，曲线如下：

数据范围

$1\leq T\leq 10^5$
$1\leq N,M\leq 800$
$1\leq K \leq 2\times N\times M$

思路

边缘一圈的点所在的线一定不是一个环，所以最少的线数相当于都是A型或B型时的线数，也就是 $N\times M$ 个，若要比 $N\times M$ 个多，则多的部分只能是图形中环的数目，贪心的让所有的环最小，则能构造出最多的环，最小的环如例图中一样，当平铺的方式是

\begin{aligned} AB\\ BA \end{aligned}

时，形成的环是最小的。

同时注意到，成环的四块砖块是可以共用的，也就是说在：

\begin{aligned} ABAB\\ BABA\\ ABAB \end{aligned}

中有3个环。

首先构造成环数量最多的 $N\times M$ ，在输出时记录当前已经拥有多少个环，若超过所需的数量则不再输出可以成环的砖块类型。

代码

1
void solve() {
2
    int x, y;
3
    char ty;
4
    int n, m, k;
5
    char a = 'A', b = 'B';
6
    cin >> n >> m >> k;
7
    cin >> x >> y >> ty;
8
    vector<string>ans(n + 1, string(m + 1, 'X'));
9
    for (int i = 1;i <= n;i++) {
10
        for (int j = 1;j <= m;j++) {
11
            if (abs(i + j - x - y) % 2) {
12
                ans[i][j] = a + b - ty;
13
            }
14
            else {
15
                ans[i][j] = ty;
16
            }
17
        }
18
    }
19

20
    int cnt = n + m;
21
    for (int i = 1;i <= n;i++) {
22
        for (int j = 1;j <= m;j++) {
23
            if (ans[i][j] == a && ans[i][j - 1] == b && ans[i - 1][j] == b && ans[i - 1][j - 1] == a)
24
                cnt++;
25
        }
26
    }
27

28
    if (cnt < k || k < n + m) {
29
        cout << "No\n";
30
        return;
31
    }
32

33
    k -= n + m;
34
    cout << "Yes\n";
35
    for (int i = 1;i <= n;i++) {
36
        for (int j = 1;j <= m;j++) {
37
            if (k > 0) {
38
                cout << ans[i][j];
39
                if (ans[i][j] == a && ans[i][j - 1] == b && ans[i - 1][j] == b && ans[i - 1][j - 1] == a)
40
                    k--;
41
            }
42
            else cout << ty;
43
        }
44
        cout << '\n';
45
    }
46
}

B-MST

题意

给定一个 $n$ 顶点的带权无向图 $G$ 。

每次询问一个点集 $S$ ，求 $S$ 关于 $G$ 的导出子图的最小生成树的质量，若无则输出-1。

数据范围

$2\leq n\leq 10^5$
$1\leq m,q\leq 10^5$
$1\leq w_i \leq 10^9$
$\sum k_i\leq 10^5$

思路

注意点数 $n$ 和边数 $m$ 的范围都不超过 $10^5$ ，若通过枚举两个点来确定符合条件的边，则复杂度是 $O(n^2)$ ，而如果按照枚举边来确定符合条件的边，复杂度是 $O(m)$ ，于是优化的思路是根据每次 $k$ 和 $\sqrt {maxn}$ 的大小关系来选择加入边的方式。

代码

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
const int maxn = 1e5 + 50;
5
struct edge {
6
    int s, t, w;
7
    bool operator<(const edge& e)const {
8
        return w < e.w;
9
    }
10
};
11

12
vector<vector<edge>>graph;
13
map<pair<int, int>, int>gp;
14

15
int s[maxn];
16
int fa[maxn];
17
int findfa(int x) {
18
    if (x == fa[x])return x;
19
    return fa[x] = findfa(fa[x]);
20
}
21

22
ll krus(int n, vector<edge>subgraph) {
23
    ll res = 0;
24
    int cnt = 0;
25
    for (auto e : subgraph) {
26
        if (cnt == n - 1)break;
27
        if (!cnt) {
28
            fa[e.t] = e.s;
29
            res += e.w;
30
            ++cnt;
31
            continue;
32
        }
33
        auto [u, v, w] = e;
34
        int fu = findfa(u), fv = findfa(v);
35
        if (fu == fv)continue;
36
        fa[fu] = fv;
37
        res += w;
38
        ++cnt;
39
    }
40
    int fx = findfa(s[1]);
41
    for (int i = 2;i <= n;i++) {
42
        if (fx != findfa(s[i])) {
43
            return -1ll;
44
        }
45
    }
46

47
    return res;
48
}
49

50
void solve() {
51
    int n, m, q;cin >> n >> m >> q;
52
    graph.assign(n + 1, vector<edge>());
53
    for (int i = 0;i <= n;i++)fa[i] = i;
54

55
    for (int i = 1;i <= m;i++) {
56
        int u, v, w;cin >> u >> v >> w;
57
        graph[u].push_back({ u,v,w });
58
        graph[v].push_back({ v,u,w });
59
        gp[{u, v}] = w;
60
        gp[{v, u}] = w;
61
    }
62
    while (q--) {
63
        int k;cin >> k;
64
        map<int, bool>mp;
65
        for (int i = 1;i <= k;i++) {
66
            cin >> s[i];
67
            fa[s[i]] = s[i];
68
            mp[s[i]] = true;
69
        }
70
        vector<edge>subgraph;
71
        if (k * k < maxn) { // 点少
72
            // 取出符合要求的边
73
            for (int i = 1;i <= k;i++) {
74
                for (int j = i + 1;j <= k;j++) {
75
                    int u = s[i], v = s[j];
76
                    if (gp.count({ u,v })) {
77
                        int w = gp[{u, v}];
78
                        subgraph.push_back({ u,v,w });
79
                    }
80
                }
81
            }
82
        }
83
        else {
84
            for (int i = 1;i <= k;i++) {
85
                int u = s[i];
86
                for (auto e : graph[u]) {
87
                    if (mp.count(e.t))
88
                        subgraph.push_back(e);
89
                }
90
            }
91
        }
92
        sort(subgraph.begin(), subgraph.end());
93
        cout << krus(k, subgraph) << "\n";
94
    }
95
}
96

97
int main() {
98
    int t = 1;
99
    while (t--)
100
        solve();
101

102
    return 0;
103
}

C-Red Walking on Grid

题意

在一个 $2\times n$ 的网格中，每个格子要么是红色（R），要么是白色（W）。每次只能踩在当前格子的上下左右相邻的红色格子上，并且在离开当前的格子之后，当前格子将从红色变为白色，提问最长。

数据范围

$1\leq n\leq 10^6$

思路

直接从左往右搜索即可，若当前列有红色格子，则它可以由前一列相邻格子的步数+1转移过来，或者是从下方或上方的红色格子转移过来，两者选更优的解作为答案即可。

代码

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
const ll maxn = 1e6 + 50;
5
const ll mo = 1e9 + 7;
6

7
ll n;
8
char mp[3][maxn];
9
ll dp[3][maxn] = { 0 };
10
void solve() {
11
    cin >> n;
12
    for (ll i = 1;i <= 2;i++) {
13
        for (ll j = 1;j <= n;j++)
14
            cin >> mp[i][j];
15
    }
16
    mp[1][0] = mp[2][0] = mp[1][n + 1] = mp[2][n + 1] = 'W';
17
    ll ans = 0;
18
    for (ll i = 1;i <= n;i++) {
19
        if (mp[1][i] == 'R')dp[1][i] = dp[1][i - 1] + 1;
20
        if (mp[2][i] == 'R')dp[2][i] = dp[2][i - 1] + 1;
21
        if (mp[1][i] == 'R' && mp[2][i] == 'R') {
22
            ll tmp = dp[1][i];
23
            if (dp[1][i] < dp[2][i] + 1) {
24
                dp[1][i] = dp[2][i] + 1;
25
            }
26
            if (dp[2][i] < tmp + 1) {
27
                dp[2][i] = tmp + 1;
28
            }
29
        }
30
        ll tmp = max(dp[1][i], dp[2][i]);
31
        ans = max(tmp, ans);
32
    }
33
    cout << max(ans - 1, 0ll) << endl;
34
}
35

36
int main() {
37
    int t = 1;
38
    // cin >> t;cin.get();
39
    while (t--)
40
        solve();
41

42
    return 0;
43
}

E-GCD VS XOR

有人卡签到。。。TAT

题意

给定正整数 $x$ ，求满足 $gcd(x,y)=x\oplus y$ 的小于 $x$ 的正整数 $y$ 。若无则打印-1

数据范围

$1\leq t\leq 10^4$
$1\leq x\leq 10^{18}$

思路

距离考虑，对于数 $x=0b10011010$ ，考虑异或的性质 $A\oplus 0=A,A\oplus A=0$ ，设 $x\oplus y=k$ ， $y\lt x$ ，我们直接构造 $k$ 为 $x$ 最右侧的 $1$ 开始的数，这样的 $k$ 可以满足必然为 $x$ 的倍数，同时，若要满足 $gcd(x,y)=k$ ，构造 $y$ 的时候要满足除了 $lowbit(x)$ 以外的数位都与 $x$ 相同。

代码

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
const ll N = 1000001;
5

6
ll lowbit(ll x) { return x & -x; }
7

8
void solve() {
9
    ll x;cin >> x;
10
    ll ans = -1;
11
    if (lowbit(x) != x) {
12
        ans = x - lowbit(x);
13
    }
14

15
    cout << ans << "\n";
16
}
17

18
int main() {
19
    int _ = 1;
20
    cin >> _;cin.get();
21
    while (_--)
22
        solve();
23

24
    return 0;
25
}

H-Instructions Substring

题意

有一个操作字符串，由W，S，A，D组成，对应上下左右位移一位，从原点 $(0,0)$ 开始，将操作字符串的一个非空连续子段作为选择的操作，问有多少操作可以经过目标点 $(x,y)$ 。

数据范围

$1\leq n\leq 2\times 10^5$
$-10^5\leq x,y\leq 10^5$

思路

考虑记录每次操作后的坐标 $(u,v)$ ，对该偏移坐标 $(\Delta x,\Delta y)$ 计数，并逐步计算到达目标 $(x,y)$ 需要去除的偏移坐标量 $(u-\Delta x,v - \Delta y)$ ，这个需要去掉的操作数乘以当前的步数坐标（去掉 $(u-\Delta x,v-\Delta y)$ 之后，从当前步开始，之后不管在哪停下，都是有效的路径数目），之后对该偏移坐标数清零，避免重复计数（之后新出现的只在之后的操作中被计数）。

代码

1
ll n, x, y;
2
string st;
3
map<char, pair<ll, ll>>dxy;
4
map<ll, map<ll, ll>>mp; // mp[i][j]:x位移量为i,y位移量为j的操作数量。
5
void solve() {
6
    cin >> n >> x >> y;
7
    cin >> st;
8
    dxy['A'] = { 0,-1 };
9
    dxy['D'] = { 0,1 };
10
    dxy['S'] = { -1,0 };
11
    dxy['W'] = { 1,0 };
12
    if (!x && !y) {
13
        cout << n * (n + 1) / 2 << endl;
14
        return;
15
    }
16
    ll ans = 0;
17
    ll u = 0, v = 0;
18
    mp[0][0] = 1; // 原点形成的符合{0,0}方案数有1个
19
    for (ll i = 0;i < n;i++) {
20
        u += dxy[st[i]].second;
21
        v += dxy[st[i]].first;
22
        if (mp.count(u - x)) {
23
            // u-x:当前走了u步，去掉之前在x轴上走过的u-x步可以到目标x轴
24
            if (mp[u - x].count(v - y)) {   // 同理
25
                // 满足去除前面的多余x,y位移，之后的操作都是符合要求的。
26
                ans += mp[u - x][v - y] * (n - i);
27
                // 这次使用过去除符合要求的位移的操作方案数目了,之后重新出现的相同位移情况需要重新计数。
28
                mp[u - x][v - y] = 0;
29
            }
30
        }
31
        mp[u][v]++;
32
    }
33

34
    cout << ans << endl;
35
}

I-Red Playing Cards

题意

对于一个长度为 $2\times n$ 的一维数组， $1$ 到 $n$ 每个元素恰好出现两次。每次操作可以删掉一个长度不小于 $2$ 的首尾相同的连续子数组，获得该连续子数组的首尾元素值乘以元素数量的分数。为最终可以得到多少分。

数据范围

$1\leq a_i\leq n\leq 3000$

思路

每个数有两个坐标，假设数 $i$ 的坐标为 $l_i$ 和 $r_i$ ，预处理出以数 $i$ 为一个操作时的分数 $f(i)$ ，那么对于区间 $[l_i,r_i]$ ，可以计算其中每个数的贡献（即 $i$ ），若出现满足 $l_i\lt l_j \lt r_j\lt r_i$ ，则用 $max(i,j)$ 代替区间 $[l_j,r_j]$ 的贡献。

计算区间 $[l_i,k]$ 的最大分数 $g(k)$ ， $g(k)$ 符合：

g(k)= \begin{cases} max(g(k-1) + i,g(l_j-1)+f(j)),& (k=r_j \quad and \quad l_i \lt l_j)\\ g(k-1) + i & \end{cases}

直到 $k=r_i$ ，得到 $f(i)=g(r_i)$ 。

代码

1
void solve() {
2
    ll n;cin >> n;
3
    vector<ll>a(2 * n + 3);
4
    map<ll, plr>idx;
5
    for (ll i = 2;i <= 2 * n + 1;i++) {
6
        cin >> a[i];
7
        if (idx.count(a[i])) {
8
            idx[a[i]].r = i;
9
            idx[a[i]].len = idx[a[i]].r - idx[a[i]].l + 1;
10
        }
11
        else idx[a[i]].l = i;
12
    }
13

14
    // 用0包裹数组，取0这一对不影响结果，但是方便统计最佳分数
15
    a[1] = a[2 * n + 2] = 0ll;
16
    idx[0] = { 1,2 * n + 2,2 * n + 2 };
17

18
    vector<pair<plr, ll>>idv;
19
    for (auto i : idx) {
20
        idv.push_back({ i.second, i.first });
21
    }
22
    sort(idv.begin(), idv.end());
23

24
    vector<ll>f(n + 1);
25
    for (auto x : idv) {
26
        ll i = x.second;
27
        ll li = x.first.l, ri = x.first.r;
28

29
        vector<ll>g(2 * n + 2);
30
        for (ll k = li;k <= ri;k++) {
31
            ll j = a[k];
32
            ll lj = idx[j].l, rj = idx[j].r;
33
            if (li < lj && k == rj) {
34
                g[k] = max(g[k - 1] + i, g[lj - 1] + f[j]);
35
            }
36
            else {
37
                g[k] = g[k - 1] + i;
38
            }
39
        }
40
        f[i] = g[ri];
41
    }
42
    cout << f[0] << endl;
43
}