(2025)第十三届重庆市大学生程序设计竞赛

codeforces补题链接
题面链接

A

题目描述

给定一个长度为 $n$ 的一个数组$A$，对于数组$A$会有$T$轮操作,第$i$轮操作操作如下：

$A_{j} \gets A_{i} | A_{(i+j) \mod n}$
经过多少轮，可以使得这个数组所有数相同？

解题思路

将数拆分为二进制,对于每个数的某一位,至少存在一个 $1$, 进行一次操作，可产生一个 $1$, 第二次操作可产生两个$1$，依次进行，可产生$1 + 1 + 2 + 3 + \cdots + i$个 $1$，那么我们就可以暴力枚举一下，复杂度为$O(n \sqrt(n))$
起始也可以大胆猜想下，至多执行 $\log_{2}n$ 次就可以使得数组的数相同。

参考代码

#include<bits/stdc++.h>

#define int long long
#define pii std::pair<int ,int>

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    for(int i = 0 ; i < n; i ++) {
        std::cin >> a[i];
    }
    
    for(int i = 0;i <= 500; i ++) {
        for(int j = 0 ; j < n; j ++) {
            a[j] |= a[(j + i) % n];
        }
        bool f = false;
        for(int j = 0 ; j < n - 1;j ++) {
            if(a[j] != a[j + 1]) {
                f = true;
                break;
            }
        }

        if(!f) {
            std::cout << i << std::endl;
            return; 
        }
    }
}

signed main () {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);
    int T = 1;
    std::cin >> T;
    while(T --) solve();
}

C

题目描述

给出数字$n$,构造一个$n \times n$的方格图，方格中划分区域，每个区域的颜色相同，相邻区域的颜色不同，现在要用最少的颜色填土涂区域。
问：如何填涂可以使得所用的最少颜色数最大？

解题思路

要使得最少的颜色数最大，无非就是以下方式填涂：

$(1,2),(1,3), \cdots , (1,n), (2,1), (2,3), \cdots , (n, n-1)$

就是让$1~n$中的数两个相邻。

还有一种思路就是对于每一行的构造，我们可以将$1~n$的上升序列进行$i$的右移($i$代表行数)
这样的移动满足题面要求的期望还是极高的, 正解为第一种，第二种期望值较高,也可满足(不要问我为什么知道，问就是打表发现的)

参考代码

#include<bits/stdc++.h>

#define int long long
#define pii std::pair<int ,int>

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    std::iota(a.begin(), a.end(), 1ll);
    for(int i = 0 ; i < n;i ++) {
        std::rotate(a.begin(), a.begin() + i, a.end());
        for(int j = 0 ; j < n; j ++) {
            std::cout << a[j] << " \n"[j == n - 1];
        }
    }
}

signed main () {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);
    int T = 1;
    std::cin >> T;
    while(T --) solve();
}

F

题面描述

给出三个数$a, b, c$，根据三个数的大小关系输出:

  • $a > b$ ,输出$Win$;
  • $a \le b , c > b$ ,输出$WIN$
  • $a \le b , c \le b$，输出$nowin$

参考代码

#include<bits/stdc++.h>

#define int long long
#define pii std::pair<int ,int>

void solve() {
    int a, b, c;
    std::cin >> a >> b >> c;
    std::cout << (a > b ? "Win" : (c > b ? "WIN" : "nowin")) << std::endl;
}

signed main () {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);
    int T = 1;
    std::cin >> T;
    while(T --) solve();
}

H

题目描述

给出三个长度为$n$的数组$A,B,C$,数组$A,B$是长度为$n$的排列，代表一个盒子中的上边界和下边界小球的排序，数组$C$代表上边界小球是否靠边($C_{i}=0 \to$ 小球$i$不靠上边界，反之，则靠上边界)。

现在需要将编号相同的小球用绳子连起来(绳子是可任意变换形状的，长度也是任意长度的，绳子不可越出盒子边界)，若绳子相交，则输出$No$,否则输出$Yes$。

解题思路

既然绳子是任意长度的,那么对于上边界没有靠边的球，可以直接连接起来，就算中间有靠边界的球相连，总有方式绕过。
那么，只剩下靠上边界的球需要考虑，不难发现上下边界的球需要序列相同才能满足相连不相交。
那么就只需要处理出那些球紧靠上边界即可

参考代码

#include<bits/stdc++.h>

#define int long long
#define pii std::pair<int ,int>

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> a(n), b(n), c(n), x, y;
    for(int i = 0; i < n; i ++) std::cin >> a[i];
    for(int i = 0; i < n; i ++) std::cin >> b[i];
    for(int i = 0; i < n; i ++) std::cin >> c[i];

    std::set<int>se;

    for(int i = 0 ; i < n; i ++) {
        if(c[i]) x.push_back(a[i]), se.insert(a[i]);
    }

    for(int i = 0 ; i < n; i ++) {
        if(se.count(b[i]) ) {
            y.push_back(b[i]);
        }
    }

    std::cout << (x == y ? "Yes" : "No") << std::endl;
}

signed main () {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);
    int T = 1;
    std::cin >> T;
    while(T --) solve();
}

L

题目描述

模拟一个栈的操作，操作$n$次，操作如下：

  • Push $x$: 将$x$压入栈。
  • Pop: 弹出栈顶元素。
  • Repeat: 将此前的操作重复，不包含当前操作。

每次操作都输出栈的元素总和，结果$ \mod 998244353$。
$1 \le n \le 2 \times 10^5, 0 \le x \le 998244353$

解题思路

首先模拟操作即可，但需要注意，当栈的大小大于 $2 \times 10^5$时，就不需要执行Repeat操作，斌且需要用数组模拟栈。

参考代码

#include<bits/stdc++.h>

#define int long long
#define pii std::pair<int ,int>
const int MOD = 998244353;
void solve() {
    int n, res = 0;
    std::cin >> n;
    std::deque<int> q;
    for(int i = 0 ; i < n; i ++) {
        std::string s;
        std::cin >> s;
        if(s == "Push") {
            int x;
            std::cin >> x;
            q.push_back(x);
            res = (res + x + MOD) % MOD;
        }else if(s == "Pop") {
            res = (res - q.back() + MOD) % MOD;
            q.pop_back();
        }else {
            res = (((res + res)%MOD) + MOD) %MOD;
            if(q.size() < 2e5) {
                int t = q.size();
                for(int i = 0 ; i < t; i ++) {
                    q.push_back(q[i]);
                }
            }
        }
        std::cout << res % MOD << std::endl;
    }
}

signed main () {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);
    int T = 1;
    // std::cin >> T;
    while(T --) solve();
}