Blog of RuSun

\begin {array}{c} \mathfrak {One Problem Is Difficult} \\\\ \mathfrak {Because You Don't Know} \\\\ \mathfrak {Why It Is Diffucult} \end {array}

ARC134

发表于 分类于
本文字数： 5.6k 阅读时长 ≈ 5 分钟
标签：        

ARC134

A - Bridge and Sheets

按照题意直接做即可。

查看代码 
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
#include <cstdio>
using namespace std;
typedef long long LL;
template <class Type>
void read(Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + c - '0';
    flag && (x = ~x + 1);
}
template <class Type>
void write(Type x)
{
    x < 0 && (putchar('-'), x = ~x + 1);
    x > 9 && (write(x / 10), 0);
    putchar(x % 10 + '0');
}
const int N = 1e5 + 10;
int n;
LL l, w, a[N];
LL get(LL x)
{
    return x / w + (x % w > 0);
}
int main()
{
    read(n), read(l), read(w);
    for (int i = 0; i < n; i++)
        read(a[i]);
    a[n] = l;
    LL res = 0, t = 0;
    for (int i = 0; i <= n; i++)
    {
        if (a[i] > t)
            res += get(a[i] - t);
        t = a[i] + w;
    }
    write(res);
    return 0;
}

B - Reserve or Reverse

题意即有一个字符串，有两个指针，在最左侧和最右侧，每次交换两个指针对应的字符，并将指针向中间移动，使得字典序最小。

使得字典序最小，需要将小的字母尽量向前移动。考虑从小到大枚举每个字符，在左侧找到第一个比其大的位置，右侧找到第一个可以换的位置，交换即可。

查看代码 
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
#include <cstdio>
#include <algorithm>
using namespace std;
template <class Type>
void read(Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + c - '0';
    flag && (x = ~x + 1);
}
template <class Type>
void write(Type x)
{
    x < 0 && (putchar('-'), x = ~x + 1);
    x > 9 && (write(x / 10), 0);
    putchar(x % 10 + '0');
}
const int N = 2e5 + 10;
int n;
char str[N];
int main()
{
    read(n);
    scanf("%s", str + 1);
    int l = 1, r = n;
    for (char c = 'a'; c <= 'z'; c++)
    {
        while (l < r)
        {
            while (l <= r && str[l] <= c)
                l++;
            int t = -1;
            for (int i = r; i > l && t == -1; i--)
                str[i] == c && (t = i);
            if (~t)
            {
                swap(str[l], str[t]);
                r = t - 1, l++;
            }
            else
                break;
        }
    }
    printf("%s", str + 1);
    return 0;
}

C - The Majority

有 $k$ 个盒子， $n$ 个球，求有多少个方案使得对于每个盒子中 $1$ 号球的数量大于其他所有球的数量和。

先将所有的盒子中先放一个 $1$ 号球，以后放其他球的时候同时放一个 $1$ 号球（相当于将每个球上都捆一个 $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
#include <cstdio>
using namespace std;
typedef long long LL;
template <class Type>
void read(Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + c - '0';
    flag && (x = ~x + 1);
}
template <class Type>
void write(Type x)
{
    x < 0 && (putchar('-'), x = ~x + 1);
    x > 9 && (write(x / 10), 0);
    putchar(x % 10 + '0');
}
const int N = 1e5 + 10, mod = 998244353;
int n, m, s;
int binpow(int b, int k)
{
    int res = 1;
    while (k)
    {
        if (k & 1)
            res = (LL)res * b % mod;
        b = (LL)b * b % mod;
        k >>= 1;
    }
    return res;
}
int C(int a, int b)
{
    if (a < b)
        return 0;
    int res = 1, inv = 1;
    for (int i = a; i > a - b; i--)
        res = (LL)res * i % mod;
    for (int i = b; i; i--)
        inv = (LL)inv * i % mod;
    return (LL)res * binpow(inv, mod - 2) % mod;
}
int lucas(int a, int b)
{
    if (!a || !b)
        return 1;
    return (LL)C(a % mod, b % mod) * lucas(a / mod, b / mod) % mod;
}
int main()
{
    read(n), read(m), read(s);
    s -= m;
    int res = 1;
    for (int i = 1, a; i < n; i++)
    {
        read(a);
        s -= a;
        if (s < 0)
        {
            puts("0");
            return 0;
        }
        res = (LL)res * lucas(a + m - 1, m - 1) % mod;
    }
    res = (LL)res * lucas(s + m - 1, m - 1) % mod;
    write(res);
    return 0;
}

D - Concatenate Subsequences

不会做，翻译一下官方题解。

令 $A=(a_1,a_2, \ldots,a_N), B=(a_{N + 1}, \ldots, a_{2N})$。 另外，设 $\mathrm{X}$ 为 $\min(A)$。如果存在 $i$ 使得 $A_i=\mathrm{X}, A_i \geq B_i$，则选择具有最小 $B_i$ 的此类 $i$ 会产生字典上最小的可能序列。下面，我们假设 $A_i \leq B_i$ 当 $A_i = \mathrm{X}$。然后，可以证明在最优解中选择了所有满足 $A_i = \mathrm{X}$ 的 $i$（否则，得到的序列在字典上显然会更大）。令 $y=(y_1, y_2, \ldots, y_K)$ 是 $i$ 的列表，使得 $A_i = \mathrm{X}$ 排序按升序排列。让我们考虑 $j$ 的最优选择，使得 $y_K < j \leq N, A_j \leq B_{c_1}$ 。让我们在将它们按 $(A_j,j)$ 升序排序后处理这些 $j$。那么，对于这样的元素，$A_j < B_{y_1}$，可以证明，如果 $j$ 大于 $y$ 的当前最后一个元素，则最优策略是添加 $j$（否则，结果将在字典上更大）。最后要考虑的是是否选择 $j$ 使得 $A_j = B_{y_1}$ 。可以显示以下内容：如果添加一个这样的 $j$ 会使结果在字典上更小，则应尽可能多地选择它们。否则，不应选择其中任何一个。可以实现上述以在 $O(N)$ 时间内找到答案，但是 $O(N \log N)$ 算法也运行得足够快。

相关文章