Contestant~. Rank 1201. Rating +25.

A. Increasing and Decreasing

题意

给定三个整数 \(x, y, n\)，构造一个长为 \(n\) 的序列 \(a\)，满足：

\(a_1 = x, a_n = y\)；
\(a_1 < a_2 < \ldots < a_n\)；
记 \(b_i = a_{i + 1} - a_i\)，\(b_1 > b_2 > \ldots > b_{n - 1}\)

如果无法构造，输出 \(-1\)。

思路

既然要尽可能构造出来，那么我们就尽可能缩小相邻 \(b_i\) 的差值，也就是说，\(b_{n - 1} = 1, b_{n - 2} = 2, \ldots\)。

我们令 \(a_n = y\)，然后递推到 \(a_1\)，最后比较一下 \(a_1\) 和 \(x\) 的大小。

显然，如果 \(a_1 > x\)，那么无解，否则就可以满足 \(a_2 - x \geq a_2 - a_1 = b_1 > b2 > \ldots\)。

最后记得设 \(a_1 = x\)。

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

对应AC代码

#define chatgpt "bits/stdc++.h"

#include chatgpt

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()

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

void solve() {
    int x, y, n;
    cin >> x >> y >> n;
    vector<int> ans(n + 1);
    ans[n] = y;
    for(int i=n-1;i>=1;i--){
        ans[i] = ans[i + 1] - (n - i);
    }
    if(ans[1] < x) cout << -1 << '\n';
    else{
        cout << x << ' ';
        for(int i=2;i<=n;i++) cout << ans[i] << ' ';
        cout << '\n';
    }
}

signed main() {
# ifdef FLOATING_OCEAN
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
# endif
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
//    init();
    int t = 1;
    cin >> t;
    while (t--) solve();
}

在多数签到题里有点偏模拟

B. Swap and Reverse

题意

给定一个字符串 \(s\) 以及一个整数 \(k\)，定义一次操作为下面两者任选一：

选择一个点 \(i, i \in [1, n - 2]\)，交换 \(s_i, s_{i + 2}\)；
选择一个点 \(i, i \in [1, n - k + 1]\)，将 \([i, i + k - 1]\) 内的字符串翻转

在任意次操作后，输出字符串的最小字典序。

思路

首先，如果没有操作 \(2\)，那么最后的答案就是分别将奇数位和偶数位上的字符排序。

如果有操作 \(2\)，我们先来考虑 \(k\) 是奇数的情况。

因为我们只能翻转奇数长度的字符，可以发现翻转操作可以等效于若干个操作 \(1\)。

而相反地，如果 \(k\) 是偶数，我们可以将奇数位和偶数位上的数交换，因此在若干次操作后，我们可以将其等效于交换任意两个相邻数。

因而，我们就只需对整个字符串排序。

从而，最后的结论是：

\(k\) 为奇数，分别对奇数位和偶数位上的字符排序；
\(k\) 为偶数，将整个字符串排序

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

对应AC代码

#define chatgpt "bits/stdc++.h"

#include chatgpt

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()

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

void solve() {
    int n, k;
    string s;
    cin >> n >> k >> s;
    if (k % 2 == 0) {
        sort(all(s));
        cout << s << '\n';
        return;
    }
    string a, b;
    for (int i = 0; i < n; i++) {
        if (i % 2 == 0) a += s[i];
        else b += s[i];
    }
    sort(all(a));
    sort(all(b));
    for (int i = 0; i < n; i++) {
        if (i % 2 == 0) cout << a[i / 2];
        else cout << b[i / 2];
    }
    cout << '\n';
}

signed main() {
# ifdef FLOATING_OCEAN
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
# endif
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
//    init();
    int t = 1;
    cin >> t;
    while (t--) solve();
}

有意思的思维题

C. Divisor Chain

题意

给定整数 \(x\)，定义一次操作为选定 \(x\) 的一个因数 \(y\)，并将 \(x\) 减去 \(y\)。

在不超过 \(1000\) 次操作，且不连续选择 两次以上 相同的因数的条件下，将 \(x\) 减为 \(1\)，并输出一种可行的方案。

思路

我们将其放到二进制下考虑：

从第 \(2\) 位开始向高位枚举；
如果第 \(i\) 位为 \(1\)，那么删去该位，也就是 \(1 << i\)

上述操作存在缺陷，因为如果出现最低位为 \(0\) 的情况，最后答案会变成 \(0\)。

因此，我们考虑直接从最低位开始枚举删除，直到最高位的前一位。

当我们达到最高位时，可以发现后面低位全都是 \(0\)，也就是说，现在 \(x\) 是 \(2\) 的次方。那么我们只需循环减去 \(\frac{x}{2}\) 即可，最后一定会变为 \(1\)。

时间复杂度：\(O(\log A)\)

对应AC代码

#define chatgpt "bits/stdc++.h"

#include chatgpt

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()

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

void solve() {
    int n;
    cin >> n;
    vector<int> ans;
    ans.pb(n);
    bitset<64> a(n);
    for(int i=0;i<64;i++){
        if(a[i]){
            if(n == (1ll << i)){
                while(n > 1) ans.pb(n /= 2);
            }else ans.pb(n -= (1ll << i));
        }
    }
    cout << ans.size() << '\n';
    for(auto e : ans) cout << e << ' ';
    cout << '\n';
}

signed main() {
# ifdef FLOATING_OCEAN
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
# endif
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
//    init();
    int t = 1;
    cin >> t;
    while (t--) solve();
}

\(1000\) 纯属骗人

D. Matrix Cascade

题意

给定一个 \(n \times n\) 的二进制矩阵，定义一次操作为选定一个点 \((x, y)\)，并将满足 \(x - i \ge \left|y - j\right|\) 的所有点 \((i, j)\) 上面的值全都反转。

输出最小操作数，使整个矩阵全变为 \(0\)。

思路

我们不妨观察这样一个三角形：

 a
bcd

我们可以发现，点 \(c\) 只会被点 \(a, b, d\) 影响到，而整个三角形都是 \(a\) 的影响范围。

因而，我们考虑 \(dp[i][j][k]\)，表示 \((i, j)\) 左边的点的状态，右边的点的状态以及自身的状态。

因为相邻两行的 \(dp\) 具有递推性，所以我们考虑从上一行推到当前行。

那么很显然，左边的点只需考虑向右影响的递推，\(dp[i][j][0] = dp[i - 1][j - 1][0]\)，同理，\(dp[i][j][1] = dp[i - 1][j + 1][1]\)。

因而，\(dp[i][j][2] = dp[i][j][0] + dp[i][j][1] + dp[i - 1][j][2]\)。

如果我们发现 \((i, j)\) 点需要修改，那么我们将 \(dp[i][j][0], dp[i][j][1], dp[i][j][2]\) 都加上 \(1\)，来表征当前点可以影响下一行。

结合图形理解，可以证明上面的递推的合理性。

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

对应AC代码

#define chatgpt "bits/stdc++.h"

#include chatgpt

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()

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

void solve() {
    int n;
    cin >> n;
    vector<string> s(n);
    for(int i=0;i<n;i++) cin >> s[i];
    vector<vector<vector<int>>> dp(n + 2, vector<vector<int>>(n + 2, vector<int>(3)));
    int ans = 0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int now = s[i - 1][j - 1] - '0';
            dp[i][j][0] = dp[i - 1][j - 1][0];
            dp[i][j][1] = dp[i - 1][j + 1][1];
            dp[i][j][2] = dp[i][j][0] + dp[i][j][1] + dp[i - 1][j][2];
            if((dp[i][j][2] + now) % 2 == 1){
                ans ++;
                dp[i][j][0] ++, dp[i][j][1] ++, dp[i][j][2] ++;
            }
        }
    }
    cout << ans << '\n';
}

signed main() {
# ifdef FLOATING_OCEAN
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
# endif
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
//    init();
    int t = 1;
    cin >> t;
    while (t--) solve();
}

赛时还想出来个二分的写法，感觉有点抽象，而且常数不小

E. Guess Game

题意

给定序列 \(s\)，定义 \(A, B\) 之间的游戏如下：

均匀随机选择两个数，可以重复，记为 \(a, b\)；
将 \(a, a|b\) 告诉 \(A\)，若 \(A\) 能根据之前自己和对手的猜测来确定 \(a < b, a > b\) 或 \(a = b\)，那么说出结果并结束游戏，否则说出自己不知道；
将 \(b, a|b\) 告诉 \(B\)，若 \(B\) 能根据之前自己和对手的猜测来确定 \(a < b, a > b\) 或 \(a = b\)，那么说出结果并结束游戏，否则说出自己不知道；
不断猜测，直到有人说出结果为止

两个人足够聪明。

定义一个人为一轮，输出游戏进行的轮数的期望。

思路

既然两个人足够聪明，那么他们肯定会从高位向低位考虑。

我们来模拟一下过程，

其中，下面的过程会默认将 \(a|b\) "离散化" 为低位全是 \(1\)，或者说，将所有 \(1\) 挪到最前面：

\(A\) 拿到了 \(a, a|b\)，如果 \(a\) 的最高位为 \(0\)，那么直接说出 \(a < b\)，否咋说出自己不知道；
\(B\) 拿到了 \(b, a|b\)，如果 \(b\) 的最高位或者次高位至少有一个为 \(0\)，那么因为 \(A\) 说自己不知道，就可以断定最高位一定是 \(1\)，那么直接说出 \(a > b\)，否则说出自己不知道；
如果 \(a\) 的次高位或者次次高位至少有一个为 \(0\)，那么因为 \(B\) 说自己不知道，就可以断定最高位和次高位一定是 \(1\)，那么直接说出 \(a < b\)，否则说出自己不知道；
\(\ldots\)

因而，最后我们可以推导出结论：

从高位向低位枚举所有 \(a|b\) 为 \(1\) 的二进制位；
如果 \(a < b\)，并且 \(a\) 的第 \(i\) 位是 \(0\)，那么进行了 \(i + (i \bmod 2 == 0)\) 轮；
如果 \(a = b\)，那么进行了 \(k + 1\) 轮，其中 \(k\) 为 \(a | b\) 中有多少个 \(1\)。
如果 \(a > b\)，并且 \(b\) 的第 \(i\) 位是 \(0\)，那么进行了 \(i + (i \bmod 2 == 1)\) 轮

如上，我们得到了复杂度为 \(O(n ^ 2 \log A)\) 的暴力算法。

我们考虑使用 \(\mathtt{01}\) 字典树来优化复杂度。

具体来说，在 \(\mathtt{dfs}\) 的时候，我们可以记录当前路径上有多少个 \(1\)，并可以轻松获取当前点是否同时具有 \(0, 1\) 节点，或同时不具有 \(0, 1\) 节点。

前者可以构造出大小关系，后者可以构造出相等关系。

将公式略微修改即可得到答案。

当然，不要忘记除 \(n^2\)，也就是总方案数。

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

对应AC代码

#define chatgpt "bits/stdc++.h"

#include chatgpt

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()

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

struct Node {
    int nxt[2], cnt;
    Node() {
        nxt[0] = nxt[1] = -1;
        cnt = 0;
    }
};

vector<Node> tr;

void insert(int x){
    int now = 0;
    for(int i= 31; i >= 0;i--) {
        int p = (x >> i) & 1;
        if(tr[now].nxt[p] == -1) {
            tr[now].nxt[p] = tr.size();
            tr.pb();
        }
        tr[now].cnt ++, now = tr[now].nxt[p];
    }
    tr[now].cnt ++;
}

void query(int v, int k, int &ans){
    if(v == -1) return;
    //存在某一位上一个为0一个为1的情况
    if(tr[v].nxt[0] != -1 && tr[v].nxt[1] != -1){
        int cnt = tr[tr[v].nxt[0]].cnt * tr[tr[v].nxt[1]].cnt % mod;
        ans = (ans + cnt * (2 * ((k + 1) / 2) + 1) % mod) % mod; //a < b
        ans = (ans + cnt * 2 % mod * ((k + 2) / 2) % mod) % mod; //a > b
    }
    //一模一样的情况
    if(tr[v].nxt[0] == -1 && tr[v].nxt[1] == -1){
        ans = (ans + (k + 1) * tr[v].cnt % mod * tr[v].cnt % mod) % mod;
    }
    query(tr[v].nxt[0], k, ans);
    query(tr[v].nxt[1], k + 1, ans);
}

static __int128 qp(__int128 x, __int128 y, __int128 m = mod) {
    static __int128 ans;
    ans = 1, x %= m;
    for (; y; y >>= 1, x = x * x % m) if (y & 1) ans = ans * x % m;
    return ans;
}

int inv(int n, int m = mod) { return qp(n, m - 2, m); }

void solve() {
    int n;
    cin >> n;
    tr = {};
    tr.pb();
    for(int i=0;i<n;i++){
        int x;
        cin >> x;
        insert(x);
    }
    int ans = 0;
    query(0, 0, ans);
    ans = ans * inv(n * n) % mod;
    cout << ans << '\n';
}

signed main() {
# ifdef FLOATING_OCEAN
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
# endif
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
//    init();
    int t = 1;
    cin >> t;
    while (t--) solve();
}

不要尝试用 \(memset\) 初始化字典树 qaq