首页 > 笔记 > NOIP算法总结

NOIP算法总结

临时抱佛脚

1.图论

最短路

1.堆优化dij

用priority_queue做堆,对于每次弹出的点

标记访问

对于所有能访问到的点

松弛

若未访问,压到堆中

2.spfa

用queue做队列,对于每次弹出的点

消除标记

对于所有能访问的点

松弛

若未标记,则标记,进入队列

最小生成树

1.kruskal

并查集初始化

边权排序

假如边上两点不在同一集合内

合并两点

把边加入最小生成树

2.prim

不大常用。。。懒得写了

强连通分量Tarjan

对于dfs每次到的节点

初始化dfn[x]=low[x]=++dfs_clock

把节点压到栈中

对于所有能访问的节点

如果dfn为0(未dfs到)

dfs那个节点

更新low(low[x]=min(low[x],low[那个节点]);)

若不为0且在不在栈中

low[x]=min(low[x],dfn[那个节点]);

如果low[x]==dfn[x]

弹出栈中的元素,直到弹出的元素等于x,弹出的元素都属于一个强连通分量

//I wanna summarize the graph
//Here we go
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <cstring>
#define M 200010
#define N 10010
using namespace std;
typedef pair<int,int> Pair;
//How to save a Graph?
//It's easy
struct node
{
	int from,to,value,next;
}e[M];
int tot,st[M];
int n,m;
//How to add a point?
void add(int x,int y,int z)
{
	e[++tot].to=y;
	e[tot].from=x;
	e[tot].value=z;
	e[tot].next=st[x];
	st[x]=tot;
}
//That's easy right?
//Now we are going to get the shortest path of the Graph
int dijsktra(int start,int end)
{
	int dis[N];
	bool flag[N];
	memset(dis,127,sizeof dis);
	memset(flag,0,sizeof flag);
	dis[start]=0;
	priority_queue< Pair,vector<Pair>,greater<Pair> >que;
	que.push(make_pair(dis[start],start));
	while (!que.empty())
	{
		Pair now=que.top();
		que.pop();
		if (flag[now.second]) continue;
		flag[now.second]=1;
		for (int i=st[now.second];i;i=e[i].next)
			if (dis[now.second]+e[i].value<dis[e[i].to])
			{
				dis[e[i].to]=dis[now.second]+e[i].value;
				if (!flag[e[i].to]) que.push(make_pair(dis[e[i].to],e[i].to));
			}
	}
	return dis[end];
}
//I hope it warks
//use queue's bellman
//very good idea
int spfa(int start,int end)
{
	int dis[N];
	bool vis[N];
	vis[start]=1;
	dis[start]=0;
	queue<int>que;
	que.push(start);
	while (!que.empty())
	{
		int now=que.front();
		que.pop();
		//int i=st[now];
		vis[now]=0;
		for (int i=st[now];i!=0;i=e[i].next)
		{
			if (dis[e[i].to]>dis[now]+e[i].value)
			{
				dis[e[i].to]=dis[now]+e[i].value;
				if (vis[e[i].to]==0)
				{
					vis[e[i].to]=1;
					que.push(e[i].to);
				}
			}
		}
	}
	return dis[end];
}
//Good
//Then let's get the MST of the Graph
//It will need ufs
//...
struct UFS
{
	int fa[M];
	void make_set()
	{
		for (int i=1;i<=m;i++)
			fa[i]=i;
	}
	int finds(int x)
	{
		if (x!=fa[x]) fa[x]=finds(fa[x]);
		return x;
	}
}ufs;
bool kruskalcmp(node a,node b)
{
	return a.value<b.value;
}
int Kruskal()
{
	int ans=0;
	ufs.make_set();
	sort(e+1,e+tot+1,kruskalcmp);
	for (int i=1;i<=m;i++)
	{
		int fx=ufs.finds(e[i].from),fy=ufs.finds(e[i].to);
		if (fx!=fy)
		{
			ufs.fa[fx]=fy;
			ans+=e[i].value;
		}
	}
	return ans;
}
//Very easy to write
//Next algorithm seems like dij
//It can be optimized by heap too
//but there is difference
int prim(int s)
{
	priority_queue<Pair,vector<Pair>,greater<Pair> >que;
	int dis[N];
	memset(dis,-1,sizeof dis);
	for (int i=st[s];i;i=e[i].next)
	{
		dis[e[i].to]=e[i].value;
		que.push(make_pair(dis[e[i].to],e[i].to));
	}
	bool vis[N];
	vis[s]=1;
	dis[s]=0;
	int ans=0;
	while(!que.empty())
	{
		Pair now=que.top();
		que.pop();
		if (vis[now.second]) continue;
		vis[now.second]=1;
		ans+=now.first;
		for (int i=st[now.second];i;i=e[i].next)
			if(!vis[e[i].to] && dis[e[i].to]>e[i].value || dis[e[i].to]!=-1)
			{
				dis[e[i].to]=e[i].value;
				que.push(make_pair(dis[e[i].to],e[i].to));
			}
	}
	return ans;
}
//Now let's study Strongly connected component
//It's called Tarjan
//Rorbot Tarjan is a great man
stack <int> s;
int ans,scc_in[N],dfn[N],low[N],dfs_clock;
int Tarjan(int x)
{
	dfn[x]=low[x]=++dfs_clock;
	s.push(x);
	for (int i=st[x];i;i=e[i].next)
		if (!dfn[e[i].to])
		{
			Tarjan(e[i].to);
			low[x]=min(low[e[i].to],low[x]);
		}
		else if (!scc_in[e[i].to])
			low[x]=min(low[x],dfn[e[i].to]);
	if (low[x]==dfn[x])
	{
		scc_in[x]=++ans;
		while(1)
		{
			int now=s.top();
			s.pop();
			scc_in[now]=ans;
			if (now==x) break;
		}
	}
}

main()
{
	int n,m,start,end,x,y,z;
	scanf("%d%d%d%d",&n,&m,&start,&end);
	for (int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);
		add(y,x,z);//有向图
	}
	printf("%d",dijsktra(start,end));
}

没测试完。。。

2.排序

sort。。。【stl大法好

3.数论

直接上程序了【懒得讲

#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#define N 10000
using namespace std;
int GCD(int a,int b)
{
	return b?GCD(b,a%b):a;
}

int EXGCD(int a,int b,int &x,int &y)
{
	if (b==0)
	{
		x=1;
		y=0;
		return a;
	}
	int ans=EXGCD(b,a%b,x,y);
	int t;
	x=y;
	y=t-a/b*y;
	return ans;

}

int LCM(int a,int b)
{
	if (a<b) swap(a,b);
	int ans=a;
	while (ans % b>0)
		ans+=a;
	return ans;
}

bool isprime(int x)
{
	for (int i=1;i<=sqrt(x+0.5);i++)
		if (!x%i) return 0;
	return 1;
}

int primeint[N];
bool boolprime[N];
int primetot;
void get_prime(int primesize)
{
	memset(boolprime,1,sizeof boolprime);
	boolprime[1]=false;
	for (int i=2;i<=primesize;i++)
	{
		if (boolprime[i])
			primeint[++primetot]=i;
		for (int j=1;i<=primetot&&primeint[j]*i<primesize;j++)
		{
			boolprime[i*primeint[j]]=0;
			if(!i%primeint[j]) break;
		}
	}
}

int quick_pow(int x,int y,int mod)
{
	int ans=1;
	while(y>0)
	{
		if (y&1)
			ans=ans*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	return ans;
}

//模运算法则
//
//(A+B) % C = (A % C + B % C) % C
//
//(A-B) % C = (A % C - B % C) % C
//
//(A * B) % C = (A % C) * (B % C) % C
//
//(A / B) % C = ???
//
//结合律
//
//((a+b) % p + c)% p = (a + (b+c) % p) % p
//
//((a*b) % p * c)% p = (a * (b*c) % p) % p
//
//分配律
//
//((a +b)% p × c) % p = ((a × c) % p + (b × c) % p) % p

/*
常用位运算详细示例

    功能              |           示例            |    位运算
———————————+ —————————————+ ——————–
去掉最后一位          | (101101->10110)           | x >> 1
在最后加一个0         | (101101->1011010)         | x << 1
在最后加一个1         | (101101->1011011)         | (x << 1)+1
把最后一位变成1       | (101100->101101)          | x | 1
把最后一位变成0       | (101101->101100)          | (x | 1)-1
最后一位取反          | (101101->101100)          | x ^ 1
把右数第k位变成1      | (101001->101101,k=3)      | x | (1 >> (k-1))
把右数第k位变成0      | (101101->101001,k=3)      | x & ! (1 << (k-1))
右数第k位取反         | (101001->101101,k=3)      | x ^ (1 << (k-1))
取末三位              | (1101101->101)            | x & 7
取末k位               | (1101101->1101,k=5)       | x & (1 << (k-1))
取右数第k位           | (1101101->1,k=4)          | x >> (k-1) && 1
把末k位变成1          | (101001->101111,k=4)      | x | (1 << (k-1))
末k位取反             | (101001->100110,k=4)      | x ^ (1 << (k-1))
把右边连续的1变成0    | (100101111->100100000)    | x & (x+1)
把右起第一个0变成1    | (100101111->100111111)    | x | (x+1)
把右边连续的0变成1    | (11011000->11011111)      | x | (x-1)
取右边连续的1         | (100101111->1111)         | (x ^ (x+1)) >> 1
去掉右起第一个1的左边 | (100101000->1000)         | x & (x ^ (x-1))
*/
main()
{
	int x,y;
	puts("====MATH====");
	scanf("%d%d",&x,&y);
	printf("GCD:%d\n",GCD(x,y));
	printf("LCM:%d\n",LCM(x,y));
	printf("pow:%d\n",quick_pow(x,y,10000007));
	puts("Test Over");
}

4.高精度

没啥好说的

直接重载

/*
 * 高精度整数运算
 * 存储及输入输出高精度整数
 * 两个整数相加
 * 两个整数相减
 * 两个整数相乘
 * 两个整数相除
 * 两个整数求模
 * 两个整数比较
 */
#include <string>
#include <vector>
#include <iostream>

using namespace std;

struct BigInt
{
	bool symbol;		//标记数字的正负
	vector<int> num;	//存储高精度整数

	BigInt(string sNum = "0")
	{
		*this = sNum;
	}

	BigInt(int iNum)
	{
		*this = iNum;
	}

	//重载 = 运算符 使之支持用 = 直接用内置整型进行赋值
	BigInt operator = (const int iNum)
	{
		//清空原有数字
		num.erase(num.begin(), num.end());
		//获取数字的符号
		int tmp(iNum);
		if(iNum < 0)
		{
			symbol = true;
			tmp = -tmp;
		}
		else
			symbol = false;
		//以倒序存储高精度整数
		//将数字按位存数
		while(tmp >= 10)
		{
			num.push_back(tmp % 10);
			tmp /= 10;
		}
		if(tmp != 0) num.push_back(tmp);
		else if(num.empty()) num.push_back(0);
		return *this;
	}

	//重载 = 运算符 使之支持用 = 直接用字符串进行赋值
	BigInt operator = (const string sNum)
	{
		//清空原有数字
		num.erase(num.begin(), num.end());
		//以倒序存储高精度整数
		for(string::size_type i(sNum.size() - 1); i > 0; --i)
			num.push_back(sNum[i] - '0');
		//确定数字符号
		if(sNum[0] == '-') symbol = true;
		else
		{
			symbol = false;
			num.push_back(sNum[0] - '0');
		}
		//清除前导零
		for(vector<int>::size_type i(num.size() - 1); num[i] == 0 && i > 0; --i)
			num.pop_back();
		return *this;
	}

	//重载 = 运算符 使之支持用 = 直接高精度整数进行赋值
	BigInt operator = (const BigInt bInt)
	{
		//清空原有数字
		num.erase(num.begin(), num.end());
		//以倒序存储高精度整数
		for(vector<int>::size_type i(0); i < bInt.num.size(); ++i)
			num.push_back(bInt.num[i]);
		//符号转存
		symbol = bInt.symbol;
		return *this;
	}

	//重载 + 运算符 使之支持用 + 进行高精度整数的加法运算
	BigInt operator + (const BigInt bInt) const
	{
		BigInt rslt;
		//同号相加
		if(bInt.symbol == (*this).symbol)
		{
			if(bInt.symbol) rslt.symbol = true;	//同负
		}
		else if((*this).symbol)	//左负 右正
		{
			rslt = bInt - (-*this);
			rslt.symbol = true;
			return rslt;
		}
		else if(bInt.symbol)	//左正 右负
		{
			rslt = *this - (-bInt);
			return rslt;
		}
		//获取相加的两个数字的长度
		vector<int>::size_type lenA(num.size()), lenB(bInt.num.size()), lng;
		lng = (lenA > lenB ? lenA : lenB);	//记录长度较长的
		//逐位相加
		for(vector<int>::size_type i(0); i < lng; ++i)
		{
			int tmp(rslt.num[rslt.num.size() - 1]);	//获取当前位原有的数字
			//相加
			if(i < lenA) tmp += num[i];
			if(i < lenB) tmp += bInt.num[i];
			rslt.num[rslt.num.size() - 1] = tmp % 10;	//存入
			rslt.num.push_back(tmp / 10);	//进位
		}
		if(rslt.num[lng] == 0) rslt.num.pop_back();	//末位为0则弹出
		return rslt;
	}

	//重载 - 运算符 使之支持用 - 进行高精度整数的加法运算
	BigInt operator - (BigInt bInt) const
	{
		BigInt rslt, myInt(*this), tmp;
		//获取相加的两个数字的长度
		vector<int>::size_type lenA(num.size()), lenB(bInt.num.size()), lng, shrt, len;
		shrt = (lenA > lenB ? lenB : lenA);	//记录长度较短的
		lng = (lenA > lenB ? lenA : lenB);	//记录长度较长的
		//同号相减
		if(bInt.symbol == myInt.symbol)
		{
			if(!bInt.symbol)	//同正
			{
				if(myInt < bInt)
				{
					tmp = myInt; myInt = bInt; bInt = tmp;	//交换
					rslt.symbol = true;
				}
			}
			else	//同负
			{
				if(myInt > bInt)
				{
					tmp = myInt; myInt = bInt; bInt = tmp;	//交换
					rslt.symbol = false;
				}
				myInt = -myInt; bInt = -bInt;	//变正
				rslt.symbol = true;
			}
		}
		else if(myInt.symbol) return -(-myInt + bInt);	//左负 右正
		else if(bInt.symbol) return myInt + (-bInt);	//左正 右负
		//逐位相减
		for(vector<int>::size_type i(0); i < lng; ++i)
		{
			if(i < shrt)
			{//相减
				if(myInt.num[i] < bInt.num[i])
				{//借位
					myInt.num[i + 1] -= 1;
					rslt.num[i] = myInt.num[i] + 10 - bInt.num[i];	//减
				}
				else rslt.num[i] = myInt.num[i] - bInt.num[i];	//减
			}
			else rslt.num[i] = myInt.num[i];
			rslt.num.push_back(0);
		}
		//消去前导0
		for(vector<int>::size_type i(rslt.num.size() - 1); rslt.num[i] == 0 && i > 0; --i)
			rslt.num.pop_back();
		return rslt;
	}

	//重载 - 运算符 使之支持用 - 进行高精度整数的加法运算 单目运算
	BigInt operator - () const
	{
		BigInt rslt(*this);
		if(rslt != 0) rslt.symbol = !rslt.symbol;
		return rslt;
	}

	//重载 * 运算符 使之支持用 * 进行高精度整数的乘法运算
	BigInt operator * (const BigInt bInt) const
	{
		BigInt rslt;
		//获取相乘的两个数字的长度
		vector<int>::size_type lenA(num.size()), lenB(bInt.num.size()), len(lenA + lenB);
		rslt.num.insert(rslt.num.begin(), len - 1, 0);	//预留位数
		//逐位相乘
		for(vector<int>::size_type i(0); i < lenA; ++i)
			for(vector<int>::size_type j(0); j < lenB; ++j)
			{
				rslt.num[i + j] += num[i] * bInt.num[j];
				rslt.num[i + j + 1] += rslt.num[i + j] / 10;
				rslt.num[i + j] %= 10;
			}
		if(rslt.num[len - 1] == 0) rslt.num.pop_back();	//去除前导零
		//同号为正 异号为负
		if(rslt != 0) rslt.symbol = symbol ^ bInt.symbol;
		return rslt;
	}

	//重载 / 运算符 使之支持用 / 进行高精度整数的除法运算
	BigInt operator / (const BigInt bInt) const
	{
		BigInt tmp, tmp2;
		string rsltS((*this).num.size(), '0');
		if(bInt == 0) return BigInt(0);	//除数为0 返回0
		//获取相除的被除数的长度
		//按倒序位读取被除数
		vector<int>::size_type i(num.size());
		string::size_type j(0);
		while(i--)
		{
			if(tmp == 0) tmp.num.pop_back();
			tmp.num.insert(tmp.num.begin(), num[i]);	//插入一个数
			//开始试除
			int i(10);
			while(i--)	//由大到小进行试除运算
			{
				tmp2 = tmp - (bInt < 0 ? -bInt : bInt) * i;	//这里对除数为负数的情况作了一些判断,我们在运算过程中要确保符号均为正
				if(tmp2 >= 0)	//首个非负的试除结果
				{
					rsltS[j] += i;	//商
					tmp = tmp2;
					break;
				}
			}
			++j;
		}
		BigInt rslt(rsltS);	//结果 该构造函数自动去除前导零
		//同号为正 异号为负
		if(rslt != 0) rslt.symbol = symbol ^ bInt.symbol;
		return rslt;
	}

	//重载 % 运算符 使之支持用 % 进行高精度整数的取模运算
	BigInt operator % (const BigInt bInt) const
	{
		BigInt rslt, tmp;
		if(*this == 0) return BigInt(0);	//除数为0 返回0
		//获取相除的被除数的长度
		//按倒序位读取被除数
		vector<int>::size_type i(num.size());
		while(i--)
		{
			if(rslt == 0) rslt.num.pop_back();
			rslt.num.insert(rslt.num.begin(), num[i]);	//插入一个数
			//开始试除
			int i(10);
			while(i--)	//由大到小进行试除运算
			{
				tmp = rslt - (bInt < 0 ? -bInt : bInt) * i;
				if(tmp >= 0)	//首个非负的试除结果
				{
					rslt = tmp;
					break;
				}
			}
		}
		//模的符号与被除数相同
		rslt.symbol = symbol;
		return rslt;
	}

	//重载 += 运算符 使之支持用 += 进行高精度整数的加法运算
	BigInt operator += (const BigInt bInt)
	{
		*this = *this + bInt;
		return *this;
	}

	//重载 -= 运算符 使之支持用 -= 进行高精度整数的减法运算
	BigInt operator -= (const BigInt bInt)
	{
		*this = *this - bInt;
		return *this;
	}

	//重载 *= 运算符 使之支持用 *= 进行高精度整数的乘法运算
	BigInt operator *= (const BigInt bInt)
	{
		*this = *this * bInt;
		return *this;
	}

	//重载 /= 运算符 使之支持用 /= 进行高精度整数的除法运算
	BigInt operator /= (const BigInt bInt)
	{
		*this = *this / bInt;
		return *this;
	}

	//重载 %= 运算符 使之支持用 %= 进行高精度整数的模运算
	BigInt operator %= (const BigInt bInt)
	{
		*this = *this % bInt;
		return *this;
	}

	//重载 < 运算符 使之支持使用 < 直接进行高精度整数的比较
	bool operator < (const BigInt bInt) const
	{
		vector<int>::size_type bLen(bInt.num.size());

		if(!bInt.symbol && symbol)	return true;	//左正 右负
		else if(bInt.symbol && !symbol) return false;	//左负 右正
		else if(num.size() != bLen)		//长度不一样,直接返回大小结果
		{
			if(!symbol) return num.size() < bLen;
			else return num.size() > bLen;
		}
		//由末位开始逐个比较
		for(vector<int>::size_type i(bLen - 1); i > 0; --i)
		{
			if(num[i] != bInt.num[i])
			{
				if(!bInt.symbol && !(*this).symbol) return num[i] < bInt.num[i];
				else return bInt.num[i] < num[i];
			}
		}
		if(!bInt.symbol && !symbol) return num[0] < bInt.num[0];	//左正 右正
		else return bInt.num[0] < num[0];	//左负右负
	}

	//重载其它比较运算符
	bool operator > (const BigInt bInt) const
	{
		return bInt < *this;
	}

	bool operator <= (const BigInt bInt) const
	{
		return !(*this > bInt);
	}

	bool operator >= (const BigInt bInt) const
	{
		return !(*this < bInt);
	}

	bool operator != (const BigInt bInt) const
	{
		return (*this < bInt) || (*this > bInt);
	}

	bool operator == (const BigInt bInt) const
	{
		return !(*this != bInt);
	}
};

//重载C++输入流运算符 使之支持C++IO流直接输入高精度整数
istream& operator >> (istream &in, BigInt& x)
{
	string tmp;
	in >> tmp;
	x = tmp;
	return in;
}

//重载C++输出流运算符 使之支持C++IO流直接输出高精度整数
ostream& operator << (ostream &out, BigInt& x)
{
	if(x.symbol) cout << '-';
	//以数字的正确顺序输出
	for(vector<int>::size_type i(x.num.size() - 1); i > 0; --i)
		out << x.num[i];
	out << x.num[0];
	return out;
}

main()
{
	BigInt a,b,c;
	cin>>a>>b;
	c=a/b;
	cout<<c;
}