下载文档原格式
大数除法16进制#include <stdio.h>#include <string.h>#define max 200int i;char jinzhi[16]={'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'}; int chu(char a[],char b[]){int shan, yu;for(yu = i = 0; a[i]; i++){yu = yu * 10 + a[i] - '0';shan = yu / 16;yu = yu % 16;b[i] = shan + '0';}b[i] = 0;return yu;}int judge(char a[]){for(i = 0; a[i]; i++)if(a[i] != '0')return 0;return 1;}void f(char a[]){int newbig;if(!judge(a)){char b[max];newbig = chu(a,b);f(b);printf("%c",jinzhi[newbig]);}}int main(void){char bigint[max];while(scanf("%s", bigint) == 1){if(strlen(bigint) == 1 ){if(bigint[0] == '0')return 0;}f(bigint);printf("\n");memset(bigint,'0',sizeof(bigint));}return 0;}最大公约数int GCD(int num1,int num2)//最大公约数{if ( num1 % num2 == 0){return num2;}elsereturn GCD( num2,num1 % num2) ;}最小公倍数int LCM(int a,int b)//最小公倍数{int temp_lcm;temp_lcm=a*b/GCD(a,b); //最小公倍数等于两数之积除以最大公约数return temp_lcm;}//求至少多少天相遇，同时出发，至少多少长方形堆正方体，分元宝类问题都是运用最小公倍数最小生成树#include<iostream>#include<cstdlib>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>using namespace std;const int inf = ( 1 << 20 ) ;int p[27]; // 并查集，用于判断两点是否直接或间接连通struct prog{int u;int v;int w;}map[80];//存储边的信息，包括起点/终点/权值bool cmp ( prog a , prog b){//排序函数，将边根据权值从小到大排return a.w<b.w;}int find(int x){//并查集的find，不解释return x==p[x]?x:p[x]=find(p[x]);}//减枝void join(int x,int y,int i){int fx=find(x),fy=find(y);if(fx!=fy){pre[fx]=fy;if(i!=-1) fee+=a[i].x;}return;}int main(){int n;while ( cin >> n , n ){int i , j ;for ( i = 0 ; i < 27 ; i ++ )p[i] = i ;//并查集初始化int k = 0 ;for ( i = 0 ; i < n - 1 ; i ++ ){//构造边的信息char str[3];int m;cin >> str >> m ;for ( j = 0 ; j < m ; j ++ ,k ++ ){char str2[3];int t;cin >> str2 >> t ;map[k].u=(str[0]-'A');map[k].v=(str2[0]-'A');map[k].w=t;}}sort ( map , map + k , cmp );//将边从小到大排序int ans=0; //所要求的答案for ( i = 0 ; i < k ; i ++ ){int x = find(map[i].u);int y = find(map[i].v);printf("%d%d\n",x,y);if( x!=y){//如果两点不在同一连通分量里，则将两点连接，并存储该边ans+=map[i].w;p[x]=y;}}cout<<ans<<endl;}return 0;}最大连续子序列-1235#include <stdio.h>#include <math.h>#include <string.h>#include <algorithm>int a[10010],maxsum,t,e,n;void ff(){int i,l,j,sum;for(i = 0; i < n; i++){sum = 0;for(l = i; l < n; l++){sum += a[l];if(sum > maxsum){maxsum = sum;t = i;e = l;// printf("%d\n",maxsum);}// printf("%d %d %d\n",i,l,sum);}}}int main(){//freopen("1235input.txt","r",stdin);int f,i;while(scanf("%d",&n)&&n){memset(a,0,sizeof(a));f =0;maxsum = -10000;for(i = 0; i < n; i++){scanf("%d",&a[i]);if(a[i] < 0)f++;}if(f == n){maxsum = 0;t = 0;e = n-1;}elseff();printf("%d %d %d\n",maxsum,a[t],a[e]);}return 0;}素数表int a[10000];//1为素数void ff(){memset(a,1,sizeof(a));for(i=2;i<=10000;i++){if(a[i]==1){printf("%d ",i);for(l=i;l<=10000;l++){if(a[l]==1)if(l%i==0)a[l]=0;}}}}================int a[10000];void ff(){memset(a,1,sizeof(a));for(int i = 2; i < 10000; i++){if(a[i] == 0){int l = i;while(i * l < 10000){a[i*l]=0;l++;} }}}BFSinclude <stdio.h>#include <string.h>int x, y, mx, my,step;char map[110][110];int move[8][2]={-1,-1,-1,0,-1,1,0,-1,0,1,1,-1,1,0,1,1};int recode[110][110];int f[110][110];struct duili{int x;int y;}a[110*110];bool judge(int m, int n){if(map[m][n]== '.' &&f[m][n]==2&& m>0 &&n>0&&m<y+1&&n<x+1) return 1;elsereturn 0;}int bfs(int i,int j){int front = 0,rear = 1;step = -1;recode[i][j] = 0; f[i][j]=1;a[front].x = i;a[front].y = j;while(front < rear){int xx = a[front].x, yy = a[front].y;front++;for(i = 0; i < 8; i++ ){if(judge(xx + move[i][0],yy + move[i][1])){f[xx + move[i][0]][yy + move[i][1]] =1 ;recode[xx + move[i][0]][yy + move[i][1]] = recode[xx][yy] + 1;a[rear].x = xx + move[i][0];a[rear].y = yy + move[i][1];rear++;if (recode[xx + move[i][0]][yy + move[i][1]] > step)step = recode[xx + move[i][0]][yy + move[i][1]];}}// for(int i = y; i > 0; i--)// {// for(int j = 1; j <= x; j++)// printf("%d",f[i][j]);// printf("\n");// }// printf("\n");}return step;}int main(){scanf("%d%d%d%d",&x, &y, &mx, &my);memset(map,0,sizeof(map));memset(f,0,sizeof(f));memset(recode,0,sizeof(recode));getchar();for(int i = y; i > 0; i--){for(int j = 1; j <= x; j++){scanf("%c",&map[i][j]);if(map[i][j]=='.')f[i][j]=2;}getchar();}// for(int i = y; i > 0; i--)// {// for(int j = 1; j <= x; j++)// printf("%c",map[i][j]);// printf("\n");// }printf("%d\n",bfs(mx,my));return 0;}CD_ROOM#include <stdio.h>int maxn;int n;int arr[20];int tempmax;void ff(int cur, int sum){if (sum > maxn)return;if (cur == n){tempmax >?= sum;return;}ff(cur + 1, sum);sum += arr[cur];ff(cur + 1, sum);}int main(void){while (tempmax = 0, scanf("%d", &n) == 1) {scanf("%d", &maxn);for (int i = 0; i < n; i++)scanf("%d", arr + i);ff(0, 0);printf("%d\n", tempmax);}return 0; }Floyed(最短路径)（可以有圈）#include <iostream>#include <string>#include <map>using namespace std;const int MAXN = 31;typedef double ValueType;//数据类型void Floyed(ValueType g[][MAXN],int n)//佛洛依德算法{for(int k=0;k<n;++k)for(int i=0;i<n;++i)for(int j=0;j<n;++j)if(g[i][j]<g[i][k]*g[k][j]) g[i][j] = g[i][k]*g[k][j];//尽可能使汇率大，这里是乘法(*)}int main(){int n,m,i,Case=0;string name,sour,dest;V alueType value;map<string,int> Currency; //用map实现name和index之间的转换V alueType graph[MAXN][MAXN];while(cin>>n){if(n==0) break;Currency.clear();memset(graph,0,sizeof(graph));for(i=0;i<n;++i)//n个顶点{cin>>name;Currency[name] = i;graph[i][i] = 1;}cin>>m;//m条边for(i=0;i<m;++i)//输入边信息创建图{cin>>sour>>value>>dest;graph[Currency[sour]][Currency[dest]] = value;}Floyed(graph,n);//佛洛依德求各个节点之间的bool ok = false;for(int i=0;i<n;++i)//求自身到自身的汇率(回路) if(graph[i][i]>1){ok=true;break;}cout<<"Case "<<++Case<<": ";if(ok) cout<<"Yes\n";else cout<<"No\n";}return 0;}3个for#include<stdio.h>#define MAX 100000000int main(){int n,m,a,b,t,i,j,k,map[202][202];while(scanf("%d%d",&n,&m)!=EOF){for(i=1;i<=n;i++)for(j=1;j<=n;j++)map[i][j]=MAX;while(m--){scanf("%d%d%d",&a,&b,&t);map[a][b]=t;map[b][a]=t;}for(k=1;k<=n;k++)for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(map[i][k]+map[k][j]<map[i][j])map[i][j]=map[i][k]+map[k][j];scanf("%d%d",&a,&b);if(map[a][b]==MAX||b>n||a<1)printf("-1\n");elseprintf("%d\n",map[a][b]);}}Dijkstra算法+注释#include <iostream>#include <string.h>#include <limits.h>#include <stdio.h>//hdu1874using namespace std;int map[1002][1002];int main(){int n,m;while(~scanf("%d%d",&n,&m)){int visted[205],dis[205];memset(visted,0,sizeof(visted)); //访问数组初始化for(int i=1;i<=n;++i){dis[i]=INT_MAX; //初始化两点之间的最短路径！！for(int j=1;j<=n;++j)map[i][j]=INT_MAX; //初始化两点间距离！！map[i][i]=0;}int a,b,c;while(m--){scanf("%d%d%d",&a,&b,&c);//输入两点间最短距离if(c<map[a][b])map[a][b]=map[b][a]=c;}int begin ,end ,pos;scanf("%d%d",&begin,&end);pos=begin;visted[pos]=1;//访问初始起始点。
ACM模板[王克纯2020年9月21日最大子串int maxSum(int * a,int n){int sum = a[0],b = 0;for(int i=0;i<n;++i){if(b>0) b += a[i];else b = a[i];if(b > sum) sum = b;}return sum;}int Kadane(const int array[], size_t length, unsigned int& left, unsigned int& right){unsigned int i, cur_left, cur_right;int cur_max, max;cur_max = max = left = right = cur_left = cur_right = 0;for(i = 0; i < length; ++i){cur_max += array[i];if(cur_max > 0){cur_right = i;if(max < cur_max){max = cur_max;left = cur_left;right = cur_right;}}else{cur_max = 0;cur_left = cur_right = i + 1;}}return max;} 快速幂void js(int &a,int &b,int num) {b=1;while(num){if(num&1) b*=a;num>>=1;a*=a;}}矩阵乘法struct mat{int n,m;//n行m列int data[MAX][MAX];};void mul(const mat& a,const mat& b,mat& c) //c=a*b{int i,j,k;if (a.m!=b.n); //报错c.n=a.n,c.m=b.m;for (i=0;i<c.n;i++){for (j=0;j<c.m;j++){for (c.data[i][j]=k=0;k<a.m;k++) {c.data[i][j]+=a.data[i][k]*b.dat a[k][j]%m;//m为余数}c.data[i][j]%=m;}}}Bit位操作(宏定义,内联函数,stl)} #define bitwrite(a,i,n)(n)?(a)[(i)/8]|=1<<(i)%8:(a)[(i)/8]&=~(1<<(i)%8)//数组a的第i位写入n;#define bitread(a,i)((a)[(i)/8]>>((i)%8))&1//读取数组a的第i位inline void write(int i,int n){n?a[i/8]|=1<<i%8:a[i/8]&=~(1<<i% 8);}inline int read(int i){return (a[i/8]>>(i%8))&1;}#include<bitset>bitset<MAX> b;错排公式为M(n)=n！（1/2!-1/3!+…..+(-1）^n/n!)M(n)=n!-n!/1!+n!/2!-n!/3!+…+(-1）^n*n!/n!=sigma(k=2~n) (-1）^k*n!/k!Dn=[n!/e+0.5]容斥原理M(n)=n![1/0!-1/1!+1/2!-1/3!+1/4! +..+(-1）^n/n!]二分模板LL findr(LL array, LL low, LL high,LL target){while(low <= high){LL mid = (low + high)/2;if (array[mid] > target) high = mid - 1;else if (array[mid] < target) low = mid + 1;else return mid;}return -1;复用代码#include<stdio.h>#include<stdlib.h>#include<string.h>#define MAX 10void print(mat t){printf("*****************\n") ;for(int i=0;i<t.n;i++){for(int j=0;j<t.m;j++){printf("%d",t.data[i][j]);}putchar('\n');}}一些常量和函数：最大Long long __int64 INF = ~(((__int64)0x1)<<63);ceil()向上取整(math.h)floor()向下取整c字符串处理函数1）提取子串--strstr函数原型：char* strstr(char*src,char*find)函数说明：从字符串src中寻找find第一次出现的位置（不比较结束符NULL）返回值：返回指向第一次出现find位置的指针，如果没有找到则返回NULL2）接尾连接--strcat函数原型：char* strcat(char*dest,char*src)函数说明：把src所指字符串添加到dest结尾处(覆盖dest结尾处的'\0')并添加'\0'3)部分连接--strncat函数原型:char* strncat(char*dest,char*src,int n);函数说明：把src所指字符串的前n个字符添加到dest结尾处（覆盖dest结尾处的’\0’）并添加’’\0’.返回值：返回指向dest的指针。
acm常用板子题
ACM常用模板题包括但不限于：
字符串操作：如字符串匹配、字符串排序、字符串还原等题目，需要熟练掌握字符串的基本操作和常用算法。
数组操作：如数组排序、数组查找、数组分割等题目，需要熟练掌握数组的基本操作和常用算法。
树形结构：如二叉树、AVL树、红黑树等题目，需要熟练掌握树形结构的基本操作和常用算法。
图论算法：如最短路径、最小生成树、拓扑排序等题目，需要熟练掌握图论算法的基本操作和常用算法。
动态规划：如背包问题、最长公共子序列、最长递增子序列等题目，需要熟练掌握动态规划的基本操作和常用算法。
搜索算法：如深度优先搜索、广度优先搜索等题目，需要熟练掌握搜索算法的基本操作和常用算法。
数据结构：如哈希表、并查集、线段树等题目，需要熟练掌握数据结构的基本操作和常用算法。
以上是一些常见的ACM模板题，当然还有很多其他的题目类型。
要提高自己的ACM水平，需要多做题、多思考、多总结，不断拓宽自己的算法和数据结构知识面。
acm模板整理和使用方法[acm模板整理和使用方法]ACM模板指的是计算机科学中常用的算法模板，是计算机专业的学生在学习算法和数据结构时必需掌握的内容。
ACM模板整理和使用方法主要包括以下问题：一、为什么要使用ACM模板？ACM模板能使算法实现变得更简单、更方便、更快捷。
尤其在ACM竞赛中，使用优秀的模板可以节省编程时间，避免出现冗余代码，使得编程效率大幅提升。
二、哪些算法需要掌握？许多常见的算法，如快速排序、线段树、并查集、Kruskal算法、Dijkstra算法、最小生成树问题等，都需要掌握。
因此，算法学习和掌握是使用ACM模板的前提。
三、如何整理和使用ACM模板？1.整理ACM模板将常用的算法的代码整理，以函数或者类的形式存放在一个文件中。
注意代码要有良好的注释，易于阅读和理解。
2.旧的代码调试如果有其他ACM竞赛选手或者教练的旧代码，需要先将其调试通过。
因为在ACM比赛中，时间十分宝贵。
如果没有调试好的代码可以使用，建议可以使用OJ网站上的代码进行练习。
3.在比赛中使用和修改模板在ACM比赛中，选手需要快速编写正确的程序并提交到OJ网站。
使用模板可以节省时间和精力，但有时候需要针对具体的问题进行修改。
在修改时需要小心，一定要保证修改后的代码与原始模板的代码所实现的算法是等效的。
4.维护和更新模板ACM模板需要不断地维护和更新，特别是在涉及到新的算法或者数据结构时。
保证ACM模板的有效性和及时性非常重要，这需要持续的学习和探索。
四、如何学习和掌握ACM模板？1.选择学习和观察别人的代码一个好的方式是看国内和国际大佬们的代码，学习他们的代码风格和思考方式。
了解其他人的ACM模板如何实现，可以帮助你提高代码风格和技术水平。
2.探索自己不熟悉的算法和数据结构ACM竞赛中考察的算法不限于常见的算法，还包括各种数论、图论、动态规划等。
掌握这些算法和数据结构可以提高解题的速度和质量。
在掌握新算法之前，阅读相关论文或文章，掌握其基本原理和实现方法。
一、贪心算法 (2)1、区间选点 (2)2、区间覆盖 (2)3、不相交区间 (2)4、哈夫曼编码 (2)5、最小值最大化、最大值最小化（二分查找） (2)二、动态规划 (5)1、最长公共子序列（LCS） (5)2、最长上升公共子序列（LIS） (7)3、子段和 (9)4、DAG上的动态规划 (13)5、区间DP (17)6、状态压缩DP (24)7、双线DP (30)8、背包问题(见背包九讲) (32)三、数据结构 (32)1、并查集 (32)2、树状数组 (34)3、（字符串）KMP匹配 (37)四、最小生成树算法 (41)Prime核心算法 (41)Kruskal算法 (44)五、单源最短路径 (50)Dijkstra核心算法 (50)Bellman_Ford算法 (54)SPFA算法（Bellman_Ford的队列实现） (58)六、二分图匹配 (61)1、匈牙利算法 (61)七、网络流 (63)1、SAP算法 (64)2、Dinic算法 (68)一、贪心算法1、区间问题区间选点选取尽量少的点覆盖所有的区间，是每个区间至少包含一个点。
对区间右端点进行排序。
区间覆盖选取尽量少的区间覆盖整个区域。
对左端点进行排序。
不相交区间选取尽量多的不相交区间。
对区间右端点进行排序。
2、哈夫曼编码3、最小值最大化、最大值最小化（二分查找）NYOJ 疯牛问题（最小值最大化）农夫 John 建造了一座很长的畜栏，它包括N (2 <= N <= 100,000)个隔间，这些小隔间依次编号为x1,...,xN (0 <= xi <= 1,000,000,000).但是，John的C (2 <= C <= N)头牛们并不喜欢这种布局，而且几头牛放在一个隔间里，他们就要发生争斗。
为了不让牛互相伤害。
John决定自己给牛分配隔间，使任意两头牛之间的最小距离尽可能的大，那么，这个最大的最小距离是什么呢？#include <cstdio>#include <iostream>#include <algorithm>using namespace std;int n, c;int pos[100005];bool judge(int k){int cnt = 1;int st = pos[0];for(int i = 1; i < n; ++i){if(pos[i] - st >= k){++cnt;if(cnt >= c)return true;st = pos[i];}}return false;}int Binary_search(int left, int right) /// 二分枚举满足条件的最大距离{while(left <= right){int mid = (left + right) >> 1;if(judge(mid)) /// 所求距离 >= mid，可以继续增大试探left = mid+1;else /// 所求距离 < mid,所以必须减小来试探right = mid-1;}return left-1;}int main(){while(~scanf("%d%d", &n, &c)){for(int i = 0; i < n; ++i)scanf("%d", &pos[i]);sort(pos, pos+n);printf("%d\n", Binary_search(0, pos[n-1] - pos[0]));}return 0;}NYOJ 摘枇杷（最大值最小化）理工学院的枇杷快熟了，ok，大家都懂得。
<数据结构>闭散列法整数hash#define max 4000037int hash[max],c[max];//hash存关键字，c存该位置关键字出现的次数bool use[max];int n,m,ans;int k[6],p[6];int locate(int k)//hash函数{int tmp;tmp = k;while(tmp<0)tmp+=max;while(tmp>=max)tmp-=max;while(use[tmp]&&hash[tmp]!=k){tmp++;if(tmp>=max)tmp-=max;}return tmp;}void insert(int k){int pos = locate(k);hash[pos] = k;use[pos] = 1;c[pos]++;}int onlyfind(int k){int pos = locate(k);if(hash[pos]==k)return c[pos];else return -1;}整数hash,开散列#include <stdio.h>#include <memory.h>#define MAX 3400000#define M 28999999int head[M],next[MAX];int lkey[MAX],up,ans;int n,m;int k[6],p[6];int hash(int key){int h;//h = ((key>>16)&&key)^(key>>8);h = ((~key)>>8)&&key ||( (key<<16) );h%=M;return h;}int find(int key){int h,p;h = hash(key);for(p=head[h];p>=0;p=next[p])if(lkey[p]==key)return 1;lkey[up] = key;next[up] = head[h];head[h] = up++;return -1;}int onlyfind(int key){int h,p;h = hash(key);for(p=head[h];p>=0;p=next[p])if(lkey[p]==key)return 1;return -1;}字符串hashint ELFhash(char *key) {unsigned h=0;while(*key) {h=(h<<4) + *key++;unsigned g=h & 0Xf0000000L;if(g) h^=g>>24;h &= ~g;}return h% M;}堆int heap[MAX+1],heapsize;void push(int key){int pos;pos = ++heapsize;while(pos>0&&heap[pos>>1]>key){heap[pos] = heap[pos>>1];pos>>=1;}heap[pos] = key;}void pop(){int key = heap[heapsize--];int pos,npos;pos = 1;npos = pos<<1;while(npos<=heapsize){if(npos+1<=heapsize&&heap[npos+1]<heap[npos])npos+=1;if(heap[npos]>=key)break;heap[pos] = heap[npos];pos = npos;npos = pos<<1;}heap[pos] = key;}二维树状数组int lowbit(int x){return x&(-x);}void updata(int x,int y,int w){int i,j;for(i=x;i<=n;i+=lowbit(i)){for(j=y;j<=n;j+=lowbit(j)){c[i][j]+=w;}}}int sum(int x,int y){int t=0,i,j;for(i=x;i>0;i-=lowbit(i)){for(j=y;j>0;j-=lowbit(j)){t+=c[i][j];}}return t;}Trie树#include<iostream>#define keyNum 26#define MaxN 50struct trie...{struct trieNode...{//trie结点的结构trieNode *link[keyNum];//下标为 'A' , 'B' , 'C' , , 'Z' 的指针数组 int num[keyNum];//插入key的次数trieNode()...{memset(num,0,sizeof(num));memset(link,NULL,sizeof(link));}void init()...{memset(link,NULL,sizeof(link));memset(num,0,sizeof(num));}};trieNode* root;trie()...{root=(trieNode*)malloc(sizeof(trieNode));//初始化时为root申请了空间 root->init();}bool Search(char *);void Insert(char []);void Delete(trieNode*);};bool trie::Search(char * x)...{if(*x==0)return false;trieNode* current=root;x++;while(*x)...{if(current->link[*(x-1)-'a'])current=current->link[*(x-1)-'a'];else break;x++;}if(*x==0&¤t->num[*(x-1)-'a'])return true;else return false;}void trie::Delete(trieNode* t)...{int i;for(i=0;i<keyNum;i++)if(t->link[i])Delete(t->link[i]);memset(t->num,0,sizeof(t->num));delete(t);}void trie::Insert(char x[])...{trieNode *current=root;int i=1;while(x[i])...{if(current->link[x[i-1]-'a']==NULL)...{current->link[x[i-1]-'a']=(trieNode*)malloc(sizeof(trieNode)); (current->link[x[i-1]-'a'])->init();}current=current->link[x[i-1]-'a'];i++;}(current->num[x[i-1]-'a'])++;}char c[ 50000 ][MaxN],tmp;int main()...{trie a;int i=0,j,num;while(scanf("%s",c[i])!=EOF)a.Insert(c[i++]);num=i;for(i=0;i<num;i++)for(j=1;c[i][j];j++)...{tmp=c[i][j];c[i][j]=0;if(a.Search(c[i]))...{c[i][j]=tmp;if(a.Search(&c[i][j]))...{ printf("%s ",c[i]);break;}}else c[i][j]=tmp;}a.Delete(a.root);return 0;}二叉查找树//key是字符串#include <stdio.h>#include <stdlib.h>#include <string.h>typedef struct BiTNode{char data[31];struct BiTNode *lchild,*rchild;}BiTNode,*BiTree;BiTree p=NULL;void InorderBST(BiTree T){if(T->lchild) InorderBST(T->lchild);printf("%s\n",T->data);if(T->rchild) InorderBST(T->rchild);}int SearchBST(BiTree T,char key[],BiTree f){int tmp1,tmp2;tmp1=tmp2=0;if(!T) {p=f;return 0;}\\找不到返回路径上最后一点else if(!strcmp(key,T->data)) {p=T;return 1;}else if(strcmp(key,T->data)<0) tmp1=SearchBST(T->lchild,key,T); else tmp2=SearchBST(T->rchild,key,T);if(tmp1||tmp2) return 1;else return 0;}BiTree InsertBST(BiTree T,char e[]){BiTree s;if(!SearchBST(T,e,NULL))//查找不到，（若已经存在则放弃）{s=(BiTree)malloc(sizeof(BiTNode));strcpy(s->data,e);s->lchild=s->rchild=NULL;if(!p) return s;else{if(strcmp(e,p->data)<0) p->lchild=s;else p->rchild=s;}}//else //若出现过做相应处理}/*int main(){BiTree T=NULL;char key[31];while(gets(key)!=NULL){if(T==NULL)T=InsertBST(T,key);//空树将返回指向根节点的指针else InsertBST(T,key);}InorderBST(T);return 0;}*/线段树#include<stdio.h>#include<memory.h>#define MAX 100001int up;int count[31];struct NODE{int l,r,flag;NODE *lcd,*rcd;void build(int i,int j);void insert(int i,int j,int k);void get(int i,int j);}node[MAX*4],*root=&node[0];void NODE::build(int i,int j){l=i;r=j;flag=1;if(l==r){lcd=rcd=NULL;}else{lcd=&node[up++];rcd=&node[up++];lcd->build(l,(l+r)/2);rcd->build((l+r)/2+1,r);}}void NODE::insert(int i,int j,int k) {if(i>r||j<l)return;if(i<=l&&j>=r){flag=k;return;}else{if(flag!=-1){lcd->insert(l,r,flag);rcd->insert(l,r,flag);}lcd->insert(i,j,k);rcd->insert(i,j,k);flag=-1;}}void NODE::get(int i,int j){if(i>r||j<l)return;if(flag!=-1){count[flag]=1;}else{lcd->get(i,j);rcd->get(i,j);}}int main(){int l,t,o,i,j,k,ans;char s[5];// freopen("in.txt","r",stdin);scanf("%d%d%d",&l,&t,&o);up=1;root->build(1,l);while(o--){scanf("%s",s);if(s[0]=='C'){scanf("%d%d%d",&i,&j,&k);root->insert(i,j,k);}else{scanf("%d%d",&i,&j);memset(count,0,sizeof(count));root->get(i,j);ans=0;for(i=1;i<=t;i++){if(count[i]){ans++;}}printf("%d\n",ans);}}return 0;}线段树动态运用#include<stdio.h>#include<memory.h>#include<algorithm>using namespace std;#define MAXN 1000001#define MAXM 50001int value[MAXN],dog[MAXN],b[MAXM],e[MAXM],rank[MAXM],ans[MAXM],ind[MAXM]; int up=1;struct NODE{int now,count;NODE *rcd,*lcd;void build(int i,int j);void insert(int key);void dele(int key);int get(int k);}node[MAXN*4],*root=&node[0];bool cmp(int p,int q){return b[p]<b[q]||b[p]==b[q]&&e[p]<e[q];}void NODE::build(int i,int j){now=(i+j)/2;if(i==j){lcd=rcd=NULL;}else{lcd=&node[up++];rcd=&node[up++];lcd->build(i,(i+j)/2);rcd->build((i+j)/2+1,j);}}void NODE::insert(int key){count++;if(lcd==NULL)return;if(key<=value[now]){lcd->insert(key);}else{rcd->insert(key);}}void NODE::dele(int key){count--;if(lcd==NULL)return;if(key<=value[now]){lcd->dele(key);}else{rcd->dele(key);}}int NODE::get(int k){if(lcd==NULL)return value[now];if(lcd->count>=k){return lcd->get(k);}else{return rcd->get(k-lcd->count);}}int main(){int n,m,i,j;// freopen("d:/in.txt","r",stdin);scanf("%d%d",&n,&m);for(i=0;i<n;i++){scanf("%d",&dog[i]);value[i]=dog[i];}sort(value,value+n);n=unique(value,value+n)-value;root->build(0,n-1);for(i=0;i<m;i++){scanf("%d%d%d",&b[i],&e[i],&rank[i]);b[i]--;e[i]--;ind[i]=i;}sort(ind,ind+m,cmp);for(i=b[ind[0]];i<=e[ind[0]];i++){root->insert(dog[i]);}ans[ind[0]]=root->get(rank[ind[0]]);for(i=1;i<m;i++){for(j=b[ind[i-1]];j<b[ind[i]];j++){root->dele(dog[j]);}for(j=e[ind[i-1]]+1;j<=e[ind[i]];j++){root->insert(dog[j]);}ans[ind[i]]=root->get(rank[ind[i]]);}for(i=0;i<m;i++){printf("%d\n",ans[i]);}return 0;}RMQvoid RMQ(int M[MAXN][LOGMAXN], int A[MAXN], int N){int i, j;//initialize M for the intervals with length 1for (i = 0; i < N; i++)M[i][0] = i;//compute values from smaller to bigger intervalsfor (j = 1; 1 << j <= N; j++)for (i = 0; i + (1 << j) - 1 < N; i++)if (A[M[i][j - 1]] < A[M[i + (1 << (j - 1))][j - 1]]) M[i][j] = M[i][j - 1];elseM[i][j] = M[i + (1 << (j - 1))][j - 1];}//产生的M[i][j]为[ i , j ]中最小的数//查询：[ l , r ]//k:=ln((r-l+1)/ln(2)); ans:=min(M[l，k],M[r-2^k+1,k]);LCA+RMQ#include <stdio.h>#include <math.h>#include <memory.h>#define MAX 1000int tree[MAX][MAX],first[MAX];int len[MAX],count[MAX];int node[2*MAX],deep[2*MAX],top;int M[MAX][32],in[MAX];int N;void dfs(int u,int pre,int d){int i,t;node[top] = u;deep[top] = d;if(first[u]==-1)first[u] = top;top++;for(i=0;i<len[u];i++){t = tree[u][i];if(pre==t)continue;dfs(t,u,d+1);node[top] = u;deep[top] = d;top++;}}void RMQ_init(){int i,j;for(i=0;i<top;i++)M[i][0] = i;for(j=1;(1<<j)<=top;j++)for(i=0;i+(1<<j)-1<top;i++)if(deep[M[i][j-1]]<deep[M[i+(1<<(j-1))][j-1]]) M[i][j] = M[i][j-1];elseM[i][j] = M[i+(1<<(j-1))][j-1];}int RMQ_query(int u,int v){int l,r,t;l = first[u];r = first[v];if(l>r){t = l;l = r;r = t;}t = log((double)(r-l+1))/log(2.0);if(deep[M[l][t]]<=deep[M[r-(1<<t)+1][t]]) return node[M[l][t]];elsereturn node[M[r-(1<<t)+1][t]];}int main(){//freopen("in.txt","r",stdin);int i,u,v,k,j,T,s;char ch;while(scanf("%d",&N)!=EOF){memset(len,0,sizeof(len));memset(in,0,sizeof(in));for(i=1;i<=N;i++){scanf("%d",&u);while((ch=getchar())!=':');while((ch=getchar())!='(');scanf("%d",&k);while((ch=getchar())!=')');for(j=1;j<=k;j++){scanf("%d",&v);in[v]++;tree[u][len[u]++] = v;//tree[v][len[v]++] = u;}}top = 0;memset(first,-1,sizeof(first));for(i=1;i<=N;i++)if(in[i]==0){s = i;break;}dfs(s,-1,0);RMQ_init();scanf("%d",&T);memset(count,0,sizeof(count));for(i=1;i<=T;i++){while((ch=getchar())!='(');scanf("%d%d",&u,&v);while((ch=getchar())!=')');s = RMQ_query(u,v);count[s]++;}for(i=1;i<=N;i++)if(count[i]>0)printf("%d:%d\n",i,count[i]);}return 0;}SB-Tree#include <stdio.h>int n,f;void solve(int a,int b,int c,int d){ //0,1,1,1if (b+d>n) return;solve(a,b,a+c,b+d);if(f){printf("%d/%d",a+c,b+d);f=0;}elseprintf(",%d/%d",a+c,b+d);solve(a+c,b+d,c,d);};int main(){int T;scanf("%d",&T);while(T--){scanf("%d",&n);f=1;solve(0,1,1,1);printf("\n");}return 0;}。
0.头文件#define _CRT_SBCURE_NO_DEPRECATE #include <set>#include <cmath>#include <queue>#include <stack>#include <vector>#include <string>#include <cstdio>#include <cstdlib>#include <cstring>#include <iostream>#include <algorithm>#include <functional>using namespace std;const int maxn = 110;1.const int INF = 0x3f3f3f3f;经典1.埃拉托斯特尼筛法/*|埃式筛法||快速筛选素数||16/11/05ztx|*/int prime[maxn];bool is_prime[maxn];int sieve(int n){int p = 0;for(int i = 0; i <= n; ++i)is_prime[i] = true;is_prime[0] = is_prime[1] = false;for (int i = 2; i <= n; ++i){ // 注意数组大小是nif(is_prime[i]){prime[p++] = i;for(int j = i + i; j <= n; j += i) // 轻剪枝，j必定是i的倍数is_prime[j] = false;}}return p; // 返回素数个数}2.快速幂/*|快速幂||16/11/05ztx|*/typedef long long LL; // 视数据大小的情况而定LL powerMod(LL x, LL n, LL m){LL res = 1;while (n > 0){if (n & 1) // 判断是否为奇数，若是则true res = (res * x) % m;x = (x * x) % m;n >>= 1; // 相当于n /= 2;}return res;}3.大数模拟大数加法/*|大数模拟加法||用string模拟||16/11/05ztx, thanks to caojiji|*/string add1(string s1, string s2){if (s1 == "" && s2 == "") return"0";if (s1 == "") return s2;if (s2 == "") return s1;string maxx = s1, minn = s2;if (s1.length() < s2.length()){maxx = s2;minn = s1;}int a = maxx.length() - 1, b = minn.length() - 1;for (int i = b; i >= 0; --i){maxx[a--] += minn[i] - '0'; // a一直在减，额外还要减个'0'}for (int i = maxx.length()-1; i > 0;--i){ if (maxx[i] > '9'){maxx[i] -= 10;//注意这个是减10maxx[i - 1]++;}}if (maxx[0] > '9'){maxx[0] -= 10;maxx = '1' + maxx;}return maxx;}大数阶乘/*|大数模拟阶乘||用数组模拟||16/12/02ztx|*/#include <iostream>#include <cstdio>using namespace std;typedef long long LL;const int maxn = 100010;int num[maxn], len;/*在mult函数中，形参部分：len每次调用函数都会发生改变，n 表示每次要乘以的数，最终返回的是结果的长度tip: 阶乘都是先求之前的(n-1)!来求n!初始化Init函数很重要，不要落下*/void Init() {len = 1;num[0] = 1;}int mult(int num[], int len, int n) {LL tmp = 0;for(LL i = 0; i < len; ++i) {tmp = tmp + num[i] * n; //从最低位开始，等号左边的tmp表示当前位，右边的tmp表示进位（之前进的位）num[i] = tmp % 10; // 保存在对应的数组位置，即去掉进位后的一位数tmp = tmp / 10; // 取整用于再次循环,与n和下一个位置的乘积相加}while(tmp) { // 之后的进位处理num[len++] = tmp % 10;tmp = tmp / 10;}return len;}int main() {Init();int n;n = 1977; // 求的阶乘数for(int i = 2; i <= n; ++i) {len = mult(num, len, i);}for(int i = len - 1; i >= 0; --i)printf("%d",num[i]); // 从最高位依次输出,数据比较多采用printf输出printf("\n");return0;}4.GCD/*|辗转相除法||欧几里得算法||求最大公约数||16/11/05ztx|*/int gcd(int big, int small){if (small > big) s, small);int temp;while (small != 0){ // 辗转相除法if (small > big) s, small); temp = big % small;big = small;small = temp;}return(big);}5.LCM/*|辗转相除法||欧几里得算法||求最小公倍数||16/11/05ztx|*/int gcd(int big, int small){if (small > big) s, small);int temp;while (small != 0){ // 辗转相除法if (small > big) s, small);temp = big % small;big = small;small = temp;}return(big);}6.全排列/*|求1到n的全排列, 有条件||16/11/05ztx, thanks to wangqiqi|*/void Pern(int list[], int k, int n) { // k表示前k 个数不动仅移动后面n-k位数if (k == n - 1) {for (int i = 0; i < n; i++) {printf("%d", list[i]);}printf("\n");}else {for (int i = k; i < n; i++) { // 输出的是满足移动条件所有全排列s[k], list[i]);Pern(list, k + 1, n);s[k], list[i]);}}}7.二分搜索/*|二分搜索||要求：先排序||16/11/05ztx, thanks to wangxiaocai|*/// left为最开始元素, right是末尾元素的下一个数，x是要找的数int bsearch(int *A, int left, int right, int x){int m;while (left < right){m = left + (right - left) / 2;if (A[m] >= x) right = m; else left = m + 1;// 如果要替换为 upper_bound, 改为:if(A[m] <= v) x = m+1; else y = m;}return left;}/*最后left == right如果没有找到135577找6，返回7如果找有多少的x，可以用lower_bound查找一遍，upper_bound查找一遍，下标相减C++自带的lower_bound(a,a+n,x)返回数组中最后一个x的下一个数的地址upper_bound(a,a+n,x)返回数组中第一个x的地址如果a+n内没有找到x或x的下一个地址，返回a+n的地址lower_bound(a,a+n,x）-upper_bound(a,a+n,x)返回数组中x的个数*/数据结构并查集8.并查集/*|合并节点操作||16/11/05ztx, thanks to chaixiaojun|*/int father[maxn]; // 储存i的father父节点void makeSet() {for (int i = 0; i < maxn; i++)father[i] = i;}int findRoot(int x) { // 迭代找根节点int root = x; // 根节点while (root != father[root]) { // 寻找根节点root = father[root];}while (x != root) {int tmp = father[x];father[x] = root; // 根节点赋值x = tmp;}return root;}void Union(int x, int y) { // 将x所在的集合和y所在的集合整合起来形成一个集合。
ACM Standard Code LibraryHuang WeiComputer Science and EngineeringAssociation of ProgramingInformation Engineering CollegeHangzhou Dianzi UniversityApril, 2007ACM 算法模板集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中国余数定理五.图论算法1. 最小生成树(Kruscal算法)2. 最小生成树(Prim算法)3. 单源最短路径(Bellman-ford算法)4. 单源最短路径(Dijkstra算法)5. 全源最短路径(Folyd算法)6. 拓扑排序7. 网络预流和最大流8. 网络最小费用最大流9. 网络最大流(高度标号预流推进)10. 最大团11. 最大二分图匹配(匈牙利算法)六.几何算法1. 几何模板2. 球面上两点最短距离3. 三点求圆心坐标七.专题讨论1. 树状数组2. 字典树3. 后缀树4. 线段树5. 并查集6. 二叉堆7. 逆序数(归并排序)8. 树状DP9. 欧拉路10. 八数码11. 高斯消元法12. 字符串匹配(KMP算法)13. 全排列,全组合第一章常用函数和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 ) return 0;else return 1;}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]="24 hello", 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:2.Lucas Number1, 3, 4, 7, 11, 18, 29, 47, 76, 123...Formula:3.Catalan Number1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012…Formula:Application:1)将n + 2 边形沿弦切割成n个三角形的不同切割数Sample:n = 2;n = 3;2)n + 1个数相乘, 给每两个元素加上括号的不同方法数Sample:n = 2; (1 (2 3)), ((1 2) 3)n = 3; (1 (2 (3 4))), (1 ((2 3) 4)) , ((1 2) (3 4)), ((1 (2 3)) 4), (((1 2) 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:Special Cases:5.Bell Numbern 个元素集合所有的划分数Formula:6.Stirling's Approximation7.Sum of Reciprocal ApproximationEulerGamma = 0.57721566490153286060651209;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: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.错排公式11.三角形内切圆半径公式12.三角形外接圆半径公式13.圆內接四边形面积公式14.基础数论公式1)模取幂2) n的约数的个数若n满足, 则n的约数的个数为第三章大数模板/**** **** **** **** **** ***** Function Name : BigNumber* Description : BigNumber's HPC* Author : HuangWei* Last Edited : 07.4.11**** **** **** **** **** ****/#include <iostream>#include <string>#include <sstream>#include <memory>#include <algorithm>#define BASE 1000 // 基数#define DIG 1100 // 存储using namespace std;class BigNumber{private:int data[DIG]; // 数据区int len; // 记录长度public:BigNumber() {len=1;memset(data,0,sizeof(data));data[0]=1;}BigNumber(int); // 输入默认十进制BigNumber(char*);BigNumber(const BigNumber &);// 类型转换BigNumber & Num_BNum(int); //把一个整数转换成BigNumber型的BigNumber & Str_BNum(char*); //把一个字符串类型的转换成BigNumber型的int Int();string Str();// HPCBigNumber & Add(const BigNumber &);BigNumber & Sub(const BigNumber &);BigNumber & Mul(const BigNumber &);BigNumber & Div(int);BigNumber & Mod(int);BigNumber & operator=(const BigNumber &);int Bigger(const BigNumber &) const;BigNumber operator + (const BigNumber &);BigNumber operator - (const BigNumber &);BigNumber operator * (const BigNumber &);BigNumber operator / (int);BigNumber operator % (int);BigNumber & operator += (const BigNumber &); BigNumber & operator -= (const BigNumber &); BigNumber & operator *= (const BigNumber &); BigNumber & operator /= (int);BigNumber & operator %= (int);};BigNumber & BigNumber::Num_BNum(int b){len=1; memset(data,0,sizeof(data));data[0] = 1;if(b < 0) {b = -b;data[0] = -1;}while(b > 0) {data[ len++ ] = b % BASE;b /= BASE;}return *this;}BigNumber & BigNumber::Str_BNum(char* sb) {int t=0, d=1, b=0, slen=strlen(sb), i;len=1; memset(data,0,sizeof(data));data[0] = 1;if(sb[0] == '-') data[0] = -1, b=1;for(i=slen-1; i>=b ;i--) {while(t >= BASE || d > BASE) {data[ len++ ] = t % BASE;t /= BASE;d = 10;}t += (sb[i]-'0') * d;d *= 10;}while(t > 0) {data[ len++ ] = t % BASE;t /= BASE;}return *this;}int BigNumber::Int(){istringstream sin;int v;sin.str( this->Str() );sin >> v;return v;} //这个函数的用法还是第一次看到，没看懂string BigNumber::Str(){int i,base_len=0;ostringstream sout;if(len == 1) {sout << '0';//sout << endl;return sout.str();}if(data[0] < 0) sout << "-";sout << data[len-1];i = BASE;while(i > 1) {base_len++;i /= 10;}for(i=len-2; i>0 ;i--) {sout.width(base_len);sout.fill('0');sout << data[i];}//sout << endl;return sout.str();} //这个函数也没有看懂BigNumber::BigNumber(int b){this->Num_BNum(b);}BigNumber::BigNumber(char* sb){this->Str_BNum(sb);}// -1 a<b, 0 a==b, 1 a>bBigNumber::BigNumber(const BigNumber & b){len = b.len; memcpy(data,b.data,sizeof(data));}int BigNumber::Bigger(const BigNumber & b) const {int i,flag;if(data[0] ==1 && b.data[0] ==1) flag = 1;else if(data[0] ==1 && b.data[0] ==-1) return 1;else if(data[0] ==-1 && b.data[0] ==1) return -1;else flag = -1;if(len > b.len) return flag;else if(len == b.len) {for(i=len-1; i>0 ;i--)if(data[i] > b.data[i]) return flag;}if(i == 0) return 0;return -flag;} //比较函数BigNumber & BigNumber::Add(const BigNumber & b) {int i;if(data[0] * b.data[0] != 1) {data[0] = -data[0];Sub(b);data[0] = -data[0];return *this;}len= len > b.len ? len : b.len;for(i=1; i<len ;i++) {data[i] += b.data[i];if(data[i] >= BASE) {data[i+1]++;data[i] -= BASE;}}if(data[i] > 0) len = i+1;return *this;} //加上b这个大数BigNumber & BigNumber::Sub(const BigNumber & b) {int i;if(data[0] * b.data[0] != 1) {data[0] = -data[0];Add(b);data[0] = -data[0];return *this;}len= len > b.len ? len : b.len;for(i=1; i<len ;i++) {data[i] -= b.data[i];if(data[i] < 0) {data[i+1]--;data[i] += BASE;}}if(data[len] < 0) {for(i=0; i<=len ;i++)data[i] = -data[i];for(i=1; i<len ;i++)if(data[i] < 0) {data[i+1]--;data[i] += BASE;}}while(data[len-1] == 0) len--;return *this;}BigNumber & BigNumber::Mul(const BigNumber & b) {BigNumber bt;int i,j,up;int temp,temp1;bt.data[0] = data[0] * b.data[0];for(i=1; i<len ;i++) {up = 0;for(j=1; j<b.len ;j++) {temp = data[i] * b.data[j] + bt.data[i+j-1] + up;if(temp >= BASE) {temp1 = temp % BASE;up = temp / BASE;bt.data[i+j-1] = temp1;}else {up = 0;bt.data[i+j-1] = temp;}}if(up != 0) bt.data[i+j-1] = up;}bt.len = i+j;while(bt.data[bt.len-1] == 0) bt.len--;*this=bt;return *this;}BigNumber & BigNumber::Div(int b){BigNumber bt;int i,down = 0;if(b < 0) bt.data[0] = -data[0] , b = -b;else bt.data[0] = data[0];for(i=len-1; i>=1 ;i--) {bt.data[i] = (data[i] + down * BASE) / b;down = data[i] + down * BASE - bt.data[i] * b;}bt.len = len;while(bt.data[bt.len-1] == 0) bt.len--;*this=bt;return *this;}BigNumber & BigNumber::Mod(int b){int temp = 0, up = 0, i;for(i=len-1; i>=1 ;i--) {temp = data[i];temp += up * BASE;up = temp % b;}if(data[0] < 0) up = -up;*this = up;return *this;}BigNumber & BigNumber::operator = (const BigNumber & b) {len = b.len; memcpy(data,b.data,sizeof(data)); return *this;}BigNumber BigNumber::operator + (const BigNumber & b) {BigNumber bt=*this; return bt.Add(b);}BigNumber BigNumber::operator - (const BigNumber & b) {BigNumber bt=*this; return bt.Sub(b);}BigNumber BigNumber::operator * (const BigNumber & b) {BigNumber bt=*this; return bt.Mul(b);}BigNumber BigNumber::operator / (int b){BigNumber bt=*this; return bt.Div(b);}BigNumber BigNumber::operator % (int b){BigNumber bt=*this; return bt.Mod(b);}BigNumber & BigNumber::operator += (const BigNumber & b) {return this->Add(b);}BigNumber & BigNumber::operator -= (const BigNumber & b) {return this->Sub(b);}BigNumber & BigNumber::operator *= (const BigNumber & b) {return this->Mul(b);}BigNumber & BigNumber::operator /= (int b){return this->Div(b);}BigNumber & BigNumber::operator %= (int b){return this->Mod(b);}第四章数论算法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;d = extended_euclid(a, n, x, y);if( b%d == 0) {x0 = ( x*(b/d) ) % n; // x0 : basic solutionint ans = n;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;x = 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);x = (x + y*m*b[i]) % n;}return (n + x%n) % n;}第五章图论算法1.最小生成树(Kruscal算法)/**** **** **** **** **** ***** Function Name : 最小生成树(Kruscal算法)* Description : ZJU 1203 Swordfish O(E*LogE)**** **** **** **** **** ****/#include <iostream>#include <algorithm>#include <cstdio>#include <cmath>using namespace std;struct struct_edges{int bv,tv; //bv 起点 tv 终点double w; //权值};struct_edges edges[10100]; //边集struct struct_a{double x;double y;};struct_a arr_xy[101];int point[101],n,e; //n 顶点数, e 边数(注意是无向网络)double sum;int kruscal_f1(int point[], int v){int i = v;while(point[i] > 0) i = point[i];return i;}bool UDlesser(struct_edges a, struct_edges b){return a.w < b.w;}void kruscal() //只需要准备好n，e，递增的边集edges[]即可使用{int v1,v2,i,j;for(i=0; i<n ;i++) point[i]=0;i = j = 0;while(j<n-1 && i<e) {v1 = kruscal_f1(point, edges[i].bv);v2 = kruscal_f1(point, edges[i].tv);if(v1 != v2) {sum += edges[i].w; //注意sum初始为0point[v1]=v2;j++;}i++;}}int main(){int k,i,j;cin>>n;k=0;while(n != 0) {sum=0;k++;for(i=0; i<n ;i++)cin>>arr_xy[i].x>>arr_xy[i].y;e=0;for(i=0; i<n ;i++) //从0开始计数for(j=i+1; j<n ;j++) //注意是无向网络{if(i == j) continue;edges[e].bv=i;edges[e].tv=j;edges[e].w=sqrt((arr_xy[i].x-arr_xy[j].x)*(arr_xy[i].x-arr_xy[j].x)+( arr_xy[i].y-arr_xy[j].y)*(arr_xy[i].y-arr_xy[j].y));e++;}sort(edges,edges+e,UDlesser); //得到一个递增的边集，注意是从0开始计数kruscal();printf("Case #%d:\n",k); //cout<<"Case #"<<k<<":"<<endl;printf("The minimal distance is: %.2f\n",sum); //输出sumcin>>n;if(n != 0) printf("\n");}}2.最小生成树(Prim算法)/**** **** **** **** **** ***** Function Name : 最小生成树(Prim算法)* Description : ZJU 1203 Swordfish O(N^2)**** **** **** **** **** ****/#include <iostream>#include <cmath>#include <cstdio>using namespace std;double sum, arr_list[101][101], min;int i, j, k=0, n;struct struct_a{float x;float y;};struct_a arr_xy[101];struct struct_b{int point;float lowcost;};struct_b closedge[101];void prim(int n) //prim 需要准备：n顶点数 arr_list[][]顶点的邻接矩阵也是从0开始计数{int i,j,k;k=0;for(j=0; j<n ;j++) {if(j != k) {closedge[j].point = k;closedge[j].lowcost = arr_list[k][j];}}closedge[k].lowcost=0;for(i=0; i<n ;i++) {min=10000;for(j=0; j<n ;j++) {if (closedge[j].lowcost != 0 && closedge[j].lowcost < min) {k = j;min = closedge[j].lowcost;}}sum += closedge[k].lowcost; //不要改成sum+=min; sum即为所求值 closedge[k].lowcost = 0;for(j=0; j<n ;j++) {if(arr_list[k][j] < closedge[j].lowcost) {closedge[j].point = k;closedge[j].lowcost = arr_list[k][j];}}}}/*arr_list[][]= Wij 如果Vi, Vj有边0 如果i=j无限大如果没有边*/int main(){cin>>n;while(n != 0) {sum=0;k++;for(i=0; i<n ;i++)cin>>arr_xy[i].x>>arr_xy[i].y;for(i=0; i<n ;i++)for(j=0; j<n ;j++) //得到邻接矩阵arr_list[][]arr_list[i][j]=arr_list[j][i]=sqrt((arr_xy[i].x-arr_xy[j].x)*(arr_xy[i].x-arr_xy[j].x)+(arr_xy[i].y-arr_xy[j].y)*(arr_xy[i].y-arr_xy[j].y));prim(n);cout<<"Case #"<<k<<":"<<endl;printf("The minimal distance is: %.2f\n",sum);cin>>n;if(n!=0) printf("\n");}}3.单源最短路径(Bellman-ford算法)/**** **** **** **** **** ***** Function Name : 单源最短路径(Bellman-ford算法)* Description : 可允许有负权**** **** **** **** **** ****/#include <stdio.h>#define MAX 100#define MAXNUM 1000000typedef struct graphnode{int vexnum; //顶点数int arcnum; //边数int gra[MAX][MAX]; //图}Graph;Graph *G;//arc数组中存储的第一个顶点到其他顶点的最短路径//结果存在dis数组中int dis[MAX];int arc[MAX][MAX];void bellman(Graph *G){int i,j;bool sign;for(i=0; i < G->vexnum ;i++) dis[i]=MAXNUM;dis[1] = 0;sign = true;for(i=1; i < G->vexnum ;i++) {sign = false;for(j=0; j < G->arcnum ;j++) {if(dis[ arc[j][0] ] < MAXNUM&& dis[ arc[j][1] ] > dis[ arc[j][0] ] + G->gra[ arc[j][0] ][ arc[j][1] ]) {dis[ arc[j][1] ]=dis[ arc[j][0] ] + G->gra[ arc[j][0] ][ arc[j][1] ];sign = true;}}}return;}4.单源最短路径(Dijkstra算法)/**** **** **** **** **** ***** Function Name : 单源最短路径 (Dijkstra算法)* Description : 贪心, O(N^2), 不能有负权**** **** **** **** **** ****/int matrix[200][200],n; //matrix[][], 30000表示无限大,即无边.否则为有边,其值为边的权值void Dijkstra(int x,int y) //起点Vx 终点Vy{int i,j,k,path[40000],mark[40000];int min,dist[40000];for(i=1;i<=n;i++) {mark[i] = 0;dist[i] = matrix[x][i];path[i] = x;}mark[x] = 1;do {min=30000;k=0;for(i=1;i<=n;i++)if(mark[i]==0 && dist[i]<min) {min = dist[i];k = i;}if(k) {mark[k] = 1;for(i=1;i<=n;i++)if(matrix[k][i]<30000 && min+matrix[k][i]<dist[i]) {dist[i] = min + matrix[k][i];path[i] = k;}}}while(k);cout<<dist[y]<<endl; //dist[y] 的值就是从Vx 到 Vy 的最短路径值//如果希望得到路径，加入如下代码：do {cout<<k<<"<--";k = path[k];}while(k!=x);cout<<x<<endl;}5.全源最短路径(Folyd算法)/**** **** **** **** **** ***** Function Name : 全源最短路径(Folyd算法)* Description : DP, O(N^3)**** **** **** **** **** ****///初始化//min_graph[i][j]=graph[i][j];//path[i][j]=j;void Floyd(){int i,j,k;for(k=0;k<vertex_number;k++) {for(i=0;i<vertex_number;i++) {for(j=0;j<vertex_number;j++) {if((graph[i][k]==-1) || (graph[k][j]==-1)) continue;if((min_graph[i][j]==-1) || (min_graph[i][j] > graph[i][k]+graph[k][j])) {min_graph[i][j] = graph[i][k]+graph[k][j]; /*最短路径值*/path[i][j] = k; /*最短路径*/}}}}}6.拓扑排序/**** **** **** **** **** ***** Function Name : 拓扑排序**** **** **** **** **** ****///degree[] 每个结点的入度//f[] 每个结点所在的层void Toplogical_sort(){int i,j;bool p=true;top=0;while(p) {p=false;top++;for(i=1;i<=n;i++)if(degree[i]==0) {p=true;f[i]=top;}for(i=1;i<=n;i++)if(f[i]==top) {for(j=1;j<=n;j++)if(map[i][j]) degree[j]--;degree[i]=-1;}}top--;}7.网络预流和最大流int rel[1000][10000]; //全局变量int pre[1000];//计算网络流//如果是二分图的匹配, 可以先对其进行网络预流以简化后续的查找int pre_flow(int n,vector<int> * v){int ret = 0;int i,j,t,t1;for(i = 0 ; i < v[0].size() ; i++){t = v[0][i]; //t是与节点0相邻接的点for(j = 0 ; j < v[t].size() ; j++){t1 = v[t][j]; //与t相邻接的点if(rel[t1][n - 1] > 0){ret++;rel[0][t]--, rel[t][0]++;rel[t][t1]--, rel[t1][t]++;rel[t1][n - 1]--, rel[n - 1][t1]++;break;}}}return ret;}/*网络中求最大流参数含义: n代表网络中节点数,第0节点为源点, 第n－1节点为汇点rel是个二维数组, rel[i][j]代表从节点i到节点j的流量v[]是一个节点数组, v[i]包含与节点i相邻接的所有节点返回值: 最大流量*/int max_flow(int n,vector<int> * v){int ret = 0,i;int t,t1,tm;queue<int> q;const int Infinite = 2000000000;while(1){for(t = 0 ; t < n ; t++) pre[t] = -1;while(!q.empty()) q.pop();q.push(0);while(!q.empty()){ //find a augmenting path using breath-first searcht = q.front();q.pop();if(t == n - 1) break; //到达汇点for(i = 0 ; i < v[t].size() ; i++){ //对于t相邻接的所有点查找可行路径 t1 = v[t][i];if(rel[t][t1] > 0 && pre[t1] == -1){pre[t1] = t;q.push(t1);}}}if(q.empty() && t != n - 1) break;tm = Infinite; //此处寻找路径最小值在二分图中可省略while(t != 0){ //find the minimal num in the patht1 = pre[t];if(rel[t1][t] < tm) tm = rel[t1][t];t = t1;}// tm = 1; //二分图中t = n - 1;while(t != 0){ //change the relationt1 = pre[t];rel[t1][t] -= tm;rel[t][t1] += tm;t = t1;}ret += tm;}return ret;}8.网络最小费用最大流/**** **** **** **** **** ****网络中最小费用最大流参数含义: np代表网络中的总节点数, v是网络节点的邻接表cost为最后求得的最小费用, mf为求得的最大流算法: 初始最小费用及最大流均为0，不断寻找可增广路增广路对应的单位费用最小并且可流修改残留网络及cost，mf. 直到无可增广路为止。
目录目录 (1)一．扩展的欧几里德和不定方程的解 (2)二．中国同余定理 (3)三．原根 (5)四．积性函数 (6)五．欧拉函数性质 (7)六．线性求1-max的欧拉函数值 (9)七．求单个欧拉函数，求最小的x(phi（n）%x==0),使得2^x =1(mod n) (10)一．扩展的欧几里德和不定方程的解解不定方程ax + by = n的步骤如下:(1)计算gcd(a, b). 若gcd(a, b)不能整除n，则方程无整数解；否则，在方程的两边同除以gcd(a, b)，得到新的不定方程a'x + b'y = n'，此时gcd(a', b') = 1(2)求出不定方程a'x + b'y = 1的一组整数解x0, y0，则n'x0，n'y0是方程a'x + b'y = n'的一组整数解。
(3)根据扩展欧几里德定理，可得方程a'x + b'y = n'的所有整数解为：x = n'x0 + b'ty = n'y0 - a't(t为整数)这也就是方程ax + by = n的所有整数解利用扩展的欧几里德算法，计算(a, b)和满足gcd = (a, b) = ax0 + by0的x0和y0，也就是求出了满足a'x0 + b'y0 = 1的一组整数解。
因此可得：x = n/gcd * x0 + b/gcd * ty = n/gcd * y0 - a/gcd * t(t是整数)int extend_Euclid(int a, int b, int &x, int &y){if (b == 0){x = 1;y = 0;return a;}int gcd= extend_Euclid ( b, a % b, x, y );int temp = x;x = y;y = temp - (a / b) * y;return gcd;}二．中国同余定理Poj 2891#include<stdio.h>#include<iostream>using namespace std;__int64 GCD(__int64 i,__int64 j){if(j==0)return i;elsereturn GCD(j,i%j);}__int64 extend_Euclid(__int64 a, __int64 b, __int64 &x, __int64 &y) {if (b == 0){x = 1;y = 0;return a;}__int64 gcd= extend_Euclid ( b, a % b, x, y );__int64 temp = x;x = y;y = temp - (a / b) * y;return gcd;}//只有两个式子的中国同余定理，return z=a*xx+x=b*yy+y;__int64 CRT_2(__int64 a,__int64 x,__int64 b,__int64 y){__int64 xx,yy,gcd;gcd=extend_Euclid(a,b,xx,yy);__int64 c=y-x;while(c<0)c+=a;if(c%gcd!=0)return -1;xx*=c/gcd;yy*=c/gcd;__int64 t=yy/(a/gcd);while(yy-t*(a/gcd)>0)t++;while(yy-(t-1)*(a/gcd)<=0)t--;return (t*(a/gcd)-yy)*b+y;}//chinese remainder theorem//crt[i][0]存的是除数，crt[i][1]存的是余数,0<=i<n,n>1,返回结果,-1表示无解__int64 CRT(__int64 crt[][2],int n){__int64 m=crt[0][0]/GCD(crt[0][0],crt[1][0])*crt[1][0]; //最大公约数__int64 ans=CRT_2(crt[0][0],crt[0][1],crt[1][0],crt[1][1])%m;for(int i=2;i<n&&ans!=-1;i++){ans=CRT_2(m,ans,crt[i][0],crt[i][1]);m*=crt[i][0]/GCD(m,crt[i][0]);ans%=m;}return ans;}int main(void){int n;__int64 a[10000][2];while(scanf("%d",&n)==1){for(int i=0;i<n;i++)scanf("%I64d%I64d",&a[i][0],&a[i][1]);if(n==1)printf("%I64d\n",a[0][1]);elseprintf("%I64d\n",CRT(a,n));}return 0;}三．原根Poj 1284 ans=φ（p-1）;//p是素数设h为一整数，n为一正整数，（h，n）=k，适合h^k=1（mod n）的最小正整数k叫做h对n的次数。
ACM模板---liang一．高精度计算： ------------------------------------------------------------ 31.高精度加法：----------------------------------------------------------- 31）C++ string类实现：----------------------------------------------- 3 2）字符数组char实现：----------------------------------------------- 32.高精度减法：----------------------------------------------------------- 41）C++ string类实现:------------------------------------------------ 4 2）字符数组char实现:------------------------------------------------ 53.高精度乘法------------------------------------------------------------- 51）字符数组char实现:------------------------------------------------ 5 2）C++ string类实现:------------------------------------------------ 64.高精度阶乘（压缩五位）------------------------------------------------- 65.高精度小数加法--------------------------------------------------------- 7 二．计算几何： -------------------------------------------------------------- 81.线段相交：------------------------------------------------------------- 82.点关于直线的对称点：点：（a,b）,直线：Ax+By+C=0------------------------- 93.求凸包 ---------------------------------------------------------------- 94.多边形面积------------------------------------------------------------ 115.皮克定理：------------------------------------------------------------ 116.三角形： ------------------------------------------------------------- 121）点和三角形的关系------------------------------------------------- 12 2）三角形各种面积算法：--------------------------------------------- 137.两圆相交面积---------------------------------------------------------- 14 三．搜索: ------------------------------------------------------------------ 151.DFS(深度优先、回溯) -------------------------------------------------- 152.BFS(广度优先) -------------------------------------------------------- 16 四．数论： ----------------------------------------------------------------- 171.最大公约数，最小公倍数：---------------------------------------------- 172.欧几里德扩展：-------------------------------------------------------- 173.大数除法求余、快速幂取余：-------------------------------------------- 174.同余： --------------------------------------------------------------- 195.筛素数 --------------------------------------------------------------- 19 五．图论 ------------------------------------------------------------------- 201.并查集： ------------------------------------------------------------- 202.最小生成树：---------------------------------------------------------- 201） Prim算法------------------------------------------------------- 21 2）克鲁斯卡尔算法--------------------------------------------------- 223.最短路径: ------------------------------------------------------------ 231）最短路径dijkstra算法-------------------------------------------- 23 1）Floyd算法（最短路径）------------------------------------------- 284.最大匹配 ------------------------------------------------------------- 295.最大流 --------------------------------------------------------------- 31 六．数据结构 --------------------------------------------------------------- 331.RMQ ------------------------------------------------------------------ 332.树状数组 ------------------------------------------------------------- 351)一维树状数组------------------------------------------------------ 352)二维树状数组------------------------------------------------------ 37 七．各种处理函数 ----------------------------------------------------------- 381.字符串 --------------------------------------------------------------- 381）字符串分解函数strtok-------------------------------------------- 38 八．动态规划 --------------------------------------------------------------- 391.最长公共子序列-------------------------------------------------------- 392.单调递增（递减）最长子序列-------------------------------------------- 403.整数规划：------------------------------------------------------------ 42一．高精度计算：1.高精度加法：1）C++ string类实现：#include<string>void sum(string &a,string b) // a=a+b{ int i,j,k,c,s;while (a.length()>b.length()) b='0'+b;// a,b处理成一样长 while (b.length()>a.length()) a='0'+a;c=0;for (i=a.length()-1; i>=0; i--){ s=a[i]-48+b[i]-48+c;if ( s>9 ) { s=s%10; c=1;} else c=0;a[i]=48+s;}if ( c>0 ) a='1'+a;}2）字符数组char实现：#include<string.h>void add(char a[],char b[])//a=a+b{int i,j,k,sum=0;k=strlen(a)>strlen(b)?strlen(a):strlen(b);a[k+1]=0;for(i=strlen(a)-1,j=strlen(b)-1;i>=0||j>=0;i--,j--,k--){ if(i>=0) sum+=a[i]-'0'; if(j>=0) sum+=b[j]-'0';a[k]=sum%10+'0'; sum/=10;}if(sum) a[0]=sum+'0';else strcpy(a,&a[1]);}2.高精度减法：1）C++ string类实现:#include<string>void f(string &a,string b){int i,j,sum=0;for(i=a.length()-1,j=b.length()-1;i>=0||j>=0;i--,j--){sum+=a[i]-'0'; if(j>=0) sum-=b[j]-'0';if(sum<0) {a[i]=sum+10+'0';sum=-1;}else {a[i]=sum+'0';sum=0;}}if(a[0]=='0') a=&a[1];for(i=0;a[i]=='0'&&i<a.length();i++) ;if(i==a.length()) a="0";}2）字符数组char实现:#include <string.h>void jian(char a[],char b[])//a-=b{int i,j,sum=0;for(i=strlen(a)-1,j=strlen(b)-1;i>=0||j>=0;i--,j--){sum+=a[i]-'0'; if(j>=0) sum-=b[j]-'0';if(sum<0) {a[i]=sum+10+'0';sum=-1;}else {a[i]=sum+'0';sum=0;}}if(a[0]=='0') strcpy(a,&a[1]);for(i=0;a[i]=='0';i++) ;if(i==strlen(a)) strcpy(a,"0");}3.高精度乘法1）字符数组char实现:#include <string.h>void chen(char a[],char b[])//a=a*b{ int i,j,k,l,sum,c[410]={0};l=strlen(a)+strlen(b);for(i=strlen(b)-1;i>=0;i--)for(j=strlen(a)-1,k=i+j+1;j>=0;j--,k--){ sum=(b[i]-'0')*(a[j]-'0')+c[k];c[k]=sum%10;c[k-1]+=sum/10;}for(i=c[0]?0:1,j=0;i<l;i++)a[j++]=(c[i]+'0'); a[j]=0;}2）C++ string类实现:#include<string>void chenn(string &a,string b)//a=a*b{ int i,j,k,l,sum,c[410]={0};l=a.length()+b.length();for(i=b.length()-1;i>=0;i--)for(j=a.length()-1,k=i+j+1;j>=0;j--,k--){ sum=(b[i]-'0')*(a[j]-'0')+c[k];c[k]=sum%10;c[k-1]+=sum/10;}i=c[0]?0:1;while(a.length()<l-i) a=a+'0';for(j=0;i<l;i++)a[j++]=(c[i]+'0');}4.高精度阶乘（压缩五位）#include<iostream>#include<iomanip>using namespace std;int a[10000];int main(void){int i,n,w,up,j;while(cin>>n){for(w=a[0]=i=1;i<=n;i++){ for(j=0,up=0;j<w;j++){a[j]=i*a[j]+up;up=a[j]/100000;a[j]%=100000;}if(up) a[w++]=up;}cout<<a[w-1];for(i=w-2;i>=0;i--)cout<<setfill('0')<<setw(5)<<a[i]; cout<<endl;}}5.高精度小数加法#include<cstring>#include<algorithm>void quw0(char a[]) //去除尾部多余的零 eg: 3.5+3.5=7.0变成 7 { int i;for(i=0;i<strlen(a);i++) //判断有没有小数点if(a[i]=='.') break;if(i!=strlen(a)){i=strlen(a)-1;while(a[i]=='0') {a[i]=0;;i--;}if(a[i]=='.') a[i]=0;;}}void add(char *a,char *b)//a=a+b{int i=0,j=0,la=strlen(a),lb=strlen(b),sum=0;while((a[i]-'.')&&i<la) i++;while((b[j]-'.')&&j<lb) j++;if(i==la) {a[i]='.';la++;};if(j==lb) {b[j]='.';lb++;};while(la-i>lb-j) {b[lb]='0';lb++;}while(lb-j>la-i) {a[la]='0';la++;}if(la<lb) { swap(a,b); swap(la,lb); }a[la+1]=0;b[lb]=0;for(i=la-1,j=lb-1;i>=0;i--,j--){ if(a[i]=='.') {a[i+1]='.';continue;}sum+=a[i]-'0'; if(j>=0) sum+=b[j]-'0';a[i+1]=sum%10+'0'; sum/=10;}if(sum) a[0]=sum+'0';else strcpy(a,&a[1]);quw0(a);//根据题目需要是否保留尾0}二．计算几何：1.线段相交：int xj(point x1,point x2,point x3,point x4)//相交为1,不交为0{if(min(x1.x,x2.x)>max(x3.x,x4.x)||min(x1.y,x2.y)>max(x3.y,x4.y)||min(x3.x,x4.x)>max(x1.x,x2.x)||min(x3.y,x4.y)>max(x1.y,x2.y) )return 0;//不交：矩形排斥实验，最小的>最大的肯定不交int a,b,c,d;a=(x1.x-x2.x)*(x3.y-x1.y)-(x1.y-x2.y)*(x3.x-x1.x);//跨立实验 b=(x1.x-x2.x)*(x4.y-x1.y)-(x1.y-x2.y)*(x4.x-x1.x);c=(x3.x-x4.x)*(x1.y-x3.y)-(x3.y-x4.y)*(x1.x-x3.x);d=(x3.x-x4.x)*(x2.y-x3.y)-(x3.y-x4.y)*(x2.x-x3.x);return a*b<=0&&c*d<=0;}2.点关于直线的对称点：点：（a,b）,直线：Ax+By+C=0#include <stdio.h>int main(){int n;float a,b,A,B,C,a1,b1;scanf("%d\n",&n);while(n--){ scanf("%f %f %f %f %f",&a,&b,&A,&B,&C);int a1=int (a-2*A*(A*a+B*b+C)/(A*A+B*B));int b1=int (b-2*B*(A*a+B*b+C)/(A*A+B*B));printf("%d %d\n",a1,b1);}}3.求凸包//根据题目改动数据类型，数组大小，排序方式#include <algorithm>#define eps 1e-8struct point{int x,y;};point pnt[100003],res[100005];bool operator<( point A,point B )//按y排也可，具体看题目要求{ return A.x < B.x || (A.x == B.x && A.y < B.y); }double mult(point p0,point p1,point p2){ r eturn (p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y)*(p2.x-p0.x); }//数组下标从0开始，n是点的个数，选中的点在保存在res数组中，个数是topint graham(point pnt[], int n, point res[])//选中的点在保存在res数组中，个数是top{ int i, len, k = 0, top = 1;sort(pnt, pnt + n); //用cmp可能超时，原因未知if (n == 0) return 0; res[0] = pnt[0];if (n == 1) return 1; res[1] = pnt[1];if (n == 2) return 2; res[2] = pnt[2];for (i = 2; i < n; i++){ while (top && mult(pnt[i], res[top], res[top-1])<=eps) top--;res[++top] = pnt[i];}len = top; res[++top] = pnt[n - 2];for (i = n - 3; i >= 0; i--){ while (top!=len && mult(pnt[i], res[top], res[top-1])<=eps) top--;res[++top] = pnt[i];}return top; // 返回凸包中点的个数}4.多边形面积//点必须是顺时针给出或逆时针给出才可用此法//使用时注意数据类型，和数据大小struct point{int x,y;}a[105];int duo(point a[],int n) //点在数组 a[]中，个数是n{ int i,s=0;for(i=1;i<=n;i++)s+=(a[i-1].x*a[i%n].y-a[i-1].y*a[i%n].x);if(s<0) s=-s;return s;// if(s%2) cout<<s/2<<".5"<<endl; 若为longl long 类型，不要用double// else cout<<s/2<<".0"<<endl;}5.皮克定理：//S=a+b÷2-1//(其中a表示多边形内部的点数,b表示多边形边界上的点数,S表示多边形的面积)#include<cmath>struct point{int x,y;};int gcd(int m,int n){if(n==0) return m;return gcd(n,m%n);}int bian(point a[],int n)//算出点A和点B组成的线段上的点{ int s=0,i;for(i=1;i<=n;i++)s+=gcd(abs(a[i-1].x-a[i%n].x),abs(a[i-1].y-a[i%n].y));return s;}int duo(point a[],int n)//求n边形的面积,注意ans未除2；{int i,s=0;for(i=1;i<=n;i++)s+=(a[i-1].x*a[i%n].y-a[i-1].y*a[i%n].x);if(s<0) s=-s;return s;}6.三角形：1）点和三角形的关系//注意数据类型#include <cmath>struct point{int x,y;};bool operator ==(point A,point B){return A.x==B.x&&A.y==B.y;} int area(point A,point B,point C)//三角形面积，未除2{int s=abs((B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x));return s;}int pan3(point a[],point p) //若点在三角形内（不含边界），返回1；{int sa,sb,sc,s;s=area(a[0],a[1],a[2]);sa=area(a[0],a[1],p);sb=area(a[0],a[2],p);sc=area(a[1],a[2],p);if(sa&&sb&&sc&&s==sa+sb+sc) return 1;if((!sa||!sb||!sc)&&s==sa+sb+sc){if(p==a[0]||p==a[1]||p==a[2]) return 4;//若点在三角形顶点上，返回4。
acm latex模板使用方法标题，ACM LaTeX模板使用方法。
ACM（Association for Computing Machinery）是一个致力于计算机科学和信息技术领域的国际学术组织，其LaTeX模板是用于撰写ACM相关论文和文章的标准格式。
下面将介绍如何使用ACM LaTeX模板来撰写论文。
1. 下载和安装TeX发行版，首先，你需要安装一个TeX发行版，比如TeX Live或者MiKTeX。
这些发行版包含了LaTeX编译器和相关的宏包，可以帮助你编译和生成PDF格式的文档。
2. 下载ACM模板文件，在ACM官方网站上可以找到最新的ACM LaTeX模板文件，包括模板文件、示例文档和相关的说明文档。
下载并解压这些文件到你的工作目录中。
3. 编辑模板文件，使用LaTeX编辑器（比如TeXworks、TeXstudio等）打开模板文件，按照你的需要修改标题、作者、摘要、正文等内容。
ACM模板提供了丰富的宏包和模板设置，可以满足ACM论文的格式要求。
4. 编译生成PDF，在LaTeX编辑器中选择编译选项，一般是选择XeLaTeX或者PDFLaTeX编译引擎，然后点击编译按钮生成PDF文件。
在编译过程中可能会有一些警告或错误信息，需要根据提示进行修改和调整。
5. 查看和修改，生成PDF后，可以用PDF阅读器打开查看，检查格式和排版是否符合ACM的要求。
根据需要进行修改和调整，直到满足要求为止。
总之，使用ACM LaTeX模板撰写论文可以帮助作者更专注于内容本身，而不用过多关心格式和排版的细节。
希望以上介绍对你有所帮助，祝你撰写顺利！。
求逆序数int solve(int f,int l){int mid=(f+l)/2,j=0,h1=f,h2=mid+1;int sum=0;if(f==l) return 0;sum+=(solve(f,mid)+solve(mid+1,l));for(;h1<=mid&&h2<=l;){if(str[i][h1]<=str[i][h2]){tem[j++]=str[i][h1];h1++;}else {tem[j++]=str[i][h2];h2++;sum+=mid-h1+1;}}while(h1<=mid){tem[j++]=str[i][h1++];}while(h2<=l){tem[j++]=str[i][h2++];}memcpy(&str[i][f],tem,sizeof(char)*j);return sum;}经典宽搜visited[a.x][a.y]=0;while (s != e && s<=N*N && e<=N*N){c = queue[s];if (c.x == b.x && c.y == b.y) break;for (i=0;i<8;i++){c = queue[s];c.x += d[i][0];c.y += d[i][1];if (visited[c.x][c.y]==1 && c.x>=0 && c.x<l && c.y>=0 && c.y<l){visited[c.x][c.y]=0;c.step++;queue[e++]=c;}}s++;}深搜一道void DFS(int a,int b){int i,j;if(putk == k){sum++;return;}visited[b]=1;for(i=a+1;i<n;i++)for(j=0;j<n;j++)if(c[i][j]=='#' && visited[j]==0){putk++;DFS(i,j);putk--;}visited[b]=0;}滑雪DPint f(int a,int b){int tem=0;if(visited[a][b]==1) return arr[a][b];if(a-1>=0 && map[a-1][b]<map[a][b])if(tem<f(a-1,b)) tem=f(a-1,b);if(a+1<r && map[a+1][b]<map[a][b])if(tem<f(a+1,b)) tem=f(a+1,b);if(b-1>=0 && map[a][b-1]<map[a][b])if(tem<f(a,b-1)) tem=f(a,b-1);if(b+1<c && map[a][b+1]<map[a][b])if(tem<f(a,b+1)) tem=f(a,b+1); //此处切记不要把f写成arr！！visited[a][b]=1;arr[a][b]=tem+1;return arr[a][b];}最长上升子序列（二分）for(i=0;i<n;i++){left=1;right=len;while(left<=right){mid=(left+right)/2;if(b[mid]<a[i]) left=mid+1;else right=mid-1;}b[left]=a[i];f[i]=left;if(len<left) len=left;if(ans<left) ans=left;}最长上升子序列void DP(int x){int i,j=0,max=0;for(i=0;i<x;i++)if(a[i]<a[x]) h[j++]=f[i];for(i=0;i<j;i++)if(max<h[i]) max=h[i];f[x]=max+1;}01背包int main(){int i,ans,j,t;scanf("%d%d",&n,&m);for(i=0;i<n;i++)scanf("%d%d",&a[i].w,&a[i].d);for(i=0;i<=m;i++)f[0][i]=0;for(i=1,t=1;i<=n;i++,t=1-t)for(j=0;j<=m;j++){f[t][j]=f[1-t][j];if(j>=a[i-1].w && f[1-t][j-a[i-1].w]+a[i-1].d>f[t][j])f[t][j]=f[1-t][j-a[i-1].w]+a[i-1].d;}ans=f[1-t][m];printf("%d\n",ans);}最长公共子序列•若给定序列X={x1,x2,…,x m}，则另一序列Z={z1,z2,…,z k}，是X的子序列是指存在一个严格递增下标序列{i1,i2,…,i k}使得对于所有j=1,2,…,k有：z j=x ij。
ACM（五篇范例）第一篇：ACMDijkstra 模板/*************************************** * About:有向图的Dijkstra算法实现 * Author:Tanky Woo * Blog:t=0;if(flag == 0){printf(“Non”);}else{for(int i=min;i<=max;++i){if(mark[i]==1 && arr[i]==0)cnt++;}}if(cnt==1)printf(“Yesn”);elseprintf(“Non”);}} return 0;搜索算法模板BFS：1.#include2.#include3.#include4.#includeing namespace std;6.const int maxn=100;7.bool vst[maxn][maxn];// 访问标记8.int dir[4][2]={0,1,0,-1,1,0,-1,0};// 方向向量9.10.struct State // BFS 队列中的状态数据结构 11.{ 12.int x,y;// 坐标位置13.int Step_Counter;// 搜索步数统计器14.};15.16.State a[maxn];17.18.boolCheckState(State s)// 约束条件检验19.{ 20.if(!vst[s.x][s.y] &&...)// 满足条件 1: 21.return 1;22.else // 约束条件冲突 23.return 0;24.} 25.26.void bfs(State st)27.{ 28.queue q;// BFS 队列29.State now,next;// 定义 2 个状态，当前和下一个30.st.Step_Counter=0;// 计数器清零 31.q.push(st);// 入队32.vst[st.x][st.y]=1;// 访问标记33.while(!q.empty())34.{ 35.now=q.front();// 取队首元素进行扩展36.if(now==G)// 出现目标态，此时为Step_Counter 的最小值，可以退出即可37.{ 38.......// 做相关处理39.return;40.} 41.for(int i=0;i<4;i++)42.{ 43.next.x=now.x+dir[i][0];// 按照规则生成下一个状态44.next.y=now.y+dir[i][1];45.next.Step_Counter=now.Step_Coun ter+1;// 计数器加1 46.if(CheckState(next))// 如果状态满足约束条件则入队 47.{ 48.q.push(next);49.vst[next.x][next.y]=1;//访问标记 50.} 51.} 52.q.pop();// 队首元素出队53.} 54.return;55.} 56.57.int main()58.{ 59.......60.return 0;61.}代码：胜利大逃亡Ignatius被魔王抓走了,有一天魔王出差去了,这可是Ignatius逃亡的好机会.魔王住在一个城堡里,城堡是一个A*B*C的立方体,可以被表示成A个B*C的矩阵,刚开始Ignatius被关在(0,0,0)的位置,离开城堡的门在(A-1,B-1,C-1)的位置,现在知道魔王将在T分钟后回到城堡,Ignatius每分钟能从一个坐标走到相邻的六个坐标中的其中一个.现在给你城堡的地图,请你计算出Ignatius能否在魔王回来前离开城堡(只要走到出口就算离开城堡,如果走到出口的时候魔王刚好回来也算逃亡成功),如果可以请输出需要多少分钟才能离开,如果不能则输出-1.Input 输入数据的第一行是一个正整数K,表明测试数据的数量.每组测试数据的第一行是四个正整数A,B,C和T(1<=A,B,C<=50,1<=T<=1000),它们分别代表城堡的大小和魔王回来的时间.然后是A块输入数据(先是第0块,然后是第1块,第2块......),每块输入数据有B行,每行有C个正整数,代表迷宫的布局,其中0代表路,1代表墙.(如果对输入描述不清楚,可以参考Sample Input中的迷宫描述,它表示的就是上图中的迷宫) 特别注意:本题的测试数据非常大,请使用scanf输入,我不能保证使用cin能不超时.在本OJ上请使用Visual C++提交.Output 对于每组测试数据,如果Ignatius能够在魔王回来前离开城堡,那么请输出他最少需要多少分钟,否则输出-1.Sample Input 1 3 3 4 20 0 1 1 1 0 0 1 1 0 1 1 1 1 1 1 1 1 0 0 1 0 1 1 1 0 0 0 0 0 1 1 0 0 1 1 0Sample Output 11代码：#include #include #include #include #includeusing namespace std;int tx[] = {0,1,-1,0,0,0,0};int ty[] = {0,0,0,1,-1,0,0};int tz[] = {0,0,0,0,0,1,-1};int arr[55][55][55];int known[55][55][55];// 访问标记int a,b,c,d;struct state{int x,y,z;// 所在的坐标int step_count;//统计搜索步数。
