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; }