备战蓝桥杯决赛----坚持第二天！！！
昨天备战第一天，博客写到凌晨。今天我想偷个懒了，还是应该给自己留点周末时间的。好了，总结一下今天所学。真的是收获满满啊，又是仅仅看会了两个算法模板（呜呜~~~），而且感觉肯定还会忘。举个非常简单的例子：我昨天总结的什么？昨天学的什么模板？是的，我现在都有点记不清昨天学习的内容了。还好给自己留了“后路”，昨天由于太晚，一部分东西没有总结，这里先总结一下昨天剩下的东西。
堆优化的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;
}可能看我这博客有点糊弄，其实没有，因为这些方法，我给的那些链接博客讲的非常好，没有必要再说一遍，然后我会给一些程序注释，方便理解（程序代码注释，第二天添加，这样有利于记忆，真的记性不好。。。应该是个好方法）