欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

备战蓝桥杯决赛----坚持第二天!!!

程序员文章站 2022-05-24 09:38:35
...

      昨天备战第一天,博客写到凌晨。今天我想偷个懒了,还是应该给自己留点周末时间的。好了,总结一下今天所学。真的是收获满满啊,又是仅仅看会了两个算法模板(呜呜~~~),而且感觉肯定还会忘。举个非常简单的例子:我昨天总结的什么?昨天学的什么模板?是的,我现在都有点记不清昨天学习的内容了。还好给自己留了“后路”,昨天由于太晚,一部分东西没有总结,这里先总结一下昨天剩下的东西。

      堆优化的Dijstra算法。

      为什么会有堆优化呢?原因很简单,当面对数据量较大的情况下,正常的思路会由于超时而报错,所以要对程序进行优化,缩减一些不必要的运行时间。

根据学到的模板,这里给出完整的程序。当然dijstra()函数是重点,不想说太多,将一些重要的点,都在注释上标注。

#include<iostream>
#include<cstring>
#include<queue> 
#include<vector>
using namespace std;
const int MAX = 100;
const int INF = 0x3f3f3f3f;
int n,m;
int graph[MAX][MAX];
int visit[MAX];
int dist[MAX];

struct qNode{
	int u;
	int c;
	qNode(int _u=0,int _c=0) : u(_u), c(_c){}
	bool operator < (const qNode &r) const{
	return c> r.c;
	}
};
struct Edge{
	int v;
	int w;
	Edge(int _v=0,int _w=0) : v(_v), w(_w){}
};
vector<Edge> E[MAX];
void dijkstra(int s){//起点
    memset(visit,0,sizeof(visit));
    memset(dist,0x3f,sizeof(dist));
    priority_queue<qNode> que;
	while(!que.empty()){
		que.pop();
	}
	que.push(qNode(s,0));
	dist[s]=0;
	qNode tem;
	while(!que.empty()){
		tem = que.top();
		que.pop();
		int u = tem.u;
		if(visit[u]){
			continue;
		}
		visit[u]=1;
		for(int i=0;i<E[u].size();i++){
			int v = E[u][i].v;
			int w =E[u][i].w;
			if(!visit[v]&&dist[u]+w<dist[v]){
				dist[v]=dist[u]+w;
				que.push(qNode(v,dist[v]));
			}
		}
	}   
}
void addEdge(int u,int v,int w){  //邻接表创建图的方法
	E[u].push_back(Edge(v,w));
}
int main(){
    cin>>n>>m;
    memset(graph,MAX,sizeof(graph));
    for(int i=0;i<m;i++){
    	int x,y,z;
    	cin>>x>>y>>z;
    	addEdge(x,y,z);
    	addEdge(y,x,z);
	}
	dijkstra(0);
	for(int i=0;i<n;i++){
		cout<<dist[i]<<endl;
	}
	return 0;
} 

另外,我们光会模板不行,当然还要看看应用,所以这里我找了两道题目,大家可以试着做做(真的变得非常简单了~~~)。

1.https://blog.csdn.net/Mashiro_ylb/article/details/78287724?locationNum=5&fps=1

2.https://blog.csdn.net/cqyz_holiday/article/details/51933197

----------------------------------------------------------------------------------------------------------------------------

       接下来就说一下今天所学,继续昨天的学习,继续看大神f_zyj总结的ACM模板,无意中发现了她的另一篇博客:2016年第七届蓝桥杯决赛心得。真的又涨了不少经验值,至少我知道重点在哪里了。十四天的复习计划,也只能是专攻必考题型这种策略了。我最先看到的是,蓝桥杯必考一道关于字符串的题目,建议最好掌握KMP与Manacher算法。所以我就想着先看看这两个,然后再看其他的,没想到,又耗尽了我一天的时间。。。心疼。

       首先是KMP算法,相对于Manacher来说简单一点,而且非常实用!!

为了帮助理解KMP,我找到了两篇博客,写的非常好(千挑万选~)

1.https://blog.csdn.net/starstar1992/article/details/54913261

2.https://blog.csdn.net/u011564456/article/details/20862555

附上一段可以AC的程序(程序中求next数组时,是借鉴的f_zyj的模板,真正的KMP是结合看到的博客,自己写出来的,要比模板好理解一些)

#include<iostream>
#include<cstring>
#include<queue> 
#include<vector>
using namespace std;
void preNext(string s,int *next,int m){
	int j=next[0]=-1;
	int i=0;
	while(i<m){
		if(j!=-1&s[i]!=s[j]){
			j=next[j];
		}
		next[++i] = ++j;
	}
	return ;
}
int KMP(string sd,int n,string sx,int m){
	int *next = new int[m];
	int j=-1;
	preNext(sx,next,m);
	for(int i=0;i<n;i++){
	    while(j>-1&&sd[i]!=sx[j+1]){
	    	j=next[j];
		}
		if(sd[i]==sx[j+1]){
			j=j+1;
		}
		if(j==m-1){
			//cout<<"在位置:"<<i-m+1<<"处存在"<<endl; //返回所有存在匹配字符串的位置 
			//j=-1;
			//i=i-m+1;
			return i-m+1; //这里加一的原因是用户看到的是实际字符串长度,我们定义的时候是从零开始的 
		}
	}
	return -1;
}
int main(){
    string str = "bacbababadababacambabacaddababacasdsd";
    string ptr = "ababaca";
    int k = KMP(str,36,ptr,7);
    cout<<k;
	return 0;
} 

       接着说一下Manacher算法,真的是很苦逼,不过我发现算法这东西,看不懂,再看;还是看不懂,再继续看。就这样一直一直循环。

还是推荐两篇博客:

先参考博客:https://segmentfault.com/a/1190000003914228
然后可以看看这篇博客(非常喜欢这个博主博客的风格,自己也打算做一个)的代码:https://subetter.com/articles/2018/03/manacher-algorithm.html

附上一段AC程序

#include <iostream>  
#include <cstring>
#include <algorithm>  

using namespace std;

char s[1000];
char s_new[2000];
int p[2000];

int Init()
{
    int len = strlen(s);
    s_new[0] = '$';
    s_new[1] = '#';
    int j = 2;

    for (int i = 0; i < len; i++)
    {
        s_new[j++] = s[i];
        s_new[j++] = '#';
    }

    s_new[j] = '\0';  // 别忘了哦
    
    return j;  // 返回 s_new 的长度
}

int Manacher()
{
    int len = Init();  // 取得新字符串长度并完成向 s_new 的转换
    int max_len = -1;  // 最长回文长度

    int id;
    int mx = 0;

    for (int i = 1; i < len; i++)
    {
        if (i < mx)
            p[i] = min(p[2 * id - i], mx - i);  // 需搞清楚上面那张图含义, mx 和 2*id-i 的含义
        else
            p[i] = 1;

        while (s_new[i - p[i]] == s_new[i + p[i]])  // 不需边界判断,因为左有'$',右有'\0'
            p[i]++;

        // 我们每走一步 i,都要和 mx 比较,我们希望 mx 尽可能的远,这样才能更有机会执行 if (i < mx)这句代码,从而提高效率
        if (mx < i + p[i])
        {
            id = i;
            mx = i + p[i];
        }

        max_len = max(max_len, p[i] - 1);
    }

    return max_len;
}

int main()
{
    while (printf("请输入字符串:\n"))
    {
        scanf("%s", s);
        printf("最长回文长度为 %d\n\n", Manacher());
    }
    return 0;
}

可能看我这博客有点糊弄,其实没有,因为这些方法,我给的那些链接博客讲的非常好,没有必要再说一遍,然后我会给一些程序注释,方便理解(程序代码注释,第二天添加,这样有利于记忆,真的记性不好。。。应该是个好方法)