ABC215

Posted on In Views:
Symbols count in article: 9.2k
题目 A B C D E F G H
通过情况 AC AC AC AC O O O X

A - Your First Judge

题面

输入字符串S，判断是否为”Hello,World!”

解法

略

代码

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
/*
 * @题目: A - Your First Judge
 * @算法: 
 * @Author: Blore
 * @Language: c++11
 * @Date: 2021-08-21 20:00:54
 * @LastEditors: Blore
 * @LastEditTime: 2021-08-21 20:01:35
 */
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define maxn 200010
#define maxm 200010
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, r, l) for (int i = r; i >= l; i--)
#define ll long long
using namespace std;
const int inf = 0x7fffffff;
int read()
{
    int p = 0, f = 1;
    char c = getchar();
    while (c < 48 || c > 57)
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= 48 && c <= 57)
        p = (p << 1) + (p << 3) + (c ^ 48), c = getchar();
    return p * f;
}
string in;
int main()
{
    cin >> in;
    if (in == "Hello,World!")
        puts("AC");
    else
        puts("WA");
    return 0;
}

B - log2(N)

题面

找到最大的$k$,使得$2^k\leqslant N$

解法

注意使用$log2()$函数会出现精度误差导致WA

代码

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
/*
 * @题目: B - log2(N)
 * @算法: 
 * @Author: Blore
 * @Language: c++11
 * @Date: 2021-08-21 20:02:12
 * @LastEditors: Blore
 * @LastEditTime: 2021-08-21 20:05:33
 */
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define maxn 200010
#define maxm 200010
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, r, l) for (int i = r; i >= l; i--)
#define ll long long
using namespace std;
const int inf = 0x7fffffff;
ll read()
{
    ll p = 0, f = 1;
    char c = getchar();
    while (c < 48 || c > 57)
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= 48 && c <= 57)
        p = (p << 1) + (p << 3) + (c ^ 48), c = getchar();
    return p * f;
}
int main()
{
    ll tmp = read();
    ll ans = 1;
    int cnt = 0;
    while (ans <= tmp)
    {
        ans *= 2;
        cnt++;
    }
    cout << cnt - 1;
    return 0;
}

C - One More aab aba baa

题面

给定字符集$S$，找到第k个排列

解法

本人使用的是next_permutation函数
官方题解另一种做法是枚举所有可能并排序去重

代码

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
/*
 * @题目: C - One More aab aba baa
 * @算法: 全排列问题
 * @Author: Blore
 * @Language: c++11
 * @Date: 2021-08-21 20:21:14
 * @LastEditors: Blore
 * @LastEditTime: 2021-08-21 20:26:00
 */
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define maxn 200010
#define maxm 200010
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, r, l) for (int i = r; i >= l; i--)
#define ll long long
using namespace std;
const int inf = 0x7fffffff;
int read()
{
    int p = 0, f = 1;
    char c = getchar();
    while (c < 48 || c > 57)
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= 48 && c <= 57)
        p = (p << 1) + (p << 3) + (c ^ 48), c = getchar();
    return p * f;
}
char tmp[10];

int main()
{
    cin >> tmp;
    int n = strlen(tmp), m = read();
    sort(tmp, tmp + n);
    int cnt = 0;

    do
    {
        cnt++;
        if (cnt == m)
            break;
    } while (next_permutation(tmp, tmp + n));
    cout << tmp;
    return 0;
}

D - Coprime 2

题面

给定含$N$个正整数的数组A，枚举所有$k(1 \le k \le M)$使得$\gcd(A_i,k)=1,1 \le i \le N$

解法

筛掉$A_i$中所有不为1的因子及其倍数，剩下的为答案

代码

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
/*
 * @题目: D - Coprime 2
 * @算法: 
 * @Author: Blore
 * @Language: c++11
 * @Date: 2021-08-21 20:12:21
 * @LastEditors: Blore
 * @LastEditTime: 2021-08-21 20:19:01
 */
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define maxn 200010
#define maxm 200010
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, r, l) for (int i = r; i >= l; i--)
#define ll long long
using namespace std;
const int inf = 0x7fffffff;
int read()
{
    int p = 0, f = 1;
    char c = getchar();
    while (c < 48 || c > 57)
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= 48 && c <= 57)
        p = (p << 1) + (p << 3) + (c ^ 48), c = getchar();
    return p * f;
}
bool vis[maxn];
void tag(int x)
{
    for (int i = 2; i * i <= x; i++)
    {
        if (x % i != 0)
            continue;
        while (x % i == 0)
            x /= i;
        vis[i] = 1;
    }
    vis[x] = 1;
}
int ans[maxn], p;
int main()
{
    int n = read(), m = read(), tmp;
    rep(i, 1, n) tmp = read(), tag(tmp);
    rep(i, 2, m)
    {
        if (vis[i])
        {
            for (int j = 1; j * i <= m; j++)
                vis[j * i] = 1;
        }
    }
    vis[1] = 0;
    rep(i, 1, m)
    {
        if (!vis[i])
            ans[++p] = i;
    }
    printf("%d\n", p);
    rep(i, 1, p) printf("%d\n", ans[i]);
    return 0;
}

E - Chain Contestant

题面

给定字符串$S$(由大写字母A-J组成)，询问满足相同的字母之间没有其他字母不同的子序列数(包括字母位置不同)

解法

考虑$dp\left[ i \right] \left[ U \right] \left[ j \right] $其中$i$为当前在串中位置，$U$为已用到的字符类型（使用二进制表示），$j$为结尾的字母。
假设当前字符为$x$，则状态转移方程如下:
①考虑前后相同的$U$，直接继承前面的方案数($dp[i][u][j] = dp[i - 1][u][j]$)（此时为不选择$x$结尾），同时如果j与$x$相同，则多继承一倍（即选择$x$结尾)V
②考虑前一位不含$x$的$V$,则此时状态转移方程为$dp[i][V’][x]=\sum{dp[i-1][V][j]}$，其中$V’$为相对于$V$仅多了$x$的情形
③只含$x$且结尾为$x$的方案$+1$
（第一维可以滚动）

代码

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
/*
 * @题目: E - Chain Contestant
 * @算法: 线性+状压DP
 * @Author: Blore
 * @Language: c++11
 * @Date: 2021-08-21 20:41:50
 * @LastEditors: Blore
 * @LastEditTime: 2021-08-21 23:22:37
 */
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define maxn 1024
#define maxm 200010
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, r, l) for (int i = r; i >= l; i--)
#define ll long long
using namespace std;
const int inf = 0x7fffffff;
int read()
{
    int p = 0, f = 1;
    char c = getchar();
    while (c < 48 || c > 57)
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= 48 && c <= 57)
        p = (p << 1) + (p << 3) + (c ^ 48), c = getchar();
    return p * f;
}
ll dp[maxn][maxn][10];
char s[maxn];
const int mod = 998244353;
int main()
{
    int n = read();
    scanf("%s", s + 1);
    rep(i, 1, n)
    {
        int x = s[i] - 'A';
        rep(u, 0, 1023)
        {
            rep(j, 0, 9)
            {
                dp[i][u][j] = dp[i - 1][u][j];
                if (j == x)
                {
                    dp[i][u][j] += dp[i - 1][u][j];
                    dp[i][u][j] %= mod;
                }
            }
        }
        rep(v, 0, 1023)
        {
            if (v & (1 << x))
                continue;
            rep(j, 0, 9)
            {
                dp[i][v | (1 << x)][x] += dp[i][v][j];
                dp[i][v | (1 << x)][x] %= mod;
            }
        }
        dp[i][(1 << x)][x]++;
    }
    ll ans = 0;
    rep(u, 0, 1023)
        rep(j, 0, 9)
            ans = (ans + dp[n][u][j]) % mod;
    printf("%lld", ans);
    return 0;
}

F - Dist Max 2

题面

给定$n$个不同的点对，定义点$i$和点$j$的距离为$\mathrm{min} (|x_i-x_j|,|y_i-y_j|)$，找到两个不同点之间距离的最大值

解法

对原数组排序后对答案二分
使用滑动窗口确定某值是否为可行解（保证$x$可行的情况下找到之前$y$的最大值和最小值，再进行判断）

代码

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
/*
 * @题目: F - Dist Max 2
 * @算法: 二分
 * @Author: Blore
 * @Language: c++11
 * @Date: 2021-08-22 16:11:38
 * @LastEditors: Blore
 * @LastEditTime: 2021-08-22 16:23:43
 */
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define maxn 200010
#define maxm 200010
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, r, l) for (int i = r; i >= l; i--)
#define ll long long
using namespace std;
const int inf = 1e9 + 1;
int read()
{
    int p = 0, f = 1;
    char c = getchar();
    while (c < 48 || c > 57)
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= 48 && c <= 57)
        p = (p << 1) + (p << 3) + (c ^ 48), c = getchar();
    return p * f;
}
vector<pair<int, int>> a;
bool check(int k)
{
    queue<pair<int, int>> q;
    int mi = inf, ma = 0;
    for (int i = 0; i < a.size(); i++)
    {
        while (!q.empty())
        {
            if (q.front().first > a[i].first - k)
                break;
            mi = min(mi, q.front().second), ma = max(ma, q.front().second);
            q.pop();
        }
        if (mi <= a[i].second - k || ma >= a[i].second + k)
            return 1;
        q.push(a[i]);
    }
    return 0;
}
int main()
{
    int n = read();
    rep(i, 1, n)
    {
        int x = read(), y = read();
        a.pb(mp(x, y));
    }
    sort(a.begin(), a.end());
    int l = 0, r = inf;
    while (r - l > 1)
    {
        int m = (l + r) >> 1;
        if (check(m))
            l = m;
        else
            r = m;
    }
    printf("%d", l);
    return 0;
}

G - Colorful Candies 2

题面

给定$n$个数（颜色），依次输出从中随机选择$1~n$个数后不同颜色数的期望。
答案对$998244353$取模

解法

考虑选择$k$个数的情况，推导可知我们所要求的答案为每一种颜色的被选择的概率之和。
则答案为$\sum_{i=1}^C \lbrace \binom{N}{K} - \binom{N-n_i}{K} \rbrace / \binom{N}{K}$，$n_i$为同种颜色的个数
此时时间复杂度为$O(n^2)$
不难发现我们可以通过合并相同的$n_i$加速$\sum_{i=1}^C \lbrace \binom{N}{K} - \binom{N-n_i}{K} \rbrace$的计算
时间复杂度$O(n\sqrt{n})$，满足时间复杂度

代码

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
/*
 * @题目: G - Colorful Candies 2
 * @算法: 组合数学、概率
 * @Author: Blore
 * @Language: c++11
 * @Date: 2021-08-23 21:16:49
 * @LastEditors: Blore
 * @LastEditTime: 2021-08-23 21:43:24
 */
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define maxn 100010
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, r, l) for (int i = r; i >= l; i--)
#define ll long long
using namespace std;
const int inf = 0x7fffffff;
int read()
{
    int p = 0, f = 1;
    char c = getchar();
    while (c < 48 || c > 57)
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= 48 && c <= 57)
        p = (p << 1) + (p << 3) + (c ^ 48), c = getchar();
    return p * f;
}
const int mod = 998244353;
ll F[maxn], rF[maxn];
ll inv(ll a, ll m)
{
    if (a == 1)
        return 1;
    return inv(m % a, m) * (m - m / a) % m;
}
void init()
{
    F[0] = rF[0] = 1;
    rep(i, 1, maxn - 1)
    {
        F[i] = F[i - 1] * i % mod;
        rF[i] = rF[i - 1] * inv(i, mod) % mod;
    }
}
ll nCm(int n, int m)
{
    if (n < m || m < 0)
        return 0;
    return F[n] * rF[m] % mod * rF[n - m] % mod;
}
map<int, int> cnum, cnumnum;
int main()
{
    init();
    int n = read();
    rep(i, 1, n)
    {
        int x = read();
        cnum[x]++;
    }
    for (map<int, int>::iterator it = cnum.begin(); it != cnum.end(); it++)
    {
        cnumnum[it->second]++;
    }
    rep(i, 1, n)
    {
        int k = i;
        ll ans = 0;
        for (map<int, int>::iterator it = cnumnum.begin(); it != cnumnum.end(); it++)
        {
            ans += (nCm(n, k) - nCm(n - it->first, k) + mod) * it->second % mod;
            ans %= mod;
        }
        ans = ans * inv(nCm(n, k), mod);
        printf("%lld\n", ans % mod);
    }
    return 0;
}