【补题】18年多校2

目录

• Game [HDU 6312]
• Swaps and Inversions [HDU 6318]

---

Game

Description

Alice and Bob are playing a game.
The game is played on a set of positive integers from 1 to $n$.

In one step, the player can choose a positive integer from the set, and erase all of its divisors from the set. If a divisor doesn’t exist it will be ignored.

Alice and Bob choose in turn, the one who cannot choose (current set is empty) loses.
Alice goes first, she wanna know whether she can win. Please judge by outputing Yes or No.

Solution

考虑$n>1$时先手取1等价于互换先后手，故Alice必胜。

#include <cstdio>

int main()
{
    int n;
    while (scanf("%d", &n) == 1)
        printf("Yes\n");
    return 0;
}

Swaps and Inversions

Description

Long long ago, there was an integer sequence a.
Tonyfang think this sequence is messy, so he will count the number of inversions in this sequence. Because he is angry, you will have to pay $x$ yuan for every inversion in the sequence.

You don’t want to pay too much, so you can try to play some tricks before he sees this sequence. You can pay $y$ yuan to swap any two adjacent elements.
What is the minimum amount of money you need to spend?

Solution

交换相邻项使数组有序需要的最小次数等于逆序数。

故所求为逆序数$\ *min(x, y)$。逆序数使用归并排序求出。

#include <cstdio>
#include <cstring>

typedef long long LL;
const int MAXN = 100000 + 10;
int A[MAXN], B[MAXN];

LL min(LL x, LL y) { return x < y ? x : y; }

LL merge(int A[], int L[], int R[], int left, int right)
{
    int i = 0, j = 0, k = 0;
    LL res = 0;
    while (i < left && j < right)
    {
        if (L[i] <= R[j])
        {
            A[k++] = L[i++];
        }
        else
        {
            A[k++] = R[j++];
            res += left - i;
        }
    }
    while (i < left)
        A[k++] = L[i++];
    while (j < right)
        A[k++] = R[j++];
    return res;
}

LL merge_sort(int A[], int n)
{
    if (n < 2)
        return 0ll;
    int mid = n / 2;
    int *L = new int[mid];
    int *R = new int[n - mid];
    int i = 0;
    for (i = 0; i < mid; i++)
        L[i] = A[i];
    for (i = mid; i < n; i++)
        R[i - mid] = A[i];
    LL inv = merge_sort(L, mid);
    inv += merge_sort(R, n - mid);
    inv += merge(A, L, R, mid, n - mid);
    delete[] L;
    delete[] R;
    return inv;
}

int main()
{
    int n, x, y;
    while (scanf("%d%d%d", &n, &x, &y) == 3)
    {
        for (int i = 0; i < n; i++)
            scanf("%d", &A[i]);
        LL ans = merge_sort(A, n);
        ans *= min(x, y);
        printf("%lld\n", ans);
    }
    return 0;
}