没有合适的资源?快使用搜索试试~ 我知道了~
资源推荐
资源详情
资源评论
1
高精度.......................................................................................................................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
2
高精度
(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
3
}
//(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;
4
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
5
}
//(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);
}
6
//////////////////////////////////////////////////////////////////////////
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
7
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++;
8
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
9
}
(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;
10
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页未读,继续阅读
资源评论
- SmileySure2014-03-03模板不错!训练使用
MasterLuo
- 粉丝: 33
- 资源: 16
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功