ACM比赛模板资源-CSDN文库

需积分: 10 68 浏览量 2014-05-09 14:49:53 上传评论收藏 216KB PDF 举报

资源详情

资源评论

资源推荐

高精度.......................................................................................................................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

}

(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

剩余24页未读，继续阅读

评论收藏

内容反馈

ltree98

粉丝: 623
资源: 17

ACM比赛模板

评论0

最新资源

ACM比赛模板

评论0

ACM程序竞赛常用模板程序

【ACM比赛模板积累ing】O(n)回文子串（Manacher）算法

ACM比赛模板及资料

最好最全的ACM模板

ACM常用模板

ACM比赛经验分享包括比赛方面的技巧和心得等

ACM模板大全【必备】

ACM比赛必带模板

ACM 比赛 PPT版

中山大学ACM模板

ACM算法模板(吉林大学).pdf

ACM之字符串模板

acm-icpc模板

ACM竞赛模板.pdf

ACMC语言浙大模板

比赛用acm 模板 好用超级

Acm程序设计比赛资料

上海交通大学ACM算法模板

Qt上位机软件串口通讯，视频源码，免费下载

代码随想录算法PDF.rar

张玉生《C语言程序设计》双色版 C语言程序设计理论教材习题参考答案.pdf

cloud compare用户手册（中文+英文）

CRC8/CRC16/CRC32常见几个标准的算法及C语言实现

STM32F4 ADC采样FFT运算测试代码

第十二届蓝桥杯大赛模拟赛（第三期）.pdf

Qt Qss三套样式文件 qss.zip

C++读取excel数据

点云粗配准算法

2021csp-j初赛试题及答案.docx

最新资源

比赛用acm 模板好用超级