2024牛客寒假算法基础集训营4

A 柠檬可乐

void solve() {
    int a, b, k;cin >> a >> b >> k;
    if (a >= k * b) {
        cout << "good\n";
    } else {
        cout << "bad\n";
    }
}

B 左右互博

玩石头游戏。
游戏一开始有 $n$ 堆石子，第 $i$ 堆石子，有 $a_i$ 个石子。两人轮流进行游戏。
轮到某个人时，这个人先选数量为 $x(x>1)$ 的一堆石子，然后选择一个整数 $y(2\le y\le x)$，将选择的 $x$ 个石子分为两堆石子，数量分别为 $\lfloor \frac{y}{x}\rfloor$ 和 $x-\lfloor \frac{y}{x}\rfloor$。

当有某个人不能操作时，则失败，另一个人胜利。
两人都绝顶聪明，必定使用最佳策略。讨厌鬼先手，他想知道他能不能获得胜利？

容易发现当 $x\ge 2$ 时就可以无限分下去，则某个数的分解次数一定是 $n-1$，则遍历相加即可。

void solve() {
    int n;cin >> n;vector<int> a(n);for (auto& i : a)cin >> i;
    int cnt = 0;
    for (int i = 0;i < n;i++) {
        if (a[i] >= 2){
            cnt += a[i] - 1;
        }
    }
    if (cnt % 2) {
        cout << "gui\n";
    } else {
        cout << "sweet\n";
    }
}

C 冬眠

阿宁生活在一个$n$ 行$m$ 列的字符矩阵中，阿宁打算在第$x$ 行$y$ 列冬眠。

在每一天，都会有 $q$ 次行循环移动或列循环移动。

• 如果是第 $z$ 行循环移动，那么第 $z$ 行所有字符往后移动一个，最后一个字符移动到第 $z$ 行开头。
• 如果是第 $z$ 列循环移动，那么第 $z$ 列所有字符往后移动一个，最后一个字符移动到第$z$ 列开头。

阿宁将要冬眠 $p$ 天，冬眠结束后阿宁想知道第 $x$ 行 $y$ 列是什么字符？

char a[110][110];
void solve() {
    int n, m, x, y;cin >> n >> m >> x >> y;
    x--, y--;
    for (int i = 0;i < n;i++) {
        for (int j = 0;j < m;j++) {
            cin >> a[i][j];
        }
    }
    int p, q;cin >> p >> q;
    vector<pair<int, int>> op(q);
    for (int i = 0;i < q;i++) {
        cin >> op[i].first >> op[i].second;
        op[i].second--;
    }
    while (p--) {
        for (int i = 0;i < q;i++) {
            if (op[i].first == 1) {
                char temp = a[op[i].second][m - 1];
                for (int j = m - 1; j > 0; j--) {
                    a[op[i].second][j] = a[op[i].second][j - 1];
                }
                a[op[i].second][0] = temp;
            } else {
                char temp = a[n - 1][op[i].second];
                for (int j = n - 1; j > 0; j--) {
                    a[j][op[i].second] = a[j - 1][op[i].second];
                }
                a[0][op[i].second] = temp;
            }
        }
    }
    cout << a[x][y] << '\n';
}

D 守恒

给定一个长度为 $n$ 的数组 $a$，
可以进行任意次操作，每次操作选择数组 $a$ 的两个元素，其中一个加 $1$，另一个减 $1$，要求每次操作后 $a$ 的各元素仍然是正整数。

操作结束后，数组的最大公约数可能有多少种不同的值？

容易知道，不管如何操作，sum[a] 始终是不变的，且数组 $a$ 可以在总和为 sum[a] 的条件下达到任何数 $(n\ge 2)$

需要特判 $(n=1):\to 1$

因此可以因式分解

#define int long long
void solve() {
    int n;cin >> n;vector<int> a(n), f(n);int cnt = 0;for (auto& i : a)cin >> i, cnt += i;
    if (n == 1) {
        cout << 1 << "\n";return;
    }
    int ans = 0;
    for (int i = 1;i * i <= cnt;i++) {
        if (cnt % i == 0) {
            if (n * i <= cnt)
                ans++;
            if (cnt / i != i && n * (cnt / i) <= cnt) {
                ans++;
            }
        }
    }
    cout << ans << '\n';
}

E 漂亮数组

求给定数组 $a$ 最多可以分为多少个总和为 $k$ 的倍数的子数组。

G/H 数三角形

求给定矩阵有多少个满足要求的等腰三角形。

• easy: $1\le n,m\le 500$
• hard: $1\le n,m\le 3000$

.*.
*** 

..*..
.*.*.
*****

...*...
..*.*..
.*...*.
*******

(待更 $\dots$)