AtCoder Beginner Contest 097

C

由于k非常小，因此直接小范围枚举即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// LUOGU_RID: 174636636
#include <bits/stdc++.h>
using namespace std;
string a[5000010];
int main()
{
    string s;
    int k, cnt = 0;
    cin >> s >> k;
    int lens = s.size();
    for (int i = 0; i < lens; i++)
    { 
        for (int j = 1; j <= k; j++)
        { 
            a[++cnt] = s.substr(i, j);
        }
    }
    sort(a, a + cnt);
    cnt = unique(a, a + cnt) - a - 1;
    cout << a[k];
    return 0;
}

D

直接用并查集维护。

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
// LUOGU_RID: 174637285
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, m, f[100001], a[100001], b[100001];
inline int find(int x)
{
    if (f[x] == x)
        return x;
    else
        return f[x] = find(f[x]);
}
signed main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        f[i] = b[a[i]] = i;
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        cin >> x >> y;
        f[find(x)] = find(y); 
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
        ans += (find(i) == find(b[i]));
    cout << ans;
    return 0;
}