首页 > 其他分享 >[暴力题解系列]2023年蓝桥杯-子串简写

[暴力题解系列]2023年蓝桥杯-子串简写

时间:2024-03-23 20:23:46浏览次数:28  
标签:遍历 暴力 int 题解 蓝桥 2023 c2 c1 type

​ 大伙都说暴力是最低级的算法,啊那确实。但是好的暴力才是真正牛逼的骗分。

咱就是说,暴力如何骗分呢?就是基于最暴力的算法一步步优化到能得更多分的暴力。

子串简写这题,首先第一步就能想到一件事情:暴力枚举子串开头和末尾的位置,检查是否是符合题目要求的字符,如果是,并且长度大于k,那就给答案加1。这是大伙都能想到的最基础的东西

#include<iostream>
#include<string>
using namespace std;
int main()
{
    int k;
    int cnt = 0;
    scanf("%d", &k);
    string a;
    cin>>a;
    char c1, c2;
    cin>>c1>>c2;
    for(int i=0; i<a.size()-k+1; i++)
    {
        if(a[i] != c1)
            continue;
        for(int j=i+k-1; j<a.size(); j++)
        {
            if(a[i] == c1 && a[j] == c2)
            {
                cnt++;
                /*for(int k=0; k<a.size(); k++)
                {
                    if(k == i || k == j)
                        cout<<"|";
                    cout<<a[k];
                }
                cout<<endl;*/
            }
        }
    }
    cout<<cnt<<endl;
    return 0;
}

那么蓝桥网官网的测试结果如何呢?

QQ截图20240323192319.png

兄弟,已经有70%的分了,蓝桥杯用暴力打真的不是问题。


​ 那么在这之上还能怎么优化呢?很快我们就能发现时间复杂度主要来自于遍历整个数组,那么有什么方法抛弃掉无用数据,只遍历有用的地方呢?显而易见,我们只需要记录符合题目要求的位置就好了,然后我们再在记录好位置的数组里进行遍历。代码在下面,详细在代码内解释:

#include<iostream>
#include<string>
#include<vector>
using namespace std;
struct vec2{	//这里是记录每个符合条件的所有信息,其实应该改名叫vec3了(笑)
    int x, type, total;
    /*
    	x:原数组位置
    	type:哪一种字符
    	total:记录当前位置之前有多少个同类型的字符
    */
};	
int main()
{
    int k;
    int cnt = 0;
    scanf("%d", &k);
    string a;
    cin>>a;
    char c1, c2;
    cin>>c1>>c2;
    int c1Cnt=0, c2Cnt=0;
    vector<vec2> dat;
    for(int i=0; i<a.size(); i++)
    {
        if(a[i] == c1)
        {
            c1Cnt ++;	//录入,并且增加总数目
            dat.push_back({i, 1, c1Cnt});
        }
        else if(a[i] == c2)
        {
            c2Cnt ++;	//其实这个没啥必要
            dat.push_back({i, 2, c2Cnt});
        }
    }
    for(int i=0; i<dat.size(); i++)
    {
        if(dat[i].type == 2)	//找到以c2结尾的数据
        {
            for(int j=i-1; j>=0; j--)	//向前寻找c1的数据
            {
                if(dat[j].type == 1 && dat[i].x - dat[j].x + 1 >=k)
                {
                    cnt+=dat[j].total;
                    /*
	为什么这里会记录当前位置之前有多少个呢?其实一开始我并没有记录这个东西,但是我突然意识到,如果还要反复往前遍历所有的type 1数据,又会是一个常数级的浪费时间。但是在C++暴力指南里我也写过,任何常数级的时间都不可浪费。而在这里,如果你还需要反复遍历整个数组的前半部分,那就约等于O(n logn)(此处的n是指vector的长度)的复杂度,最坏情况会变成O(n^2)[即前面一大堆type 1数据类型,只有最后一位是type 2]。但是如果提前记录了之前的个数,那么在随机数据的情况下时间复杂度一般来说相当于一个比较小的常数,最坏情况下也只需要O(n)的复杂度就可以完成。因为遍历到末尾之后只需要找到上一个type 1然后加上总和即可。
                    */
                    break;
                }
            }
        }
    }
    cout<<cnt<<endl;
    return 0;
}

那么这个代码的结果如何呢?image-20240323193913308.png

兄弟,又多2个点啊兄弟。不过为什么还有一个点没过呢?他不是TLE,而是WA。

​ 回到代码,可以发现一个很大的问题,如果c1和c2是一样的字符呢?那么他就会一直认为数据里的都是c1,就不存在c2了,这时候就需要额外特判一下。把这个问题改完那就直接完美的用暴力拿下这题了,嘛,不过我现在要偷懒啦不想改啦。

标签:遍历,暴力,int,题解,蓝桥,2023,c2,c1,type
From: https://www.cnblogs.com/ComputerEngine/p/18091616

相关文章

  • 2023年红蓝对抗-HW蓝队基本知识点
    1.Linux排查思路(1)首先检测用户账号安全,如新增用户和可疑用户以及高权限用户。(2)history命令查看历史linux指令,uptime查看用户登录信息(3)检查端口(netstat命令)和进程(ps命令),重点观察资源占用率高的进程(4)检查日志信息,var/log文件夹内的一些系统日志和安全日志。(5)利用自动......
  • 【蓝桥杯】(3.19矩形总面积)
    #include<iostream>#defineLLlonglongusingnamespacestd;intmain(){LLx1,y1,x2,y2,x3,y3,x4,y4;cin>>x1>>y1>>x2>>y2>>x3>>y3>>x4>>y4;LLs1,s2,s;s1=(x2-x1)*(y2-y1);s2=(x4-......
  • 第十三届蓝桥杯省赛真题 Java C 组【原卷】
    文章目录发现宝藏【考生须知】试题A:排列字母试题B:特殊时间试题C:纸张尺寸试题D:求和试题E:\mathbf{E}:......
  • 题解:AT_arc174_a [ARC174A] A Multiply
    题传。先要将\(C\)分类。\(C>0\),为了使答案更大,要乘上一个最大的区间和。\(C\le0\),为了使答案更大,选择乘上一个最小的区间和,因为此时我们可以贪心地想,如果区间和越小,乘上一个负数或\(0\)后,答案减少得越小,甚至乘上负数,还会使答案增大,所以也可以用负负得正来解释。当......
  • P8756 [蓝桥杯 2021 省 AB2] 国际象棋 题解
    设计状态什么的就不讲了,这里是对其它题解的优化。怎么优化呢,我们可以知道的是我们只要明确了当前行的状态,上一行的可选集就是知道的,如果我们明确了当前行以及上一行的状态,那么上上行的可选集就是知道的,于是我们就可以使用二进制子集枚举来写,这样就减去了全部不合法的枝叶,我们可以......
  • 机器学习金融预测领域2023部分综述论文阅读记录
    23年的综述最近读了3篇,总结笔记如下:本期所有论文链接:2023综述https://www.alipan.com/s/ySur3StxKip点击链接保存,或者复制本段内容,打开「阿里云盘」APP,无需下载极速在线查看,视频原画倍速播放。(2023)A_Systematic_Survey_of_AI_Models_in_Financial_Mark评价:原文写的一般,可以......
  • CF794F Leha and security system 题解
    题目链接:CF或者洛谷首先观察到题目的修改\(x\rightarrowy\),是每个位置的\(x\)都要变,那就显然的拆位去算每一位的贡献。当然,你又发现\(x\rightarrowy\),这玩意属于值为\(x\)的位变化成\(y\),那么这个和普通的拆位区别就在于这是维护值域维的拆位,我们拆位\(0\sim9\)......
  • SpringBoot 面向面试学习(2023.03.23更新)
    导语在网上找了很多SpringBoot相关的教程,要么是针对初学者面向实战入门的视频,要么基于面试但存在收费或不全面的问题……因此参考网上博客特此总结了一些可能常见的面试题,循序渐进,以问题为导向,以面试为场景进行学习/复习。JavaGuide提供的Spring常见面试题总结可以去看,里面......
  • #17 2023.3.18
    645.loj4038「SNOI2024」树V图646.loj4039「SNOI2024」矩阵647.loj4040「SNOI2024」拉丁方648.loj4041「SNOI2024」平方数649.loj4042「SNOI2024」公交线路650.loj3903「PA2022」Palindrom651.loj3904「PA2022」WielkiZderzaczTermionów652.loj......
  • 第十四届蓝桥杯大赛软件赛省赛Python 《01串的熵》
    问题描述问题类型暴力,枚举、问题分析由例题知对于一个长度为L的01串,设0出现的次数为x,则1出现的次数为L-x,其信息熵整理后可表示为:基于此,我们可以给出当长度L=23333333的01串,其信息熵为11625907.5798时,该字符串中0和1的个数分别为多少。题目限制0出现的次数比1少,可以通过......