高精度模板(算法必备)

c语言高精度运算模板
好的，下面为你提供一个C语言高精度运算模板，包括高精度加法、减法和乘法：
高精度加法：直接对位相加，当某位超过10直接取模运算，然后下一位直接对加相应多出的数即可。

高精度减法：当输入的$ss1$小于$ss2$时，需要交换两者的顺序，并率先输出一个负号。

然后执行循环，在循环中如果$a(i)<b(i)$，则直接向下一位借位，然后本位加10，$a(i)$加10。

高精度乘法：使用双重循环，$c$下标对应关系为$i+j-1$（$i=j=1$开始）。

在循环中，将$a(i)$和$b(j)$相乘后的结果累加到$c(i+j-1)$中。

你可以根据实际需求对模板进行修改和调整，以满足不同的计算需求。

如果你还有其他问题，请随时向我提问。

高精度算法大全在一般的科学计算中,会经常算到小数点后几百位或者更多,当然也可能是几千亿几百亿的大数字.一般这类数字我们统称为高精度数,高精度算法是用计算机对于超大数据的一种模拟加,减,乘,除,乘方,阶乘,开放等运算.譬如一个很大的数字N >= 10^ 100, 很显然这样的数字无法在计算机中正常存储.于是, 我们想到了办法,将这个数字拆开,拆成一位一位的或者是四位四位的存储到一个数组中, 用一个数组去表示一个数字.这样这个数字就被称谓是高精度数.对于高精度数,也要像平常数一样做加减乘除以及乘方的运算,于是就有了高精度算法:由于计算机输入计算结果的精度通常受到计算机的限制，如：在双精度方式下，计算机最多只能输出16位有效数字，如果超过16位，则只能按浮点形式输出，另外，一般计算机实数表示的范围为1038，如果超过这个范围，计算机就无法表示了。

但是我们可以通过一些简单的办法来解决这个问题。

这就是我们要说的高精度计算机。

一、基本方法：在计算机上进行高精度计算，首先要处理好以下几个基本问题：1、数据的接收与存储；2、计算结果位数的确定；3、进位处理和借位处理；4、商和余数的求法；下面我们逐一介绍一下这几个问题的解决方法。

1、数据的接收与存储：要在计算机上进行高精度计算，首先就应该有精确的输入，即计算机要精确地接收和存储数据。

通常：①、当输入的数值在计算机允许的范围内时，可以用数值型变量来接收数据。

②、当输入的数据超过计算机允许显示的精度范围时，采用字符来接收数据。

③、分离各位数字。

接收数据子模块(字符型变量接收数据)：prucedure readdata(var in:array[1..100] of integer);var ch:char;i,k:integer;beginread(ch);k:=0;while ch in['0'..'9'] do begininc(k);int[k]:=ord(ch)-48;read(ch);end;end;2、计算结果位数的确定①、两数之和的位数最大为较大的数的位数加1。

⾼精度模板【重载运算符+压位】昨天做⼀道DP的题（矩阵取数游戏），本来是很简单的，但是要⽤⾼精度，⼜不想⽤__int128⽔过去（谁让NOIP不让），于是⾃⼰打了⼀个⼩时，最后成功挂了。

于是本蒟蒻痛定思痛，感觉⾼精度还是重载运算符好⽤啊，就花了⼏个⼩时打了⼀个⾃以为⽐较好记好⽤⾼精度模板：注意暂不⽀持负数，如果发现有bug欢迎指出。

/*采⽤重载运算符，压B位⽀持⾼精数赋值与输出、⾼精加(减)⾼精、⾼精乘低(⾼)精、⾼精除(模)低精、⾼精的⽐较注意：暂不⽀持负数*/#include<cstdio>#include<cstring>#include<stack>#include<iostream>#include<algorithm>using namespace std;typedef long long LL;const int N=128,B=4;const LL base=1e4;//压B位，base为1eBstruct HP{private:int len;LL a[N];inline void clear(){while(!a[len]&&len>1) --len;}//清除前导0public:HP(){ //结构体初始化memset(a,0ll,sizeof a);len=0;}//注意因为是压B位的，所以输出要特殊处理void print(){//输出⾼精度数printf("%lld",a[len]);for(int i=len-1;i>0;--i)for(int j=base/10;j>0;j/=10) printf("%lld",a[i]/j%10);puts("");}/*以下是重载运算符*/HP& operator =(LL x){//⽤LL初始化⾼精度数 HP后加了&才可以实现像a=b=c这样连续赋值stack<char> st;string s;if(!x) return *this="0";while(x){st.push(x%10+'0');x/=10;}while(!st.empty()) s+=st.top(),st.pop();//其实就是把int转换为string再调⽤init_s()return *this=s;}HP& operator =(const string &s){//⽤string初始化⾼精度数memset(a,0ll,sizeof a);len=0;//这⾥赋值为0才可以保证重复赋值时不会出锅。

C++⾼精度除法及模板本⽂介绍的是⼀个超过long long 范围的数除⼀个较⼩的数，⽤vector 模拟计算过程，同时输出商和余数Code：#include <iostream>#include <algorithm>#include <vector>using namespace std;vector<int > A;int b, r;vector<int > div(vector<int > &a, int b, int &r){vector<int > res;int t = 0;for (int i = a.size() - 1; i >= 0; i --){t = t* 10 + a[i];res.push_back(t / b);t %= b;r = t;}reverse(res.begin(), res.end());while (!res.back() && res.size() > 1) res.pop_back();return res;}int main(){string a;cin >> a >> b;for (int i = a.size() - 1; i >=0 ; i --) A.push_back(a[i] ^ 48);auto c = div(A, b, r);for (int i = c.size() - 1; i >= 0; i --) cout << c[i];cout << endl;cout << r << endl;return 0;}字符串输⼊，由低到⾼位存⼊vector ，在从vector ⾼位开始算，这样算的结果是有前导0的，所以要reverse ⼀下，前导零就变成了后缀0，去掉后返回，再逆序输出即可。

插值多项式的构造
上的ENO插值多项式 p2 (x, y)，需要六个三角 为了构造 ∆0 上的 插值多项式 形网格， 形网格，不妨设阴影部分 为选定的三角形网格模板， 为选定的三角形网格模板，记为
S = {∆0 , ∆i , ∆ j , ∆k , ∆ia , ∆ jb}
有限体积法选用的一般三角形计算网格
Jiang对WENO格式进行了改进和提高， Jiang对WENO格式进行了改进和提高，提出了 格式进行了改进和提高 一种新的光滑措施， 一种新的光滑措施，能使这种格式在光滑的
阶精度， ENO格式达到 区域达到 (2r −1) 阶精度，在ENO格式达到 r 阶精度的 情况下) 在间断解区域权设置系数近似于零， 情况下)，在间断解区域权设置系数近似于零，可达到 基本无震荡的效果。 基本无震荡的效果。 上述进行的研究，大多局限于结构网格上。近年来， 上述进行的研究，大多局限于结构网格上。近年来， 在非结构网格上开展这方面的工作也有了一些进展， 在非结构网格上开展这方面的工作也有了一些进展，如 Abgrall，Harten对ENO格式进行了研究,Hu等人对 格式进行了研究,Hu等人对WENO Abgrall，Harten对ENO格式进行了研究,Hu等人对WENO 格式进行了研究。 格式进行了研究。但总起来说开展这方面的研究工作不 还不很成熟，没有形成全面系统的理论体系。 多，还不很成熟，没有形成全面系统的理论体系。 近年来又出现了用点云离散计算区域的无网格算法， 近年来又出现了用点云离散计算区域的无网格算法， 适合处理复杂的气动外形。 适合处理复杂的气动外形。
选取十个三角形网格作为基构造weno二次插值多项式选取的典型的网格模板如下图特殊情况的网格模板i特殊情况的网格模板ii为了构造上的eno插值多项式需要六个三角形网格插值多项式需要六个三角形网格02yxp不妨设阴影部分00iikjjkaibkkbjaiajbiajbibkakbja插值多项式的构造为选定的三角形网格模板记为jbiakjis0上述网格三角形可以重合有限体积法选用的一般三角形计算网格

高精度乘法模板一、引言在数学运算中，乘法是一种基本的运算方式。

在现实生活中，我们经常需要进行大数相乘的运算，比如计算金融数据、密码学中的加密算法等。

然而，由于计算机的内存限制和运算速度的限制，直接进行大数相乘是一件非常困难的事情。

因此，我们需要一种高精度乘法模板来解决这个问题。

二、高精度乘法模板的实现思路高精度乘法模板的实现思路可以分为以下几个步骤：1. 将两个大数转化为字符串由于计算机内存的限制，我们无法直接使用整型或浮点型变量来存储大数。

因此，我们可以将大数转化为字符串来进行处理。

在C++中，可以使用string类来方便地处理字符串。

2. 将字符串表示的大数转化为数组为了方便计算，我们可以将字符串表示的大数转化为数组。

数组的每个元素表示大数的一位数字。

在C++中，可以使用vector容器来存储数组。

3. 实现乘法运算乘法运算的实现可以采用竖式乘法的方式。

具体步骤如下：•遍历第一个大数的每一位数字，与第二个大数的每一位数字相乘，并将结果保存在一个新的数组中。

•对新数组进行进位处理，确保每一位数字都在0-9的范围内。

•将新数组转化为字符串表示的大数。

4. 处理特殊情况在实际应用中，还需要考虑一些特殊情况的处理，比如大数为0的情况、大数为负数的情况等。

三、高精度乘法模板的代码实现下面是一个简单的C++代码实现示例：#include <iostream>#include <vector>#include <string>using namespace std;string multiply(string num1, string num2) {int m = num1.size();int n = num2.size();vector<int> res(m + n, 0);for (int i = m - 1; i >= 0; i--) {for (int j = n - 1; j >= 0; j--) {int mul = (num1[i] - '0') * (num2[j] - '0');int p1 = i + j, p2 = i + j + 1;int sum = mul + res[p2];res[p1] += sum / 10;res[p2] = sum % 10;}}string result = "";for (int i = 0; i < res.size(); i++) {if (!(result.empty() && res[i] == 0)) {result.push_back(res[i] + '0');}}return result.empty() ? "0" : result;}int main() {string num1 = "123";string num2 = "456";string result = multiply(num1, num2);cout << result << endl;return 0;}四、高精度乘法模板的应用举例高精度乘法模板可以应用于很多实际问题中。

2021/6/4
856 × 25 4280 1712 21400
图3
A3A2A1 × B2B1 C’4C’3 C’2 C’1 C”5C”4C”3C”2 C6C 5C4C 3C2C1 图4
11
高精度乘法的参考程序： #include<iostream> #include<cstring> #include<cstdio> using namespace std; int main() {
示例：123456789 ÷45 = 1’ 2345’ 6789 ÷ 45 = 274’ 3484
∵ 1 / 45 = 0 ， 1%45=1 ∴ 取12345 / 45 = 274 ∵ 12345 % 45 = 15 ∴ 取156789/45 = 3484 ∴ 答案为2743484, 余数为156789%45 = 9
//按位相除 //删除前导0
2021/6/4
16
实质上，在做两个高精度数运算时候，存储高精度数的 数组元素可以不仅仅只保留一个数字，而采取保留多位数 （例如一个整型或长整型数据等），这样，在做运算（特别 是乘法运算）时，可以减少很多操作次数。例如图5就是采用 4位保存的除法运算，其他运算也类似。具体程序可以修改上 述例题予以解决，程序请读者完成。
图5
2021/6/4
【算法分析】 做除法时，每一次上商的值都在０～９，每次求得的余
数连接以后的若干位得到新的被除数，继续做除法。因此， 在做高精度除法时，要涉及到乘法运算和减法运算，还有移 位处理。当然，为了程序简洁，可以避免高精度除法，用0～ 9次循环减法取代得到商的值。这里，我们讨论一下高精度数 除以单精度数的结果，采取的方法是按位相除法。

专用模板目录：一、图论1．最大团2．拓扑排序3．最短路和次短路4．SAP模板5．已知各点度，问能否组成一个简单图6．KRUSKAL7. Prim算法求最小生成树8. Dijkstra9 . Bellman-ford10. SPFA11. Kosaraju 模板12. tarjan 模板二、数学1. 剩余定理2. N!中质因子P的个数3.拓展欧几里得4.三角形的各中心到顶点的距离和5.三角形外接圆半径周长6.归并排序求逆序数7. 求N！的位数8.欧拉函数9. Miller-Rabin,大整数分解，求欧拉函数10. 第一类斯特林数11.计算表达式12.约瑟夫问题13．高斯消元法14. Baby-step,giant-step n是素数.n任意15. a^b%c=a ^(b%eular(c)+eular(c)) % c16.判断第二类斯特林数的奇偶性17.求组合数C(n,r)18.进制转换19.Ronberg算法计算积分20.行列式计算21. 返回x 的二进制表示中从低到高的第i位22.高精度运算 +-*/23.超级素数筛选三、数据结构1．树状数组2.线段树求区间的最大、小值3.线段树求区间和4.单调队列5.KMP模板6. 划分树，求区间第k小数7.最大堆，最小堆模板8. RMQ模板求区间最大、最小值9.快速排序，归并排序求逆序数.10.拓展KMP四、计算几何1.凸包面积2.Pick公式求三角形内部有多少点3.多边形边上内部各多少点以及面积pick4.平面最远点对5.判断矩形是否在矩形内6.判断点是否在多边形内7.判断4个点(三维)是否共面8.凸包周长9.等周定理变形一直两端点和周长求最大面积10.平面最近点对11.单位圆最多覆盖多少点(包括边上)12.多边形费马点求点到多边形各个点的最短距离13.矩形并周长14.zoj 2500 求两球体积并一、图论1.最大团#include<iostream>#include<algorithm>using namespace std;int n,m;int cn;//当前顶点数int best;//当前最大顶点数int vis[50];//当前解int bestn[50];//最优解int map[50][50];//临界表void dfs(int i){if(i>n){for(int j=1;j<=n;j++) bestn[j]=vis[j];best=cn;return ;}int ok=1;for(int j=1;j<i;j++){if(vis[j]==1&&map[i][j]==0){ok=0;break;}}if(ok){//进入左子树vis[i]=1;cn++;dfs(i+1);cn--;}if(cn+n-i>best){//进入右子树vis[i]=0;dfs(i+1);}}int main(){while(scanf("%d%d",&n,&m)==2){memset(vis,0,sizeof(vis));memset(map,0,sizeof(map));while(m--){int p,q;scanf("%d%d",&p,&q);map[p][q]=map[q][p]=1;//无向图}cn=0;best=0;dfs(1);printf("%d\n",best);}return 0;}2.拓扑排序#include<iostream>#include<cstring>using namespace std;int map[105][105],in[105],vis[105],ans[105],n;int flag;void dfs(int step){if(flag) return ;if(step==n+1) {flag=1; printf("%d",ans[1]);for(int i=2;i<=n;i++) printf(" %d",ans[i]);printf("\n");return ;}for(int i=1;i<=n;i++){if(vis[i]==0&&in[i]==0){vis[i]=1;for(int j=1;j<=n;j++){if(map[i][j]>0){map[i][j]=-map[i][j];in[j]--;}}ans[step]=i;dfs(step+1);vis[i]=0;for(int j=1;j<=n;j++){if(map[i][j]<0){map[i][j]=-map[i][j];in[j]++;}}}}}int main(){while(scanf("%d",&n)==1){flag=0;memset(map,0,sizeof(map));memset(vis,0,sizeof(vis));memset(in,0,sizeof(in));for(int i=1;i<=n;i++){int t;while(scanf("%d",&t),t){map[i][t]=1;in[t]++;}}dfs(1);}return 0;}3．最短路和次短路#include<iostream>#include<cstdio>#include<vector>#include<cstring>using namespace std;class Node{public:int e,w;//表示终点和边权};const int inf=(1<<25);int main(){int ci;cin>>ci;while(ci--){vector<Node> G[1005];//用邻接表存边int n,m;cin>>n>>m;for(int i=1;i<=m;i++){Node q;int u;cin>>u>>q.e>>q.w;G[u].push_back(q);}int s,f;//起点和终点cin>>s>>f;//dijkstra 求最短路和次短路int flag[1005][2];int dis[1005][2],cnt[1005][2];//0表示最短路，1表示次短路memset(flag,0,sizeof(flag));for(int i=1;i<=n;i++) dis[i][0]=dis[i][1]=inf;dis[s][0]=0;cnt[s][0]=1;//初始化for(int c=0;c<2*n;c++) //找最短路和次短路，故要进行2*n次循环也可以改成while(1){int temp=inf,u=-1,k;//找s-S'集合中的最短路径,u记录点的序号，k记录是最短路或者是次短路for(int j=1;j<=n;j++){if(flag[j][0]==0&&temp>dis[j][0]) temp=dis[j][0],u=j,k=0;else if(flag[j][1]==0&&temp>dis[j][1]) temp=dis[j][1],u=j,k=1;}if(temp==inf) break;//S'集合为空或者不联通，算法结束//更新路径flag[u][k]=1;for(int l=0;l<G[u].size();l++){int d=dis[u][k]+G[u][l].w,j=G[u][l].e;//important//4种情况if(d<dis[j][0]){dis[j][1]=dis[j][0];cnt[j][1]=cnt[j][0];dis[j][0]=d;cnt[j][0]=cnt[u][k];}else if(d==dis[j][0]){cnt[j][0]+=cnt[u][k];}else if(d<dis[j][1]){dis[j][1]=d;cnt[j][1]=cnt[u][k];}else if(d==dis[j][1]){cnt[j][1]+=cnt[u][k];}}}int num=cnt[f][0];//最短路int cc=cnt[f][1];//次短路}return 0;}4．SAP模板#include<iostream>#include<cstdio>#include<cstring>using namespace std;const int inf=(1<<31)-1;const int point_num=300;int cap[point_num][point_num],dist[point_num],gap[point_num];//初始化见main里面int s0,t0,n;//源,汇和点数int find_path(int p,int limit=0x3f3f3f3f){if(p==t0) return limit;for(int i=0;i<n;i++)if(dist[p]==dist[i]+1 && cap[p][i]>0){int t=find_path(i,min(cap[p][i],limit));if(t<0) return t;if(t>0){cap[p][i]-=t;cap[i][p]+=t;return t;}}int label=n;for(int i=0;i<n;i++) if(cap[p][i]>0) label=min(label,dist[i]+1);if(--gap[dist[p]]==0 || dist[s0]>=n ) return -1;++gap[dist[p]=label];return 0;}int sap(){//初始化s,ts0=0,t0=n-1;int t=0,maxflow=0;gap[0]=n;while((t=find_path(s0))>=0) maxflow+=t;return maxflow;}int main(){int ci;while(cin>>ci>>n){//初始化memset(cap,0,sizeof(cap));memset(dist,0,sizeof(dist));memset(gap,0,sizeof(gap));//初始化capwhile(ci--){int x,y,c;cin>>x>>y>>c;x--;y--;cap[x][y]+=c;//因题而异}int ans=sap();cout<<ans<<endl;}return 0;}5．已知各点度，问能否组成一个简单图#include<iostream>#include<cstdio>#include<algorithm>using namespace std;const int inf=(1<<30);int d[1100];bool cmp(int x,int y){return x>y;}int main(){int ci;scanf("%d",&ci);while(ci--){int n,flag=1,cnt=0;scanf("%d",&n); for(int i=0;i<n;i++){scanf("%d",&d[i]);if(d[i]>n-1||d[i]<=0) flag=0; cnt+=d[i];}if(flag==0||cnt%2){printf("no\n");continue;}sort(d,d+n,cmp);for(int l=n;l>0;l--){for(int i=1;i<l&&d[0];i++){d[0]--,d[i]--;if(d[i]<0){flag=0;break;}}if(d[0]) flag=0;if(flag==0) break;d[0]=-inf;sort(d,d+l,cmp);}if(flag) printf("yes\n");else printf("no\n");}return 0;}6.KRUSKAL#include<iostream>#include<algorithm>using namespace std;int u[15005],v[15005],w[15005],fath[15005],r[15005];int ans1[15005],ans2[15005];bool cmp(int i,int j){return w[i]<w[j];}int find(int x){return fath[x]==x?x:fath[x]=find(fath[x]);}int main(){int n,m;cin>>n>>m;for(int i=1;i<=n;i++) fath[i]=i;for(int i=1;i<=m;i++) r[i]=i;for(int i=1;i<=m;i++){cin>>u[i]>>v[i]>>w[i];}sort(r+1,r+m+1,cmp);int maxn=0,ans=0,k=0;for(int i=1;i<=m;i++){int e=r[i];int x=find(u[e]),y=find(v[e]);if(x!=y){ans+=w[e];fath[x]=y;if(w[e]>maxn) maxn=w[e];ans1[k]=u[e];ans2[k++]=v[e];}}return 0;}7.prime求最小生成树语法：prim(Graph G,int vcount,int father[]);参数：G：图，用邻接矩阵表示vcount：表示图的顶点个数father[]：用来记录每个节点的父节点返回值：null注意：常数max_vertexes 为图最大节点数常数infinity为无穷大源程序：#define infinity 1000000#define max_vertexes 5typedef int Graph[max_vertexes][max_vertexes];void prim(Graph G,int vcount,int father[]){int i,j,k;intlowcost[max_vertexes],closeset[max_vertexes],used[max_vertexes]; for (i=0;i<vcount;i++){lowcost[i]=G[0][i];closeset[i]=0;used[i]=0;father[i]=-1;}used[0]=1;for (i=1;i<vcount;i++){j=0;while (used[j]) j++;for (k=0;k<vcount;k++)if ((!used[k])&&(lowcost[k]<lowcost[j])) j=k;father[j]=closeset[j];used[j]=1;for (k=0;k<vcount;k++)if (!used[k]&&(G[j][k]<lowcost[k])){ lowcost[k]=G[j][k];closeset[k]=j; }}}8.Dijkstra语法：result=Dijkstra(Graph G,int n,int s,int t, int path[]); 参数：G：图，用邻接矩阵表示n：图的顶点个数s：开始节点t：目标节点path[]：用于返回由开始节点到目标节点的路径返回值：最短路径长度注意：输入的图的权必须非负顶点标号从0 开始用如下方法打印路径：i=t;while (i!=s){printf("%d<--",i+1);i=path[i];}printf("%d\n",s+1);源程序：int Dijkstra(Graph G,int n,int s,int t, int path[]){int i,j,w,minc,d[max_vertexes],mark[max_vertexes];for (i=0;i<n;i++) mark[i]=0;for (i=0;i<n;i++){ d[i]=G[s][i];path[i]=s; }mark[s]=1;path[s]=0;d[s]=0;for (i=1;i<n;i++){minc=infinity;w=0;for (j=0;j<n;j++)if ((mark[j]==0)&&(minc>=d[j])) {minc=d[j];w=j;}mark[w]=1;for (j=0;j<n;j++)if((mark[j]==0)&&(G[w][j]!=infinity)&&(d[j]>d[w]+G[w][j])){ d[j]=d[w]+G[w][j];path[j]=w; }}return d[t];}9.Bellman-ford语法：result=Bellman_ford(Graph G,int n,int s,int t,int path[],int success);参数：G：图，用邻接矩阵表示n：图的顶点个数s：开始节点t：目标节点path[]：用于返回由开始节点到目标节点的路径success：函数是否执行成功返回值：最短路径长度注意：输入的图的权可以为负，如果存在一个从源点可达的权为负的回路则success=0顶点标号从0 开始用如下方法打印路径：i=t;while (i!=s){printf("%d<--",i+1);i=path[i];}printf("%d\n",s+1);源程序：int Bellman_ford(Graph G,int n,int s,int t,int path[],int success){int i,j,k,d[max_vertexes];for (i=0;i<n;i++) {d[i]=infinity;path[i]=0;}d[s]=0;for (k=1;k<n;k++)for (i=0;i<n;i++)for (j=0;j<n;j++)if (d[j]>d[i]+G[i][j]){d[j]=d[i]+G[i][j];path[j]=i;}success=0;for (i=0;i<n;i++)for (j=0;j<n;j++)if (d[j]>d[i]+G[i][j]) return 0;success=1;return d[t];}10. SPFA#include<iostream>#include<cstdio>#include<cstring>#include<vector>using namespace std;const __int64 maxn=1001000;const __int64 inf=1000100000;struct edge//邻接表{__int64 t,w;//s->t=w;__int64 next;//数组模拟指针};__int64 p[maxn],pf[maxn];//邻接表头节点edge G[maxn],Gf[maxn];//邻接表__int64 V,E;//点数[1-n] 边数__int64 dis[maxn];__int64 que[maxn],fro,rear;//模拟队列__int64 vis[maxn];__int64 inque[maxn];//入队次数bool spfa(__int64 s0){fro=rear=0;for(__int64 i=1;i<=V;i++) dis[i]=inf;dis[s0]=0;memset(vis,0,sizeof(vis));memset(inque,0,sizeof(inque));que[rear++]=s0;vis[s0]=1;inque[s0]++;while(fro!=rear){__int64 u=que[fro];fro++;if(fro==maxn) fro=0;vis[u]=0;for(__int64 i=p[u];i!=-1;i=G[i].next){__int64 s=u,t=G[i].t,w=G[i].w;if(dis[t]>dis[s]+w){dis[t]=dis[s]+w;if(vis[t]==0){que[rear++]=t,vis[t]=1;inque[t]++;if(inque[t]>V) return false;if(rear==maxn) rear=0;}}}}return true;}int main(){__int64 ci;scanf("%I64d",&ci);while(ci--){scanf("%I64d%I64d",&V,&E);memset(p,-1,sizeof(p));memset(pf,-1,sizeof(pf)); for(__int64 i=0;i<E;i++){__int64 u,v,w;scanf("%I64d%I64d%I64d",&u,&v,&w);G[i].t=v;G[i].w=w;G[i].next=p[u];p[u]=i;Gf[i].t=u;Gf[i].w=w;Gf[i].next=pf[v];pf[v]=i;}__int64 ans=0;spfa(1);//求第一个点到其他点的最短距离和for(__int64 i=1;i<=V;i++) ans+=dis[i];//反方向再来一次spfa 求其他点到第一个点的最短距离和 for(__int64 i=1;i<=V;i++) p[i]=pf[i];for(__int64 i=0;i<E;i++) G[i]=Gf[i];spfa(1);for(__int64 i=1;i<=V;i++) ans+=dis[i];printf("%I64d\n",ans);}return 0;}11.Kosaraju模板#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int maxn=100000;struct edge{int t,w;//u->t=w;int next;};int V,E;//点数(从1开始)，边数int p[maxn],pf[maxn];//邻接表原图,逆图edge G[maxn],Gf[maxn];//邻接表原图,逆图int l,lf;void init(){memset(p,-1,sizeof(p));memset(pf,-1,sizeof(pf));l=lf=0;}void addedge(int u,int t,int w,int l){G[l].w=w;G[l].t=t;G[l].next=p[u];p[u]=l;}void addedgef(int u,int t,int w,int lf){Gf[l].w=w;Gf[l].t=t;Gf[l].next=pf[u];pf[u]=l;}///Kosaraju算法,返回为强连通分量个数bool flag[maxn]; //访问标志数组int belg[maxn]; //存储强连通分量,其中belg[i]表示顶点i属于第belg[i]个强连通分量int numb[maxn]; //结束时间(出栈顺序)标记,其中numb[i]表示离开时间为i的顶点//用于第一次深搜,求得numb[1..n]的值void VisitOne(int cur, int &sig){flag[cur] = true;for (int i=p[cur];i!=-1;i=G[i].next){if (!flag[G[i].t]){VisitOne(G[i].t,sig);}}numb[++sig] = cur;}//用于第二次深搜,求得belg[1..n]的值void VisitTwo(int cur, int sig){flag[cur] = true;belg[cur] = sig;for (int i=pf[cur];i!=-1;i=Gf[i].next){if (!flag[Gf[i].t]){VisitTwo(Gf[i].t,sig);}}//Kosaraju算法,返回为强连通分量个数int Kosaraju_StronglyConnectedComponent(){int i, sig;//第一次深搜memset(flag,0,sizeof(flag));for ( sig=0,i=1; i<=V; ++i ){if ( false==flag[i] ){VisitOne(i,sig);}}//第二次深搜memset(flag,0,sizeof(flag));for ( sig=0,i=V; i>0; --i ){if ( false==flag[numb[i]] ){VisitTwo(numb[i],++sig);}}return sig;}int main(){while(scanf("%d",&V)==1){init();for(int i=1;i<=V;i++){int u=i,t,w=1;while(scanf("%d",&t)==1&&t){E++;addedge(u,t,w,l++);addedgef(t,u,w,lf++);}}int ans=Kosaraju_StronglyConnectedComponent(); printf("%d\n",ans);}return 0;12.tarjan模板//自己模板#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int maxn=100000;int V,E;//点数(1) 边数struct edge//邻接表{int t,w;//u->t=w;int next;};int p[maxn];//表头节点edge G[maxn];int l;void init(){memset(p,-1,sizeof(p));l=0;}//添加边void addedge(int u,int t,int w,int l)//u->t=w;{G[l].w=w;G[l].t=t;G[l].next=p[u];p[u]=l;}//tarjan算法求有向图强联通分量int dfn[maxn],lowc[maxn];//dfn[u]节点u搜索的次序编号,lowc[u]u或者u的子树能够追溯到的栈中的最早的节点int belg[maxn];//第i个节点属于belg[i]个强连通分量int stck[maxn],stop;//stck栈int instck[maxn];//第i个节点是否在栈中int scnt;//强联通分量int index;void dfs(int i){dfn[i]=lowc[i]=++index;instck[i]=1;//节点i入栈stck[++stop]=i;for(int j=p[i];j!=-1;j=G[j].next){int t=G[j].t;//更新lowc数组if(!dfn[t])//t没有遍历过{dfs(t);if(lowc[i]>lowc[t]) lowc[i]=lowc[t];}//t是i的祖先节点else if(instck[t]&&lowc[i]>dfn[t]) lowc[i]=dfn[t];}//是强连通分量的根节点if(dfn[i]==lowc[i]){scnt++;int t;do{t=stck[stop--];instck[t]=0;belg[t]=scnt;}while(t!=i);}}int tarjan(){stop=scnt=index=0;memset(dfn,0,sizeof(dfn));memset(instck,0,sizeof(instck));for(int i=1;i<=V;i++){if(!dfn[i]) dfs(i);}return scnt;}int main(){while(scanf("%d",&V)==1){init();for(int i=1;i<=V;i++){int x;while(scanf("%d",&x)==1&&x){E++;addedge(i,x,1,l++);}}int ans=tarjan();printf("%d\n",ans);}return 0;}//吉大模板邻接表版#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int maxn=100000;int V,E;//点数(1) 边数struct edge//邻接表{int t,w;//u->t=w;int next;};int p[maxn];//表头节点edge G[maxn];int l;void init(){memset(p,-1,sizeof(p));l=0;}//添加边void addedge(int u,int t,int w,int l)//u->t=w;{G[l].w=w;G[l].t=t;G[l].next=p[u];p[u]=l;}//tarjan算法求有向图强联通分量int dfn[maxn],lowc[maxn];//dfn[u]节点u搜索的次序编号,lowc[u]u或者u的子树能够追溯到的栈中的最早的节点int stck[maxn],stop;//stck栈int pre[maxn];//int scnt;//强联通分量int cnt;//void dfs(int v)//1-V{int t,minc=lowc[v]=pre[v]=cnt++;stck[stop++]=v;for(int i=p[v];i!=-1;i=G[i].next){int pv=G[i].t;if(pre[pv]==-1) dfs(pv);if(lowc[pv]<minc) minc=lowc[pv]; }if(minc<lowc[v]){lowc[v]=minc;return ;}do{dfn[t=stck[--stop]]=scnt;lowc[t]=V;}while(t!=v);++scnt;}int tarjan(){stop=cnt=scnt=0;memset(pre,-1,sizeof(pre));for(int i=1;i<=V;i++){if(pre[i]==-1) dfs(i);}return scnt;}int main(){while(scanf("%d",&V)==1){init();for(int i=1;i<=V;i++){int x;while(scanf("%d",&x)==1&&x){E++;addedge(i,x,1,l++);}}int ans=tarjan();printf("%d\n",ans);}return 0;}二、数学1．剩余定理int mod(int c[],int b[],int n){int all_multy=1,sum=0;int i,j,x[5];for(i=0;i<n;i++)all_multy*=c[i];for(i=0;i<n;i++)x[i]=all_multy/c[i];for(i=0;i<n;i++){j=1;while((x[i]*j)%c[i]!=1)j++;x[i]*=j;}for(i=0;i<n;i++)sum+=(b[i]*x[i]);return sum%all_multy;}2．N!中质因子P的个数//对于任意质数p，n！中有（n/p+n/p^2+n/p^3+...)个质因子p。

高精度算法问题的引入由于计算机运算是有模运算,数据范围的表示有一定限制,如整型int(C++中int 与long相同)表达范围是(-2^31~2^31-1),unsigned long(无符号整数)是(0~2^32-1),都约为几十亿.如果采用实数型,则能保存最大的double只能提供15~16位的有效数字,即只能精确表达数百万亿的数。

因此,在计算位数超过十几位的数时,不能采用现有类型,只能自己编程计算。

目前在青少年信息学奥林匹克竞赛中所涉及到的高精度计算包括加(addition)、减(subtract)、乘(multiply)、除(divide)四种基本运算。

此外，在C++语言中，int类型（4个字节/32位计算机）元素存储十进制的一位数字非常浪费空间，并且运算量也非常大，因此常将程序代码优化为万进制，即数组的每个元素存储高精数字的四位。

（为什么选择万进制，而不选择更大的进制呢？十万进制中的最大值99999相乘时得到的值是9999800001超过4个字节的存储范围而溢出，从而导致程序计算错误。

）本文以暂时以10进制为例讲述高精度算法一、高精度数字的存储高精度计算通用方法:高精度计算时一般用一个数组来存储一个数,数组的一个元素对应于数的一位(当然,在以后的学习中为了加快计算速度,也可用数组的一个元素表示数的多位数字,暂时不讲),表示时,由于数计算时可能要进位,因此为了方便,将数由低位到高位依次存在数组下标对应由低到高位置上,另外,我们申请数组大小时,一般考虑了最大的情况,在很多情况下,表示有富余,即高位有很多0,可能造成无效的运算和判断,因此,我们一般将数组的第0个下标对应位置来存储该数的位数.如数:3485(三千四百八十五)，表达在数组a[10]上情况是:下标0 1 2 3 4 5 6 7 8 9内容 4 5 8 4 3 0 0 0 0 0说明：位数个位十位百位千位例：一个不超过200位的非负整数，可能有多余的前导0。

高精度模板施工工法高精度模板施工工法一、前言高精度模板施工工法是一种应用于建筑工程的先进施工技术，通过使用精确的模板和优质的材料，可以实现高精度的施工效果。

本文将介绍该工法的特点、适应范围、工艺原理、施工工艺、劳动组织、机具设备、质量控制、安全措施、经济技术分析和工程实例，以便读者全面了解该工法的应用和优势。

二、工法特点高精度模板施工工法具有以下几个特点：1. 精确性高：由于采用了精确的模板和控制措施，可以实现非常高的施工精度，符合工程设计要求。

2. 施工速度快：高精度模板施工工法采用模块化施工，可提高施工速度，缩短工期，提高工作效率。

3. 质量可控：通过精确的模板和严格的质量控制措施，可以确保施工质量稳定可靠，减少施工质量问题。

4. 环保节能：该工法能够最大限度地减少材料的浪费，并降低对环境的影响，符合绿色施工的要求。

三、适应范围高精度模板施工工法适用于各种类型的建筑工程，特别是对于要求施工精度高、工期紧的工程，如高层建筑、桥梁、隧道等。

同时，该工法也适用于特殊材料的施工，如玻璃幕墙、墙面装饰等。

四、工艺原理高精度模板施工工法的理论依据是通过对施工工法与实际工程之间的联系、采取的技术措施进行分析和解释。

工程实际上采用的是先制作模板，然后在现场组装起来。

在施工过程中，通过模板的精确定位和控制，以及严格的质量和安全控制措施，来实现施工过程的精确、高效和安全。

五、施工工艺高精度模板施工工法包括以下几个阶段：1. 深入了解工程设计要求和施工条件。

2. 制作精确的模板和支撑系统。

3. 进行现场模板的组装和安装。

4. 进行混凝土浇筑和养护。

5. 进行模板的拆除和整理。

六、劳动组织高精度模板施工工法需要优秀的施工团队和管理人员，他们应该具备相关的经验和技术知识，能够组织和协调好各个施工环节，确保施工的高质量和高效率。

七、机具设备高精度模板施工工法需要使用一系列专用机具和设备，如塔吊、脚手架、模板支撑系统等。

免费模板~~~ACM Standard Code LibraryHuang WeiSoftware EngineeringComputer and Software CollegeHangzhou Dianzi UniversityOctober,2008ACM算法模板集Contents一.常用函数与STL二.重要公式与定理1.Fibonacci Number2.Lucas Number3.Catalan Number4.Stirling Number(Second Kind)5.Bell Number6.Stirling's Approximation7.Sum of Reciprocal Approximation8.Young Tableau9.整数划分10.错排公式11.三角形内切圆半径公式12.三角形外接圆半径公式13.圆內接四边形面积公式14.基础数论公式三.大数模板，字符读入四.数论算法1.Greatest Common Divisor最大公约数2.Prime素数判断3.Sieve Prime素数筛法4.Module Inverse模逆元5.Extended Euclid扩展欧几里德算法6.Modular Linear Equation模线性方程(同余方程)7.Chinese Remainder Theorem中国余数定理(互素与非互素)8.Euler Function欧拉函数9.Farey总数9.Farey序列构造ler_Rabbin素数测试，Pollard_rho因式分解五.图论算法1.最小生成树(Kruscal算法)2.最小生成树(Prim算法)3.单源最短路径(Bellman-ford算法)4.单源最短路径(Dijkstra算法)5.全源最短路径(Folyd算法)6.拓扑排序7.网络预流和最大流8.网络最小费用最大流9.网络最大流(高度标号预流推进)10.最大团11.最大匹配(Hungary，HopcroftKarp算法)12.带权二分图最优匹配(KM算法)13.强连通分量(Kosaraju算法)14.强连通分量(Gabow算法)15.无向图割边割点和双连通分量16.最小树形图O(N^3)17.最小树形图O(VE)六.几何算法1.几何模板2.球面上两点最短距离3.三点求圆心坐标4.三角形几个重要的点七.专题讨论1.树状数组2.字典树3.后缀树4.线段树5.并查集6.二叉堆7.逆序数(归并排序)8.树状DP9.欧拉路10.八数码11.高斯消元法12.字符串匹配(KMP算法)13.全排列,全组合14.二维线段树15.稳定婚姻匹配16.后缀数组17.左偏树18.标准RMQ-ST19.度限制最小生成树20.最优比率生成树(0/1分数规划)21.最小花费置换22.区间K大数23.LCA-RMQ-ST24.LCA–Tarjan25.指数型母函数26.指数型母函数(大数据)27.AC自动机(字典树+KMP)28.FFT(大数乘法)29.二分图网络最大流最小割30.混合图欧拉回路31.无源汇上下界网络流32.二分图最小点权覆盖33.带约束的轨道计数(Burnside引理)34.三分法求函数波峰35.单词计数，DFA自动机，Trie图(完全AC自动机)36.字符串和数值hash37.滚动队列，前向星表示法38.最小点基，最小权点基39.LCSubsequence O(N^2/logN)40.伸展树41.Treap42.0/1分数规划K约束43.表达式求值44.乘除法博弈,Wythoff博弈45.状态压缩的积木型DP46.解一般线性方程组(消元法)47.块状链表48.Factor Oracle第一章常用函数和STL一.常用函数#include<stdio.h>int getchar(void);//读取一个字符,一般用来去掉无用字符char*gets(char*str);//读取一行字符串#include<stdlib.h>void*malloc(size_t size);//动态内存分配,开辟大小为size的空间void qsort(void*buf,size_t num,size_t size,int(*compare)(const void*,const void*));//快速排序Sample:int compare_ints(const void*a,const void*b){int*arg1=(int*)a;int*arg2=(int*)b;if(*arg1<*arg2)return-1;else if(*arg1==*arg2)return0;else return1;}int array[]={-2,99,0,-743,2,3,4};int array_size=7;qsort(array,array_size,sizeof(int),compare_ints);#include<math.h>//求反正弦,arg∈[-1,1],返回值∈[-pi/2,+pi/2]double asin(double arg);//求正弦,arg为弧度,弧度=角度*Pi/180.0,返回值∈[-1,1]double sin(double arg);//求e的arg次方double exp(double arg);//求num的对数,基数为edouble log(double num);//求num的根double sqrt(double num);//求base的exp次方double pow(double base,double exp);#include<string.h>//初始化内存,常用来初始化数组void*memset(void*buffer,int ch,size_t count);memset(the_array,0,sizeof(the_array));//printf是它的变形,常用来将数据格式化为字符串int sprintf(char*buffer,const char*format,...);sprintf(s,"%d%d",123,4567);//s="1234567"//scanf是它的变形,常用来从字符串中提取数据int sscanf(const char*buffer,const char*format,...);Sample:char result[100]="24hello",str[100];int num;sprintf(result,"%d%s",num,str);//num=24;str="hello";//字符串比较,返回值<0代表str1<str2,=0代表str1=str2,>0代表str1>str2 int strcmp(const char*str1,const char*str2);二.常用STL[标准container概要]vector<T>大小可变的向量,类似数组的用法,容易实现删除list<T>双向链表queue<T>队列,empty(),front(),pop(),push()stack<T>栈,empty(),top(),pop(),push()priority_queue<T>优先队列,empty(),top(),pop(),push()set<T>集合map<key,val>关联数组,常用来作hash映射[标准algorithm摘录]for_each()对每一个元素都唤起（调用）一个函数find()查找第一个能与引数匹配的元素replace()用新的值替换元素,O(N)copy()复制（拷贝）元素,O(N)remove()移除元素reverse()倒置元素sort()排序,O(N log(N))partial_sort()部分排序binary_search()二分查找merge()合并有序的序列,O(N)[C++String摘录]copy()从别的字符串拷贝empty()判断字符串是否为空erase()从字符串移除元素find()查找元素insert()插入元素length()字符串长度replace()替换元素substr()取子字符串swap()交换字符串第二章重要公式与定理1.Fibonacci Number0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610…Formula:011211i i i n n F F F F F F −−===+⎡⎤⎥==⎥⎠⎦2.Lucas Number1,3,4,7,11,18,29,47,76,123...Formula:n nn L =+⎝⎠⎝⎠3.Catalan Number1,2,5,14,42,132,429,1430,4862,16796,58786,208012…Formula:110(2,)1*n n n i n ii C n n Cat n Cat Cat Cat −−−==+=∑Application:1)将n +2边形沿弦切割成n 个三角形的不同切割数Sample:n =2;n =3;2)n +1个数相乘,给每两个元素加上括号的不同方法数Sample:n =2;(1(23)),((12)3)n =3;(1(2(34))),(1((23)4)),((12)(34)),((1(23))4),(((12)3)4)3)n 个节点的不同形状的二叉树数(严《数据结构》P .155)4)从n *n 方格的左上角移动到右下角不升路径数Sample:n =2;n =3;4.Stirling Number(Second Kind)S(n,m)表示含n 个元素的集合划分为m 个集合的情况数或者是n 个有标号的球放到m 个无标号的盒子中,要求无一为空,其不同的方案数Formula:,1,11,0 (0 || ) (1)n m n m n m m n m S S m S n m −−−=<⎧⎨+×>≥⎩,01(1)(,)()!m i n n m i S C m i m i m ==−××−∑Special Cases:,0,11,2,3,1,01211(3323)6(,2)1n n n n n n n n n n n S S S S S C n S −−===−=−×+==5.Bell Numbern 个元素集合所有的划分数Formula:,0nn n ii B S ==∑6.Stirling's Approximation!nn n e ⎞=⎟⎠7.Sum of Reciprocal ApproximationEulerGamma =0.57721566490153286060651209;11ln() ()n i n EulerGamma n i==+→∞∑8.Young TableauYoung Tableau(杨式图表)是一个矩阵,它满足条件:如果格子[i,j]没有元素,则[i+1,j]也一定没有元素如果格子[i,j]有元素a[i,j],则[i+1,j]要么没有元素,要么a[i+1,j]>a[i,j]Y[n]代表n 个数所组成的杨式图表的个数Formula:121212(1) (2)n n n Y Y Y Y n Y n −−===+−×>Sample:n =3;9.整数划分将整数n 分成k 份,且每份不能为空,任意两种分法不能相同1)不考虑顺序for (int p=1;p<=n ;p++)for (int i=p;i<=n ;i++)for (int j=k;j>=1;j--)dp[i][j]+=dp[i-p][j-1];cout<<dp[n][k]<<endl;2)考虑顺序dp[i][j]=dp[i-k][j-1];(k=1..i)3)若分解出来的每个数均有一个上限mdp[i][j]=dp[i-k][j-1];(k=1..m)10.错排公式121201(1)()n n n D D D n D D −−===−×+11.三角形内切圆半径公式22a b cp s sr a b c++===++12.三角形外接圆半径公式4abcR s=13.圆內接四边形面积公式2a b c dp s +++==14.基础数论公式1)模取幂%((((%)*)%))%n a b a b a b b=…2)n 的约数的个数若n 满足1212m n n n m n p p p =+++…,则n 的约数的个数为12(1)(1)(1)m n n n +++…第三章大数模板typedef int hugeint;//应不大于,以防乘法时溢出const int Base=1000;const int Capacity=1000;struct xnum{int Len;int Data[Capacity];xnum():Len(0){}xnum(const xnum&V):Len(V.Len){memcpy(Data,V.Data,Len*sizeof*Data);}xnum(int V):Len(0){for(;V>0;V/=Base)Data[Len++]=V%Base;}xnum(char S[]);xnum&operator=(const xnum&V){Len=V.Len;memcpy(Data,V.Data,Len*sizeof*Data);return*this;}int&operator[](int Index){return Data[Index];}int operator[](int Index)const{return Data[Index];}void print(){printf("%d",Len==0?0:Data[Len-1]);for(int i=Len-2;i>=0;i--)for(int j=Base/10;j>0;j/=10)printf("%d",Data[i]/j%10);}};xnum::xnum(char S[]){int I,J;Data[Len=0]=0;J=1;for(I=strlen(S)-1;I>=0;I--){Data[Len]+=(S[I]-'0')*J;J*=10;if(J>=Base)J=1,Data[++Len]=0;}if(Data[Len]>0)Len++;}int compare(const xnum&A,const xnum&B){int I;if(A.Len!=B.Len)return A.Len>B.Len?1:-1;for(I=A.Len-1;I>=0&&A[I]==B[I];I--);if(I<0)return0;return A[I]>B[I]?1:-1;}xnum operator+(const xnum&A,const xnum&B){xnum R;int I;int Carry=0;for(I=0;I<A.Len||I<B.Len||Carry>0;I++) {if(I<A.Len)Carry+=A[I];if(I<B.Len)Carry+=B[I];R[I]=Carry%Base;Carry/=Base;}R.Len=I;return R;}xnum operator-(const xnum&A,const xnum&B){xnum R;int Carry=0;R.Len=A.Len;int I;for(I=0;I<R.Len;I++){R[I]=A[I]-Carry;if(I<B.Len)R[I]-=B[I];if(R[I]<0)Carry=1,R[I]+=Base;else Carry=0;}while(R.Len>0&&R[R.Len-1]==0)R.Len--;return R;}xnum operator*(const xnum&A,const int B){int I;if(B==0)return0;xnum R;hugeint Carry=0;for(I=0;I<A.Len||Carry>0;I++){if(I<A.Len)Carry+=hugeint(A[I])*B;R[I]=Carry%Base;Carry/=Base;}R.Len=I;return R;}xnum operator*(const xnum&A,const xnum&B){int I;if(B.Len==0)return0;xnum R;for(I=0;I<A.Len;I++){hugeint Carry=0;for(int J=0;J<B.Len||Carry>0;J++){if(J<B.Len)Carry+=hugeint(A[I])*B[J];if(I+J<R.Len)Carry+=R[I+J];if(I+J>=R.Len)R[R.Len++]=Carry%Base;else R[I+J]=Carry%Base;Carry/=Base;}}return R;}xnum operator/(const xnum&A,const int B){xnum R;int I;hugeint C=0;for(I=A.Len-1;I>=0;I--){C=C*Base+A[I];R[I]=C/B;C%=B;}R.Len=A.Len;while(R.Len>0&&R[R.Len-1]==0)R.Len--;return R;}//divxnum operator/(const xnum&A,const xnum&B){int I;xnum R,Carry=0;int Left,Right,Mid;for(I=A.Len-1;I>=0;I--){Carry=Carry*Base+A[I];Left=0;Right=Base-1;while(Left<Right){Mid=(Left+Right+1)/2;if(compare(B*Mid,Carry)<=0)Left=Mid;else Right=Mid-1;}R[I]=Left;Carry=Carry-B*Left;}R.Len=A.Len;while(R.Len>0&&R[R.Len-1]==0)R.Len--;return R;}//modxnum operator%(const xnum&A,const xnum&B){int I;xnum R,Carry=0;int Left,Right,Mid;for(I=A.Len-1;I>=0;I--){Carry=Carry*Base+A[I];Left=0;Right=Base-1;while(Left<Right){Mid=(Left+Right+1)/2;if(compare(B*Mid,Carry)<=0)Left=Mid;else Right=Mid-1;}R[I]=Left;Carry=Carry-B*Left;}R.Len=A.Len;while(R.Len>0&&R[R.Len-1]==0)R.Len--;return Carry;}istream&operator>>(istream&In,xnum&V){char Ch;for(V=0;In>>Ch;){V=V*10+(Ch-'0');if(cin.peek()<='')break;}return In;}ostream&operator<<(ostream&Out,const xnum&V){int I;Out<<(V.Len==0?0:V[V.Len-1]);for(I=V.Len-2;I>=0;I--)for(int J=Base/10;J>0;J/=10)Out<<V[I]/J%10;return Out;}xnum gcd(xnum a,xnum b){if(compare(b,0)==0)return a;else return gcd(b,a%b);}int div(char*A,int B){int I;int C=0;int Alen=strlen(A);for(I=0;I<Alen;I++){C=C*Base+A[I]-'0';C%=B;}return C;}xnum C(int n,int m){int i;xnum sum=1;for(i=n;i>=n-m+1;i--)sum=sum*i;for(i=1;i<=m;i++)sum=sum/i;return sum;}#define MAXN9999#define DLEN4class BigNum{private:int a[1000];//可以控制大数的位数int len;//大数长度public:BigNum(){len=1;memset(a,0,sizeof(a));} BigNum(const int);BigNum(const char*);BigNum(const BigNum&);BigNum&operator=(const BigNum&);BigNum operator+(const BigNum&)const;BigNum operator-(const BigNum&)const;BigNum operator*(const BigNum&)const;BigNum operator/(const int&)const;BigNum operator^(const int&)const;int operator%(const int&)const;bool operator>(const BigNum&T)const;void print();};BigNum::BigNum(const int b){int c,d=b;len=0;memset(a,0,sizeof(a));while(d>MAXN){c=d-(d/(MAXN+1))*(MAXN+1);d=d/(MAXN+1);a[len++]=c;}a[len++]=d;}BigNum::BigNum(const char*s){int t,k,index,l,i;memset(a,0,sizeof(a));l=strlen(s);len=l/DLEN;if(l%DLEN)len++;index=0;for(i=l-1;i>=0;i-=DLEN){t=0;k=i-DLEN+1;if(k<0)k=0;for(int j=k;j<=i;j++)t=t*10+s[j]-'0';a[index++]=t;}}BigNum::BigNum(const BigNum&T):len(T.len){ int i;memset(a,0,sizeof(a));for(i=0;i<len;i++)a[i]=T.a[i];}BigNum&BigNum::operator=(const BigNum&n){ len=n.len;memset(a,0,sizeof(a));int i;for(i=0;i<len;i++)a[i]=n.a[i];return*this;}BigNum BigNum::operator+(const BigNum&T)const{ BigNum t(*this);int i,big;//位数big=T.len>len?T.len:len;for(i=0;i<big;i++){t.a[i]+=T.a[i];if(t.a[i]>MAXN){t.a[i+1]++;t.a[i]-=MAXN+1;}}if(t.a[big]!=0)t.len=big+1;else t.len=big;return t;}BigNum BigNum::operator-(const BigNum&T)const{ int i,j,big;bool flag;BigNum t1,t2;if(*this>T){t1=*this;t2=T;flag=0;}else{t1=T;t2=*this;flag=1;}big=t1.len;for(i=0;i<big;i++){if(t1.a[i]<t2.a[i]){j=i+1;while(t1.a[j]==0)j++;t1.a[j--]--;while(j>i)t1.a[j--]+=MAXN;t1.a[i]+=MAXN+1-t2.a[i];}else t1.a[i]-=t2.a[i];}t1.len=big;while(t1.a[len-1]==0&&t1.len>1){t1.len--;big--;}if(flag)t1.a[big-1]=0-t1.a[big-1];return t1;}BigNum BigNum::operator*(const BigNum&T)const{BigNum ret;int i,j,up;int temp,temp1;for(i=0;i<len;i++){up=0;for(j=0;j<T.len;j++){temp=a[i]*T.a[j]+ret.a[i+j]+up;if(temp>MAXN){temp1=temp-temp/(MAXN+1)*(MAXN+1);up=temp/(MAXN+1);ret.a[i+j]=temp1;}else{up=0;ret.a[i+j]=temp;}}if(up!=0)ret.a[i+j]=up;}ret.len=i+j;while(ret.a[ret.len-1]==0&&ret.len>1)ret.len--;return ret;}BigNum BigNum::operator/(const int&b)const{BigNum ret;int i,down=0;for(i=len-1;i>=0;i--){ret.a[i]=(a[i]+down*(MAXN+1))/b;down=a[i]+down*(MAXN+1)-ret.a[i]*b;}ret.len=len;while(ret.a[ret.len-1]==0&&ret.len>1)ret.len--;return ret;}int BigNum::operator%(const int&b)const{int i,d=0;for(i=len-1;i>=0;i--){d=((d*(MAXN+1))%b+a[i])%b;}return d;}BigNum BigNum::operator^(const int&n)const{BigNum t,ret(1);if(n<0)exit(-1);if(n==0)return1;if(n==1)return*this;int m=n;while(m>1){t=*this;int i;for(i=1;i<<1<=m;i<<=1){t=t*t;}m-=i;ret=ret*t;if(m==1)ret=ret*(*this);}return ret;}bool BigNum::operator>(const BigNum&T)const{ int ln;if(len>T.len)return true;else if(len==T.len){ln=len-1;while(a[ln]==T.a[ln]&&ln>=0)ln--;if(ln>=0&&a[ln]>T.a[ln])return true;else return false;}else return false;}void BigNum::print(){int i;cout<<a[len-1];for(i=len-2;i>=0;i--){cout.width(DLEN);cout.fill('0');cout<<a[i];}}//读取整数const int ok=1;int get_val(int&ret){ret=0;char ch;while((ch=getchar())>'9'||ch<'0');do{ret=ret*10+ch-'0';}while((ch=getchar())<='9'&&ch>='0');return ok;}//带负数int get_val(int&ret){ret=0;char ch;bool neg=false;while(((ch=getchar())>'9'||ch<'0')&&ch!='-');if(ch=='-'){neg=true;while((ch=getchar())>'9'||ch<'0');}do{ret=ret*10+ch-'0';}while((ch=getchar())<='9'&&ch>='0');ret=(neg?-ret:ret);return ok;}//读取整数,可判EOF和EOLconst int eof=-1;const int eol=-2;int get_val(int&ret){ret=0;char ch;while(((ch=getchar())>'9'||ch<'0')&&ch!=EOF);if(ch==EOF)return eof;do{ret=ret*10+ch-'0';}while((ch=getchar())<='9'&&ch>='0');if(ch=='\n')return eol;return ok;}//读取浮点数int get_val(double&ret){ret=0;double base=0.1;char ch;bool dot=false,neg=false;while(((ch=getchar())>'9'||ch<'0')&&ch!='.'&&ch!='-');if(ch=='-'){neg=true;while(((ch=getchar())>'9'||ch<'0')&&ch!='.'&&ch!='-');}do{if(ch=='.'){dot=true;continue;}if(dot){ret+=(ch-'0')*base;base*=0.1;}else ret=ret*10+(ch-'0');}while(((ch=getchar())<='9'&&ch>='0')||ch=='.');ret=(neg?-ret:ret);return ok;}typedef long long LL;//LL MultiMod(LL a,LL b,LL c){//if(b)//return(a*(b&1)%c+(MultiMod(a,b>>1,c)<<1))%c; //return0;//}LL MultiMod(LL a,LL b,LL c){LL ret=0,d=a;for(;b;b>>=1,d<<=1,d%=c)if((b&1))ret=(ret+d)%c;return ret;}//128-bits integer's power with mod in O(64*LogN)LL ModPower(LL base,LL exp,LL mod){LL ret=1;for(;exp;exp>>=1,base=MultiMod(base,base,mod)) if((exp&1))ret=MultiMod(ret,base,mod);return ret;}第四章数论算法1.Greatest Common Divisor最大公约数int GCD(int x,int y){int t;while(y>0){t=x%y;x=y;y=t;}return x;}2.Prime素数判断bool is_prime(int u){if(u==0||u==1)return false;if(u==2)return true;if(u%2==0)return false;for(int i=3;i<=sqrt(u);i+=2)if(u%i==0)return false;return true;}3.Sieve Prime素数筛法const int M=1000;//M:sizebool mark[M];//true:prime numbervoid sieve_prime(){memset(mark,true,sizeof(mark));mark[0]=mark[1]=false;for(int i=2;i<=sqrt(M);i++){if(mark[i]){for(int j=i*i;j<M;j+=i)mark[j]=false;}}}4.Module Inverse模逆元//ax≡1(mod n)int Inv(int a,int n){int d,x,y;d=extended_euclid(a,n,x,y);if(d==1)return(x%n+n)%n;else return-1;//no solution}5.Extended Euclid扩展欧几里德算法//如果GCD(a,b)=d,则存在x,y,使d=ax+by//extended_euclid(a,b)=ax+byint extended_euclid(int a,int b,int&x,int&y){int d;if(b==0){x=1;y=0;return a;}d=extended_euclid(b,a%b,y,x);y-=a/b*x;return d;}6.Modular Linear Equation模线性方程(同余方程) //如果GCD(a,b)不能整除c,则ax+by=c没有整数解//ax≡b(mod n)n>0//上式等价于二元一次方程ax–ny=bvoid modular_linear_equation(int a,int b,int n){int d,x,y,x0,gcd;//可以减少扩展欧几里德溢出的可能gcd=GCD(a,n);if(b%gcd!=0){cout<<"no solution"<<endl;return;}a/=gcd;b/=gcd;n/=gcd;d=extended_euclid(a,n,x,y);if(b%d==0){x0=(x*(b/d))%n;//x0:basic solutionint ans=n;//min x=(x0%(n/d)+(n/d))%(n/d)for(int i=0;i<d;i++){ans=(x0+i*(n/d))%n;cout<<ans<<endl;}}else cout<<"no solution"<<endl;}7.Chinese Remainder Theorem中国余数定理//x≡b[i](mod w[i]),i∈[1,len-1]//前提条件w[i]>0,且w[]中任意两个数互质int chinese_remainder(int b[],int w[],int len){int i,d,x,y,m,n,ret;ret=0;n=1;for(i=0;i<len;i++)n*=w[i];for(i=0;i<len;i++){m=n/w[i];d=extended_euclid(w[i],m,x,y);ret=(ret+y*m*b[i])%n;}return(n+ret%n)%n;}//m≡r[i](mod a[i])//a[i]可以不互素//-1表示无解/*Pku2891Strange Way to Express Integers假设C≡A1(mod B1)，C≡A2(mod B2)。

高精度模板施工工法高精度模板施工工法一、前言高精度模板施工工法是一种在建筑施工中广泛应用的技术，它通过采取一系列的工艺原理和施工工艺，能够实现高精度的模板施工，提高施工效率，保证施工质量，降低施工风险。

本文将详细介绍高精度模板施工工法的特点、适应范围、工艺原理、施工工艺、劳动组织、机具设备、质量控制、安全措施、经济技术分析和工程实例等内容。

二、工法特点高精度模板施工工法的特点主要有以下几点：精确度高、施工效率高、适用范围广、施工质量可控、风险控制好等。

三、适应范围高精度模板施工工法适用于各类建筑工程，特别是对于要求较高的大型工程和特殊建筑物，如高层建筑、桥梁、水利工程等，能够满足工程的准确度和施工效率要求。

四、工艺原理高精度模板施工工法的原理主要包括施工工法与实际工程的联系和采取的技术措施。

通过对施工工法与实际工程的对接，确定模板施工的具体要求和步骤；采取先进的技术措施，如激光测量、数字化设计和全过程三维建模等，来保证施工的精确度和效率。

五、施工工艺高精度模板施工工法的施工过程分为多个阶段，包括设计阶段、准备阶段、模板制作阶段、施工阶段和验收阶段。

针对每个阶段，都会进行详细的描述，包括具体的步骤、要点和注意事项，以便读者了解施工工艺的每一个细节。

六、劳动组织良好的劳动组织是高精度模板施工工法的保证，需要合理调配施工人力资源，安排施工人员的工作任务，明确责任和权限，确保施工过程的顺利进行。

七、机具设备高精度模板施工工法所需的机具设备包括激光测量仪、数控切割机、数字化设备等。

本文将对这些机具设备的特点、性能和使用方法进行详细介绍，以便读者对其进行了解。

八、质量控制高精度模板施工工法的质量控制是确保施工质量达到设计要求的关键。

本文将详细介绍质量控制的方法和措施，包括质量检测、质量监控和质量整改等，以确保施工过程中的质量稳定和成功。

九、安全措施在高精度模板施工工法中，安全是至关重要的，需要特别注意施工中的危险因素和安全措施。

高精模板包括哪些随着科技的不断发展，高精模板在各行各业中扮演了重要的角色。

高精模板是指具有高精度、高效率、高质量的模型或样板，可用于各种任务和应用。

本文将介绍高精模板所包括的几个方面。

1. 高精图像模板高精图像模板是一种通过强大的算法和处理技术，生成高质量图像的模板。

这些模板可以用于图像处理、计算机视觉、虚拟现实等领域。

高精图像模板可以应用于图像增强、图像恢复、图像修复等任务，提供清晰、真实的图像输出。

2. 高精音频模板高精音频模板可以用于音频处理、音频识别、音频合成等任务。

通过先进的音频处理算法，高精音频模板可以提供高质量的音频输出。

这些模板可以应用于语音识别、语音合成、音频增强等应用场景，帮助用户实现更好的听觉体验。

3. 高精视频模板高精视频模板是一类用于视频处理、视频编辑、视频合成等任务的模板。

这些模板可以通过先进的视频处理算法提供高质量的视频输出。

高精视频模板可以应用于视频剪辑、视频修复、视频增强等任务，提供清晰、流畅的视频效果。

4. 高精模型模板高精模型模板是一种预先训练好的模型，可以用于各种机器学习和深度学习任务。

这些模板经过大规模数据集的训练和优化，可以提供高精度和高效率的模型预测结果。

高精模型模板包括各种类型的模型，如图像分类模型、文本生成模型、目标检测模型等，可以应用于各种领域的任务。

5. 高精设计模板高精设计模板是指用于设计领域的模板，可以应用于平面设计、UI设计、3D 建模等任务。

这些模板提供了高质量的设计元素和设计思路，帮助设计师快速创建出高精度的设计作品。

高精设计模板不仅可以加快设计过程，还可以提高设计作品的品质和吸引力。

总结起来，高精模板涵盖了图像、音频、视频、模型和设计等多个方面。

它们可以提供高质量的输出结果，帮助用户解决各种任务和应用需求。

随着科技的不断进步，高精模板将在各行各业中发挥更加重要的作用，并为用户带来更好的体验和效果。

注：本文使用的关键词为“高精模板、高精度、高效率、高质量、图像处理、计算机视觉、虚拟现实、音频处理、音频识别、音频合成、视频处理、视频编辑、视频合成、机器学习、深度学习、图像分类、文本生成、目标检测、平面设计、UI 设计、3D建模”。

压位⾼精度模板不⾛程序，直接上板⼦。

第⼀个板⼦压四位，⽀持带符号的加减乘。

第⼆个板⼦压九位，⽀持不带符号的四则运算和取模。

都封装了。

#include <iostream>#include <cstdio>#include <cstring>using namespace std;struct intX{static const int M=600;int xb[M+5];intX& operator=(const char* c){memset(xb,0,sizeof(xb));int n=strlen(c),j=1,k=1;for(int i=1;i<n;i++,k*=10){if(k==10000) j++,k=1;xb[j]+=k*(c[n-i]-'0');}xb[0]=j,xb[M]=c[0]-'0';return *this;}intX& operator=(int a){char s[25];sprintf(s+1,"%d",a);if(a<0) s[0]='1'; else s[0]='0';return *this=s;}intX() {memset(xb,0,sizeof(xb)); xb[0]=1;}intX(int n) {*this=n;}bool operator>(const intX &b) const{if(xb[M]!=b.xb[M]) return xb[M]<b.xb[M];if(xb[0]!=b.xb[0]) return xb[M]?xb[0]<b.xb[0]:xb[0]>b.xb[0];for(int i=xb[0];i>0;i--)if(xb[i]!=b.xb[i]) return xb[M]?xb[i]<b.xb[i]:xb[i]>b.xb[i];return false;}bool operator<(const intX &b) const {return b>*this;}bool operator<=(const intX &b) const {return !(*this>b);}bool operator>=(const intX &b) const {return !(b>*this);}bool operator!=(const intX &b) const {return b>*this||*this>b;}bool operator==(const intX &b) const {return !(b>*this)&&!(*this>b);}intX operator+(const intX &b) const{intX c,d=b,e=*this;if(xb[M]^b.xb[M]){e.xb[M]=d.xb[M]=0;c=e>d?e-d:d-e;if((e>d&&xb[M]) || (e<d&&b.xb[M])) c.xb[M]=1;return c;}c.xb[0]=max(xb[0],b.xb[0]), c.xb[M]=xb[M];for(int i=1;i<=c.xb[0];i++){}if(c.xb[c.xb[0]+1]>0) c.xb[0]++;return c;}intX operator-(const intX &b) const{intX c,d=b,e=*this;if(e<0 && d<0) {d.xb[M]=e.xb[M]=0; return d-e;}else if(d<0) {d.xb[M]=0; return d+e;}else if(e<0) {d.xb[M]=1; return d+e;}else if(e<d) {c=d-e; c.xb[M]=1; return c;}c.xb[0]=xb[0];for(int i=1;i<=c.xb[0];i++){c.xb[i]+=xb[i]-b.xb[i];if(c.xb[i]<0) c.xb[i]+=10000, c.xb[i+1]--;}while(!c.xb[c.xb[0]]&&c.xb[0]>1) c.xb[0]--;return c;}intX& operator+=(const intX &b) {return *this=*this+b;} intX& operator-=(const intX &b) {return *this=*this-b;} intX operator*(const intX &b) const{intX c;c.xb[0]=xb[0]+b.xb[0]+1;for(int i=1;i<=xb[0];i++)for(int j=1;j<=b.xb[0];j++)c.xb[i+j-1]+=xb[i]*b.xb[j],c.xb[i+j]+=c.xb[i+j-1]/10000,c.xb[i+j-1]%=10000;while(!c.xb[c.xb[0]] && c.xb[0]>1) c.xb[0]--;if(*this!=0 && b!=0) c.xb[M]=xb[M]^b.xb[M];return c;}intX operator*=(const intX &b) {return *this=*this*b;} void readX(intX &b){char s[2*M]; scanf("%s",s+1);if(s[1]=='-') s[1]='0',s[0]='1'; else s[0]='0';b=s;}void writeX(){if(xb[M]) printf("-");printf("%d",xb[xb[0]]);for(int i=xb[0]-1;i>0;i--)printf("%04d",xb[i]);}};int main(){intX a,b;a.readX(a),b.readX(b);(a+b).writeX();return 0;}#include<iostream>#include<cstdio>#include<cstring>using namespace std;const int LEN=10000+1,BIT=9;static const int MOD=1000000000;long long s[LEN];bool flag;intX() {memset(s,0,sizeof(s)); s[0]=flag=1;}intX& operator=(const char *num){int l=strlen(num);memset(s,0,sizeof(s));for(int i=l-1;i>=0;i-=BIT){++s[0];long long w=1;for(int j=i;j>i-BIT && j>=0;j--)s[s[0]]+=(num[j]^48)*w, w*=10;}return *this;}intX& operator=(int num){char a[LEN];sprintf(a,"%d",num);return *this=a;}intX(int n) {*this = n;}intX(const char *n) {*this = n;}bool operator>(const intX &a) const{if(s[0]!=a.s[0]) return s[0]>a.s[0];int up=max(s[0],a.s[0]);for(int i=0;i<up;i++)if(s[up-i]!=a.s[up-i]) return s[up-i]>a.s[up-i];return false;}bool operator<(const intX &a) const {return a>*this;}bool operator<=(const intX &a) const {return !(*this>a);}bool operator>=(const intX &a) const {return !(a>*this);}bool operator!=(const intX &a) const {return a>*this||*this>a;}bool operator==(const intX &a) const {return !(a>*this)&&!(*this>a);} intX operator+(const intX &a) const{intX c;int x=0;c.s[0]=max(a.s[0],s[0])+1;for(int i=1;i<=c.s[0];i++)c.s[i]=a.s[i]+s[i]+x,x=c.s[i]/MOD,c.s[i]%=MOD;while(c.s[c.s[0]]==0 && c.s[0]>1) c.s[0]--;return c;}intX& operator+=(const intX &a) {return *this=*this+a;}intX operator-(const intX &a) const{intX c;c.s[0]=max(a.s[0],s[0])+1;if(*this<a) c.flag=false;for(int i=1;i<=c.s[0];i++){if(c.flag) c.s[i]+=s[i]-a.s[i];else c.s[i]+=a.s[i]-s[i];if(c.s[i]<0) c.s[i]+=MOD, c.s[i+1]--;}while(c.s[c.s[0]]==0 && c.s[0]>1) c.s[0]--;intX& operator-=(const intX &a) {return *this=*this-a;}intX operator*(const intX &a) const{intX c;c.s[0]=s[0]+a.s[0];for(int i=1;i<=s[0];i++){int x=0;for(int j=1;j<=a.s[0];j++)c.s[i+j-1]+=s[i]*a.s[j]+x,x=c.s[i+j-1]/MOD,c.s[i+j-1]%=MOD;c.s[i+a.s[0]]=x;}while(c.s[c.s[0]]>0) c.s[0]++;while(c.s[c.s[0]]==0 && c.s[0]>1) c.s[0]--;return c;}intX& operator*=(const intX &a) {return *this=*this*a;}intX operator<<(const int &num){s[0]++;for(int i=1;i<=s[0];i++){s[i]<<=num;if(s[i-1]>=MOD) s[i-1]-=MOD, ++s[i];}while(s[s[0]]==0 && s[0]>1) s[0]--;return *this;}intX operator>>(const int &num){for(int i=s[0];i>=1;i--){if((s[i]&1) && i>1) s[i-1]+=MOD;s[i]>>=num;}while(s[s[0]]==0 && s[0]>1) s[0]--;return *this;}intX operator/(const intX &k) const{intX c=*this,tmp,lt,a;a=k;tmp.s[1]=1;while(c>=a) a=a<<1,tmp=tmp<<1;while(tmp.s[0]>1 || tmp.s[1]){if(c>=a) c-=a, lt+=tmp;a=a>>1, tmp=tmp>>1;}c=lt;while(c.s[c.s[0]]==0 && c.s[0]>1) c.s[0]--;if(c.s[0]<1) c.s[c.s[0]=1]=0;return c;}intX& operator/=(const intX &a) {return *this=*this/a;}intX operator%(const intX &a) const {return *this-*this/a*a;} intX& operator%=(const intX &a) {return *this=*this%a;} };ostream& operator<<(ostream &out,const intX &a){if(!a.flag) putchar('-');for(int i=a.s[0]-1;i>=1;i--)printf("%0*lld",BIT,a.s[i]);return out;}istream& operator>>(istream &in,intX &a){char str[LEN];scanf("%s",str);a=str;return in;}UPD：距离第⼀次写就这篇⽂章已有5个⽉，在此期间遇到了很多需要⾼精的题，才发现之前的模板有很多的缺陷，压位和多种运算固然不错，但独⽴性太差，码量过多与基于⾃损相减的除法运算复杂度过⾼还是硬伤，于是这次更新了新的Wint。

oi算法模板OI（竞赛信息学）是指竞赛化的信息学学科，通过算法设计和程序编写的方式，解决实际问题。

在OI竞赛中，掌握一些常用的算法模板是非常重要的，因为这些模板可以帮助选手快速解决问题，提高编程效率。

下面是一些常用的OI算法模板，供参考：1. 排序算法模板：- 冒泡排序：依次比较相邻元素，交换位置直到队列有序；- 快速排序：选择一个基准元素，将小于基准的元素置于其左侧，大于基准的元素置于其右侧，再对两侧递归进行快速排序；- 归并排序：将待排序队列划分成两个子队列，对子队列进行排序后再合并。

2. 图论算法模板：- 最短路径算法：例如Dijkstra算法和Floyd算法，分别用于求解单源最短路径和多源最短路径问题；- 最小生成树算法：例如Prim算法和Kruskal算法，分别用于求解无向图的最小生成树问题；- 拓扑排序：用于有向无环图中，将所有顶点排成一个线性序列，使得图中任意一对顶点u、v满足u在v之前。

3. 动态规划算法模板：- 01背包问题：给定n件物品，每件物品的重量为w，价值为v，背包的容量为C，求解背包可以装入的物品的最大总价值；- 最长公共子序列（LCS）：给定两个序列X和Y，求解X和Y的最长公共子序列的长度；- 最长递增子序列（LIS）：给定一个序列A，求解A的最长递增子序列的长度。

4. 字符串算法模板：- KMP算法：用于在一个文本串S中查找一个模式串P的出现位置，时间复杂度为O(n+m)；- Manacher算法：用于求解一个字符串中的最长回文子串，时间复杂度为O(n)；- Trie树：一种用于高效存储和搜索大量字符串的数据结构，常用于字符串匹配问题。

除了以上介绍的算法模板，还有许多其他常用的算法模板，如最大流算法、二叉树遍历算法、并查集算法等。

选手可以根据题目的要求和具体情况选择合适的算法模板来解决问题。

对于OI算法模板的学习和掌握，建议选手进行一些练习和实战。

可以参加一些在线的编程资源和平台，如Codeforces、AtCoder和LeetCode等，通过参加竞赛和练习题来提高自己的算法能力。

ｔ ｎｍｅｈ ｄｒｄ ｃｓｔ ｅｐｏｅｔ ｎｅｒｒｂ Ｏ ． ｉ ｔ ｏ ｅ ｕｅ ｈ ｒｊｃｉ ｒｏ ｙ２ ｏ ｏ
Ｋｅ ｗｏ ｄ ： ｃ ｍｅ ａ ｃ ｌ ｒ ｔｏ ｙ ｒ ｓ ａ ｒ ａｉ ａ ｉｎ；ｃ ｌ ｒ ｔｏ ａ ｇ ｔ ｅ ｅ ｔ ｎ ｍｅ ｈ ｄ ｂ ａｉ ａｉｎ ｔ ｒ ｅ ；ｄ ｔｃ ｉ ｔ ｏ ｂ ｏ
定模 板 ， 出了精 确 的检 测算 法． 提 实验 结 果表 明 ， 相 同的摄 像机 和相 同的环境 下 ， 在 新标 定模板 和检
测 算法标 定 的投 影误 差 比黑 白棋 盘格 的标定 结果 减 少 了 ２ ． ０ 关键 词 ：摄像 机 标 定 ； 定模板 ； 测 算法 标 检
中 图分类 号 ：ＴＮ３ １ ４ 文献标 志码 ：Ａ ９． 文 章编 号 ： ２ ３９ ７ ２ １ ） ４０ ８ —４ ０ ５ —８ Ｘ（ ０ １ ０ —０ ２０
ｌ ｗ ｃ ｕ ａ ｙ ｏ ｘ ｓ ｉ ｇ ｃ ｍｍ ｏ ｈ ｃ ｅ ｂ ａ ｄ ｄ ｔ ｃ ｉ ｎ ｍｅ ｈ ｄ ． Ｔｈ ｅ ｃ ｌ ｒ ｔｏ ａ ｇ ｔ ｏ ａ ｃ ｒ ｃ ｆ ｅ ｉｔｎ ｏ ｎ ｃ ｅｋ ｒ ｏ ｒ ｅｅｔ ｔｏ ｓ ｏ ｅ ｎ ｗ ａ ｉ ａ ｉ ｎ ｔ ｒ ｅ ｂ ｕ ｅ ｒ ｄ ｅ ｔｃｒ ｌ ｓ ｉｓ ｐ ｉ ｉ ｖ ｌｍ ｅ ｔ ｎ ｈ ｓ ｈ ｓ ｅ ｓ ｏ ｍ ａ ｅ ｈ ａ ｎ ｒ ｃ ｕ ａ ｅ ｓ ｓ ｇ ａ ｉｎ ｉ ｃｅ ａ ｔ ｒｍ ｔ ｅ ｅ ｅ ｎ ，ａ ｄ ｔ ｕ ａ ａ ｙ ｔ ｋ ，ｃ ｅ ｐ ａ ｄ ｍｏ ｅ ａ ｃ ｒ ｔ ｉ ｆ ａ ｕ ｅ ｏ ａ ｅ ｔ ｈ ｈ ｃ ｅ ｂ ａ ｄ Ｉ ａ ｙ ａ ｄ ａ ｃ ｒ ｔ ｏ ｄ ｔ ｃ ｈ ｅ ｄ ｓｇ ｅ ａ — ｅ ｔ ｒ ｓ ｃ ｍｐ ｒ ｄ ｗｉｈ ｔ ｅ ｃ ｅ ｋ ｒ ｏ ｒ ． ｔｉ ｅ ｓ ｎ ｃ ｕ ａ ｅ ｔ ｅ ｅ ｔｔ ｅｎ ｗ ｅ ｉ ｎ ｄ ｃ ｍ ｓ

f+ j+
1 2
=
mM(∆j
+
3 2
f
+
−
∆j
+
1 2
f+,
∆j+
1 2
f+
−
∆j−
1 2
f
+)
f
fj−+
1 2
=
mM(∆j
+
3 2
f
−
−
∆j+
1 2
f−,
∆j+
1 2
f−
−
∆j−
1 2
f
−)
fj± = f ±(u(xj),
∆j+
1 2
f
±
=
fj±+1
−
fj±
方程在t = 0.9和t = 2时图像分别如图(??)和图(??)所示。
Figure 10: t = 0.9
Figure 11: t = 2
7 二阶Godunov格式(MUSCL格式)
对于单个守恒律方程
∂u ∂f (u)
df
+
= 0, a(u) =
(30)
∂t ∂x
du
与上方程相容的守恒型格式
unj +1
=
unj
−
λ(fj+
1 2
−
fj−
1 2
)
≡
(E∆x (∆t)un )j ,
+ αu],
f −(u)
=
1 [f (u) − αu]
(47)
2
2
9 WENO格式
取α