Atcoder Beginner Contest 235

By xiaruize 2022年1月20日

A - Rotate

Method

显而易见，ans=111(a+b+c)显而易见，ans=111(a+b+c)

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define MOD 1000000007
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define ll long long
#define fir first
#define sz(a) int((a).size())
#define double long double
#define INF 0x3f3f3f3f
#define debug(c, x) cerr << c << ':' << x << endl;
const int N = 1e5 + 10;

// bool st;

// bool en;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    int x;
    cin >> x;
    int a = x / 100;
    int b = x / 10 % 10;
    int c = x % 10;
    cout << 111 * (a + b + c) << endl;
    return 0;
}

B - Climbing Takahashi

Method

暴力出奇迹

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
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define MOD 1000000007
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define ll long long
#define fir first
#define sz(a) int((a).size())
#define double long double
#define INF 0x3f3f3f3f
#define debug(c, x) cerr << c << ':' << x << endl;
const int N = 1e5 + 10;

// bool st;
int n;
int a[N];
// bool en;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++)
    {
        if (a[i] <= a[i - 1])
        {
            cout << a[i - 1] << endl;
            return 0;
        }
    }
    cout << a[n] << endl;
    return 0;
}

C - The Kth Time Query

###Method

由0≤ai≤109→0 \leq a_i \leq 10^9 \rightarrow 离散化 ∵1≤N≤2×105∴\because 1\leq N\leq 2\times10^5 \therefore 空间不会炸

用gi,jg_{i,j}记录离散化后的数ii的第jj次出现的位置

时间复杂度 O(nlogn)O(nlogn)

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
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define MOD 1000000007
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define ll long long
#define fir first
#define sz(a) int((a).size())
#define double long double
#define INF 0x3f3f3f3f
#define debug(c, x) cerr << c << ':' << x << endl;
const int N = 2e5 + 10;

// bool st;
map<int, int> mp;
int n, q;
int a[N];
int cnt = 1;
vector<int> g[N];
// bool en;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        if (!mp[a[i]])
            mp[a[i]] = cnt++;
        g[mp[a[i]]].pb(i);
    }
    for (int i = 1; i <= q; i++)
    {
        int x, k;
        cin >> x >> k;
        if (mp[x] == 0 || g[mp[x]].size() < k)
            cout << "-1" << endl;
        else
            cout << g[mp[x]][k - 1] << endl;
    }
    return 0;
}

D - Multiply and Rotate

Method

暴力出奇迹

反向进行dfsdfs，由nn向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
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
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define MOD 1000000007
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define ll long long
#define fir first
#define sz(a) int((a).size())
#define double long double
#define INF 0x3f3f3f3f
#define debug(c, x) cerr << c << ':' << x << endl;
const int N = 1e5 + 10;

// bool st;
int a, n, now = 1;
int ans = INF;
int cnt = 0;
map<int, bool> mp;
// bool en;

int cd(int x)
{
    int cnt = 0;
    while (x)
    {
        cnt++;
        x /= 10;
    }
    return cnt;
}

int p(int a, int b)
{
    int res = 1;
    for (int i = 1; i <= b; i++)
        res *= a;
    return res;
}

void dfs(int x, int cnt)
{
    // cerr << x << endl;
    if (mp[x])
        return;
    mp[x] = true;
    if (x < 1)
        return;
    if (x == 1)
    {
        ans = min(ans, cnt);
        return;
    }
    if (x % a == 0)
        dfs(x / a, cnt + 1);
    if (x / 10 != 0)
        dfs(x / p(10, cd(x) - 1) + (x % p(10, cd(x) - 1)) * 10, cnt + 1);
    return;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    cin >> a >> n;
    dfs(n, 0);
    if (ans == INF)
        cout << "-1" << endl;
    else
        cout << ans << endl;
    return 0;
}

E - MST + 1

Method

What is minimum spanning tree and Kruskal?

image

由于题目查询为离线查询，所以可以考虑将要查询的边提前全部插入图中

做Kruskal算法

1.当前边为要查询的边时，只检查，不操作

2.当前边为原图的边时正常操作

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
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define MOD 1000000007
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define ll long long
#define fir first
#define sz(a) int((a).size())
#define double long double
#define INF 0x3f3f3f3f
#define debug(c, x) cerr << c << ':' << x << endl;
const int N = 4e5 + 10;

// bool st;
int n, m, q;
struct edge
{
    int u, v, w;
    int isq = 0;
} s[N];
int fa[N];
bool ans[N];
// bool en;

int get(int x)
{
    if (fa[x] == x)
        return x;
    return fa[x] = get(fa[x]);
}

void merge(int x, int y)
{
    fa[get(x)] = get(y);
}

bool cmp(edge a, edge b)
{
    return a.w < b.w;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    cin >> n >> m >> q;
    for (int i = 1; i <= n; i++)
        fa[i] = i;
    for (int i = 1; i <= m; i++)
    {
        cin >> s[i].u >> s[i].v >> s[i].w;
    }
    for (int i = 1; i <= q; i++)
    {
        cin >> s[i + m].u >> s[i + m].v >> s[i + m].w;
        s[i + m].isq = i;
    }
    sort(s + 1, s + 1 + m + q, cmp);
    for (int i = 1; i <= m + q; i++)
    {
        if (get(s[i].u) != get(s[i].v))
        {
            if (s[i].isq)
                ans[s[i].isq] = true;
            else
                merge(s[i].u, s[i].v);
        }
    }
    for (int i = 1; i <= q; i++)
        if (ans[i])
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    return 0;
}

F - Variety of Digits

Method

状压数位dp

dpi,j,0dp_{i,j,0}表示到第ii位，已有的数为jj，有多少种可能。

j=(a1a2...an)2j=(a_1a_2...a_n)_2其中每个二进制位aia_i表示题目要求的数字cic_i是否存在

dpi,j,1dp_{i,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
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
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define MOD 998244353
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define ll long long
#define fir first
#define sz(a) int((a).size())
#define double long double
#define INF 0x3f3f3f3f
#define debug(c, x) cerr << c << ':' << x << endl;
const int N = 1e5 + 10;

// bool st;
int dp[10005][2005][2];
string s;
int a[15];
int m, msk, now;
// bool en;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    cin >> s >> m;
    int n = s.size();
    for (int i = 0; i < s.size(); i++)
        s[i] -= '0';
    for (int i = 1; i <= m; i++)
        cin >> a[i];
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < 1024; j++)
        {
            for (int k = 0; k < 10; k++)
            {
                dp[i + 1][j | (1 << k)][0] += dp[i][j][0];
                dp[i + 1][j | (1 << k)][1] += dp[i][j][1] * 10 + dp[i][j][0] * k;
            }
        }
        if (i != 0)
        {
            for (int j = 1; j < 10; j++)
            {
                dp[i + 1][1 << j][0]++;
                dp[i + 1][1 << j][1] += j;
            }
        }
        for (int j = 0; j < s[i]; j++)
        {
            if (i || j)
            {
                dp[i + 1][msk | 1 << j][0]++;
                dp[i + 1][msk | 1 << j][1] += now * 10 + j;
            }
        }
        for (int j = 0; j < 1024; j++)
        {
            dp[i + 1][j][0] %= MOD;
            dp[i + 1][j][1] %= MOD;
        }
        msk |= 1 << s[i];
        now = (now * 10 + s[i]) % MOD;
    }
    int p = 0;
    for (int i = 1; i <= m; i++)
        p |= 1 << a[i];
    int ans = 0;
    for (int i = 0; i < 1024; i++)
        if ((i & p) == p)
        {
            ans += dp[n][i][1];
            ans %= MOD;
        }
    if ((msk & p) == p)
    {
        ans += now;
        ans %= MOD;
    }
    cout << ans << endl;
    return 0;
}