中山大学ACM模板.zip_中山大学ACM模板资源-CSDN下载

共1个文件

pdf：1个

版权申诉

178 浏览量 2022-09-24 10:58:30 上传评论 1 收藏 190KB ZIP 举报

中山大学ACM算法模板是一个专为参与ACM（国际大学生程序设计竞赛）的团队准备的资源集合，旨在帮助参赛者快速理解和实现常见的算法问题。这个压缩包中的核心内容是"中山大学ACM模板.pdf"，这是一份详细的指导文档，包含了多种算法的实现和解析。 1. **算法基础**：在ACM竞赛中，基础算法是解决问题的关键。这份模板可能涵盖了排序（如快速排序、归并排序、堆排序）、搜索（如二分查找、广度优先搜索、深度优先搜索）、图论（如最短路径算法Dijkstra、Floyd-Warshall、拓扑排序）以及动态规划等基础知识。 2. **数据结构**：ACM比赛中的问题往往涉及到高效的数据结构应用，如链表、队列、栈、树（二叉树、平衡树如AVL和红黑树）、图等。中山大学的模板可能详细解释了这些数据结构的实现和操作。 3. **数学知识**：ACM竞赛中数学思维的运用至关重要，包括组合数学、数论、概率论等。模板可能包含了一些常用的数学技巧和公式，以及如何在编程中应用它们。 4. **字符串处理**：字符串操作在文本处理问题中十分常见，模板可能包括了字符串匹配（如KMP算法）、最长公共子序列等方法。 5. **编码技巧**：模板可能会介绍一些编程技巧，比如如何优化代码以提高运行效率，如何避免溢出，以及如何使用位运算等高级技巧。 6. **IO与时间限制**：ACM比赛中，输入输出的效率和代码的执行时间是决定成绩的重要因素。模板可能提供了快速读入和输出的方法，如使用scanf/printf而非cin/cout，或者使用多线程预读取数据。 7. **调试与测试**：在模板中，可能还会介绍如何编写测试用例，进行单元测试，以及如何利用调试工具定位和修复问题。 8. **团队协作**：ACM比赛通常以团队形式进行，模板可能包含关于团队分工、代码共享和版本控制（如Git）的建议。这份中山大学ACM模板对于准备参加此类竞赛的学生来说是一份宝贵的资源，它可以帮助他们快速提升算法能力，理解并掌握竞赛中常见的问题解决策略，从而在比赛中取得更好的成绩。通过深入学习和实践这份模板，学生不仅可以提升编程技能，还能锻炼分析问题和解决问题的能力，这对于未来的学习和职业发展都将大有裨益。

资源推荐

资源详情

资源评论

收起资源包目录

中山大学ACM模板.zip （1个子文件）

中山大学ACM模板.pdf 216KB

高精度.......................................................................................................................2

(1)高精函数........................................................................................................2

(2)高精开方........................................................................................................6

(3)高精类............................................................................................................9

计算几何.................................................................................................................13

(1)凸包..............................................................................................................13

(2)最远点对......................................................................................................14

(3)最近点对......................................................................................................16

(4)简单多边形的重心 ......................................................................................17

(5)直线问题......................................................................................................17

(6)计算多边形面积(凹凸都适用).....................................................................19

(7)判断点线在多边行内...................................................................................19

图论算法.................................................................................................................20

(1)生成树问题..................................................................................................20

(2)最短路问题..................................................................................................20

(3)网络流问题..................................................................................................20

//网络流（最大流程序,标号法)................................................................20

//网络流（最大流程序,前流推进).............................................................21

//网络流（最小费用最大流程序) by peipei..............................................22

(4)二分图问题..................................................................................................23

//最大基数匹配..........................................................................................23

//最大权匹配..............................................................................................24

(5)Euler 回路 ....................................................................................................25

(6)连通性问题..................................................................................................26

//无向图的割顶和桥(pku 1523 测试)........................................................26

//极大强连通分支(tested by uva 247)........................................................26

数据结构.................................................................................................................27

(1)堆 .................................................................................................................27

(2)线段树..........................................................................................................28

(3)树状数组......................................................................................................28

(4)哈希表..........................................................................................................30

(5)左偏树..........................................................................................................30

数论算法.................................................................................................................31

简单的数论算法(gcd,ext_euclid,中国剩余定义，Euler 函数).........................31

//最大公约数..............................................................................................31

//中国剩余定义，高精度 ..........................................................................32

//中国剩余定理,int 版本 ............................................................................34

(2)随机素数测试与大数分解...........................................................................35

字符串.....................................................................................................................37

(1)KMP.............................................................................................................37

(2)后缀数组......................................................................................................38

(3)LIS(nlogn)....................................................................................................38

(4)最小串表示法(O(N)算法)............................................................................38

(5)最大公共上升子列(平方算法).....................................................................38

模拟算法.................................................................................................................39

表达式求值 ......................................................................................................39

特殊问题.................................................................................................................41

(1)LCA+RMQ...................................................................................................41

(2)FFT...............................................................................................................42

//多项式乘法..............................................................................................44

(3)最大团..........................................................................................................46

排序.........................................................................................................................46

(1)快速排序(找第 n 大数)................................................................................46

(2)归并排序(逆序数)........................................................................................47

(3)希尔排序......................................................................................................48

(4)基数排序......................................................................................................48

(5)STL 的 sort 函数 ..........................................................................................49

高精度

(1)高精函数

//高精例程

/////////////////////////////////////////////////////////////

//常用函数 //

//(1)add(bint a, bint b, bint& c)大数加法 c=a+b //

//(2)add(bint a, type b, bint& c)高精加单精 c=a+b //

//(3)by(bint a, type b, bint& c)高精乘单精 c=a*b, //

// **注意:b 应小于 base** //

//(4)by(bint a, bint b, bint& c)大数乘法 c=a*b //

//(5)div(bint a, type b, bint& c, type& d)高精除单精 //

// c = a/b, d = a%b; //

//(6)input(bint& a)输入高精,无效输入返回 0,否则返回 1 //

//(7)output(bint& a)输出高精 //

/////////////////////////////////////////////////////////////

//少用函数 //

//(8)move(bint& a)二进制右移,即除 2 操作 //

//(9)sub(bint a, bint b, bint& c)大数减法 c=a-b,a>=b //

//(10)sub(bint a, type b, bint& c)高精减单精 c=a-b,a>=b //

//(11)cmp(bint a, bint b)比较 a 和 b,>,==,<分别返回 //

// 正数,0,负数. //

//(12)give(bint a, bint& b)赋值 b = a; //

//(13)give(type a, bint& b)赋值 b = a; //

//(14)shift(bint& a, type k)段移位函数,把 a 移动 k 段,变大 mod^k//

//(15)div(bint a, bint b, bint& c, bint& d)大数除法 //

// c=a/b,d=a%b,**注意:需要函数(1),(2),(4),(9),(11),(13), //

// (14)** //

/////////////////////////////////////////////////////////////

#include <stdio.h>

#include <string.h>

//////////////////////////////////////

#define MAX 100

#define mod 10000

#define baselen 4

#define in(a) scanf("%d",&a)

#define out1(a) printf("%d",a)

#define out2(a) printf("%04d",a)

typedef int type;

/////////////////////////////////////

struct bint{

type dig[MAX], len;

bint(){len = 0, dig[0] = 0;}

};

////////////////////////////////////////////

//常用函数

//(1)

void add(bint a, bint b, bint& c){

type i, carry ;

for( i = carry = 0; i <= a.len || i <= b.len || carry; i++){

if(i<=a.len)carry += a.dig[i];

if(i<=b.len)carry += b.dig[i];

c.dig[i] = carry%mod;

carry /= mod;

}

c.len = i - 1;

用 FinePrint 打印 - 可在 www.fineprint.com.cn 订购

PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.com.cn

}

//(2)

void add(bint a, type b, bint& c){

type i;

for( i = 0; i <= a.len || b; i++){

if(i<=a.len)b += a.dig[i];

c.dig[i] = b%mod;

b /= mod;

}

c.len = i-1;

}

//(3)

void by(bint a, type b, bint& c){

type i, carry;

for( i = carry = 0; i <= a.len || carry; i++){

if( i <= a.len ) carry += b*a.dig[i];

c.dig[i] = carry%mod;

carry /= mod;

}

i--;

while( i && !c.dig[i] )i--;

c.len = i;

}

//(4)

void by(bint a, bint b, bint& c){

type i, j, carry;

for( i=a.len+b.len+1; i>=0; i--)c.dig[i] = 0;

for( i=0; i<=a.len; i++){

carry = 0;

for( j=0; j<=b.len||carry; j++){

carry += c.dig[i+j];

if(j<=b.len)carry += a.dig[i]*b.dig[j];

c.dig[i+j] = carry%mod;

carry /= mod;

}

i = a.len+b.len+1;

while(i&&c.dig[i]==0)i--;

c.len = i;

}

//(5)

void div(bint a, type b, bint& c, type& d){

type i;

for(i = a.len,d = 0; i>=0 ; i--){

d = d*mod + a.dig[i];

c.dig[i] = d/b;

d = d%b;

}

i = a.len;

while(i&&c.dig[i]==0)i--;

c.len = i;

}

//(6)

bool input(bint& a){

type i, j, w, k, p;

char data[MAX*baselen+1];

if(scanf("%s",data)==EOF)return false;

w = strlen(data) - 1, a.len = 0;

for(p=0;p<=w&&data[p]=='0';p++);

while(1){

i = j = 0, k = 1;

while(i<baselen&&w>=p){

j = j+ (data[w--] - '0')*k;

k *= 10, i++;

}

a.dig[a.len++] = j;

if(w<p)break;

}

a.len--;

return true;

}

//(7)

void output(bint& a){

type i;

i = a.len - 1;

out1(a.dig[a.len]);

while(i>=0)out2(a.dig[i--]);

}

////////////////////////////////////////////////////////////////////////

//少用函数

//(8)

void move(bint& a){

type carry, k, t;

k = a.len+1, carry = 0;

while(k--){

t = a.dig[k]&1;

a.dig[k] = (a.dig[k]>>1);

if(carry)a.dig[k] += (mod>>1);

carry = t;

}

if(a.len&&a.dig[a.len]==0)a.len--;

}

//(9)

void sub(bint a, bint b, bint& c){

type i, carry;

for( i=carry=0; i<=a.len; i++){

c.dig[i] = a.dig[i]-carry;

if(i<=b.len)c.dig[i] -= b.dig[i];

if(c.dig[i]<0)carry = 1, c.dig[i] += mod;

else carry = 0;

}

i--;

while(i&&c.dig[i]==0)i--;

c.len = i;

}

//(10)

void sub(bint a, type b, bint& c){

type i;

for( i=0; i<=a.len; i++){

c.dig[i] = a.dig[i]-b;

if(c.dig[i]<0)b = 1, c.dig[i] += mod;

else b = 0;

}

i--;

while(i&&c.dig[i]==0)i--;

c.len = i;

用 FinePrint 打印 - 可在 www.fineprint.com.cn 订购

PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.com.cn

}

//(11)

int cmp(bint a, bint b){

if(a.len<b.len)return -1;

if(a.len>b.len)return 1;

int i = a.len;

while(i&&a.dig[i]==b.dig[i])i--;

return a.dig[i] - b.dig[i];

}

//(12)

void give(bint a, bint& b){

int i = 0;

while(i<=a.len){

b.dig[i] = a.dig[i];

i++;

}

b.len = a.len;

}

//(13)

void give(type a, bint& b){

b.dig[0] = a%mod;

a /= mod;

if(a>0)b.dig[1] = a, b.len = 1;

else b.len = 0;

}

//(14)

void shift(bint& a, type k){

int i;

i = a.len+k;

while(i>=k){

a.dig[i] = a.dig[i-k];

i --;

}

while(i>=0)a.dig[i--] = 0;

a.len += k;

}

//(15)

void div(bint a, bint b, bint& c, bint& d){

type x, k;

bint temp;

give(a, d);

c.len = c.dig[0] = 0;

while( cmp(d,b)>0 ){

k = d.len - b.len;

if( d.dig[d.len] > b.dig[b.len] )

x = d.dig[d.len] / (b.dig[b.len] + 1);

else if( k )

k--, x = ( d.dig[d.len]*mod + d.dig[d.len-1])/(b.dig[b.len] + 1);

else break;

by( b, x, temp);

shift( temp, k );

sub(d, temp, d);

give( x, temp );

shift(temp, k);

add(c, temp, c);

}

if(cmp(d,b)>=0) sub(d,b,d), add(c,(type)1, c);

}

//////////////////////////////////////////////////////////////////////////

int main(){

bint a, b, c, d, start, end, mid;

while(input(a)){

give(a,end);

end.len /= 2;

end.dig[++end.len] = mod - 1;

give(a,start);

start.len /= 2;

if(start.len==0)start.dig[0] = 0;

else start.dig[--start.len] = 1;

while(cmp(end,start)>=0){

add(end,start,mid);

move(mid);

by(mid,mid,d);

if(cmp(d,a)<=0)add(mid,1,start);

else sub(mid,1,end);

}

output(end);

printf("\n");

}

return 0;

}

(2)

高精开方

//by zhonglei

#include<stdio.h>

#include<string.h>

#include<math.h>

int big(char s1[],char s2[]){

int len1,len2,i,q;

q=0;

while(s1[q]=='0') q++;

strcpy(s1,s1+q);

if(strlen(s1)==0){

s1[0]='0';

s1[1]=0;

}

q=0;

while(s2[q]=='0') q++;

strcpy(s2,s2+q);

if(strlen(s2)==0){

s2[0]='0';

s2[1]=0;

}

len1=strlen(s1);

len2=strlen(s2);

if(len1>len2)

return 1;

else if(len1<len2)

return 0;

else{

for(i=0;i<len1;i++){

if(s1[i]>s2[i])

return 1;

else if(s1[i]<s2[i])

用 FinePrint 打印 - 可在 www.fineprint.com.cn 订购

PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.com.cn

return 0;

}

return 0;

}

void mul(char s[],int t,char re[]){

int left,i,j,k,len;

char c;

left=0;

j=0;

for(i=strlen(s)-1;i>=0;i--){

k=t*(s[i]-'0')+left;

re[j++]=(k%10)+'0';

left=k/10;

}

while(left>0){

re[j++]=(left%10)+'0';

left/=10;

}

re[j]=0;

len=strlen(re);

for(i=0;i<len/2;i++){

c=re[i];

re[i]=re[len-1-i];

re[len-1-i]=c;

}

return;

}

void sub(char a[],char b[]){

int left,len1,len2,temp,j;

len1=strlen(a)-1;

len2=strlen(b)-1;

left=0;

while(len2>=0){

temp=a[len1]-b[len2]+left;

if(temp<0){

temp+=10;

left=-1;

}

else

left=0;

a[len1]=temp+'0';

len1--;

len2--;

}

while(len1>=0){

temp=a[len1]-'0'+left;

if(temp<0){

temp+=10;

left=-1;

}

else

left=0;

a[len1]=temp+'0';

len1--;

}

j=0;

while(a[j]=='0') j++;

strcpy(a,a+j);

if(strlen(a)==0){

a[0]='0';

a[1]=0;

}

return;

}

void sqr(char s[],char re[]){

char temp[1010];

char left[1010];

char p[1010];

int i,j,k,len1,len2,q;

len1=strlen(s);

if(len1%2==0){

left[0]=s[0];

left[1]=s[1];

left[2]=0;

j=2;

}

else{

left[0]=s[0];

left[1]=0;

j=1;

}

re[0]='0';

re[1]=0;

q=0;

while(j<=len1){

mul(re,20,temp);

len2=strlen(temp);

for(i=9;i>=0;i--){

temp[len2-1]=i+'0';

mul(temp,i,p);

if(!big(p,left))

break;

}

re[q++]=i+'0';

re[q]=0;

sub(left,p);

len2=strlen(left);

left[len2]=s[j];

left[len2+1]=s[j+1];

left[len2+2]=0;

j+=2;

}

int main(){

char s[1010],re[1010];

int i;

freopen("test.txt","r",stdin);

while(scanf("%s",s)!=EOF){

re[0]=0;

sqr(s,re);

i=0;

while(re[i]=='0') i++;

strcpy(re,re+i);

printf("%s\n",re);

}

用 FinePrint 打印 - 可在 www.fineprint.com.cn 订购

PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.com.cn

}

(3)

高精类

//高精类，包括加减乘除取模运算

//written by magic pig on 8th June

#include <iostream.h>

#include <string.h>

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

#define MAX 130

#define base 10000

#define baselen 4

long countnub = 0;

//此大整数类用数组 digital[MAX]表示一个大整数;

//一个 digital 表示最大为 9999;

//len 表示目前整数的用到最大 digital 位,sign 表示符号;

class Int {

public :

//构造函数;

Int();

//比较函数,第二个参数为 0 则表示绝对值比较;

long cmp(Int ,long);

//判断是否为 0;

bool zero();

//判定奇偶性;

bool odd();

//右移一个二进制位

Int move();

//赋值;

Int operator = (long);

Int operator = (Int );

Int operator = (char*);

//双目运算;

Int operator +(Int );

Int operator -(Int );

Int operator *(Int );

Int operator /(Int );

Int operator %(Int );

//输入输出;

friend ostream& operator <<(ostream&,Int );

friend istream& operator >>(istream& ,Int& );

private :

long digital[MAX];

long sign;

long len;

//十进制移位

Int shift(long k);

};

Int ::Int(){digital[len=0] = 0, sign = 1;}

long Int::cmp(Int obj, long sel = 1){

if(sel&&obj.sign+sign == 0)return sign - obj.sign; //比较正负号;

long k = len - obj.len;//比较长度;

if(k)return sel? sign*k : k;

for(k = len; k>0 && obj.digital[k] == digital[k]; k--); //比较数位;

return sel? sign * ( digital[k] - obj.digital[k] ): digital[k]-obj.digital[k];

}

bool Int::zero(){ return digital[0]+len ==0; }

bool Int:: odd(){ return digital[0]&1; }

Int Int::move(){

if(digital[0]<=1&&len==0)digital[0] = 0;

else {

int k = len , t, carry=0;

if (digital[len]==1)len--;

while(k>=0){

t = digital[k]&1;

digital[k]= digital[k]>>1;

if(carry)digital[k] += base/2;

k--;

carry = t;

}

if(this->zero())sign = 1;

return *this;

}

///////////////////////////////////////////////////////////////////////////////////

Int Int::operator =(Int obj){

for(len = 0, sign = obj.sign; len <= obj.len; len++)digital[len]=obj.digital[len];

len--;

return *this;

}

Int Int::operator = (long obj){

if(obj<0)sign = -1, obj = -obj;

else sign = 1;

digital[0] = obj%base;

if(obj/=base){

digital[1] = obj%base, len = 1;

if(obj/=base)digital[2] = obj%base, len = 2;

}

else len = 0;

return *this;

}

Int Int::operator = (char *s){

int i, j, l, k;

if(s[0] == '-')l = 1,sign = -1;

else l = 0, sign = 1;

i=l;

while(s[i])i++;

i--;

k=0;

while(i-baselen+1>=l){

for(j=1,digital[k]=0;j<=baselen;j++)

digital[k]=digital[k]*10+s[i-baselen+j]-'0';

i = i-baselen,k++;

}

digital[k] = 0;

while(i>=l)digital[k] = digital[k]*10 + s[l++] - '0';

if(k)len = k-(digital[k]==0);

else len = 0;

用 FinePrint 打印 - 可在 www.fineprint.com.cn 订购

PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.com.cn

评论收藏

内容反馈

版权申诉

刘良运

粉丝: 103

中山大学ACM模板.zip_中山大学ACM模板

中山大学ACM模板

acm_pku_code.zip_Code p_acm pku_acm pku pu_acm.pku_pku acm

acm.zip_acm72.com网_contour c_www.:acm72.com

ACM模板-f_zyj.zip_ACM模板_ACM模板-f_zyj_CSDN积分_acm必备模板_f_zyj ACM

中山大学ACM模板 中山大学 ACM 模板

中山大学《ACM模板》

中山大学ACM模板.rar

一份用于ACM类比赛的算法代码模板.zip

一份用于 ACM 类比赛的算法代码模板.zip

ACM.rar_ACM_ACM Hwang .p_ACM java_pku 1689 rubbery_ppt

上海交大ACM模板.zip_上海交大ACM模板_上海大学

Beijing.zip_2014 ACM_ACM Beijing_acm icpc _beijing_icpc

ACM.zip_www .acm 1024.com

ACM.zip_ACM_poj_poj3187_poj3669

data-structure--acm.zip_ACM 模板

ACM模板and所有算法汇总.zip

《ACM模板》《算法全家桶》《算法竞赛中的初等数论》.zip

ACM.zip_ACM算法_solvea78_算法_算法模板_算法模版

ACM算法模板(吉林大学).zip_ACM算法_acm 吉林大学_数据结构_算法_算法模版

用于 ACM 的算法代码模板.zip

ACM.zip_ACM_Core Servlet_acm教程

ACM-SJTU.rar_ACM_SJTU ACM模板_acm.sjtu_sjtu_sjtu hao yuan acm

ACM.zip_ACM实用小算法

ACM.zip_ACM习题_ACM编程_ACM编程练习_编程 习题集

ACM模板(浙大).zip_浙江大学ACM算法模板

kuangbin的ACM模板（新）.zip_kuangbin ACM算法模板

kuangbin的ACM模板（新）.zip_ACM_indicatesz9_kuangbin 的cf id_kuangbin模板

ACM模板-清华大学.zip

kuangbin的ACM模板（新） .zip_kuangbin的ACM模板（新）

acm.zip_acm.zip

问题记录

电子商务模拟教学实验室建设方案.doc

最新资源

中山大学ACM模板中山大学 ACM 模板

ACM.zip_ACM习题_ACM编程_ACM编程练习_编程习题集