杭州电子科技大学ACM集训队资料集
杭州电子科技大学ACM集训队资料集
2005.11
Contents
一 Acm比赛注意事项 …………………………………………… 02
二 Numbers和数学公式 ………………………………………… 05
三 数论
……………………………………………………….. 08
四 大数类 ………………………………………………………….. 10
五 计算几何模板 ………………………………………………….. 14
六 经典算法和源码 ……………………………………………….. 27
1128_求矩形面积和_线段树 ………………….. 27
匈牙利算法1525 ……………………………….. 31
最大子段和 ……………………………………... 32
字典树 …………………………………………... 35
1203_kruscal …………………………………... 37
1203_prim ………………………………………. 40
Dijkstra ………………………………………….. 43
Bellman—ford ………………………………….. 45
七 线性规划...............................................................................67
八 高斯消元...............................................................................69
九 图论相关算法........................................................................74
十 三角函数
............................................................................84
1
杭州电子科技大学ACM集训队资料集
Acm比赛注意事项
1. 服务器不支持long double类型,最高支持到double(浮点型)和long long
(长整型),注意 double 比float 更适宜。
2. while语句中的(cin>>M>>N && M!=0 && N!=0)(注意是与还是或)上式也
可改写成(cin>>M>>N && (M || N))
3. 在有些题目,特别是数据比较烦的时候,或者数据精度要求高的时候,可能
精度要求不够。。。
,m=1; for(i=1; i<=k; 4. (引用其他人的)奇怪的事情多着呢.昨天我做2305时候
i++) m *= 2和 m = (1<
>n && n!=-1)
{ ... }
则会出错,而应该
while(cin>>n && n > 0)
{ ... }
这是在zoj_1475中的一个陷阱。
16. 打开文件的语句别写错了,还有文件名小心郁闷死你.多注意点细节,不要频繁提交。
常用的词汇(如max,min)作为变量名在本地机上可以正常编译,但递交上17. 一些
去不一定能编译.更郁闷的是用了一些常用的词汇,编译也通过了,输出也是正确的,但就是wa.解决方案:单词前面加上一个字母,比如lmax,lmin
18. 当提交一直WA时,再仔细读一边题目,而不是一味的想特殊数据。
19. 关于比赛配合问题:1) 拿到题目一般是每人看几道题..也就是扫描一下输入输出什么的,简单讨论一下确定出一道最简单的让一个人去做,机子空着毕竟比较浪费...剩下两个人就可以把题目熟悉起来了...三个人讨论题目的话机子又空着了~~呵呵,一般两个人讨论就行了. 2) 开始地时候三个人分工好每人看几道题,第一时间找到最简单地题,然后一个人开始写程序,另外两个人开始讨论剩下的题目,按照难度/可能通过率/熟悉程度/决定下面做那些题目,然后在纸上写程序,调试. 3) 还有随时注意观察其他队的动态如果有的题目大多数队都通过了而自己还没有做的话,赶快做这个题目。或者是自己一个题目做了很久没有通过,而其他队也没有通过的话,很有可能就是数据有问题或者题目有陷阱,赶快换题目做。比赛不是比谁能做出难题,而是谁能做出更多的题目。
4
杭州电子科技大学ACM集训队资料集
Numbers和数学公式
一. Fibonacci Number
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610 …
二. Lucas Number (特殊的Fibonacci Number )
1, 3, 4, 7, 11, 18, 29, 47, 76, 123 , ...
三. Catalan Number
1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012,
742900, 2674440, 9694845, …
计算公式: C(2n, n) / (n + 1)
应用:
1. 将 n + 2 边形沿弦切割成 n个三角形的不同切割数
2. n +,个数相乘,给每两个元素加上括号的不同方法数
eg: 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. the number of rooted, trivalent trees with n + 1 nodes
eg: n = 2
n = 3
4. the number of paths of length 2n through an n-by-n grid that do not rise above
the main diagonal(对角线).
5
杭州电子科技大学ACM集训队资料集
eg: n = 2
n = 3
5. 结点数为 n 的二叉树的不同构造数.
四. striling number(斯特灵数)
1, 3 , 13, 75, 541, 4683, 47293, 545835, 7087261,
102247563 …
构造法:
n个有标号的球放到m 个无标号的盒子中,要求无一为空,其不同的方案数
记作: s(n,m)
s(0,0) = 0, s(n,k)=0 (n1,m>=1)
五. bell number (和striling number 相似)
1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975,…
定义:
N元集合的所有划分数称为Bell数,
记做Bn,根据第二类Stirling数的意义,我们可以很容易的得到:
Bn=sigma(S(n,k)) (k=1,2…n) // sigma求和
六. 杨式图表的个数
杨式图表(Young Tableau)是一个矩阵,它满足条件:
如果格子(i , j)没有元素,则它右边和上边的相邻格子也一定没有元素。
如果格子(i , j)有元素a[i,j],则它右边和上边的相邻格子要么没有元素,要么比a[i,j]
大。
1 ~ n 所组成的杨式图表的个数由下式给出:
a(1) = 1, a(2) = 2
a(n) = a(n-1) + (n-1) * a(n-2) (n>2)
6
杭州电子科技大学ACM集训队资料集
上图为n = 3 的 杨式图表
七 钩子公式
对于给定形状,不同的杨式图表的个数为n! 除以每个格子的钩子长度加1的积。
其中,钩子长度定义为该格子右边的格子数和它上面的格子数子和。
八. 三角形内切圆半径
s=(a+b+c)/2
九. 三角形外接圆半径
r =(a*b*c)/(4*s) 其中s为三角形面积。
十. 圆內接四边形面积公式
圆內接四边形,其四边边长分別为a,b,c,d 。
令 s=(a+b+c+d) / 2,则四边行面积为
sqrt( (s-a)*(s-b)*(s-c)*(s-d) )
7
杭州电子科技大学ACM集训队资料集
数论模板
int gcd(int a, int b)//最大公约数
{
if(b==0)
return a;
else
return gcd(b, a%b);
}
//扩展的欧拉函数,返回放在x, y中
// d = gcd(a, b) 这里求得的x, y满足 d = ax + by int extend_euclid(int a,int b,int &x,int &y)
{
int t,d;
if (b==0) {x=1;y=0;return a;}
d=extend_euclid(b,a %b,x,y);
t=x;
x=y;
y=t-a/b*y;
return d;
}
//求解同余方程ax=b(mod n)
void linear_solve(int a, int b, int n)
{
int d, x, y;
d = extend_euclid(a, n, x, y);//调用扩展的欧拉函数
if(b%d==0)
{
int e = (x*(b/d))%n;//e等于x0
int ans = n;
for(int i=0; i分析:安全优先或效率优先对效率的影响不大,而使用较高的进制对效率的影响相对明显;
为了使用方便jia,...,jia4,jian,...,jian4,chen,...,chen4基本上都独立实现,因而有较多的冗余代码;
*/
#include
#include
#include
const bool SafeFirst=false; //一般当同时使用了两个或两个以上大数运算时应设置为true;设置安全优先还是效率优先.若效率优先(false),一定要保证传入到函数中的数据都是规格的大数,否则可能出错.效率差常数倍,一般是1倍,要看具体数据,数据越小,而lmax开得越大,差距越大.一般建议用true const int nw=8; //jz中0的个数,nw<=8
const int jz=100000000; //配置进制,只能是10^nw
const int lmax=100000; //大数数组开的大小,(lmax-1)*nw为大数的位数
void jia(const int a[],const int b[],int c[]) //大数a[]加大数b[],结果存在c[]中 {
int i,top;
top=a[0]>b[0]?a[0]:b[0];
if (SafeFirst) //在false情况下,如果传入的c[]非规格的,不能保证返回的c[]规格
{
memset(c,0,sizeof(int)*lmax);
}else
10
杭州电子科技大学ACM集训队资料集
{
c[top+1]=0;
}
for (i=1;i<=top;i++)
{
c[i]+=a[i]+b[i];
if (c[i]>=jz)
{
c[i]-=jz;
c[i+1]++;
}
}
if (c[top+1]>0)
c[0]=top+1;
else
c[0]=top;
}
void jia2(int a[],const int b[]) //对大数a[]累加另一大数b[] {
int i,top;
if (SafeFirst)
memset(a+a[0]+1,0,sizeof(int)*(lmax-a[0]-1));
top=a[0]>b[0]?a[0]:b[0];
for (i=1;i<=b[0];i++)
{
a[i]+=b[i];
if (a[i]>=jz)
{
a[i]-=jz;
a[i+1]++;
}
}
if (a[top+1]>0)
a[0]=top+1;
else
a[0]=top;
}
void jia3(const int a[],const int b,int c[]) //大数a[]加上小数b,存在c[]中
{
int i;
unsigned int t;
if (SafeFirst) memset(c,0,sizeof(int)*lmax);
memcpy(c,a,sizeof(int)*(a[0]+1));
t=c[1]+b;
11
杭州电子科技大学ACM集训队资料集
c[1]=t%jz;
i=1;
while (t>=jz)
{
t/=jz;
t+=c[i+1];
c[i+1]=t%jz;
i++;
}
if (c[0]=jz)
{
t/=jz;
t+=a[i+1];
a[i+1]=t%jz;
i++;
}
if (a[0]=b[]
{
int i,jw;
if (SafeFirst) //若为false,不能保证传出的c[]是规格的
{
memset(c,0,sizeof(int)*lmax);
}
jw=0;
for (i=1;i<=b[0];i++)
{
if (a[i]-jw>=b[i])
12
杭州电子科技大学ACM集训队资料集
{
c[i]=a[i]-jw-b[i];
jw=0;
}
else
{
c[i]=a[i]+jz-jw-b[i];
jw=1;
}
}
for (i=b[0]+1;i<=a[0];i++)
{
if (a[i]-jw>=0)
{
c[i]=a[i]-jw;
jw=0;
}else
{
c[i]=a[i]+jz-jw;
jw=1;
}
}
i=a[0];
while (c[i]==0) i--;
if (i>0) c[0]=i;
else
c[0]=1;
}
void jian2(int a[],const int b[]) //a[]-=b[];a[]>b[]
{
int i;
if (SafeFirst) memset(&a[a[0]+1],0,sizeof(int)*(lmax-a[0]-1));
for (i=1;i<=b[0];i++)
{
a[i]-=b[i];
if (a[i]<0)
{
a[i]+=jz;
a[i+1]--;
}
}
while (a[i]<0 && i0) a[0]=i;
else a[0]=1;
}
void jian3(const int a[],const int b,int c[]) //a[]>=b
{
int i;
memcpy(c,a,sizeof(int)*(a[0]+1));
if (SafeFirst) memset(&c[c[0]+1],0,sizeof(int)*(lmax-a[0]-1));
c[1]-=b;
i=1;
while (c[i]<0)
{
c[i+1]+=c[i]/jz;
c[i]%=jz;
if (c[i]<0)
{
c[i+1]--;
c[i]+=jz;
}
i++;
}
i=c[0];
while (c[i]==0) i--;
if (i>0) c[0]=i;
else
c[0]=1;
}
void jian4(int a[],const int b)
{
int i;
a[1]-=b;
i=1;
while (a[i]<0)
{
a[i+1]+=a[i]/jz;
a[i]%=jz;
if (a[i]<0)
{
14
杭州电子科技大学ACM集训队资料集
a[i+1]--;
a[i]+=jz;
}
i++;
}
i=a[0];
while (a[i]==0) i--;
if (i>0) a[0]=i;
else
a[0]=1;
}
/********************************************************************
***************************/
inline void chen(const int a[],const int b[],int c[]) //大数乘大数 {
__int64 t=0;
int up=0,i,j,k;
if (SafeFirst)
memset(c,0,sizeof(int)*lmax);
for (i=1;i<=a[0];i++)
{
up=0;
for (j=1;j<=b[0];j++)
{
k=i+j-1;
t=(__int64)a[i]*b[j]+up;
c[k]+=t%jz;
up=t/jz;
while (c[k]>=jz)
{
c[k+1]++;
c[k]-=jz;
}
}
if (up>0)
{
c[i+b[0]]+=up;
}
}
i=a[0]+b[0];
while (c[i]==0) i--;
if (i>0) c[0]=i;
15
杭州电子科技大学ACM集训队资料集
else
c[0]=1;
}
inline void chen2(const int a[],const int b,int c[]) //大数乘小数{
__int64 t;
int up=0,i;
if (SafeFirst)
memset(c,0,sizeof(int)*lmax);
for (i=1;i<=a[0];i++)
{
t=(__int64)a[i]*b+up;
c[i]=t%jz;
up=t/jz;
}
c[i]+=up;
while (c[i]>=jz)
{
c[i+1]=c[i]/jz;
c[i]%=jz;
i++;
}
if (c[i]==0) i--;
if (i>0) c[0]=i;
else
c[0]=1;
}
/********************************************************************
***************************/ void chghtl(const int a[],int b[])
{
int t,i,j,p=0;
memset(b,0,sizeof(int)*nw*lmax);
for (i=1;i<=a[0];i++)
{
t=a[i];
for (j=1;j<=nw;j++)
{
p++;
b[p]=t%10;
t/=10;
}
16
杭州电子科技大学ACM集训队资料集
}
while (b[p]==0) p--;
if (p>0) b[0]=p;
else b[0]=1;
}
void chglth(const int a[],int b[]) {
int i,j,top;
memset(b,0,sizeof(int)*lmax);
for (i=1;i<=a[0];i+=nw)
{
b[0]++;
top=i+nw-1;
if (top>a[0]) top=a[0];
for (j=top;j>=i;j--)
{
b[b[0]]=b[b[0]]*10+a[j];
}
}
}
void chu(int a[],const int b[],int c[]) //c[]=a[]%b[],a[]/=b[];a[]>=0 && b[]>0;
{
int *a1=new int[nw*lmax],*b1=new int[nw*lmax],*c1=new
int[nw*lmax],i,j,lcount;
bool ok;
memset(a1,0,sizeof(int)*nw*lmax);
memset(b1,0,sizeof(int)*nw*lmax);
memset(c1,0,sizeof(int)*nw*lmax);
chghtl(a,a1);
chghtl(b,b1);
for (i=a1[0];i>=b1[0];i--)
{
if (i=1;j--)
if (a1[i+j-b1[0]]b1[j])
17
杭州电子科技大学ACM集训队资料集
{
ok=true;
break;
}
lcount=0;
while (ok)
{
for (j=1;j<=b1[0];j++)
{
a1[i+j-b1[0]]-=b1[j];
if (a1[i+j-b1[0]]<0)
{
a1[i+j-b1[0]]+=10;
a1[i+j-b1[0]+1]--;
}
}
lcount++;
) for (j=b1[0];j>=1;j--
if (a1[i+j-b1[0]]b1[j])
{
ok=true;
break;
}
}
c1[i-b1[0]+1]=lcount;
}
i=a1[0];
while (c1[i]==0) i--;
if (i>0) c1[0]=i;
else
c1[0]=1;
i=b1[0];
while (a1[i]==0) i--;
if (i>0) a1[0]=i;
else
a1[0]=1;
for (i=1;i<=a1[0];i++)
if (a1[i]>9)
{
a1[i+1]+=a1[i]/10;
18
杭州电子科技大学ACM集训队资料集
a1[i]%=10;
}
while (a1[i]>9)
{
a1[i+1]=a1[i]/10;
a1[i]%=10;
i++;
}
if (a1[i]==0) i--;
if (i>0) a1[0]=i;
else
a1[0]=1;
chglth(a1,c);
chglth(c1,a);
delete []a1;
delete []b1;
delete []c1;
}
void chu2(const int a[],const int b[],int c[], int d[]) //c[]=a[]/b[];d[]=a[]%b[]
{
memcpy(c,a,sizeof(int)*lmax);
chu(c,b,d);
}
void chu3(int a[],const int b,int c[]) //c[]=a[]%b; a[]/=b;
{
__int64 t;
int i;
memcpy(c,a,sizeof(int)*lmax);
for (i=c[0];i>=1;i--)
{
if (i0) a[0]=i;
else
a[0]=1;
i=1;
while (c[i]>=jz)
{
c[i+1]=c[i]/jz;
c[i]%=jz;
i++;
}
if (c[i]==0) i--;
if (i>0) c[0]=i;
else
c[0]=1;
}
void chu4(const int a[],const int b,int c[],int d[]) //c[]=a[]/b; d[]=a[]%b;
{
memcpy(c,a,sizeof(int)*lmax);
chu3(c,b,d);
}
/********************************************************************
***************************/
void chgstn(const char s[],int a[]) //字符串转大数 {
int i,t1,l,j,t;
memset(a,0,sizeof(a));
l=strlen(s);
for (i=l-1;i>=0;i-=nw)
{
t=0;
t1=i-nw+1;
if (t1<0) t1=0;
for (j=t1;j<=i;j++)
t=t*10+s[j]-'0';
a[0]++;
a[a[0]]=t;
}
}
void output(const int c[]) //大数输出
{
int i,w,j,n;
20
杭州电子科技大学ACM集训队资料集
printf("%d",c[c[0]]);
for (i=c[0]-1;i>0;i--)
{
n=c[i];
w=0;
while (n>0)
{
w++;
n/=10;
}
for (j=0;j0) printf("%d",c[i]);
}
printf("\n");
}
void jiecheng(int n=-1) {
int begin,i,cost,*t=new int[lmax],*a=new int[lmax];
memset(t,0,sizeof(t)*lmax);
memset(a,0,sizeof(a)*lmax);
if (n<0)
scanf("%d",&n);
begin=time(0);
a[0]=1;
a[1]=1;
for (i=2;i<=n;i++)
{
for (int j=1;j<=a[0];j++)
t[j]=a[j];
t[0]=a[0];
chen2(t,i,a);
}
cost=time(0)-begin;
output(a);
printf("Cost time : %d\n",cost);
delete []t;
delete []a;
}
void chenfang(const int a[],int n,int c[]) //求a[]的n次方 {
int i,*b=new int[lmax];
memcpy(b,a,sizeof(int)*lmax);
memcpy(c,a,sizeof(int)*lmax);
21
杭州电子科技大学ACM集训队资料集
for (i=2;i<=n;i++)
{
chen(b,a,c);
memcpy(b,c,sizeof(int)*lmax);
}
delete []b;
}
void examinechenfang() //检测chenfang()的正确性 {
int a[lmax]={0},b[lmax]={0},n;
char s[nw*lmax];
while (scanf("%s",s)!=EOF)
{
scanf("%d",&n);
chgstn(s,a);
chenfang(a,n,b);
output(b);
}
}
void examinejia()
{
int a[lmax]={0},b[lmax]={0},c[lmax]={0},n,i;
char s[nw*lmax];
while (scanf("%s",s)!=EOF)
{
scanf("%d",&n);
chgstn(s,a);
memset(c,0,sizeof(c));
for (i=1;i<=n;i++)
{
memcpy(b,c,sizeof(int)*lmax);
jia(a,b,c);
}
output(c);
}
}
void examinejia2()
{
int a[lmax]={0},c[lmax]={0},n,i;
char s[nw*lmax];
while (scanf("%s",s)!=EOF)
{
scanf("%d",&n);
chgstn(s,a);
22
杭州电子科技大学ACM集训队资料集
memset(c,0,sizeof(c));
for (i=1;i<=n;i++)
{
jia2(c,a);
}
output(c);
}
}
void examinejia3()
{
int a[lmax],b,c[lmax],n,i;
char s[lmax*nw];
while (scanf("%s%d%d",s,&b,&n))
{
// memset(c,0,sizeof(c));
chgstn(s,a);
for (i=1;i<=n;i++)
{
jia3(a,b,c);
memcpy(a,c,sizeof(int)*lmax);
}
output(c);
}
}
void examinejia4()
{
int a[lmax],b,n,i;
char s[lmax*nw];
while (scanf("%s%d%d",s,&b,&n))
{
chgstn(s,a);
for (i=1;i<=n;i++)
{
jia4(a,b);
}
output(a);
}
}
void examinejian()
{
int a[lmax]={0},b[lmax]={0},c[lmax]={0},n,i;
char s[nw*lmax];
while (scanf("%s",s)!=EOF)
{
23
杭州电子科技大学ACM集训队资料集
scanf("%d",&n);
chgstn(s,a);
memset(c,0,sizeof(c));
for (i=1;i<=n;i++)
{
memcpy(b,c,sizeof(int)*lmax);
jia(a,b,c);
}
output(c);
for (i=1;i<=n;i++)
{
memcpy(b,c,sizeof(c));
jian(b,a,c);
}
output(c);
}
}
void examinejian2()
{
int a[lmax]={0},b[lmax]={0},c[lmax]={0},n,i;
char s[nw*lmax];
while (scanf("%s",s)!=EOF)
{
scanf("%d",&n);
chgstn(s,a);
memset(c,0,sizeof(c));
for (i=1;i<=n;i++)
{
memcpy(b,c,sizeof(int)*lmax);
jia(a,b,c);
}
output(c);
for (i=1;i<=n;i++)
{
jian2(c,a);
}
output(c);
}
}
void examinejian3()
{
int a[lmax],b,c[lmax],n,i;
char s[lmax*nw];
while (scanf("%s%d%d",s,&b,&n))
24
杭州电子科技大学ACM集训队资料集
{
// memset(c,0,sizeof(c));
chgstn(s,a);
for (i=1;i<=n;i++)
{
jia3(a,b,c);
memcpy(a,c,sizeof(int)*lmax);
}
output(a);
for (i=1;i<=n;i++)
{
jian3(a,b,c);
memcpy(a,c,sizeof(int)*lmax);
}
output(a);
}
}
void examinejian4() {
int a[lmax],b,n,i;
char s[lmax*nw];
while (scanf("%s%d%d",s,&b,&n))
{
chgstn(s,a);
for (i=1;i<=n;i++)
{
jia4(a,b);
}
output(a);
for (i=1;i<=n;i++)
{
jian4(a,b);
}
output(a);
}
}
void examinechu()
{
int a[lmax],b[lmax],c[lmax];
char s[lmax*nw];
while (scanf("%s",s))
{
chgstn(s,a);
scanf("%s",s);
25
杭州电子科技大学ACM集训队资料集
chgstn(s,b);
chu(a,b,c);
output(a);
output(c);
}
}
void examinechu2() {
int a[lmax],b[lmax],c[lmax],d[lmax];
char s[lmax*nw];
while (scanf("%s",s)!=EOF)
{
chgstn(s,a);
scanf("%s",s);
chgstn(s,b);
chu2(a,b,c,d);
output(c);
output(d);
}
}
void examinechu4() {
int a[lmax],c[lmax],d[lmax],b;
char s[nw*lmax];
while (scanf("%s%d",s,&b)!=EOF)
{
chgstn(s,a);
chu4(a,b,c,d);
output(c);
output(d);
}
}
int main()
{
// 以下用来检测各函数的正确性
jiecheng();
// examinechenfang(); // examinejia(); // examinejia2(); // examinejia3(); // examinejia4(); // examinejian(); // examinejian2(); // examinejian3();
26
杭州电子科技大学ACM集训队资料集 // examinejian4();
// examinechu();
// examinechu2();
// examinechu4();
return 0;
}
取模.cpp
int div(char *A,int B)
{
int I;
int C = 0;
int Alen=strlen(A);
for (I = 0; I
#include
#include
#include
#include
#include
using namespace std;
typedef double TYPE;
#define Abs(x) (((x)>0)?(x):(-(x))) #define Sgn(x) (((x)<0)?(-1):(1)) #define Max(a,b) (((a)>(b))?(a):(b)) #define Min(a,b) (((a)<(b))?(a):(b))
#define Epsilon 1e-10
#define Infinity 1e+10
#define Pi 3.14159265358979323846
TYPE Deg2Rad(TYPE deg)
{
return (deg * Pi / 180.0); }
TYPE Rad2Deg(TYPE rad)
{
return (rad * 180.0 / Pi); }
28
杭州电子科技大学ACM集训队资料集 TYPE Sin(TYPE deg)
{
return sin(Deg2Rad(deg));
}
TYPE Cos(TYPE deg)
{
return cos(Deg2Rad(deg));
}
TYPE ArcSin(TYPE val)
{
return Rad2Deg(asin(val));
}
TYPE ArcCos(TYPE val)
{
return Rad2Deg(acos(val));
}
TYPE Sqrt(TYPE val)
{
return sqrt(val);
}
struct POINT
{
TYPE x;
TYPE y;
TYPE z;
POINT() : x(0), y(0), z(0) {};
POINT(TYPE _x_, TYPE _y_, TYPE _z_ = 0) : x(_x_), y(_y_), z(_z_) {};
};
// cross product of (o->a) and (o->b) // 叉乘
TYPE Cross(const POINT & a, const POINT & b, const POINT & o) {
return (a.x - o.x) * (b.y - o.y) - (b.x - o.x) * (a.y - o.y);
}
// planar points' distance // 两个点的距离
TYPE Distance(const POINT & a, const POINT & b)
29
杭州电子科技大学ACM集训队资料集 {
return Sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) +
(a.z - b.z) * (a.z - b.z)); }
struct LINE
{
POINT a;
POINT b;
LINE() {};
LINE(POINT _a_, POINT _b_) : a(_a_), b(_b_) {};
};
// 返回直线 Ax + By + C =0 的系数
void Coefficient(const LINE & L, TYPE & A, TYPE & B, TYPE & C)
{
A = L.b.y - L.a.y;
B = L.a.x - L.b.x;
C = L.b.x * L.a.y - L.a.x * L.b.y; }
void Coefficient(const POINT & p,const TYPE a,TYPE & A,TYPE & B,TYPE & C)
{
A = Cos(a);
B = Sin(a);
C = - (p.y * B + p.x * A); }
// 线段
struct SEG
{
POINT a;
POINT b;
SEG() {};
SEG(POINT _a_, POINT _b_):a(_a_),b(_b_) {};
};
// 圆
struct CIRCLE
{
TYPE x;
TYPE y;
TYPE r;
CIRCLE() {}
30
杭州电子科技大学ACM集训队资料集
CIRCLE(TYPE _x_, TYPE _y_, TYPE _r_) : x(_x_), y(_y_), r(_r_) {}
};
POINT Center(const CIRCLE & circle)
{
return POINT(circle.x, circle.y);
}
TYPE Area(const CIRCLE & circle)
{
return Pi * circle.r * circle.r;
}
//两个圆的公共面积
TYPE CommonArea(const CIRCLE & A, const CIRCLE & B)
{
TYPE area = 0.0;
const CIRCLE & M = (A.r > B.r) ? A : B;
const CIRCLE & N = (A.r > B.r) ? B : A;
TYPE D = Distance(Center(M), Center(N));
if ((D < M.r + N.r) && (D > M.r - N.r))
{
TYPE cosM = (M.r * M.r + D * D - N.r * N.r) / (2.0 * M.r * D);
TYPE cosN = (N.r * N.r + D * D - M.r * M.r) / (2.0 * N.r * D);
TYPE alpha = 2.0 * ArcCos(cosM);
TYPE beta = 2.0 * ArcCos(cosN);
TYPE TM = 0.5 * M.r * M.r * Sin(alpha);
TYPE TN = 0.5 * N.r * N.r * Sin(beta);
TYPE FM = (alpha / 360.0) * Area(M);
TYPE FN = (beta / 360.0) * Area(N);
area = FM + FN - TM - TN;
}
else if (D <= M.r - N.r)
{
area = Area(N);
}
return area;
31
杭州电子科技大学ACM集训队资料集 }
// 矩形
//矩形的线段
// 2
// --------------- b
// | |
// 3 | | 1 // a ---------------
// 0
struct RECT
{
POINT a; // 左下点
POINT b; // 右上点
RECT() {};
RECT(const POINT & _a_, const POINT & _b_)
{
a = _a_;
b = _b_;
}
};
//根据下标返回多边形的边
SEG Edge(const RECT & rect, int idx)
{
SEG edge;
while (idx < 0) idx += 4;
switch (idx % 4)
{
case 0:
edge.a = rect.a;
edge.b = POINT(rect.b.x, rect.a.y);
break;
case 1:
edge.a = POINT(rect.b.x, rect.a.y);
edge.b = rect.b;
break;
case 2:
edge.a = rect.b;
edge.b = POINT(rect.a.x, rect.b.y);
break;
case 3:
edge.a = POINT(rect.a.x, rect.b.y);
32
杭州电子科技大学ACM集训队资料集
edge.b = rect.a;
break;
default:
break;
}
return edge;
}
TYPE Area(const RECT & rect)
{
return (rect.b.x - rect.a.x) * (rect.b.y - rect.a.y);
}
// 两个矩形的公共面积
TYPE CommonArea(const RECT & A, const RECT & B) {
TYPE area = 0.0;
POINT LL(Max(A.a.x, B.a.x), Max(A.a.y, B.a.y));
POINT UR(Min(A.b.x, B.b.x), Min(A.b.y, B.b.y));
if ((LL.x <= UR.x) && (LL.y <= UR.y))
{
area = Area(RECT(LL, UR));
}
return area;
}
// 多边形 ,逆时针或顺时针给出x,y
struct POLY
{
int n; //n个点
TYPE * x; //x,y为点的指针,首尾必须重合
TYPE * y;
POLY() : n(0), x(NULL), y(NULL) {};
POLY(int _n_, const TYPE * _x_, const TYPE * _y_)
{
n = _n_;
x = new TYPE[n + 1];
memcpy(x, _x_, n*sizeof(TYPE));
x[n] = _x_[0];
33
杭州电子科技大学ACM集训队资料集
y = new TYPE[n + 1];
memcpy(y, _y_, n*sizeof(TYPE));
y[n] = _y_[0];
}
};
//多边形顶点
POINT Vertex(const POLY & poly, int idx)
{
idx %= poly.n;
return POINT(poly.x[idx], poly.y[idx]); }
//多边形的边
SEG Edge(const POLY & poly, int idx)
{
idx %= poly.n;
return SEG(POINT(poly.x[idx], poly.y[idx]),
POINT(poly.x[idx + 1], poly.y[idx + 1]));
}
//多边形的周长
TYPE Perimeter(const POLY & poly)
{
TYPE p = 0.0;
for (int i = 0; i < poly.n; i++)
p = p + Distance(Vertex(poly, i), Vertex(poly, i + 1));
return p;
}
bool IsEqual(TYPE a, TYPE b)
{
return (Abs(a - b) < Epsilon); }
bool IsEqual(const POINT & a, const POINT & b) {
return (IsEqual(a.x, b.x) && IsEqual(a.y, b.y));
}
bool IsEqual(const LINE & A, const LINE & B)
{
TYPE A1, B1, C1;
34
杭州电子科技大学ACM集训队资料集
TYPE A2, B2, C2;
Coefficient(A, A1, B1, C1);
Coefficient(B, A2, B2, C2);
return IsEqual(A1 * B2, A2 * B1) &&
IsEqual(A1 * C2, A2 * C1) &&
IsEqual(B1 * C2, B2 * C1);
}
// 判断点是否在线段上
bool IsOnSeg(const SEG & seg, const POINT & p)
{
return (IsEqual(p, seg.a) || IsEqual(p, seg.b)) ||
(((p.x - seg.a.x) * (p.x - seg.b.x) < 0 ||
(p.y - seg.a.y) * (p.y - seg.b.y) < 0) &&
(IsEqual(Cross(seg.b, p, seg.a), 0))); }
//判断两条线断是否相交,端点重合算相交
bool IsIntersect(const SEG & u, const SEG & v)
{
return (Cross(v.a, u.b, u.a) * Cross(u.b, v.b, u.a) >= 0) &&
(Cross(u.a, v.b, v.a) * Cross(v.b, u.b, v.a) >= 0) &&
(Max(u.a.x, u.b.x) >= Min(v.a.x, v.b.x)) &&
(Max(v.a.x, v.b.x) >= Min(u.a.x, u.b.x)) &&
(Max(u.a.y, u.b.y) >= Min(v.a.y, v.b.y)) &&
(Max(v.a.y, v.b.y) >= Min(u.a.y, u.b.y)); }
//判断两条线断是否平行
bool IsParallel(const LINE & A, const LINE & B)
{
TYPE A1, B1, C1;
TYPE A2, B2, C2;
Coefficient(A, A1, B1, C1);
Coefficient(B, A2, B2, C2);
return (A1 * B2 == A2 * B1) &&
((A1 * C2 != A2 * C1) || (B1 * C2 != B2 * C1)); }
//判断两条直线断是否相交
bool IsIntersect(const LINE & A, const LINE & B)
{
35
杭州电子科技大学ACM集训队资料集
return !IsParallel(A, B);
}
//直线相交的交点
POINT Intersection(const LINE & A, const LINE & B)
{
TYPE A1, B1, C1;
TYPE A2, B2, C2;
Coefficient(A, A1, B1, C1);
Coefficient(B, A2, B2, C2);
POINT I(0, 0);
I.x = - (B2 * C1 - B1 * C2) / (A1 * B2 - A2 * B1);
I.y = (A2 * C1 - A1 * C2) / (A1 * B2 - A2 * B1);
return I;
}
bool IsInCircle(const CIRCLE & circle, const RECT & rect)
{
return (circle.x - circle.r >= rect.a.x) &&
(circle.x + circle.r <= rect.b.x) &&
(circle.y - circle.r >= rect.a.y) &&
(circle.y + circle.r <= rect.b.y); }
//判断是否简单多边形
bool IsSimple(const POLY & poly)
{
if (poly.n < 3)
return false;
SEG L1, L2;
for (int i = 0; i < poly.n - 1; i++)
{
L1 = Edge(poly, i);
for (int j = i + 1; j < poly.n; j++)
{
L2 = Edge(poly, j);
if (j == i + 1)
{
if (IsOnSeg(L1, L2.b) || IsOnSeg(L2, L1.a))
return false;
36
杭州电子科技大学ACM集训队资料集
}
else if (j == poly.n - i - 1)
{
if (IsOnSeg(L1, L2.a) || IsOnSeg(L2, L1.b))
return false;
}
else
{
if (IsIntersect(L1, L2))
return false;
}
} // for j
} // for i
return true;
}
//求多边形面积
TYPE Area(const POLY & poly)
{
if (poly.n < 3) return TYPE(0);
double s = poly.y[0] * (poly.x[poly.n - 1] - poly.x[1]);
for (int i = 1; i < poly.n; i++)
{
s += poly.y[i] * (poly.x[i - 1] - poly.x[(i + 1) % poly.n]);
}
return s/2;
}
//判断是否在多边形上
bool IsOnPoly(const POLY & poly, const POINT & p) {
for (int i = 0; i < poly.n; i++)
{
if (IsOnSeg(Edge(poly, i), p))
{
return true;
}
}
return false;
}
//判断是否在多边形内部
bool IsInPoly(const POLY & poly, const POINT & p) {
37
杭州电子科技大学ACM集训队资料集
SEG L(p, POINT(Infinity, p.y));
int count = 0;
for (int i = 0; i < poly.n; i++)
{
SEG S = Edge(poly, i);
if (IsOnSeg(S, p))
{
return false; //如果想让 在poly上则返回 true,
//则改为true
}
if (!IsEqual(S.a.y, S.b.y))
{
POINT & q = (S.a.y > S.b.y)?(S.a):(S.b);
if (IsOnSeg(L, q))
{
++count;
}
else if (!IsOnSeg(L, S.a) && !IsOnSeg(L, S.b) && IsIntersect(S, L))
{
++count;
}
}
}
return (count % 2 != 0);
}
// 点阵的凸包,返回一个多边形
POLY ConvexHull(const POINT * set, int n) // 不适用于点少于三个的情况 {
POINT * points = new POINT[n];
memcpy(points, set, n * sizeof(POINT));
TYPE * X = new TYPE[n];
TYPE * Y = new TYPE[n];
int i, j, k = 0, top = 2;
for(i = 1; i < n; i++)
{
if ((points[i].y < points[k].y) ||
((points[i].y == points[k].y) &&
(points[i].x < points[k].x)))
{
k = i;
38
杭州电子科技大学ACM集训队资料集
}
}
std::swap(points[0], points[k]);
for (i = 1; i < n - 1; i++)
{
k = i;
for (j = i + 1; j < n; j++)
{
if ((Cross(points[j], points[k], points[0]) > 0) ||
((Cross(points[j], points[k], points[0]) == 0) &&
(Distance(points[0], points[j]) < Distance(points[0], points[k]))))
{
k = j;
}
}
std::swap(points[i], points[k]);
}
X[0] = points[0].x; Y[0] = points[0].y;
X[1] = points[1].x; Y[1] = points[1].y;
X[2] = points[2].x; Y[2] = points[2].y;
for (i = 3; i < n; i++)
{
while (Cross(points[i], POINT(X[top], Y[top]),
POINT(X[top - 1], Y[top - 1])) >= 0)
{
top--;
}
++top;
X[top] = points[i].x;
Y[top] = points[i].y;
}
delete [] points;
POLY poly(++top, X, Y);
delete [] X;
delete [] Y;
39
杭州电子科技大学ACM集训队资料集
return poly;
}
从6边长求4面体体积啊
Cayley-Menger Determinant 3 维时的情形(2维相当于海伦公式).
| 0 1 1 1 1 |
| 1 0 D12 D13 D14 |
288*V^2 = | 1 D21 0 D23 D24 |
| 1 D31 D32 0 D34 |
| 1 D41 D42 D43 0 |
其中
V 是四面体的体积.
Dij 是连结顶点i和顶点j的边长的平方(记得是平方).
求球面上两点最短距离模板.cpp
/计算圆心角lat表示纬度,-90<=w<=90,lng表示经度
//返回两点所在大圆劣弧对应圆心角,0<=angle<=pi
double angle(double lng1,double lat1,double lng2,double lat2)
{
double dlng=fabs(lng1-lng2)*pi/180;
while (dlng>=pi+pi)
dlng-=pi+pi;
if (dlng>pi)
dlng=pi+pi-dlng;
lat1*=pi/180,lat2*=pi/180;
return acos(cos(lat1)*cos(lat2)*cos(dlng)+sin(lat1)*sin(lat2));
}
//计算距离,r为球半径
double line_dist(double r,double lng1,double lat1,double lng2,double lat2)
{
double dlng=fabs(lng1-lng2)*pi/180;
while (dlng>=pi+pi)
dlng-=pi+pi;
if (dlng>pi)
dlng=pi+pi-dlng;
lat1*=pi/180,lat2*=pi/180;
return r*sqrt(2-2*(cos(lat1)*cos(lat2)*cos(dlng)+sin(lat1)*sin(lat2)));
}
//计算球面距离,r为球半径
inline double sphere_dist(double r,double lng1,double lat1,double lng2,double lat2)
40
杭州电子科技大学ACM集训队资料集
{
return r*angle(lng1,lat1,lng2,lat2);
}
射线与三角形所在平面的交点.cpp
//v0,dir为点和方向。p1,p2,p3为三角形
//nor为交点
//最后5行判断交点是否在三角形内
int occluded(double v0[],double dir[],double p1[],double p2[],double p3[])
{
double v1[]={p2[0]-p1[0],p2[1]-p1[1],p2[2]-p1[2]};
double v2[]={p3[0]-p2[0],p3[1]-p2[1],p3[2]-p2[2]};
double nor[3];
double a,b;
double area1,area2,area3,area4;
crossproduct(nor,v1,v2);
b=(v0[0]-p1[0])*nor[0]+(v0[1]-p1[1])*nor[1]+(v0[2]-p1[2])*nor[2];
a=dir[0]*nor[0]+dir[1]*nor[1]+dir[2]*nor[2];
if (fabs(a)area4+inf) return 0;
return 1;
}
41
杭州电子科技大学ACM集训队资料集
以知三点求圆心坐标.cpp
double GetRadiusBy3Points( double x1 , double y1 ,
double x2 , double y2 ,
double x3 , double y3 ,
double &x , double &y ) {
//由 ( x - x1 )^2 + ( y - y1 )^2 = ( x - x2 )^2 + ( y - y2 )^2 得
//2*( x2 - x1 )*x + 2*( y2 - y1 )*y = x2^2 - x1^2 + y2^2 - y1^2
//同理得
//2*( x3 - x2 )*x + 2*( y3 - y2 )*y = x3^2 - x2^2 + y3^2 - y2^2
//由行列式解方程得 x , y
double a11 , a12 , a21 , a22 , b1 , b2 ;
double d , d1 , d2 ;
a11 = 2 * ( x3 - x2 ) ;
a12 = 2 * ( y3 - y2 ) ;
a21 = 2 * ( x2 - x1 ) ;
a22 = 2 * ( y2 - y1 ) ;
b1 = x3*x3 - x2*x2 + y3*y3 - y2*y2 ;
b2 = x2*x2 - x1*x1 + y2*y2 - y1*y1 ;
d = a11*a22 - a12*a21 ;
d1 = b1*a22 - a12*b2 ;
d2 = a11*b2 - b1*a21 ;
// x , y 是圆心坐标
x = d1 / d ;
y = d2 / d ;
return (x1 - x)*(x1 - x) + (y1 - y)*(y1 - y) ; }
42
杭州电子科技大学ACM集训队资料集
点到直线距离
#include
#include
using namespace std;
double RtnDistance(double x1,double y1,double x2,double y2,double px,double py)
{
const double minjd=0.001;
double x,y,d,k,minx,maxx,miny,maxy;
if (fabs(x1-x2)x2?x2:x1;
miny=y1>y2?y2:y1;
maxx=x1>x2?x1:x2;
maxy=y1>y2?y1:y2;
if ((maxx-x>-minjd && x-minx>-minjd)&&(maxy-y>-minjd && y-miny>-minjd))
return d;
d=sqrt((x1 - px) * (x1 - px) + (y1 - py) * (y1 - py));
if (sqrt((x2 - px) * (x2 - px) + (y2 - py) * (y2 - py))>x1>>y1>>x2>>y2>>px>>py)
cout<建立一个从double到int的映射,从而可以处理实数。
******************************************************************************/
#include
#include 为:
// | a00 a01 ... a0n-1 1 0 ... 0 | // | a10 a11 ... a1n-1 0 1 ... 0 | // | ... ... ... ... ......... | // | am-10 am-11... am-1n-1 0 0 ... 1 | // b : 双精度实型一维数组(长度为m。存放不等式约束条件的右端项 b0~bm-1 // c : 双精度实型一维数组,长度为m+n。存放目标函数中的系数,其中后m个分量为0, 即存放次序为:
// c = (c0, c1, ..., cn-1, 0, ..., 0); // m : 整型变量。不等式约束条件的个数。
// n : 整型变量。变量个数
// x : 双精度实型1维数组,长度为m +n.其中前n个分量返回目标函数f的极小值的n个坐标(即最优解),第n+1个分量[即x(n))返回目标函数f的极小值,其余为本函数的工作单元。 int jlplq(double a[], double b[], double c[], int m, int n, double x[])
{
int i,mn,k,j,l,*js;
double s,z,dd,y,*p,*d;
js=(int *)malloc(m*sizeof(int));
p=(double *)malloc(m*m*sizeof(double));
d=(double *)malloc(m*(m+n)*sizeof(double));
for (i=0; i<=m-1; i++) js[i]=n+i;
mn=m+n; s=0.0;
while (1==1) {
for (i=0; i<=m-1; i++)
for (j=0; j<=m-1; j++)
p[i*m+j]=a[i*mn+js[j]];
l=brinv(p,m);
if (l==0)
{ x[n]=s; free(js); free(p);
free(d); return(l);
}
brmul(p,a,m,m,mn,d);
for (i=0; i<=mn-1; i++) x[i]=0.0;
for (i=0; i<=m-1; i++) {
s=0.0;
for (j=0; j<=m-1; j++)
s=s+p[i*m+j]*b[j];
x[js[i]]=s;
}
67
杭州电子科技大学ACM集训队资料集
k=-1; dd=1.0e-35;
for (j=0; j<=mn-1; j++) {
z=0.0;
for (i=0; i<=m-1; i++)
z=z+c[js[i]]*d[i*mn+j];
z=z-c[j];
if (z>dd) { dd=z; k=j;}
}
if (k==-1) {
s=0.0;
for (j=0; j<=n-1; j++)
s=s+c[j]*x[j];
x[n]=s; free(js); free(p);
free(d); return(1);
}
j=-1;
dd=1.0e+20;
for (i=0; i<=m-1; i++)
if (d[i*mn+k]>=1.0e-20) {
y=x[js[i]]/d[i*mn+k];
if (y
using namespace std;
const int num = 100;
double matrix[num][num + 1]; //系数矩阵,从0开始
double ans[num]; //结果数组
void exchange_col(int p1,int p2,int n) //交换p1行和p2行的所有数据
{
double t;
int i;
for(i = 0 ; i <= n ; i++)
t = matrix[p1][i],matrix[p1][i] = matrix[p2][i],matrix[p2][i] = t;
}
bool gauss(int n) //求解系数矩阵为n的线性方程组
69
杭州电子科技大学ACM集训队资料集 {
int i,j,k;
int p;
double r;
for(i = 0 ; i < n - 1 ; i++){
p = i;
for(j = i + 1 ; j < n ; j++){ //寻找i列最大值位置
if(matrix[j][i] > matrix[p][i])
p = j;
}
if(matrix[p][i] == 0) return false;
if(p != i)
exchange_col(i,p,n);
for(j = i + 1 ; j < n ; j++){ //剩余列进行消元
r = matrix[j][i] / matrix[i][i];
for(k = i ; k <= n ; k++)
matrix[j][k] -= r * matrix[i][k];
}
}
for(i = n - 1 ; i >= 0 ; i--){ //获得结果
ans[i] = matrix[i][n];
for(j = n - 1 ; j > i ; j--)
ans[i] -= matrix[i][j] * ans[j];
ans[i] /= matrix[i][i];
}
return true;
}
KMP算法
/*
串的模式匹配算法,给出主串s,匹配串s1及主串中开始匹配位置pos求匹配串s1在主串中从pos开始的首次出现位置,找不到返回,1
void get_nextval(const string & s,int * p)该函数求匹配串的位置信息,在调用Index_KMP
之前调用,p保存s中每个位置的前驱位置
int Index_KMP(const string & s,const string & s1,int pos)
s为要匹配的主串,s1为匹配串,pos为主串中的开始匹配位置
*/
#include
70
杭州电子科技大学ACM集训队资料集 #include
using namespace std;
void get_nextval(const string & s,int * p)
int i = 0,j = -1;
p[0] = -1;
while(i < s.size()){
if(j == -1 || s[i] == s[j]){ ++i,++j;
if(s[i] != s[j]) p[i] = j;
else
p[i] = p[j];
}
Else
j = p[j];
}
}
int Index_KMP(const string & s,const string & s1,int pos)
{
int i = pos - 1,j = 0;
int * next = new int[s1.size()];
get_nextval(s1,next);
while(i <= s.size() && j <= s1.size()){
if(j == -1 || s[i] == s1[j])
++i,++j;
else
j = next[j];
}
if(j > s1.size())
return i - s1.size();
else
return -1;
}
网络流:
max_flow.cpp
/* 计算网络流,如果是二分图的匹配,可以先对其进行网络预流以简化后续的查找
参数含义:n代表网络中共有多少节点,第0节点为源点,第n,1节点为汇点
71
杭州电子科技大学ACM集训队资料集
rel是个二维数组,rel[i][j]代表从节点i到节点j的流量,rel为全局变量数组
v[]是一个节点数组,v[i]包含与节点i相邻接的所有节点
*/
#include
#include
#include
using namespace std;
int rel[1000][10000]; //全局变量
int pre_flow(int n,vector * 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的流量,rel为全局变量数组
v[]是一个节点数组,v[i]包含与节点i相邻接的所有节点
返回值 :最大流量
*/
int max_flow(int n,vector * v) {
int ret = 0,i;
72
杭州电子科技大学ACM集训队资料集
int * pre = new int[n]; //或者将其变为全局数组,不用每次都分配
int t,t1,tm;
queue 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 search
t = 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 path
t1 = pre[t];
if(rel[t1][t] < tm)
tm = rel[t1][t];
t = t1;
}
// tm = 1; //二分图中
t = n - 1;
while(t != 0){ //change the relation
t1 = pre[t];
rel[t1][t] -= tm;
rel[t][t1] += tm;
t = t1;
}
ret += tm;
}
delete pre;
return ret;
73
杭州电子科技大学ACM集训队资料集
}
/*
网络中最小费用最大流的模板。
参数含义:np代表网络中的总节点数,v是网络节点的邻接表,cost
为最后求得的最小费用,mf为求得的最大流
返回值 :无
算法: 初始最小费用及最大流均为0,不断寻找可增广路(增广路对应的单位
费用最小并且可流),修改残留网络及cost,mf。直到无可增广路为止。
*/
/*
需要用到的全局变量
const int Max = 200000000;
vector v[110]; //存储每个节点的邻接点
int flow[110][110]; //flow[i][j]代表由i节点到j节点的可行流量
int fcost[110][110]; //fcost[i][j]代表由i节点到j节点的单位流量费用
int ct[110]; //ct[i]代表单位容量到达i节点的最小费用
int pre[110]; //可行节点的前驱节点
*/
void get_flow(int np,const vector * v,int & cost,int & mf)
{
int t,t1,tm,i,j;
bool out;
cost = 0,mf = 0;
while(1){
for(i = 0 ; i < np ; i++)
pre[i] = -1,ct[i] = Max;
ct[0] = 0;
while(1){
out = false;
for(i = 0 ; i < np ; i++){
for(j = 0 ; j < v[i].size() ; j++){
t = v[i][j];
if(flow[i][t] > 0 && ct[i] != Max && ct[i] + fcost[i][t] < ct[t]){
74
杭州电子科技大学ACM集训队资料集
out = true;
ct[t] = ct[i] + fcost[i][t];
pre[t] = i;
}
}
}
if(!out) break;
}
if(ct[np - 1] != Max){
t = np - 1;
tm = Max; //此处寻找流量最小值
while(t != 0){ //find the minimal num in the path
t1 = pre[t];
if(flow[t1][t] < tm)
tm = flow[t1][t];
t = t1;
}
mf += tm; //流量增加
t = np - 1;
while(t != 0){ //change the relation
t1 = pre[t];
flow[t1][t] -= tm;
flow[t][t1] += tm;
cost += tm * fcost[t1][t]; //费用增加
t = t1;
}
}
else
break;
}
}
max_flow_pre_label.cpp
#include
#include
#include
using namespace std;
/*
函数接口:int Relabel_To_Front(int s,int d)
参数含义:s为源点,d为汇点
75
杭州电子科技大学ACM集训队资料集
返回值 :网络最大流
调用函数前的初始化工作:ver置为网络中节点的个数,c[i][j]代表节点i到
节点j的流量,vl[i]存放i与相邻的所有节点
其它全局变量均初始化为零
*/
const int VEX = 405; //网络中顶点数
const int HMAX = 810; //最大高度的定义,只要大于顶点的2倍就可以了
int f[VEX][VEX]; //流量
int c[VEX][VEX]; //边最大容量
int h[VEX]; //节点高度
int e[VEX]; //节点容量
int ver; //节点数目
vector vl[VEX]; //邻接表,vl[i]存放与i相邻的节点
void Push(int u,int v) //流推进,由节点u推向v
{
int cf = c[u][v] - f[u][v]; //u,v边的容量
int d = e[u] < cf ? e[u] : cf;
f[u][v] += d;
f[v][u] = -f[u][v];
e[u] -= d;
e[v] += d;
}
void Relabel(int u) //对u重新标号
{
int i,t,cf;
int hmin = HMAX;
for(i = 0 ; i < vl[u].size() ; i++){ //寻找相邻最低点
t = vl[u][i];
cf = c[u][t] - f[u][t];
if(cf > 0 && h[u] <= h[t] && h[t] < hmin)
hmin = h[t];
}
h[u] = hmin + 1;
}
void Init_Preflow(int s) //初始化网络流,s为源点
76
杭州电子科技大学ACM集训队资料集 {
int i;
int u;
h[s] = ver; //初始化高度
for(i = 0 ; i < vl[s].size() ; i++){
u = vl[s][i];
f[s][u] = c[s][u];
f[u][s] = -c[s][u];
e[u] = c[s][u];
e[s] -= c[s][u];
}
}
void Discharge(int u) {
int i = 0;
int cf,v;
if(vl[u].size() == 0) return;
while(e[u] > 0){
if(i < vl[u].size()) {
v = vl[u][i];
cf = c[u][v] - f[u][v];
}
if(i >= vl[u].size()){
Relabel(u);
i = 0;
}
else if(cf > 0 && h[u] == h[v] + 1)
Push(u,v);
else
i++;
}
}
int Relabel_To_Front(int s,int d) //s为源点,d为汇点 {
int u,i,old_h;
list l;
list::iterator iter;
Init_Preflow(s);
77
杭州电子科技大学ACM集训队资料集
iter = l.begin();
for(i = 0 ; i < ver ; i++){
if(i != s && i != d)
l.insert(iter,i);
}
iter = l.begin();
while(iter != l.end()){
u = *iter;
old_h = h[u];
Discharge(u);
if(h[u] > old_h){
l.erase(iter);
l.insert(l.begin(),u);
iter = l.begin();
}
iter++;
}
return e[ver - 1];
}
字符串处理
/***********************************************************
void get_word(char * p,vector & v);
p指向待处理的字符串,v为结果存放数组
从一个字符串中提取出所有的单词,其中单词由a,z或
A,Z的字符组成,其它出现的字符均为分隔符,提取出的单词
存放在v数组中。
string to_lower(const string & so)
将字符串so转换为小写的形式,返回结果
************************************************************/
#include
#include
#include
78
杭州电子科技大学ACM集训队资料集
using namespace std;
void get_word(char * p,vector & v)
{
string st;
v.clear();
while(*p){
while(!isalpha(*p) && *p) p++;
if(!*p) break;
st.resize(0);
while(isalpha(*p))
st += *p++;
v.push_back(st);
}
}
string to_lower(const string & so) {
int i;
string s = so;
for(i = 0 ; i < s.size() ; i++)
s[i] = tolower(s[i]);
return s;
}
生成全排列.cpp
#include
using namespace std;
void createper(int n)//n!<2000000000 {
int total,i,j,k,t,*a=new int[n],top;
total=1;
for (i=1;i<=n;i++)
{
a[i]=i;
total*=i;
}
for (i=1;ia[k]) k--;
t=a[j-1];
a[j-1]=a[k];
a[k]=t;
top=(j+n-1)/2;
for (k=j;k<=top;k++)
{
t=a[k];
a[k]=a[n-k+j];
a[n-k+j]=t;
}
for (j=1;j>n)
{
createper(n);
printf("ok\n");
}
return 0;
}
生成全组合
#include using namespace std; void createfab(int m,int n)
{
int i,j,lcount,*a=new int[n+2];
for (i=1;i<=n;i++)
{
a[i]=i;
}
80
杭州电子科技大学ACM集训队资料集
a[n+1]=m+1;
for (j=1;j0;i--)
{
if (a[i]>m>>n)
{
createfab(m,n);
}
return 0;
}
母函数
/*#include "stdio.h" main()
{
int a[10001];
int b[10001];
int p;
81
杭州电子科技大学ACM集训队资料集
int i,j,k;
int n;
while(scanf("%d",&n)!=EOF)
{
//scanf("%d",&p);//P为相邻两个数的差,比如要求一个数的所有奇数分解,那么把P设为2就
可以了
p=2;
for(i=0;i<=n;i++)
{
a[i]=1;
b[i]=0;
}
for(k=p+1;k<=n;k=k+p)//相应的类似ZOJ1666的指数分解只要在这里修改两个条件就可以实现
{
for(i=0;i<=n;i++)
for(j=0;j<=n;j=j+k)
{
if(i+j>n) break;
b[i+j]=b[i+j]+a[i];
}
for(j=0;j<=n;j++)
{
a[j]=b[j];
b[j]=0;
}
}
printf("result=%d\n",a[n]);
}
}*/
//效率更高的动态规划法
#include "stdio.h"
int main()
{
int a[10001];
int i,j,n;
int p;
while(scanf("%d",&n)!=EOF)
{
scanf("%d",&p);
for(i=0;i<=n;i++)
a[i]=0;
a[0] = 1;
for(i=1; i<=n; i=i+p) ////相应的类似ZOJ1666的指数分解只要把这里修改成
for(i=1;i<=n;p++,i=p*p)就可以了
82
杭州电子科技大学ACM集训队资料集
for(j=0; j+i<=n; j++)
{
a[j+i] += a[j];
}
printf("result=%d\n",a[n]);
}
return 0;
}
83
杭州电子科技大学ACM集训队资料集
三角公式总表
2nπRn,,R112,,?L=R= S=L= 弧长扇R=R18036022
bca?正弦定理:=== 2R(R为三角形外接圆半径) sinAsinBsinC
222222?余弦定理:a=b+c-2bc b=a+c-2accosB cosA
222bca,,222cosCc=a+b-2ab cosA ,2bc
abc11112,h?S=a=absinC=bcsinA=acsinB==2RsinAsinBsinC?a 22224R
222asinBsinCbsinAsinCcsinAsinBp(p,a)(p,b)(p,c)====pr= 2sinB2sinC2sinA
1(其中, r为三角形内切圆半径) p,(a,b,c)2
?同角关系:
,,sinxcosytg,sin,,sec,?商的关系:?=== ? ctg,,,,cos,,csc,xcos,ysin,
r1y? ? sec,,,,tg,,csc,sin,,,cos,,tg,xcosr,
r1x? ? csc,,,,ctg,,sec,cos,,,sin,,ctg,ysinr,
sin,,csc,,cos,,sec,,tg,,ctg,,1?倒数关系:
222222sin,,cos,,sec,,tg,,csc,,ctg,,1?平方关系:
22asin,,bcos,,a,bsin(,,,),? (其中辅助角与点(a,b)
b在同一象限,且tg,) ,a
Asin(,,x,,),,,0,A,0?函数y=k的图象及性质:()
,21,,,x,,振幅A,周期T=, 频率f=, 相位,初相 ,T
,,3,x,,?五点作图法:令依次为 求出x与y, 依0,,,,2,22
,,x,y点作图
84
杭州电子科技大学ACM集训队资料集
?诱导公试
三角函数值等于, sin cos tg ctg 的同
三角函数值,前面加 - -tg,ctg,- -sin + ,,cos,名
tg, ctg, sin ,cos,上一个把,- +---,,看作锐角时,
tg,ctg,三角函数值的符号; sin, ,,cos,原+--++
tg, ctg, sin, cos,2 即:函数名不变,符号,,-+---
tg, ctg, sin, cos,看象限 2k ,,+++++
三角函数值等于, sin con tg ctg 的异,ctg, tg, sin, cos, 三角函数值,前面加,,++++名2
,ctg,tg, sin,cos, 上一个把, ,,+---看作锐角时,2
,3ctg,tg, sin, 三角函数值的符号;cos, ,,--++原2
,3ctg,tg, sin,cos, 即:函数名改变,符号,,-+--2
看象限
?和差角公式
sin(,,,),sin,cos,,cos,sin,cos(,,,),cos,cos,,sin,sin,? ?
,,tg,tg,,tg,,tg,,tg(,,,)(1,tg,,tg,)tg(,),? ? 1,tg,tg,,
,,,,,,tg,tg,tg,tg,tg,tg,,,tg(,,),? 其中当A+B+C=π时,有: 1,tg,tg,tg,tg,tg,tg,,,,,,
ABACBCtgA,tgB,tgC,tgA,tgB,tgCi). ii). tgtg,tgtg,tgtg,1222222?二倍角公式:(含万能公式)
85
杭州电子科技大学ACM集训队资料集
,2tg,,,?sin2,2sincos, 21,tg,
2,1,tg2222,,,,,cos2,cos,sin,2cos,1,1,2sin,? 21,tg,
2,2tg1cos21cos2tg,,,,,22,sin?tg2, ? ?cos,,,,,22121,tg,2,tg, ?三倍角公式:
3sin,3,3sin,,4sin,,4sin,sin(60:,,)sin(60:,,)?
3cos,3,,3cos,,4cos,,4cos,cos(60:,,)cos(60:,,)?
3,,3tg,tg? tg,3,,tg,,tg(60,,),tg(60,,)21,3tg,
,?半角公式:(符号的选择由所在的象限确定) 2
1cos1cos1cos,,,,,,,,,2sinsincos? ? ? ,,,,,222222
1cos,,,,,2221cos2sin1cos2cos?cos ? ? ,,,,,,,2222
,,,,21sin(cossin)cossin? ,,,,,,2222
,,,,1,cossin1,costg,,,,? 21,cos,1,cos,sin,
?积化和差公式:
11,,,,sin,cos,,sin(,,,),sin(,,,)cos,sin,,sin(,,,),sin(,,,)22
11 ,,,,,,cos,cos,,cos(,,,),cos(,,,)sin,sin,,,cos(,,,),cos,,,22
?和差化积公式:
,,,,,,,,,,,,sinsin2sincossinsin2cossin? ? ,,,,,,,,2222
,,,,,,,,,,,,coscos2coscoscoscos2sinsin? ? ,,,,,,,,,2222?反三角函数:
86
杭州电子科技大学ACM集训队资料集 名称 函数式 定义域 值域 性质
y,arcsinx ,,,,,,arcsin(-x),-arcsinx,1,1增 奇 反正弦函数 ,,,,22,,
y,arccosx arccos(,x),,,arccosx ,,0,, ,,,1,1减 反余弦函数
y,arctgx ,,arctg(-x) , -arctgx,,奇 反正切函数 R 增 ,,,,22,,
y,arcctgx arcctg(,x),,,arcctgx ,,0,, 反余切函数 R 减
?最简单的三角方程
方程 方程的解集
sinx,a a,1 ,,x|x,2k,,arcsina,k,Z
ka,1 ,,,,x|x,k,,,1arcsina,k,Z
cosx,a a,1 ,,x|x,2k,,arccosa,k,Z
a,1 ,,x|x,2k,,arccosa,k,Z
tgx,a ,,x|x,k,,arctga,k,Z
ctgx,a ,,x|x,k,,arcctga,k,Z
87