概要

比赛地址

2020 Multi-University Training Contest 10

题目

1007. Coin Game

题目大意

有 N 个机器，每个机器按第一次可以获得 a[i]，按第二次可以获得 b[i]，按第三次可以获得 a[i]，后面再按不获得。

问：按第一次至第 k 次，分别至多能获得多少？

解题思路

每个 machine 给予的硬币可以等价成, 一个重量为 1 的价值为 a[i] 的硬币, 以及一个重量为 2 的价值为 a[i] + b[i] 的硬币, 这两硬币之间没有相互影响. (对于第 i 个 machine, 如果只取一个, 等价于取重量为 1 的那枚, 如果取了前两个, 等于取了重量为 2 的那枚, 如果三个都取了, 等价于同时取了重量为 1 和重量为 2 的那枚)。

可以按性价比从大到小排序, 然后选性价比最高的那些, 直到取到的硬币总重量不小于 k. 如果这时候取的硬币总重量恰好为 k, 那么这一定就是最优取法. 否则就是总重量恰好为 k + 1, 这时候我们需要丢弃一枚性价比最低的重量为 2 的硬币, 拿多一枚重量为 1 的硬币。

然后 dp 即可。

AC代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
int read()
{
    int res = 0, f = 0; char c = getchar();
    while(!isdigit(c) && c != '-') c = getchar();
    if(c == '-') f++, c = getchar();
    while(isdigit(c)) res = (res<<3)+(res<<1)+(c^48), c = getchar();
    return f ? -res : res;
}

const int maxn = 5e6+10;
const int threshold = 10000000;
const LL inf = 4e18;

int n, m, a[maxn], b[maxn];
unsigned long long k1, k2;

unsigned long long xorShift128Plus()
{
    unsigned long long k3 = k1, k4 = k2;
    k1 = k4;
    k3 ^= (k3 << 23);
    k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26);
    return k2 + k4;
}

void gen(int n, unsigned long long _k1, unsigned long long _k2)
{
    k1 = _k1, k2 = _k2;
    for(int i = 1; i <= n; i++)
    {
        a[i] = xorShift128Plus() % threshold + 1;
        b[i] = xorShift128Plus() % threshold + 1;
        b[i] += a[i];
    }
}

int main()
{
    unsigned long long t1, t2;
    while(~scanf("%d%d%llu%llu", &n, &m, &t1, &t2))
    {
        gen(n, t1, t2);
        sort(a+1, a+n+1, greater<int>());
        sort(b+1, b+n+1, greater<int>());
        int x = 1, y = 0;
        LL ans = a[1], sum = a[1];
        for(int i = 2; i <= m; i++)
        {
            LL tmp1 = -inf, tmp2 = -inf;
            if(x < n) tmp1 = a[x+1];
            if(x >= 1 && y < n) tmp2 = b[y+1]-a[x];
            if(tmp1 > tmp2) x++, sum += tmp1;
            else x--, y++, sum += tmp2;
            ans ^= sum;
        }
        printf("%lld\n", ans);
    }
    return 0;
}

1010. Tic-Tac-Toe-Nim

题目大意：

给你一个 3\times 3 的数字表格，每个格子中有一定数量的石子。每次可以拿掉其中一堆石子的 1 至全部个。当某一行石子被拿光时，游戏结束，最后拿石子的玩家获胜。

为了加快游戏进程，要求两位玩家第一次必须拿光一堆石子。问，先手玩家第一次拿的堆中，有多少是可以保证必胜的？

问题分析：

首先，两人最开始拿光的两堆不能在同一行或者同一列，否则先手只需要拿光这一行（列）的另一堆得全部石子即可获胜。不妨设拿掉后的局面如下：

\begin{matrix}
0&a_{12}&a_{13} \cr a_{21}&a_{22}&0 \cr a_{31}&a_{32}&a_{33}
\end{matrix}

那么最终的状态为：

\begin{matrix}
0&1&1 \cr 1&1&0 \cr 1&0&1
\end{matrix}

到这个状态后，先手不论怎么走都会失败；如果有人破坏这个局面（将某个 1 提前变成 0），则另一方只需将此行（列）中另一堆拿光即可获胜。

问题转化为了 7 堆石子，其中 6 堆的石子数量为 a_{ij}-1，与两个开始被拿光的堆不同行列的堆石子数量为 a_{ij} 的一个普通 Nim 游戏。

AC代码：

#include <bits/stdc++.h>
using namespace std;
int a[4][4];

int id(int i, int j) {
    i--, j--;
    int idx = 3 - i % 3 - j % 3;
    int idy = 3 - i / 3 - j / 3;
    return 3 * idy + idx + 1;
}

bool ok(int i, int j) {
    return (i % 3 != j % 3) && ((i - 1) / 3 != (j - 1) / 3);
}

bool judge(int i) {
    for (int j = 1; j <= 9; j++) {
        if (!ok(i, j)) continue;
        int x = id(i, j);
        int ans = 0;
        for (int k = 1; k <= 9; k++) {
            if (k == i || k == j) continue;
            int now = a[(k - 1) / 3 + 1][(k - 1) % 3 + 1];
            ans ^= (k == x ? now : now - 1);
        }
        if (ans == 0) return false;
    }
    return true;
}

int main()
{
    int T; scanf("%d", &T);
    while (T--) {
        for (int i = 1; i <= 3; i++) {
            for (int j = 1; j <= 3; j++) {
                scanf("%d", &a[i][j]);
            }
        }
        int cnt = 0;
        for (int i = 1; i <= 9; i++) {
            if (judge(i)) {
                cnt++;
            }
        }
        printf("%d\n", cnt);
    }
    return 0;
}