Practice.

A. Immobile Knight

题意

规定一个棋子只能沿着 \(1 \times 2\) 矩形的对角线行走。

给定一个棋盘的尺寸，输出让棋子无法行走的点的位置。如果点不存在，输出任意点。

思路

能走的尺寸数量有限，我们直接分类讨论，这边定义较短边为 \(n\)，较长边为 \(m\)。

  1. \(n = 1\)，那么随便哪个点都是答案；

  2. \(n = 2或3, m = 3\)，那么中心点就是答案

其余情况，随便输出即可。

注意，输出的点一定要在棋盘内，否则是无效答案。

时间复杂度：\(O(1)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define fs first
#define sc second

const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f;

void init(){}

void solve() {
    int n, m;
    cin >> n >> m;
    bool f = n > m;
    if(n > m) swap(n , m);
    if(n == 1) cout << 1 << ' ' << 1 << '\n';
    else if(n == 2 && m <= 3 || n == 3 && m == 3) {
        if(f) swap(n, m);
        cout << (n + 1) / 2 << ' ' << (m + 1) / 2 << '\n';
    }
    else cout << 1 << ' ' << 1 << '\n';
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    init();
    int t = 1;
    cin >> t;
    while(t --) solve();
}

分类讨论即可~

B. Array Recovery

题意

定义 \(d\) 序列为原非负序列 \(a\) 构造而成，构造满足 \(d_1 = a_1, d_i = |a_i - a_{i - 1}|\)。

给定 \(d\)，判断是否能唯一确定 \(a\)，若能，输出 \(a\)。

思路

首先，我们化简右式，得到 \(a_i = a_{i - 1} ± d_i\)。

因为 \(a\) 的所有元素都是非负的，因而 \(a_{i - 1} ± d_i \geq 0\)。

那么很明显了，我们既然要唯一确定 \(a\)，那么我们只能 \(+ d_i\)，而 \(- d_i\) 的条件就是 \(a_{i - 1} \geq d_i\)。

因而，只要 \(a_{i - 1} \geq d_i\)，那么就无法唯一确定，否则我们按顺序构造出原序列 \(a\) 即可。

时间复杂度：\(O(n)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define fs first
#define sc second

const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f;

void init(){}

void solve() {
    //让它只能递增
    int n;
    cin >> n;
    vector<int> ans(n);
    cin >> ans[0];
    bool f = true;
    for(int i=1;i<n;i++){
        int cur;
        cin >> cur;
        ans[i] = ans[i - 1] + cur;
        if(cur != 0 && ans[i - 1] >= cur) f = false;
    }
    if(f){
        for(auto e : ans) cout << e << ' ';
        cout << '\n';
    }else cout << -1 << '\n';
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    init();
    int t = 1;
    cin >> t;
    while(t --) solve();
}

简单的构造题捏

C. Card Game

题意

给定 \(n\) 张牌，\(n\) 为偶数，每个牌具有一个数字，所有牌的数字组成的序列是长为 \(n\) 的排列。

现在，给定两个玩家 \(A, B\)，每个玩家拥有 \(\frac{n}{2}\) 张牌，规定奇数局 \(A\) 先手，偶数局 \(B\) 先手。每一局每个玩家要打出一张牌并弃置，规定后手要打出比先手大的牌，否则先手赢。所有回合结束后，若没有玩家赢，那么平局。

在所有牌的分配方案中，统计 \(A, B\) 赢的方案数以及平局的方案数，并输出这三个数\(\mod 998244353\)。

思路

首先，平局只有一种方案，我们约定一个由 \(A, B\) 组成的字符串为从 \(1\) 开始按顺序分牌的方案，那么这个方案就是 \(BAABBAABBA\ldots\)

观察不难得到，只要某个方案有一个位置的字符和上面不一样，那么就可以断定已经有玩家胜利了，并且这个位置之后的元素可以任意分配。

也就是说，我们可以采用递归的方法计算。如果前 \(n\) 个数已经确定，那么我们只需计算组合数 \(C^\frac{n}{2}_{n-1}, C^\frac{n}{2}_{n-2}\)，然后交叉累计即可（即按照 \(BA, AB, BA,\ldots\) 的顺序计算）。

当然会涉及到求组合数，因为本题数据量不大，但是数据范围大，我们不妨用 \(java\) 的大数。

时间复杂度：\(O(n)\)

对应AC代码

import java.io.*;
import java.math.*;
import java.util.*;
import java.util.concurrent.atomic.*;

public class Main{
    private static BigInteger fact(int to){
        BigInteger ans = BigInteger.ONE;
        for(int i=2;i<=to;i++) ans = ans.multiply(BigInteger.valueOf(i));
        return ans;
    }

    private static BigInteger C(int n, int k){
        return fact(n).divide(fact(n - k)).divide(fact(k));
    }

    private static BigInteger[] calc(int n){
        if(n == 2) return new BigInteger[]{BigInteger.ONE, BigInteger.ZERO, BigInteger.ONE};
        else{
            BigInteger[] pre = calc(n - 2);
            return new BigInteger[]{C(n - 1, n / 2).add(pre[1]), C(n - 2, n / 2).add(pre[0]), BigInteger.ONE};
        }
    }

    private static void solve(Console console) throws Exception {
        BigInteger mod = BigInteger.valueOf(998244353);
        int n = console.nextInt();
        for(BigInteger ans : calc(n)) console.print(ans.mod(mod) + " ");
        console.println();
    }

    public static void main(String[] args) throws Exception {
        Console console = new Console();
        int t = console.nextInt();
        while(t -- > 0) solve(console);
        console.close();
    }

    //快读模板 此处略去
    public static class Console implements Closeable {}
}

有点暴力.jpg