官方题解 | COCR 普及赛 #1

MuktorFM

2025-04-13 20:59:22

发布于：云南

336阅读

0回复

0点赞

T1 大型の组合：数学

难度：红下位

正解

本题看似是一道求组合公式的题，利用 $C_N^1$ 公式即可得出结果。但是看看数据范围，long long 都做不到啊，只能用 string 来存。这里可以用组合的性质： $C_N^1$ 等于 $N$ 。因此这道题输入什么就输出什么即可。

#include<bits/stdc++.h>
using namespace std;
int main(){
    string s; cin >> s;
    cout << s;
    return 0;
}

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

预计得分： $100pts$

T2 危险の试剂：数论

难度：橙中位

题意说明

就是让你求出弹珠最多能在试剂瓶里分裂几次，如果不能激活就输出 $-1$ 。

体积公式

在特殊说明部分已经给出了球体、直圆柱体的体积计算公式了，直接带入即可。需要注意的是，由于 $\pi$ 和 $\frac{4}{3}$ 是小数，因此需要使用 double 进行存储。

球体体积计算公式如下：

$V_1=\frac{4}{3}\pi{r_1}^3$

直圆柱体体积计算公式如下：

$V_0=\pi{r_0}^2h$

特殊说明部分已说明不计球体之间的空隙，因此试剂瓶最多可以容纳 $\lfloor \frac{V_1}{V_0}\rfloor$ 个球。当可容纳球的数量不足 $1$ 个时，说明不能激活，直接输出 $-1$ 。

代入计算：

double qiu = (4 / 3.0) * 3.14 * r1 * r1 * r1;
double yuanzhu = 3.14 * r0 * r0 * h;
long long maxx = floor(yuanzhu / qiu);
if(maxx < 1){
    cout << -1 << endl;
    continue;
}

特殊性质 A

因为在这个性质中， $h=r_0=k=r_1$ ，通过简单的计算可得：

$maxx\lt1$

因此不可以所有药剂都不可激活，全部输出 $-1$ 即可。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int T; cin >> T;
    while(T--){
        cout << -1 << endl;
    }
    return 0;
}

时间复杂度： $O(T)$

预计得分： $28pts$

正解 | 枚举法（推荐）

由于 $k$ 值的范围较小（ $\le10^6$ ），可以直接采用枚举的方式找出最多可以分裂多少次，其时间是 $log$ 级的。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int T; cin >> T;
    while(T--){
        long long h,r0,k,r1; cin >> h >> r0 >> k >> r1;
        double qiu = (4 / 3.0) * 3.14 * r1 * r1 * r1;
        double yuanzhu = 3.14 * r0 * r0 * h;
        if(qiu > yuanzhu){
            cout << -1 << endl;
            continue;
        }
        long long maxx = floor(yuanzhu / qiu),have = 1,ans = 0;
        for(int i = 1;have <= maxx;i++){
            have *= k;
            ans++;
        }
        if(have > maxx) cout << ans - 1 << endl;
        else cout << ans << endl;
    }
    return 0;
}

时间复杂度： $O(T\times log_k^{\frac{yuanzhu}{qiu}})$

预计得分： $120pts$

正解 | 数学法

我们可以采用换底公式来解答这个问题。根据换底公式：

$\log_bN=\frac{\log_aN}{\log_ab}$

可得，篮球最多可分裂的秒数是：

$\log s=\lfloor\frac{\log maxx}{\log k}\rfloor$

在此之后，我们需要验证计算结果是否超过实际分裂的最大数量，如果分裂秒数为负数，则直接设为 $-1$ 。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int T; cin >> T;
    while(T--){
        long long h,r0,k,r1; cin >> h >> r0 >> k >> r1;
        double qiu = (4 / 3.0) * 3.14 * r1 * r1 * r1; // 球体体积计算
        double yuanzhu = 3.14 * r0 * r0 * h; // 直圆柱体体积计算
        long long maxx = floor(yuanzhu / qiu); // floor：向下取整
        if(maxx < 1){ // 可容纳少于一个篮球
            cout << -1 << endl;
            continue; // 提前结束
        }
        double s = log(maxx) / log(k); // 换底公式
        long long l = floor(s); // 向下取整
        cout << l << "\n";
    }
    return 0;
}

时间复杂度： $O(T)$

预计得分： $120pts$

注意：虽然这份代码时间复杂度更低，但是由于多次的数学计算，可能导致精度丢失，面对没有 Special Judge 的或者精度要求更高的题目题目可能会 WA，所以不推荐这种解法。

T3 重要の春联：模拟

难度：红中位

正解

这是一道简单的输出题，找到公式直接输出即可。然而，作者似乎并不满意1e9的数据范围，把数据大小开到1e12，因此需要 long long 储存。右下角的坐标根据图片模拟易得：横坐标是横幅的宽+竖幅的长+横幅的宽；竖坐标是竖幅的长+横幅的长。

#include<bits/stdc++.h>
using namespace std;
int main(){
    long long a,b,x,y; cin >> a >> b >> x >> y;
    cout << a + y + a << " " << x + b;
    return 0;
}

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

预计得分： $140pts$

T4 时空の穿越：矩阵

难度：绿下位

题意简化

给定序列 $F$ ，有：

$\begin{equation*} F_i= \begin{cases} 1, & 1\le (i\le 5)\\ F_{i-1}+2\times F_{i-2}+3\times F_{i-3}+5\times F_{i-4}+8\times F_{i-5}, & (i \ge 6)\\ \end{cases} \end{equation*}$

求 $Ans$ ，其中：

$\begin{equation*} Ans= \begin{cases} F_N\mod 2^{32}, & F_N\mod 2^{32}\lt 2^{31}\\ (F_N\mod 2^{32})-2^{32}, & F_N\mod 2^{32}\ge 2^{31}\\ \end{cases} \end{equation*}$

暴力代码

很显然的一个递推式子。直接模拟一下即可。

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
ull _,n;
ull dp[1005];
int main(){
    cin>>_;
    while(_--){
        cin>>n;
        dp[1]=dp[2]=dp[3]=dp[4]=dp[5]=1;
        for(ull i=6;i<=n;i++) dp[i]=
            dp[i-1]+
            (dp[i-2]<<1)+
            (dp[i-3]<<1)+dp[i-3]+
            (dp[i-4]<<2)+dp[i-4]+
            (dp[i-5]<<3);
        cout<<(int)dp[n]<<'\n';
    }
    return 0;
}

时间复杂度： $O(TN)$

空间复杂度： $O(N)$

预计得分： $30pts$

空间优化

显然 $dp_i$ 只与 $dp_{i-1},dp_{i-2},dp_{i-3},dp_{i-4},dp_{i-5}$ 有关。所以我们只需要记录 $6$ 个数即可。

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
ull _,n,a,b,c,d,e,t;
int main(){
    cin>>_;
    while(_--){
        cin>>n;
        a=b=c=d=e=1;
        for(ull i=6;i<=n;i++){
            t=a;
            a=b;
            b=c;
            c=d;
            d=e;
            e+=(c<<1)+(b<<1)+b+(a<<2)+a+(t<<3);
        }
        cout<<(int)e<<'\n';
    }
    return 0;
}

时间复杂度： $O(TN)$

空间复杂度： $O(1)$

预计得分： $30pts$

正解

由线性递推联想到矩阵加速。

回忆一下斐波那契数列的矩阵加速：定义矩阵：

$\begin{bmatrix} F_{n} \\ F_{n-1} \end{bmatrix}$

得到：

$M \times \begin{bmatrix} F_{n-1} \\ F_{n-2} \end{bmatrix} =\begin{bmatrix} F_{n} \\ F_{n-1} \end{bmatrix}$

根据矩阵乘法，得到：

$M_{1,1} \times F_{n-1}+ M_{1,2} \times F_{n-2} = F_n \\ M_{2,1} \times F_{n-1} + M_{2,2} \times F_{n-2} = F_{n-1}$

所以得到：

$M = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}$

于是问题转化为：

$\begin{bmatrix} 1 \\ 1 \end{bmatrix} \times M^{n-1}$

矩阵快速幂即可。

类似地，我们定义矩阵：

$\begin{bmatrix} F_n \\ F_{n-1} \\ F_{n-2} \\ F_{n-3} \\ F_{n-4} \end{bmatrix}$

得到：

$M \times \begin{bmatrix} F_{n-1} \\ F_{n-2} \\ F_{n-3} \\ F_{n-4} \\ F_{n-5} \end{bmatrix} = \begin{bmatrix} F_n \\ F_{n-1} \\ F_{n-2} \\ F_{n-3} \\ F_{n-4} \end{bmatrix}$

根据矩阵乘法，得到：

$M_{1,1} \times F_{n-1} + M_{1,2} \times F_{n-2} + M_{1,3} \times F_{n-3} + M_{1,4} \times F_{n-4} + M_{1,5} \times F_{n-5}=F_n\\ M_{2,1} \times F_{n-1} + M_{2,2} \times F_{n-2} + M_{2,3} \times F_{n-3} + M_{2,4} \times F_{n-4} + M_{2,5} \times F_{n-5}=F_{n-1}\\ M_{3,1} \times F_{n-1} + M_{3,2} \times F_{n-2} + M_{3,3} \times F_{n-3} + M_{3,4} \times F_{n-4} + M_{3,5} \times F_{n-5}=F_{n-2}\\ M_{4,1} \times F_{n-1} + M_{4,2} \times F_{n-2} + M_{4,3} \times F_{n-3} + M_{4,4} \times F_{n-4} + M_{4,5} \times F_{n-5}=F_{n-3}\\ M_{5,1} \times F_{n-1} + M_{5,2} \times F_{n-2} + M_{5,3} \times F_{n-3} + M_{5,4} \times F_{n-4} + M_{5,5} \times F_{n-5}=F_{n-4}$

所以得到：

$M = \begin{bmatrix} 1 & 2 & 3 & 5 & 8\\ 1 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 0\\ \end{bmatrix}$

于是问题转化为：

$M^{n-5} \times \begin{bmatrix} 1\\ 1\\ 1\\ 1\\ 1 \end{bmatrix}$

矩阵快速幂即可。

#include<bits/stdc++.h>
using namespace std;
#define uint unsigned int
#define ull unsigned long long
#define rep(i,l,r) for(int i=l;i<=r;i++)
struct mat{
    int n,m;
    uint a[7][7];
    inline void empty(){
        this->n=this->m=0;
        memset(this->a,0,sizeof(this->a));
        return;
    }
    inline void resize(const int &n,const int &m){
        empty();
        this->n=n,this->m=m;
        return;
    }
    inline void unit(const int &n){
        empty();
        this->n=this->m=n;
        rep(i,1,n) this->a[i][i]=1;
        return;
    }
    inline void fill(const int &x){
        rep(i,1,this->n) rep(j,1,this->m) this->a[i][j]=x;
        return;
    }
    inline mat operator*(const mat &a){
        mat res;
        res.resize(this->n,a.m);
        rep(i,1,res.n) rep(j,1,res.m) rep(k,1,this->m) res.a[i][j]+=this->a[i][k]*a.a[k][j];
        return res;
    }
    inline void operator*=(const mat &a){
        *this=*this*a;
        return;
    }
};
int _;
ull n;
mat x,y,res;
int main(){
    cin>>_;
    while(_--){
        cin>>n;
        if(n>5) n-=5;
        else{
            cout<<"1\n";
            continue;
        }
        x.resize(5,1);
        x.fill(1);
        y.resize(5,5);
        y.a[1][1]=y.a[2][1]=y.a[3][2]=y.a[4][3]=y.a[5][4]=1;
        y.a[1][2]=2,y.a[1][3]=3,y.a[1][4]=5,y.a[1][5]=8;
        res.unit(5);
        while(n){
            if(n&1) res*=y;
            y*=y;
            n>>=1;
        }
        res*=x;
        cout<<(int)(res.a[1][1])<<'\n';
    }
    return 0;
}

时间复杂度： $O(T \log N)$

空间复杂度： $O(1)$

预计得分： $100pts$

T5 可恶の施工：最小生成树、贪心

难度：绿中位

题意简化

给定一个无向带权连通图，求在保证图连通的前提下，最少删除多少条边使得剩余边的总权值不超过给定的限制 $p$ 。若无法满足条件，输出 -1。

关键观察

最优解的结构一定是 保留权值较小的边，同时保证图的连通性。
这与 最小生成树 (MST) 的性质一致：MST 是权值和最小的连通子图。
因此，问题转化为：在 MST 的基础上，尽可能多地保留权值小的额外边，使得总权值不超过 $p$ 。

算法思路

构建最小生成树：
- 使用 Kruskal 算法求出 MST，记录其权值和 $sum_{\text{MST}}$ 和使用的边数 $n-1$ 。
- 若 $sum_{\text{MST}} > p$ ，直接输出 -1（无解）。
贪心添加额外边：
- 将 非 MST 边 按权值从小到大排序。
- 依次尝试添加这些边，直到总权值超过 $p$ 。
- 最终删除的边数为 总边数 $m$ - 保留的边数。

时间复杂度分析

Kruskal 算法：排序边 $O(m \log m)$ ，并查集操作 $O(m \alpha(n))$ ，总体 $O(m \log m)$ 。
贪心添加额外边：遍历至多 $m$ 条边， $O(m)$ 。
总复杂度： $O(T \cdot m \log m)$ ，其中 $T$ 为测试用例数量。

部分分策略

测试点	数据范围	特殊性质	可用算法	预计得分
1-2	$N, M \leq 10$	无	暴力枚举删边组合	10pts
3-4	$N, M \leq 100$	无	枚举保留边数 + Kruskal	30pts
5	$N \leq 10^5, M \leq 2e5$	所有边权相等	贪心保留最多边	25pts
6	$M = N-1$ （树结构）	树边权和是否超过 $p$	直接判断 $sum \leq p$	10pts
7-10	$N \leq 10^5, M \leq 2e5$	无	正解算法	100pts

特殊性质说明：

性质 A：所有边权相等时，保留尽可能多的边即可，无需考虑权值大小。
性质 B：图为树时，若 $sum_{\text{MST}} > p$ 则无解，否则必须保留全部树边（不能删除任何边，否则不连通）。

正解代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#define int long long
using namespace std;
struct node{
	int from, to, len;
	bool operator < (const node &b) const{
		return len < b.len;
	}
}edge[100005], edge2[100005];
int father[100005];
int find(int n){return (father[n] == n ? n : father[n] = find(father[n]));}
bool merge(int x, int y){
	int n = find(x), m = find(y);
	if(n == m) return 0;
	father[min(n, m)] = max(n, m);
	return 1;
}
int n, m, k, ct, ctt, cttt;
void solve(){
	cin >> n >> m >> k;
	ct = ctt = cttt = 0;
	for(int i = 1; i <= n; i++) father[i] = i;
	for(int i = 1; i <= m; i++){
		cin >> edge[i].from >> edge[i].to >> edge[i].len;
	}
	sort(edge + 1, edge + m + 1);
	for(int i = 1; i <= m; i++){
		if(merge(edge[i].from, edge[i].to)){
			ct++;
			ctt += edge[i].len;
			if(ct == n - 1){
				for(int j = i + 1; j <= m; j++) edge2[++cttt] = edge[j];
				break;
			}
		}else{
			edge2[++cttt] = edge[i];
		}
	}
	if(ctt > k || ct < n - 1){
		cout << "NO\n";
		return;
	}
	for(int i = 1; i <= cttt; i++){
		ctt += edge2[i].len, ct++;
		if(ctt > k){
			cout << m - ct + 1 << '\n';
			return;
		}
	}
	cout << "0\n";
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int t;
	cin >> t;
	while(t--) solve();

	return 0;
}

T6 散落の字符：Manacher算法、大模拟

难度：蓝中位

题意说明

本次题目比较复杂，需要我们计算以下问题的答案。

通过迷宫的最小花费 $sum$ 。
转换 $sum$ 并拼接到 $s$ 后面，转换 $s$ 为 01 字符串。
计算转换为偶回文串最小花费 $f$ 的值。
连接 $t$ 和 $s$ ，计算最长回文串 $l$ 的值。

走迷宫

这一部分采用任何搜索算法均可。期待大家给出~~出题组没做出来的~~ dp 的办法。以下是 dijkstra 的做法：

struct Node {
    int x, y, cost;
    bool operator<(const Node& other) const {
        return cost > other.cost; // 最小堆
    }
};

void dijkstra() {
    priority_queue<Node> pq;
    pq.push({1, 1, migong[1][1]});
    vis[1][1] = true;

    while (!pq.empty()) {
        Node current = pq.top();
        pq.pop();
        int x = current.x, y = current.y, cost = current.cost;

        if (x == n && y == m) {
            ret = cost;
            return;
        }

        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 1 || nx > n || ny < 1 || ny > m || vis[nx][ny]) {
                continue;
            }
            vis[nx][ny] = true;
            pq.push({nx, ny, cost + migong[nx][ny]});
        }
    }
}

转换与拼接

这一部分直接采用模拟即可。一个字符的ASCII码值为偶数是 $\bmod2$ 的结果为 $0$ ，否则为 $1$ 。

a=to_string(ret);
cin>>b;
d+=b;
for (int i = 0;i < a.size();++i){
	if (a[i]=='0'){
		d+=d[d.size()-1];
	}else{
		d+=monib[a[i]-'0'];
	}
}
for (int i = 0;i < d.size();++i){
	d[i]=((int)d[i])%2+'0';
}
t=d;
cin>>c;
c+=d;

计算 f 的值

在这一步中，我们需要推理一下。数据保证 $s$ 可以转化为偶回文串，说明 $s + min_a$ 的结果是偶数或者拼接后的 $s$ 的中间值为 $0$ 。如果是第二种可能，就只需要保证其它部分是偶回文串即可。

因此无论如何，只要保证拼接后的 $s$ 是一个回文串即可保证是偶回文串。我们只需要从 $i=0$ 一直到 $i=|s|\div2$ 遍历一遍，找到改变成偶回文串的最小花费。对于每个第 $i$ 项，我们只需考虑是改变成 0 还是 1 的花费更小。

for(int i = 0;i < d.size() / 2;i++){
  if(d[i] == d[d.size() - i - 1]) continue;
  else ans1 += min(w[i],w[d.size() - i - 1]);
}

计算 l 的值

暴力做法：枚举每一段 l 中的子串。代码如下：

for(int i = 0;i < l.size();i++){
    for(int j = i + 1;j < l.size();j++){
        if(hw(l.substr(i,j + 1))) maxx = max(maxx,j - i + 1);
    }
}

时间复杂度： $O(|l|^2)$

预计得分： $50pts$

我们可以使用 Manacher 算法来解决 $l$ 的计算。回文自动机的 Manacher 算法可以在 $O(N)$ 时间中解决最长回文子串问题。

下面就是模板的 Manacher 算法了（这里使用 % 避免边界问题，若有想要深入学习的请见：这里）：

int alen=c.size(),len=2;
s[0]='%';
s[1]='#';
for (int i=0;i<alen;++i){
    s[len++]=c[i];
    s[len++]='#';
}
s[len]='#';
int mid=1,r=1,ans1=-1;
for (int i=1;i<=len;++i){
    maxs[i]=0;
}
for (int i=1;i<=len;++i){
    if (i<r){
        maxs[i]=min(r-i,maxs[mid*2-i]);
    }else{
        maxs[i]=1;
    }
    while (s[i-maxs[i]]==s[i+maxs[i]]){
        maxs[i]+=1;
    }
    if (r<i+maxs[i]){
        mid=i;
        r=i+maxs[i];
    }
    ans1=max(maxs[i]-1,ans1);
}

时间复杂度： $O(|l|)$

预计得分： $200pts$

正解

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int hmod = 1e9 + 7, base = 31;
int n, m, migong[333][333], dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};
long long w[200025], dp[200010], ret = 1e13;
bool vis[333][333];
char monib[30] = {'0', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i'};
string a, b, c, d, t;
char s[13000000];
int maxs[13000000];

struct Node {
    int x, y, cost;
    bool operator<(const Node& other) const {
        return cost > other.cost; // 最小堆
    }
};

void dijkstra() {
    priority_queue<Node> pq;
    pq.push({1, 1, migong[1][1]});
    vis[1][1] = true;

    while (!pq.empty()) {
        Node current = pq.top();
        pq.pop();
        int x = current.x, y = current.y, cost = current.cost;

        if (x == n && y == m) {
            ret = cost;
            return;
        }

        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 1 || nx > n || ny < 1 || ny > m || vis[nx][ny]) {
                continue;
            }
            vis[nx][ny] = true;
            pq.push({nx, ny, cost + migong[nx][ny]});
        }
    }
}

signed main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> migong[i][j];
        }
    }

    dijkstra();
    a = to_string(ret);
    cin >> b;
    d += b;
    for (int i = 0; i < a.size(); ++i) {
        if (a[i] == '0') {
            d += d[d.size() - 1];
        } else {
            d += monib[a[i] - '0'];
        }
    }
    for (int i = 0; i < d.size(); ++i) {
        d[i] = ((int)d[i]) % 2 + '0';
    }
    t = d;
    cin >> c;
    c += d;
    int alen = c.size(), len = 2;
    s[0] = '%';
    s[1] = '#';
    for (int i = 0; i < alen; ++i) {
        s[len++] = c[i];
        s[len++] = '#';
    }
    s[len] = '#';
    int mid = 1, r = 1, ans1 = -1;
    for (int i = 1; i <= len; ++i) {
        maxs[i] = 0;
    }
    for (int i = 1; i <= len; ++i) {
        if (i < r) {
            maxs[i] = min(r - i, maxs[mid * 2 - i]);
        } else {
            maxs[i] = 1;
        }
        while (s[i - maxs[i]] == s[i + maxs[i]]) {
            maxs[i] += 1;
        }
        if (r < i + maxs[i]) {
            mid = i;
            r = i + maxs[i];
        }
        ans1 = max(maxs[i] - 1, ans1);
    }
    for (int i = 0; i < t.size(); ++i) {
        cin >> w[i];
    }
    n = t.size();
    for (int i = 0; i < d.size() / 2; ++i) {
        if (d[i] == d[d.size() - i - 1]) continue;
        else ans1 += min(w[i], w[d.size() - i - 1]);
    }
    cout << ans1 << "\n";
    return 0;
}

时间复杂度： $O(n\times m\times \log{n\times m}))$

预计得分： $200pts$

有帮助，赞一个

去预览

0/2000

全部评论 6

Lyzc0dr
马拉车、矩阵加速……COCR普及赛有点可怕

2025-04-17 来自浙江
0
- MuktorFM
  回复
  Lyzc0dr
  不超纲
  
  2025-04-17 来自云南
  0
dream92143
抽象の难度分布

2025-04-12 来自江苏
0
#AP.
有题解了吗

2025-04-12 来自浙江
0
咕咕咕
?

2025-03-03 来自江西
0
- 秦桧的宣言
  回复
  咕咕咕
  还有徽章
  
  2025-04-07 来自浙江
  0
- 咕咕咕
  回复
  秦桧的宣言
  是不是回复错人了
  
  2025-04-07 来自江西
  0
- MuktorFM
  回复
  秦桧的宣言
  下个月挑战赛奖池多得很
  
  2025-04-08 来自云南
  0
cjj
奖品只有盲盒嘛

2025-03-03 来自广东
0
cjdst
？？？

2025-03-02 来自广东
0