Codeforces Round #813 (Div. 2) A~C

Codeforces Round #813 (Div. 2)

A. Wonderful Permutation

题目大意

给出一串排列，问通过几次交换数字可以使前 k 个数字之和最小。排列中每个数字只出现一次

题目分析

前 k 个数字最小则使前 k 个数字为 1~k 即可，出现一个大于 k 的数字即需要交换一次。

code

#include

using namespace std;

const int N = 110;

int n, m, k, t;

struct node
{
    int l, r;
}q[N];

void solve()
{
    int a[N] = {0};
    cin >> n >> k;

    for(int i = 1; i <= n; i ++)
    {
        cin >> a[i];
    }

    int cnt = 0;
    for(int i = 1; i <= k; i++)
        if(a[i] > k)cnt ++;
    cout << cnt << "\n";
}

int main()
{
    cin >> t;
    while(t --) solve();
    return 0;
}
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

B. Woeful Permutation

题目大意

求出满足 lcm(1,p1)+lcm(2,p2)+…+lcm(n,pn)lcm⁡(1,p1)+lcm⁡(2,p2)+…+lcm⁡(n,pn)最小的含 n 个数字的排列。排列中每个数字只出现一次。（lcm为最大公约数）

题目分析

有序排列中，相邻两个数互质，最小公倍数为它们的乘积。交换相邻两个数字即可满足题意。要注意，排列元素个数为偶数的时候应从第二位开始换

code

#include

using namespace std;

const int N = 1e5 + 10;

int n, m, k, t;

void solve()
{
    int a[N] = {0};
    cin >> n;

    if(n % 2)
    {
        cout << 1 << " ";
        for(int i = 2; i < n; i += 2)
            cout << i + 1 <<" " << i << " ";
    }
    else
    {
        for(int i = 1; i < n; i += 2)
        {
            cout << i + 1 << " " << i << " ";
        }
    }
    puts("");
}

int main()
{
    cin >> t;
    while(t --) solve();
    return 0;
}
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

题目大意

给出一串数字，问通过几次操作（将某个数全部变为零）可以将序列从小到大排列。

题目分析

当数列本身有序则不需要进行操作。

当其本身无序时，从后往前找到第一个大于最后一个数字的数u，并求出他之前的数字种类，再次过程中若u后的数字u也受到影响，也需要加上 u v 之间之前未出现过的数字种类。

code

#include 

using namespace std;

const int N = 1e5+10;

int n, m, k, t;

void solve()
{
    int a[N] = {0}, b[N] = {0};

    cin >> n;
    int sum = 0;

    for(int i = 1;i <= n;i++) cin >> a[i];

    int flg = 1;
    int tem = 0;

    for(int i = n; i >= 1; i--)
    {
        if(a[i-1] > a[i])
        {
            tem = i-1;
            flg = 0;
            break;
        }
    }

    if(flg) cout << 0 << "\n";
    else
    {
        for(int i = 1;i <= tem;i++)
        {
            if(!b[a[i]])
            {
                sum ++;
                b[a[i]] = 1;
            }
        }
        int res = -1;
        for(int i = n;i > tem; i--)
        {
            if(b[a[i]])
            {
                res = i;
                break;
            }
        }
        for(int j = tem;j <= res; j ++)
        {
            if(!b[a[j]])
            {
                sum++;
                b[a[j]] = 1;
            }
        }
        cout << sum << "\n";
    }
}

int main()
{
    cin >> t;
    while(t--) solve();
    return 0;
}
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