Floor Tiles

题目大意

img

让你构造一个$n\times m$的只包含”A”或”B”的字符，”A””B”含义如上图，将其按照构造的位置拼接，需要你恰好有$K$条曲线，并且会限定某个位置为”A”或”B”。

解题思路

观察性质发现，从外部的曲线进入一定会从外围曲线出去，剩下的线条一定是内部的环。而每种类型的字符对应的图四条边都有线条，易得进出外围的曲线一定是$\frac {2(n+m)}2=n+m$个。又观察到全”A”或全”B”一定没有环，而$2\times 2$字符对应第一行”AB”，第二行”BA”，能得到一个单位圆，故一定多构造出一个线条的最优策略。考虑根据输入给定位置的限定字符全赋值成该字符。然后根据该位置的横纵坐标关系与该位置具体限定字符模拟构造“ABAB”交错或”BABA”交错。

参考代码

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> PII;
typedef long long LL;
const int INF = 0x3f3f3f3f3f3f3f3f;

bool multi = 1;

void solve(){
    int n, m, k;
    cin >> n >> m >> k;
    int x, y;
    char z;
    cin >> x >> y >> z;
    vector<vector<char>> ans(n + 1, vector<char>(m + 1));
    k -= n + m;
    if(k < 0) {
        cout << "No\n";
        return;
    }
    if(k == 0) {
        cout << "Yes\n";
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                cout << z;
            }
            cout << '\n';
        }
        return;
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            ans[i][j] = z;
        }
    }
    if((x + y) % 2 == 0 && z == 'A' || (x + y) % 2 == 1 && z == 'B') {
        for(int i = 1; i < n; i++) {
            for(int j = (i % 2 == 1 ? 1 : 2); j < m; j += 2) {
                ans[i][j] = ans[i + 1][j + 1] = 'A';
                ans[i + 1][j] = ans[i][j + 1] = 'B';
                if(--k == 0) {
                    i = n;
                    break;
                }
            }
        }
    }else{
        for(int i = 1; i < n; i++) {
            for(int j = (i % 2 == 1 ? 2 : 1); j < m; j += 2) {
                ans[i][j] = ans[i + 1][j + 1] = 'A';
                ans[i + 1][j] = ans[i][j + 1] = 'B';
                if(--k == 0) {
                    i = n;
                    break;
                }
            }
        }
    }

    if(k > 0) {
        cout << "No\n";
        return;
    }else{
        cout << "Yes\n";
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                cout << ans[i][j];
            }
            cout << '\n';
        }
        return;
    }
    
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T = 1;
    if(multi) cin >> T;
    while(T--) {
        solve();
    }

    return 0;
}

MST

题目大意

给你一个图，多次询问若干个结点构成的最小生成树的权值之和。

解题思路

考虑根号分治，由于询问总结点个数不超过$10^5$，对于单次询问结点个数多的，直接做$kruskal$最小生成树跑给定的所有边；对于单次询问结点个数少的，先用$map$存入所有边，再暴力循环枚举询问的结点找到所有这些结点之间的边，然后做一遍$kruskal$。

考虑两种情况分治的界限$V$，对于询问结点个数多的时间复杂度为$O(qlogm)$即$O(\frac