AcWing 蓝桥杯 2025 每日一题

AcWing 蓝桥杯集训 2025 每日一题
Start: 2025.03.03
End: Doing
Plan: PM 22:30-23:30

蓝桥杯集训2025每日一题

Week-1

1. 农夫约翰的奶酪块

参考：6122

超出时间限制：Time Limit Exceeded

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <vector>
using namespace std;

// 切割一次，返回本次新增的方案数
int cutOne(int x, int y, int z, vector<vector<vector<bool>>>& block){
    int N = block.size();
    // 切割本位置
    block[x][y][z] = false;
    
    // 检测这个方块所在的三个方向
    int count = 0, i;
    for(i=0; i<N && block[i][y][z]==false; i++)  ;
    if(i==N)  count++;
    for(i=0; i<N && block[x][i][z]==false; i++)  ;
    if(i==N)  count++;
    for(i=0; i<N && block[x][y][i]==false; i++)  ;
    if(i==N)  count++;
    
    // 返回本次新增的方案数
    return count;
}


int main(){
    // 输入
    int N, Q;
    cin >> N >> Q;
    vector<vector<vector<bool>>> block(N, vector<vector<bool>>(N, vector<bool>(N, true)));
    
    // 处理
    int ans = 0;
    for(int i=0; i<Q; i++){
        int x, y, z;
        cin >> x >> y >> z;
        ans += cutOne(x, y, z, block);
        cout << ans << endl;
    }
    
    
    return 0;
}

时间复杂度：O(N)O(N).

空间复杂度：O(N3)O(N^3).

Accepted

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1010;

// 实际上不需要三维，用二维去计数对应位置的第三方向被切割了多少个即可
int a[N][N], b[N][N], c[N][N];
int n, q;

int main(){
    cin >> n >> q;
    
    int ans = 0;
    for(int i=0; i<q; i++){
        int x, y, z;
        cin >> x >> y >> z;
        a[x][y]++, b[y][z]++, c[x][z]++;
        if(a[x][y] == n)  ans++;
        if(b[y][z] == n)  ans++;
        if(c[x][z] == n)  ans++;
        cout << ans << endl;
    }
    
    return 0;
}

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

空间复杂度：O(N2)O(N^2).

2. 哞叫时间

参考：6123

Accepted

本题解法就是暴力。

并不是所有的题目都需要什么巧解，你要知道，解题就是穷举所有的可能！

那么对于这种已经告知了全是小写字母的，而且长度固定的，显然 abb 式是可以枚举的！

而匹配只需要一轮遍历即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

int main(){
    // 输入
    int n, f;
    string s;
    cin >> n >> f;
    cin >> s;
    
    vector<string> ans;
    // 均是小写字母，直接穷举所有的abb式  O(26*25*N)
    for(char a='a'; a<='z'; a++){
        for(char b='a'; b<='z'; b++){
            if(a == b)  continue;   // 题目要求是不能一样
            
            // 查找已经存在的abb
            string ts = s;
            int cnt = 0;
            for(int i=0; i+2<n; i++){
                if(ts[i]==a and ts[i+1]==ts[i+2] and ts[i+1]==b){
                    ts[i] = ts[i+1] = ts[i+2] = '#';    // 占位符
                    cnt++;
                }
            }
            
            // 查找剩下的修改一次能否达到 abb 的
            int flag = 0;
            for(int i=0; i+2<n; i++){
                if(ts[i]=='#' or ts[i+1]=='#' or ts[i+2]=='#')  continue;
                if(ts[i]==a and ts[i+1]==b or ts[i]==a and ts[i+1]==b or ts[i+1]==b and ts[i+2]==b){
                    flag = 1;
                    break;
                }
            }
            
            // 能否达到 f 次
            if(cnt + flag >= f){
                string path = "";
                path+=a, path+=b, path+=b;
                ans.push_back(path);
            }
        }
    }
    
    // 输出答案
    cout << ans.size() << endl;
    for(string &ts : ans)  cout << ts << endl;
    
    return 0;
}

时间复杂度：O(26×25×N)O(26\times 25\times N).

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

Accepted

每个位置都修改一次（改为 26 个任意字母），来检测。再加上检查一整条字符串，就会是O(N×26×N)O(N \times 26 \times N) 不行！

但是，可以优化，你发现，实际上修改一个字母，只会影响局部的几个字符串的统计情况，因此，并不需要全部重新统计。

所以，先统计一遍字符串的匹配情况O(N)O(N)，再每个位置修改一次字符O(N×26)O(N \times 26)，然后只需要把影响的局部的统计情况更新一下即可O(1)O(1)，总的复杂度是 O(N+N×26×1)=O(26×N)O(N + N\times 26 \times 1) = O(26\times N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 20010, M = 26;

int n, f;
string S;

int cnt[M][M];  // cnt[a][b] 表示 abb 出现的次数
bool ans[M][M]; // ans[a][b] true表示abb是一个正确答案 

// 检查从 l 到 r 出现的 abb 式，令abb变化v大小
void update(int l, int r, int v){
    // 防越界
    l = max(0, l), r = min(n-1, r);
    for(int i=l; i+2<=r; i++){
        char a = S[i], b = S[i+1], c = S[i+2];
        if(a!=b and b==c)
            cnt[a-'a'][b-'a'] += v; // v 可能会是 -1 或 1
        if(cnt[a-'a'][b-'a'] >= f)
            ans[a-'a'][b-'a'] = true;
    }
}

int main(){
    cin >> n >> f;
    cin >> S;
    
    // 统计全部情况
    update(0, n-1, 1);
    
    // 查找改变一个位置
    for(int i=0; i<n; i++){
        // 可以改为任意字母（改之前还得把被改位置的原计数-1）
        update(i-2, i+2, -1);
        char t = S[i];
        for(int c='a'; c<='z'; c++){
            if(S[i] == c)  continue;
            S[i] = c;
            // 改完之后，只影响局部，只需要更新局部，这一点很重要！
            update(i-2, i+2, 1);
            // 改回去
            update(i-2, i+2, -1);
        }
        // 恢复字母，还要把改动原计数+1
        S[i] = t;
        update(i-2, i+2, 1);
    }
    
    // 输出答案
    vector<string> allS;
    for(int i=0; i<M; i++){
        for(int j=0; j<M; j++){
            if(ans[i][j]){
                string t = "";
                t += i+'a', t += j+'a', t += j+'a';
                allS.push_back(t);
            }
        }
    }
    
    cout << allS.size() << endl;
    for(string &t : allS)  cout << t << endl;

    return 0;
}

时间复杂度：O(26×N)O(26\times N).

空间复杂度：O(26×26)O(26\times 26).

3. 蛋糕游戏

参考：6118

Time Limit Exceeded

这种做法肯定是能正确，但是超时了，我是直接模拟过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
// 超时 Time Limit Exceeded
#include <iostream>
#include <vector>
using namespace std;


void game(vector<int>& a){
    // 一直玩游戏，直到吃完
    int bSum = 0, eSum = 0;
    while(true){
        // b先堆叠最大的中间两个
        int n1 = a.size();
        // 多余 4 个，则往中间堆叠
        if(n1 >= 4){
            int maxi = 1;
            for(int i=1; i+1<n1-1; i++)
                if(a[i]+a[i+1] > a[maxi]+a[maxi+1])  maxi = i;
            a.insert(a.begin()+maxi, a[maxi]+a[maxi+1]);
            a.erase(a.begin()+maxi+1);
            a.erase(a.begin()+maxi+1);
        }
        // 只有2个，则直接堆叠吃掉
        else{
            bSum = a[0]+a[1];
            break;
        }
        
        // e 开始吃左右两边的
        int n2 = a.size();
        if(a[0] > a[n2-1]){
            eSum += a[0];
            a.erase(a.begin()+0);
        }
        else{
            eSum += a[n2-1];
            a.erase(a.begin()+n2-1);
        }
    }
    
    // 吃完了，输出结果
    cout << bSum << " " << eSum << endl;
}

int main(){
    // 输入
    int T;
    cin >> T;
    for(int i=0; i<T; i++){
        int N;
        cin >> N;
        vector<int> a(N);
        for(int j=0; j<N; j++)  cin >> a[j];
        game(a);
    }
    
    return 0;
}

时间复杂度：每个小测试O(N2)每个小测试O(N^2).

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

Accepted

要看透本质。这实际上是左右脑互搏。（先手奶牛称为“左脑”，后手奶牛称为“右脑”）

最终互搏的结果是“左脑吃了序列中间的一段区域的蛋糕”“右脑吃了左侧的一部分和右侧的一部分，且，右脑总是吃了左右端点中较大的那个，但较大的那个有可能是左脑合成的蛋糕！（重点）”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// 重新思考，你会发现，实际上只有e有选择权
// b只要足够贪心，就不会堆叠任何e能够吃到的蛋糕
// 那么就只需要把e的能吃的情况都枚举出来，选择最优的就是答案（e才有选择权）
// 同时，可以直接算出b是比e多吃两个蛋糕的，即b=e+2,那么 2e+2 = n，故e = (n-2)/2
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


void game(vector<long long>& sum, int N){
    // 直接枚举e的所有拿取情况，即直接从左右两边拿，一共拿走e个
    // 问：为什么不会吃更多？因为b会想尽办法让e吃不到任何自己堆叠了的蛋糕！
    int e = (N-2)/2;
    long long bSum = 0, eSum = 0;
    
    // 左边吃k个，右边吃e-k个
    for(int k=0; k<=e; k++)
        eSum = max(eSum, sum[k] + sum[N] - sum[N-(e-k)]);
    
    // 计算b吃的即可
    bSum = sum[N] - eSum;
    
    // 输出
    cout << bSum << " " << eSum << endl;
}

int main(){
    int T;  cin >> T;
    while(T--){
        int N;  cin >> N;
        vector<long long> a(N+1);
        vector<long long> sum(N+1);     // sum[i] 表示前i个元素和
        sum[0] = 0;
        for(int i=1; i<=N; i++){
            cin >> a[i];  sum[i] = sum[i-1]+a[i];   // 直接预处理
        }
        
        // 进行游戏
        game(sum, N);
    }
    
    return 0;
}

时间复杂度：每个小测试O(N)每个小测试O(N).

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

4. 哞叫时间II

参考：6134.哞叫时间II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
using namespace std;

const int N = 1000010;
long long ans = 0;

int a[N];
int cnt1[N];    // cnt[i] 表示数字i出现的次数
int unique[N];  // unique[i] 表示索引i之前的不同数字的数量
int cnt2[N];


int main(){
    int n;  cin >> n;
    for(int i=0; i<n; i++)  cin >> a[i];
    
    // 先统计到达i时，前面已经出现多少个不同的数字
    for(int i=0; i-1<n; i++){
        cnt1[a[i]]++;
        if(cnt1[a[i]] == 1)  unique[i+1] = unique[i]+1;
        else unique[i+1] = unique[i];
    }
    
    // 从后往前看，找到第两个相同数字时，就开始计入答案
    for(int i=n-1; i>=0; i--){
        cnt2[a[i]]++;
        if(cnt2[a[i]] == 2){
            ans += unique[i];
            // 如果其实前面有这个数字，说明多算了一个不同数字
            if(cnt1[a[i]] > 2)  ans--;
        }
    }
    
    cout << ans;
    
    return 0;
}

时间复杂度：O(N)O(N).

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

5. 奶牛体验

参考：6135.奶牛体验

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <vector>
using namespace std;

const int N = 7510;

int a[N];
int b[N];
int n;
int ans[N];     // 存储输出答案
int correct[N]; // correct[i] 表示i之前的所有对应正确的数量

void check(int l, int r){
    int sum = 0;
    // 查看反转部分的正确对应数量
    for(int i=0; i<=r-l; i++)
        if(a[l+i] == b[r-i])
            sum++;
    
    // 未反转部分的正确对应数量
    sum += l-1>=0 ? correct[l-1] : 0;
    sum += r<n-1? correct[n-1]-correct[r] : 0;
    
    // 收集答案
    ans[sum]++;
}

int main(){
    cin >> n;
    for(int i=0; i<n; i++)  cin >> a[i];
    cin >> b[0];
    if(a[0] == b[0])  correct[0] = 1;
    for(int i=1; i<n; i++){
        cin >> b[i];
        correct[i] = correct[i-1];
        if(a[i] == b[i])  correct[i]++;
    }
    
    // 两层遍历即可
    for(int l=0; l<n; l++)
        for(int r=l; r<n; r++)
            check(l, r);
    
    // 输出
    for(int i=0; i<=n; i++)  cout << ans[i] << endl;
    
    
    return 0;
}

时间复杂度：O(N3)O(N^3).

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
using namespace std;

const int N = 7510;

int a[N];
int b[N];
int n;
int ans[N];     // 输出答案
int dp[N][N];   // dp[i][j] 表示反转i,j之后正确对应的数量


int main(){
    cin >> n;
    for(int i=1; i<=n; i++)  cin >> a[i];
    for(int i=1; i<=n; i++)  cin >> b[i];
    
    // 计算初始不改变顺序时，有多少正确对应的
    int cnt = 0;
    for(int i=1; i<=n; i++)  if(a[i] == b[i])  cnt++;
    
    // 只交换一个，即本身
    for(int i=1; i<=n; i++){
        dp[i][i] = cnt;
        ans[dp[i][i]]++;
    }
    
    // 交换相邻两个
    for(int i=1; i<=n-1; i++){
        dp[i][i+1] = cnt + (a[i]==b[i+1]) + (a[i+1]==b[i]) - (a[i]==b[i]) - (a[i+1]==b[i+1]);
        ans[dp[i][i+1]]++;
    }
    
    // 交换其他的[i, i+len]
    for(int len=2; len<=n-1; len++){
        for(int i=1; i+len<=n; i++){
            // 状态转移
            dp[i][i+len] = dp[i+1][i+len-1] + (a[i]==b[i+len]) + (a[i+len]==b[i]) - (a[i]==b[i]) - (a[i+len]==b[i+len]);
            // 更新答案
            ans[dp[i][i+len]]++;
        }
    }
    
    // 输出答案
    for(int i=0; i<=n; i++)  cout << ans[i] << endl;
    
    return 0;
}

时间复杂度：O(N2)O(N^2).

空间复杂度：O(N2)O(N^2).

Week-2

6.

参考：

1

时间复杂度：O()O().

空间复杂度：O()O().

1

时间复杂度：O()O().

空间复杂度：O()O().

评论
avatar
isSeymour
志之所趋，无远弗届，穷山距海，不能限也。
文章
73
标签
36
分类
10
Follow Me
最新文章
Transformer 开山之作
Transformer 开山之作
大模型推荐系统 (应用)
大模型推荐系统 (应用)
大模型推荐系统（4）直接推荐范式
大模型推荐系统（4）直接推荐范式
分类
标签
C/C++前后端分离Transformer汇编语言AssemblyGNN计算机视觉计网实验原神颜色素材ML密码学数据库系统原理数字逻辑实验数据结构后端GCNNode2VecDeepWalkPageRankDL身份认证LLMLaTeXLinux现代密码学Markdwon监督学习理论PHPPythonPyTorchPandas正则表达式SQLCTFWEB技术sqlmap
归档
网站资讯
文章数目 :
73
已运行时间 :
本站总字数 :
378.2k
本站访客数 :
本站总访问量 :
最后更新时间 :