Forever丶CIL 首页文章列表标签分类
Codeforces Round#609(Div.2)
|算法

Codeforces Round #609 (Div. 2)

比赛链接

A - Equation

签到题

题意是给你一个整数，让你找两个比它大的合数，并且它们的差是这个整数。

数据范围 $1\le n\le10^7$

你输出的两个整数$a,b$均要满足 $1 \le a,b\le10^9$

那么先预处理出质数来，然后暴力枚举。 当然，因为合数太多，你不预处理质数也无妨，每次用 $sqrt(i)$的复杂度判断也可。

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
#include <bits/stdc++.h>

using namespace std;

const int Maxn = 20000000;
const int MaxE = 11000000;

bool Not_prime[Maxn + 10];
int prime[Maxn + 10];
int n, len = 0;

void Linear_sieve_prime() //线性筛素数
{
    Not_prime[1] = 0;
    for (int i = 2; i <= MaxE; i++)
    {
        if (Not_prime[i] == 0)
            prime[++len] = i;
        for (int j = 1; j <= len; j++)
        {
            if (prime[j] * i > MaxE)
                break;
            Not_prime[i * prime[j]] = 1;
            if (!(i % prime[j]))
                break;
        }
    }
}

void Solve()
{
    Linear_sieve_prime();

    scanf("%d", &n);
    for (int i = n + 1; i <= Maxn; i++)
    {
        //printf("%d %d\n",Not_prime[9],Not_prime[8]);
        if (Not_prime[i - n] && Not_prime[i]) //暴力枚举
        {
            printf("%d %d\n", i, i - n);
            break;
        }
    }
}
int main()
{
    Solve();

    return 0;
}

B - Modulo Equality

给你一个初始集合，和一个目标集合，你要给初始集合中的每一个数加$x$，再让初始集合中的数都模$m$，让初始集合和目标集合相等。求最小的$x$。

$1≤n≤2000,1≤m≤109$

也挺简单的，你想想，假设我们不模$m$，那么是不是初始集合中小的对应目标集合中的小的，初始集合中的大的对应目标集合中的大的，因为同时加一个相同的数嘛，大小关系不变。

其实模$m$之后还是一样的做法，举个例子，初始集合是$\{1,2,3\}$ 目标集合是$\{0,1,2\}$ ，模$m=4$。它加了$x$之后，要么是$1\rightarrow0,2\rightarrow1,3\rightarrow2$ ,要么是$1\rightarrow1,2\rightarrow2,3\rightarrow0$，要么是$1\rightarrow2,2\rightarrow0,3\rightarrow1$，你看它都是顺着来的，他就不可能$1\rightarrow2,3\rightarrow0$去，我这都是排好序的了，所以我们只需要从上面三种情况中找一个$x$最小的就好啦

那么详细过程就是，先分别排序，然后把第一个集合延长一倍，类似于破环为链，然后每种情况只需要看一下第一个数对应过去$x$是多少就好啦。

再举个例子：

0 0 1 2 0 0 1
0 0 1 2
0 0 1 2
0 0 1 2
0 0 1 2

就这个样子对应就好啦

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
#include <bits/stdc++.h>

using namespace std;

const int Maxn = 6000;
const int Inf = 0x3f3f3f3f;

int n, m;
int A[Maxn], B[Maxn];
int ans = Inf;

inline int cmp(int a, int b) { return a < b; }

void Solve()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &A[i]);
    for (int i = 1; i <= n; i++)
        scanf("%d", &B[i]);

    sort(A + 1, A + 1 + n, cmp);
    sort(B + 1, B + 1 + n, cmp);

    for (int i = n + 1; i <= 2 * n; i++)
        A[i] = A[i - n];
    for (int i = 1; i <= n; i++)
        for (int i = 1; i <= n; i++)
        {
            int Add = 0, flag = 0;
            if (B[1] >= A[i])
                Add = B[1] - A[i];
            else
                Add = m - A[i] + B[1];
            //printf("<%d %d>\n",i,Add);

            for (int j = i + 1; j <= n + i - 1; j++)
            {
                if ((A[j] + Add) % m != B[j - i + 1])
                {
                    flag = 1;
                    break;
                }
            }

            if (!flag)
                ans = min(ans, Add);
        }

    printf("%d\n", ans);
}
int main()
{
    Solve();

    return 0;
}

C - Long Beautiful Integer

这个题先定义了一个$beautiful$数，啥是$beautiful$数啊，就是给你一个$k$，这个数如果满足第$i$位和第$i+k$位相同，那它就是$beautiful$数。

现在给你一个$n$位的数，和$k$，问比这个数大的最小的$beautiful$数是啥。

$2 \le n \le 200000,1 \le k\le n$

你看这个数据范围，那肯定得构造一个数出来啊，首先我们得知道，这个数字啊，他有一个性质，假设$a$的第i位比$b$的第i位大，然后他俩前$i-1$位都一样，那甭管后面是多少了，反正$a$比$b$大就对了。

所以我们只要把前$k$位构造好，就$ok$了

前$k$位咋构造？为了保证是比原数大的最小的数，那么能和原数一样咱就让他们一样,用$s$数组存那个$n$位数，咱再搞个$A$数组，前$k$位和$s$一样，然后后面的就按照$A[i]=A[i-k]$的方式赋上初始值，然后咱比较一下$A$和$s$谁大，要是$A$大，那咱就求完了，要是$s$大，那咱就给$A$的第k位加$1$，这就提到我前面说的那个数的性质，你这里加个$1$，肯定比$s$大了，当然要注意，可能要进位，这个考虑到就可以了。

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
#include <bits/stdc++.h>

using namespace std;

const int Maxn = 3000000;

int n, k;
char s[Maxn];
char A[Maxn];

void Solve()
{
    scanf("%d%d", &n, &k);
    scanf("%s", s + 1);
    for (int i = 1; i <= k; i++)
        A[i] = s[i];
    for (int i = k + 1; i <= n; i++)
        A[i] = A[i - k];

    if (strcmp(s + 1, A + 1) > 0)
    {
        int p = k;
        if (A[p] <= '8')
            A[p]++;
        else if (A[p] == '9')
        {
            A[p] = '0';
            for (int i = p - 1; i >= 1; i--)
            {
                if (A[i] <= '8')
                {
                    A[i]++;
                    break;
                }
                else
                    A[i] = '0';
            }
        }
        
        for (int i = k + 1; i <= n; i++)
            A[i] = A[i - k];
    }

    cout << strlen(A + 1) << endl
         << (A + 1) << endl;
}
int main()
{
    Solve();

    return 0;
}

D - Domino for Young

这个题挺巧妙的啊，给你一个底是平的，高大于等于$1$的棋盘，让你放$1×2$或者$2×1$的多米诺骨牌，问你最多可以放几个？

就这个样子的：

做法特别简单，两步，第一步：涂色，第二步：数，做完了。

涂色：

注意看啊，黑白相间的，就国际象棋棋盘啥样你就照着那个涂。

数：

数数黑的多还是白的多，哪个少输出哪个。

解释：甭管你是$1×2$还是$2×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
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

inline int read()
{
    int fl = 1, rt = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            fl = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        rt = rt * 10 + ch - '0';
        ch = getchar();
    }
    return fl * rt;
}

void Solve()
{
    ll w = 0ll, b = 0ll;
    int n, a, si = 1;

    n = read();

    for (int i = 1; i <= n; i++) //边涂色边数格子
    {
        a = read();

        if (si)
        {
            if (a % 2)
                w += (ll)(a / 2 + 1), b += (ll)(a / 2);
            else
                w += (ll)(a / 2), b += (ll)(a / 2);
        }
        else
        {
            if (!(a % 2))
                w += (ll)(a / 2), b += (ll)(a / 2);
            else
                w += (ll)(a / 2), b += (ll)(a / 2 + 1);
        }

        si ^= 1;
    }

    printf("%lld\n", min(w, b));
}

int main()
{
    Solve();

    return 0;
}

E - K Integers

这个题就是给你一个n的排列，每次你可以交换两个数，让你把$f(1),f(2),f(3)…f(n)$输出出来，$f(i)$代表通过两两交换弄出$1234…i$需要的最小交换次数。

$1\le n \le 10^5$

这个题还是有点难度的。

假设它不让你求那么多，他就只让你求$f(n)$，那这个题就贼水了，直接归并排序或者树状数组求个逆序对就行了。

但其实他让你求$f(1) f(2)… f(n)$，也是用一样的方法，逆序对就用树状数组啦，关键要处理的就是不连续的情况。

你看看：

$1XXXX2X3X4$

$X$代表其他数，这里$1234$已经是顺序了，我们主要研究$X$如何处理，对于一个$X$我们要么把他搞到最左边，要么把他搞到最右边，对吧，他要交换几次才可以到最左或者最右，要看他左边有几个要被换过来的数呗，那么为了交换次数最少，肯定是把数聚集到中位数左右，也就是变成：

$XXXX1234XX$

这样我们一共交换了几次？$7$次。

看一下怎么算的：

$1\,XX\,2\,X\,3\,XX\,4$

如果我们要把$123$都移到$4$的紧左边。
实际上答案就是$\sum_{}($目标位置$-$初始位置$)$。

因为最后要变成 $XXXXX1\,2\,3\,4\,$

这样$1$移动了$5$位，$2$移动了$3$位，$3$移动了$2$位，一共$10$步

为了好算，我们可以表示成$1,2,3$均移动到$4$上，再$-1-2-3$，这样我们的算式就可以表示成：

$(9\times4-1-4-6)-1-2-3$

那么问题来了，这个$9\times4$用求逆序对的树状数组就可求出来，$-1-2-3$也不过是等差数列求和罢了，那个$-1-4-6$咋办？

答案是再开一个树状数组，每次把位置插入进去不就完了。$OK$

这是把左边的靠过来的计算方法，右边同理就好了。

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
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MaxT = 800000;
const int Maxn = 201000;

int n;
int Pos[Maxn];
ll T1[MaxT + 10];
ll T2[MaxT + 10];

int read()
{
    int fl = 1, rt = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            fl = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        rt = rt * 10 + ch - '0';
        ch = getchar();
    }
    return fl * rt;
}

void Insert(ll *T, int x, ll y) //树状数组的插入操作
{
    while (x <= MaxT)
        T[x] += y, x += x & (-x);
}
ll Search(ll *T, int x) //查询操作
{
    ll ret = 0;
    while (x > 0)
        ret += T[x], x -= x & (-x);
    return ret;
}

void Solve()
{
    n = read();
    int a;

    for (int i = 1; i <= n; i++)
        a = read(), Pos[a] = i;

    ll ans1 = 0ll, ans2 = 0ll;

    for (int i = 1; i <= n; i++)
    {
        ans1 += i - 1 - Search(T1, Pos[i]); //求逆序对

        Insert(T1, Pos[i], 1ll);
        Insert(T2, Pos[i], (ll)Pos[i]);

        int l = 1, r = n, mid = (l + r) >> 1; //求中点
        while (l <= r)
        {
            mid = (l + r) >> 1;
            if ((Search(T1, mid) << 1) <= i)
                l = mid + 1;
            else
                r = mid - 1;
        }
        ans2 = 0;

        //左边
        ll cnt = (ll)Search(T1, mid), sum = (ll)Search(T2, mid);
        ans2 += mid * cnt - sum - cnt * (cnt - 1ll) / 2ll;

        //右边
        cnt = i - cnt, sum = Search(T2, n) - sum;
        ans2 += sum - cnt * (ll)(mid + 1ll) - cnt * (cnt - 1ll) / 2ll;

        printf("%lld ", ans1 + ans2);
    }
}
int main()
{
    Solve();

    return 0;
}
文章作者: FcAYH
文章链接: http://www.fcayh.cn/2021/04/03/cf-609div2/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Forever丶CIL！
codeforces枚举构造数论-数学树状数组