【未完】训练赛20190304：KMP+树状数组+线段树+优先队列

头炸了啊，只做出L题，前两天刚看的Shawn zhou的博客学习的，幸亏看了啊，否则就爆零了，发现题目都是经典题，线段树，KMP，我都没看过，最近又在复习考研，真后悔大一大二没好好学习啊，得抽时间好好补一下了。还报名了蓝桥杯啊，心里好没底。。。

A	Watto and Mechanism
B	Infinite Inversions
C	Pashmak and Parmida's problem
D	Balanced Lineup
E	Snowflake Snow Snowflakes
F	敌兵布阵
G	Oulipo
H	Power Strings
I	Period
J	Hat’s Words
K	Black Box
L	搬果子

G:KMP经典题

称长的为文本串，短的为模式串，求文本串中含有多少模式串。KMP的经典题，主要就是一个next[]数组，next[]数组记录字符串的前后缀相同个数，都在注释里了。

#include<iostream>

#include<string>

#include<stdio.h>

using namespace std;

const int maxn = 1e6;

string tex, pat;									//tex文本串  pat模式串

int nex[maxn];

void getnext(string pat, int lenpat) {				//获取nex数组

	int j = nex[0] = -1;							//j相当于记录nex[i]的值

	for (int i = 1; i < lenpat; i++) {				//求next[1]~next[len-1]

		while (j != -1 && pat[i] != pat[j + 1]) {

			j = nex[j];								//j回退，直到j回退到-1或pat[i]==pat[j+1]

		}

		if (pat[i] == pat[j+1])j++;					//相等，先令j指向这个位置。

		nex[i] = j;									//赋值给nex[i]

	}

}

int kmp(string tex, string pat) {

	int lent = tex.size(), lenp = pat.size();

	getnext(pat,lenp);									//获取模式串的nex[]数组

	int cnt = 0, j = -1;								//cnt：成功匹配次数

	for (int i = 0; i < lent; i++) {					//试图匹配tex

	//	cout << "i=	" << i << endl;

		while (j != -1 && tex[i] != pat[j + 1]) {

			j = nex[j];									//j回退，直到j回退到-1或pat[i]==pat[j+1]

		}

		if (tex[i] == pat[j + 1])

			j++;										//匹配的话，继续

		if (j == lenp-1)

		/*	cout << i+2-lenp<< "\n",*/cnt++, j = nex[j];			//i下标从零开始的，应该属输出 i+1-(lenp)+1

	}

	return cnt;

}

int main() {

	int t;

	cin >> t;

	while (t--) {

	cin >> pat>>tex;

	int lenp = pat.size();

	cout << kmp(tex, pat) << "\n";

	}

	//for (int i = 0; i < lenp; i++)

	//	cout << nex[i]+1 << " ";

	return 0;

}

H:KMP求循环节

主要是对next[]数组的应用，重点是判断循环节，然后求循环次数。

#include<iostream>

#include<string>

#include<stdio.h>

using namespace std;

const int maxn = 1e6;

string tex, pat;									//tex文本串  pat模式串

int nex[maxn];

void getnext(string pat, int lenpat) {				//获取nex数组

	int j = nex[0] = -1;							//j相当于记录nex[i]的值

	for (int i = 1; i < lenpat; i++) {				//求next[1]~next[len-1]

		while (j != -1 && pat[i] != pat[j + 1]) {

			j = nex[j];								//j回退，直到j回退到-1或pat[i]==pat[j+1]

		}

		if (pat[i] == pat[j+1])j++;					//相等，先令j指向这个位置。

		nex[i] = j;									//赋值给nex[i]

	}

}

int main() {

	string s;

	while (cin >> s&&s[0] != '.') {

		int lens = s.size();

		getnext(s, lens);

		if (lens % (lens - nex[lens-1]-1) == 0)    //重点是判断是否能够循环节，循环节：lens-(nex[lens-1]+1)

			cout << lens / (lens - nex[lens-1]-1) << "\n";

		else cout << "1\n";

	}

	return 0;

}

I:Period ：KMP

L:优先队列 小顶堆

注意头文件，greater<>的头文件  #include<functional>　　和　　priority_queue<int,vector<int>,greater<int> >p;　　别写错了。

#include<iostream>

#include<algorithm>

#include<string>

#include<vector>

#include<queue>

#include<functional>

using namespace std;

#define ll long long

int main() {

	int n;

	while (cin >> n) {

		int t, cnt = 0;

		priority_queue<int,vector<int>,greater<int> >p;

		for (int i = 0; i < n; i++) {

			cin >> t;

			p.push(t);

		}

		while (p.size() != 1) {

			int p1 = p.top();

			p.pop();

			int p2 = p.top();

			p.pop();

			cnt += p1 + p2;

			p.push(p1 + p2);

		}

		cout << cnt<<"\n";

	}

	return 0;

}