【补题】18年多校1

2019-04-07

目录

Maximum Multiple

Description

Given an integer $n$, Chiaki would like to find three positive integers $x,\ y$ and $z$ such that: $n=x+y+z\ (1<n<10^6),\ x∣n,\ y∣n,\ z∣n$ and $xyz$ is maximum.

Solution

  1. $n<3$时，无解。

  2. $n|3$时，$max(xyz)=(n/3)^3$。

  3. $n|4$时，$max(xyz)=2(n/4)^3$。

  4. 其他时候，$x=y=z$显然不是解；不妨设$x<y$，可知$x\leq \frac{1}{5}n,\ y\leq\frac{1}{2}n$，显然也无解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <cstdio>

int main()
{
    int T;
    scanf("%d", &T);
    for (int tt = 1; tt <= T; tt++)
    {
        long long n;
        scanf("%lld", &n);
        if (n < 3)
            printf("-1\n");
        else if (n % 3 == 0)
            printf("%lld\n", n * n * n / 27);
        else if (n % 4 == 0)
            printf("%lld\n", n * n * n / 32);
        else
            printf("-1\n");
    }
    return 0;
}

Triangle Partition

Description

Chiaki has $3n,\ 1<n<1000$ points $p_1,\ p_2,\ …,\ p_{3n}$. It is guaranteed that no three points are collinear.

Chiaki would like to construct n disjoint triangles where each vertex comes from the $3n$ points.

Solution

贪心。按坐标从小到大排序，三个一组依次输出即可。

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
#include <cstdio>

const int maxn = 1000 + 1;
struct P
{
    int x, y, id;
    bool operator<(const P& b) const
    {
        if (x != b.x)
            return x < b.x;
        else
            return y < b.y;
    }
};
P a[3 * maxn];

int main()
{
    int T;
    scanf("%d", &T);
    for (int tt = 1; tt <= T; tt++)
    {
        int n;
        scanf("%d", &n);
        for (int i = 0; i < 3 * n; i++)
        {
            scanf("%d%d", &a[i].x, &a[i].y);
            a[i].id = i + 1;
        }
        sort(a, a + 3 * n);
        for (int i = 0; i < n; i++)
            printf("%d %d %d\n", a[3 * i].id, a[3 * i + 1].id, a[3 * i + 2].id);
    }
    return 0;
}

Time Zone

Description

Chiaki often participates in international competitive programming contests. The time zone becomes a big problem.

Given a time in Beijing time (UTC +8), Chiaki would like to know the time in another time zone s.

Solution

简单模拟。经由时间戳进行计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <cstdio>

int main()
{
    int T;
    scanf("%d", &T);
    for (int tt = 1; tt <= T; tt++)
    {
        int x, y;
        double z;
        scanf("%d%d UTC%lf", &x, &y, &z);
        int sum = (x - 8) * 60 + y;
        if (z > 0)
            sum += int((z * 10 + 0.1) * 6);
        else
            sum += int((z * 10 - 0.1) * 6);
        if (sum < 0)
            sum += 1440;
        sum %= 1440;
        printf("%02d:%02d\n", sum / 60, sum % 60);
    }
    return 0;
}

Balanced Sequence

Description

Chiaki has $n$ strings $s_1,\ s_2,\ \dots,\ s_n$ consisting of ‘(‘ and ‘)’. A string of this type is said to be balanced:

  • if it is the empty string
  • if A and B are balanced, AB is balanced,
  • if A is balanced, (A) is balanced.

Chiaki can reorder the strings and then concatenate them get a new string t. Let $f(t)$ be the length of the longest balanced subsequence (not necessary continuous) of t. Chiaki would like to know the maximum value of $f(t)$ for all possible t.

Solution

首先对每个串进行处理，消除匹配后的串为左侧若干个右括号（数量记为r）和右侧若干个左括号（数量记为l）组成。

为了使括号匹配尽可能多而排列所有串。显然应将所有$l-r > 0$的串放在所有$l-r < 0$的串左侧。
对于$l-r > 0$的串，从左至右依次放置时，显然未匹配的左括号数L不断增大；故为尽可能匹配，应该将r小的串排在前面。
同理，对于$l-r < 0$的串，应将l大的串放在前面。

依上述策略排序，然后再处理一次，得到最后剩下未匹配括号的数量。

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
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
const int MAXN = 100000 + 10;
char str[MAXN];
int cnt = 0;

struct Pair
{
    int id, l, r;
    int v;
    Pair(int id = 0, int l = 0, int r = 0) : id(id), l(l), r(r)
    {
        v = l - r;
    }
    bool operator<(const Pair &b) &
    {
        if (v >= 0 && b.v <= 0)
            return true;
        else if (v <= 0 && b.v >= 0)
            return false;
        else if (v > 0 && b.v > 0)
            return r < b.r;
        else if (v < 0 && b.v < 0)
            return l > b.l;
    }
}a[MAXN];

void analyse(char *s)
{
    int l = 0, r = 0;
    for ( ; *s; ++s)
    {
        if (*s == '(') //)
            l++;
        else if (l)
            l--;
        else
            r++;
    }
    a[cnt] = Pair(cnt, l, r);
    cnt++;
}

int solve(int n)
{
    sort(a, a + n);
    int L = 0, R = 0;
    for (int i = 0; i < n; i++)
    {
        if (L < a[i].r)
        {
            R += a[i].r - L;
            L = a[i].l;
        }
        else
        {
            L += a[i].v;
        }
    }
    return L + R;
}

int main()
{
    int T;
    scanf("%d", &T);
    for (int tt = 1; tt <= T; tt++)
    {
        cnt = 0;
        int n;
        scanf("%d%d", &n);
        int sum = 0;
        for (int i = 0; i < n; i++)
        {
            scanf("%s", str);
            sum += strlen(str);
            analyse(str);
        }
        printf("%d\n", sum - solve(n));
    }
    return 0;
}

Distinct Values

Description

Chiaki often participates in international competitive programming contests. The time zone becomes a big problem.

Given a time in Beijing time (UTC +8), Chiaki would like to know the time in another time zone s.

Solution

简。

Chiaki Sequence Revisited

Description

Chiaki is interested in an infinite sequence $a_1,\ a_2,\ a_3,\ …,$ which is defined as follows:

Chiaki would like to know the sum of the first n terms of the sequence, i.e. $\sum\limits_{i=1}^{n}a_i$. As this number may be very large, Chiaki is only interested in its remainder modulo (1e9+7).

Solution

通项难以通过化简得出，于是打表找规律。

观察发现数列从1开始递增，并且每个数字重复出现若干次数。不考虑$a_1$从第二项开始计数，则设数列$b_n$为数字n在$a_n$中出现的次数，不难得到 $b_{2^n}=n+1$，$b_{2^nk}=b_{2^n}=n+1$。

© 2019 blog - Powered by Hexo - Theme Chan