Made By—NYIST_Lzq （李朝强）2016.05.23
目录
一、最长公共子序列 (5)
二、单调递增子序列 (5)
三、常用几何公式 (7)
四、常用求和公式 (9)
五、常用三角公式 (10)
六、行列式求值 (11)
七、求n的n次方的最高位数字 (12)
八、输入输出外挂 (12)
九、把分数化为循环小数和把循环小数化为分数 (12)
十、计算某天是星期几的方法 (13)
十一、求最长回文子串长度（manacher算法） (14)
十二、大数运算 (14)
十三、快速排序 (17)
十四、欧拉函数和最大公约数的组合应用 (18)
十五、字典树 (20)
十六、KMP (21)
十七、AC自动机 (22)
十八、后缀数组 (23)
十九、归并排序求逆序数 (25)
二十、二叉树重建 (26)
二十一、线段树 (27)
二十二、矩阵快速幂 (28)
二十三、最小生成树 (33)
二十四、最短路 (35)
二十五、给定四面体六条边的长度，求其体积 (37)
二十六、卡特兰数 (38)
二十七、多重背包 (40)
二十八、扩展欧几里得 (40)
二十九、莫比乌斯反演 (41)
三十、判断两条线段是否相交 (42)
三十一、三角形有向面积 (43)
三十二、求一个数的n的k次方的前三位和后三位 (43)
三十三、点到直线的距离 (43)
三十四、求两个圆的交点 (43)
三十五、组合数公式 (44)
三十六、求a对mod的逆元 (44)
三十七、区域分割问题 (44)
三十八、托兰定理 (45)
三十九、皮克定理 (45)
四十、隔板法 (45)
四十一、子矩形最大和 (46)
四十二、区间dp (47)
四十三、一个圆和一个圆环的相交面积 (51)
四十四、两个圆环的相交面积 (52)
四十五、分治法求等比数列的前n项和 (53)
四十六、双联通分量（Tarjan缩点算法） (53)
四十七、瓶颈路 (54)
最长公共子序列
1.（可打印路径）：时间复杂度O(n^2)
#include
#include
using namespace std;
const int N = 1005;
int dp[N][N];
short dir[N][N];
char s1[N], s2[N];
int len1, len2;
int LCS() {
for(int i = 1; i <= len1; i++) {
for(int j = 1; j <= len2; j++) {
if(s1[i-1] == s2[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
dir[i][j] = 1;
}
else if(dp[i-1][j] >= dp[i][j-1]) {
dp[i][j] = dp[i-1][j];
dir[i][j] = 0;
}
else {
dp[i][j] = dp[i][j-1];
dir[i][j] = 2;
}
}
}
return dp[len1][len2];
}
void print(int l1, int l2) { //打印路径
if(l1 == 0 || l2 == 0) return ;
if(dir[l1][l2] == 1) {
print(l1-1, l2-1);
printf("%c ", s1[l1-1]);
}
else if(dir[l1][l2] == 0)
print(l1-1, l2);
else print(l1, l2-1);
} int main()
{
while(~scanf("%s%s", s1, s2)) {
len1 = strlen(s1);
len2 = strlen(s2);
printf("%d\n", LCS());
print(len1, len2);
printf("\n");
}
return 0;
}
如果不需要打印路径，只需把LCS函数改成下面的即可。
int LCS(char *s1, char *s2) {
memset(dp, 0, sizeof(dp));
int len1 = strlen(s1), len2 = strlen(s2);
for(int i = 1; i <= len1; i++) {
for(int j = 1; j <= len2; j++) {
if(s1[i-1] == s2[j-1])
dp[i][j] = dp[i-1][j-1] + 1;
else
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
return dp[len1][len2];
}
单调递增子序列
先回顾经典的O(n^2)的动态规划算法，设A[i]表示序列中的第i个数，F[i]表示从1到i这一段
中以i结尾的最长上升子序列的长度，初始时设F[i] = 0(i = 1, 2, ..., len(A))。则有动态规划方程：F[i] = max{1, F[j] + 1} (j = 1, 2, ..., i - 1, 且A[j] < A[i])。
现在，我们仔细考虑计算F[i]时的情况。假设有两个元素A[x]和A[y]，满足
(1) x < y < i
(2) A[x] < A[y] < A[i]
(3) F[x] = F[y]
此时，选择F[x]和选择F[y]都可以得到同样
的F[i]值，那么，在最长上升子序列的这个位置中，
应该选择A[x]还是应该选择A[y]呢？
很明显，选择A[x]比选择A[y]要好。因为由于条件(2)，在A[x+1] ... A[i-1]这一段中，如果存在A[z]，A[x] < A[z] < a[y]，则与选择A[y]相比，将会得到更长的上升子序列。再根据条件(3)，我们会得到一个启示：根据F[]的值进行分类。对于F[]的每一个取值k，我们只需要保留满足F[i] = k的所有A[i]中的最小值。设D[k]记录这个值，
即D[k] = min{A[i]} (F[i] = k)。
注意到D[]的两个特点：
(1) D[k]的值是在整个计算过程中是单调不上升的。
(2) D[]的值是有序的，即D[1] < D[2] < D[3] < ... < D[n]。
利用D[]，我们可以得到另外一种计算最长上升子序列长度的方法。设当前已经求出的最长上升子序列长度为len。先判断A[i]与D[len]。若A[i] > D[len]，
则将A[i]接在D[len]后将得到一个更长的上升子序列，len = len + 1，D[len] = A[i]；
否则，在D[1]..D[len]中，找到最大的j，满足D[j] < A[i]。令k = j + 1，则有D[j] < A[i] <= D[k]，
将A[i]接在D[j]后将得到一个更长的上升子序列，同时更新D[k] = A[i]。
最后，len即为所要求的最长上升子序列的长度。
在上述算法中，若使用朴素的顺序查找在D[1]..D[len]查找，由于共有O(n)个元素需要计算，
每次计算时的复杂度是O(n)，则整个算法的时间复杂度为O(n^2)，与原来的算法相比没有任何进步。
但是由于D[]的特点(2)，我们在D[]中查找时，可以使用二分查找高效地完成，则整个算法的时间复杂度
下降为O(nlogn)，有了非常显著的提高。需要注意的是，D[]在算法结束后记录的并不是一个符合题意的最长上升子序列！
这个算法还可以扩展到整个最长子序列系列问题，整个算法的难点在于二分查找的设计，需要非常小心注意。
1.O(n^2)写法
#include
#include
int main()
{
char a[10005];
int n,i,j,max,d[10005],l;
scanf("%d",&n);
getchar();
while(n--)
{
gets(a);
l=strlen(a);
memset(d,0,sizeof(d));
for(i=1; i for(j=0; j if(a[i]>a[j]&&d[i] d[i]=d[j]+1; max=0; for(i=0; i if(d[i]>max) max=d[i]; printf("%d\n",max+1); } return 0; } 2.O(nlogn)写法 #include const int N = 100005; int dp[N]; int main() { int n, a; while(~scanf("%d", &n)) { int len = 0; scanf("%d", &a); dp[++len] = a; for(int i = 1; i < n; i++) { scanf("%d", &a); if(dp[len] < a) dp[++len] = a; else { int l = 1, r = len; while(l <= r) { int mid = (l + r) / 2; if(dp[mid] > a) r = mid - 1; else l = mid + 1; } dp[l] = a; } } printf("%d\n", len); } return 0; } 常用几何公式： 三角形: 1. 半周长P=(a+b+c)/2 2. 面积S= a(Ha)/2 = absin(C)/2 = sqrt(P(P-a)(P-b)(P-c)) 3. 中线Ma=sqrt(2(b^2+c^2)-a^2)/2=sqrt(b^2+c^2+2bccos(A))/2 4. 角平分线Ta=sqrt(bc((b+c)^2-a^2))/(b+c)=2bccos(A/2)/(b+c) 5. 高线Ha=bsin(C)=csin(B)=sqrt(b^2-((a^2+b^2-c^2)/(2a))^2) 6. 内切圆半径r=S/P=asin(B/2)sin(C/2)/sin((B+C)/2) =4Rsin(A/2)sin(B/2)sin(C/2)=sqrt((P-a)(P-b)(P-c)/P) =Ptan(A/2)tan(B/2)tan(C/2) 7. 外接圆半径R=abc/(4S)=a/(2sin(A))=b/(2sin(B))=c/(2sin(C)) 四边形: D1,D2为对角线,M对角线中点连线,A为对角线夹角 1. a^2+b^2+c^2+d^2=D1^2+D2^2+4M^2 2. S=D1D2sin(A)/2 (以下对圆的内接四边形) 3. ac+bd=D1D2 4. S=sqrt((P-a)(P-b)(P-c)(P-d)),P为半周长 正n边形: R为外接圆半径,r为内切圆半径 1. 中心角A=2PI/n 2. 内角C=(n-2)PI/n 3. 边长a=2sqrt(R^2-r^2)=2Rsin(A/2)=2rtan(A/2) 4. 面积S=nar/2=nr^2tan(A/2)=nR^2sin(A)/2=na^2/(4tan(A/2)) 圆: 1. 弧长l=rA 2. 弦长a=2sqrt(2hr-h^2)=2rsin(A/2) 3. 弓形高h=r-sqrt(r^2-a^2/4)=r(1-cos(A/2))=atan(A/4)/2 4. 扇形面积S1=rl/2=r^2A/2 5. 弓形面积S2=(rl-a(r-h))/2=r^2(A-sin(A))/2 棱柱: 1. 体积V=Ah,A为底面积,h为高 2. 侧面积S=lp,l为棱长,p为直截面周长 3. 全面积T=S+2A 棱锥: 1. 体积V=Ah/3,A为底面积,h为高 (以下对正棱锥) 2. 侧面积S=lp/2,l为斜高,p为底面周长 3. 全面积T=S+A 棱台: 1. 体积V=(A1+A2+sqrt(A1A2))h/3,A1.A2为上下底面积,h为高(以下为正棱台) 2. 侧面积S=(p1+p2)l/2,p1.p2为上下底面周长,l为斜高 3. 全面积T=S+A1+A2 圆柱: 1. 侧面积S=2PIrh 2. 全面积T=2PIr(h+r) 3. 体积V=PIr^2h 圆锥: 1. 母线l=sqrt(h^2+r^2) 2. 侧面积S=PIrl 3. 全面积T=PIr(l+r) 4. 体积V=PIr^2h/3 圆台: 1. 母线l=sqrt(h^2+(r1-r2)^2) 2. 侧面积S=PI(r1+r2)l 3. 全面积T=PIr1(l+r1)+PIr2(l+r2) 4. 体积V=PI(r1^2+r2^2+r1r2)h/3 球: 1. 全面积T=4PIr^2 2. 体积V=4PIr^3/3 球台: 1. 侧面积S=2PIrh 2. 全面积T=PI(2rh+r1^2+r2^2) 3. 体积V=PIh(3(r1^2+r2^2)+h^2)/6 球扇形: 1. 全面积T=PIr(2h+r0),h为球冠高,r0为球冠底面半径 2. 体积V=2PIr^2h/3 常用求和公式： 求和公式,k = 1....n 1. sum( k ) = n(n+1)/2 2. sum( 2k-1 ) = n^2 3. sum( k^2 ) = n(n+1)(2n+1)/6 4. sum( (2k-1)^2 ) = n(4n^2-1)/3 5. sum( k^3 ) = (n(n+1)/2)^2 6. sum( (2k-1)^3 ) = n^2(2n^2-1) 7. sum( k^4 ) = n(n+1)(2n+1)(3n^2+3n-1)/30 8. sum( k^5 ) = n^2(n+1)^2(2n^2+2n-1)/12 9. sum( k(k+1) ) = n(n+1)(n+2)/3 10. sum( k(k+1)(k+2) ) = n(n+1)(n+2)(n+3)/4 12. sum( k(k+1)(k+2)(k+3) ) = n(n+1)(n+2)(n+3)(n+4)/5 公式分类公式表达式 乘法与因式分解a2-b2=(a+b)(a-b) a3+b3=(a+b)(a2-ab+b2) a3-b3=(a-b)(a2+ab+b2) 三角不等式|a+b|≤|a|+|b||a-b|≤|a|+|b||a|≤b<=>-b≤a≤b |a-b|≥|a|-|b| -|a|≤a≤|a| 一元二次方程的解-b+√(b2-4ac)/2a -b-b+√(b2-4ac)/2a 根与系数的关系X1+X2=-b/a X1*X2=c/a 注：韦达定理 判别式b2-4a=0 注：方程有相等的两实根 b2-4ac>0 注：方程有一个实根 b2-4ac<0 注：方程有共轭复数根 三角函数公式 两角和公式sin(A+B)=sinAcosB+cosAsinB sin(A-B)=sinAcosB-sinBcosA cos(A+B)=cosAcosB-sinAsinB cos(A-B)=cosAcosB+sinAsinB tan(A+B)=(tanA+tanB)/(1-tanAtanB) tan(A-B)=(tanA-tanB)/(1+tanAtanB) cot(A+B)=(ctgActgB-1)/(ctgB+ctgA) cot(A-B)=(cotAcotB+1)/(cotB-cotA) 倍角公式tan2A=2tanA/(1-tan2A) cot2A=(cot2A-1)/2cota cos2a=cos2a-sin2a=2cos2a-1=1-2sin2a 半角公式sin(A/2)=√((1-cosA)/2) sin(A/2)=-√((1-cosA)/2) cos(A/2)=√((1+cosA)/2)cos(A/2)=-√((1+cosA)/2) tan(A/2)=√((1-cosA)/((1+cosA)) tan(A/2)=-√((1-cosA)/((1+cosA)) cot(A/2)=√((1+cosA)/((1-cosA)) ctg(A/2)=-√((1+cosA)/((1-cosA)) 和差化积2sinAcosB=sin(A+B)+sin(A-B) 2cosAsinB=sin(A+B)-sin(A-B) 2cosAcosB=cos(A+B)-sin(A-B) -2sinAsinB=cos(A+B)-cos(A-B) sinA+sinB=2sin((A+B)/2)cos((A-B)/2 cosA+cosB=2cos((A+B)/2)sin((A-B)/2) tanA+tanB=sin(A+B)/cosAcosB tanA-tanB=sin(A-B)/cosAcosB cotA+cotB=sin(A+B)/sinAsinB -cotA+cotB=sin(A+B)/sinAsinB 某些数列前n项和1+2+3+4+5+6+7+8+9+…+n=n(n+1)/21+3+5+7+9+11+13+15+…+(2n-1)=n 2 2+4+6+8+10+12+14+…+(2n)=n(n+1)12+22+32+42+52+62+72+82+…+n2=n(n +1)(2n+1)/6 13+23+33+43+53+63+…n3=n2(n+1)2/4 1*2+2*3+3*4+4*5+5*6+6*7+…+n(n +1)=n(n+1)(n+2)/3 正弦定理a/sinA=b/sinB=c/sinC=2R 注：其中R 表示三角形的外接圆半径 余弦定理b2=a2+c2-2accosB 注：角B是边a和边c的夹角 圆的标准方程(x-a)2+(y-b)2=r2注：（a,b）是圆心坐标 圆的一般方程x2+y2+Dx+Ey+F=0 注：D2+E2-4F>0 抛物线标准方程y2=2px y2=-2px x2=2py x2=-2py 直棱柱侧面积S=c*h 斜棱柱侧面积S=c'*h 正棱锥侧面积S=1/2c*h' 正棱台侧面积S=1/2(c+c')h' 圆台侧面积S=1/2(c+c')l=pi(R+r) l 球的表面积S=4pi*r2 圆柱侧面积S=c*h=2pi*h 圆锥侧面积S=1/2*c*l=pi*r*l 弧长公式l=a*r a是圆心角的弧度数r >0 扇形面积公式s=1/2*l*r 锥体体积公式V=1/3*S*H 圆锥体体积公式V=1/3*pi*r2h 斜棱柱体积V=S'L 注：其中,S'是直截面面积，L是侧棱长 柱体体积公式V=s*h 圆柱体V=pi*r2h 常用三角公式： 转化公式： cosa*seca=1 sina*csca=1 tana*cota=1 1+(tana)^2=(seca)^2 1+(cota)^2=(csca)^2 (sina)^2+(cosa)^2=1 和角公式 sin(a+b)=sina*cosb+cosa*sinb sin(a-b)=sina*cosb-cosa*sinb cos(a+b)=cosa*cosb-sina*sinb cos(a-b)=cosa*cosb+sina*sinb tan(a+b)=(tana+tanb)/(1-tana*tanb) cot(a+b)=(cota*cotb-1)/(cota+cotb) 倍角公式 sin2a=2sina*cosa cos2a=(cosa)^2-(sina)^2=2(cosa)^2-1=1-2(sin a)^2 tan2a=2tana/[1-(tana)^2] sin(3a)=3sina-4(sina)^3 cos(3a)=4(cosa)^3-3cosa tan(3a)=[3tana-(tana)^3]/[1-3(tana^2)] 积化和差 sina*cosb=[sin(a+b)+sin(a-b)]/2 cosa*sinb=[sin(a+b)-sin(a-b)]/2 cosa*cosb=[cos(a+b)+cos(a-b)]/2 sina*sinb=[cos(a-b)-cos(a+b)]/2 和差化积 sina+sinb=2sin[(a+b)/2]cos[(a-b)/2] sina-sinb=2sin[(a-b)/2]cos[(a+b)/2] cosa+cosb=2cos[(a+b)/2]cos[(a-b)/2] cosa-cosb=-2sin[(a+b)/2]sin[(a-b)/2] 万能公式 令tan(a/2)=t sina=2t/(1+t^2) cosa=(1-t^2)/(1+t^2) tana=2t/(1-t^2) 辅助角公式 asint+bcost=(a^2+b^2)^(1/2)sin(t+r) cosr=a/[(a^2+b^2)^(1/2)] sinr=b/[(a^2+b^2)^(1/2)] tanr=b/a 半角公式 sin^2(a/2)=(1-cos(a))/2 cos^2(a/2)=(1+cos(a))/2 tan(a/2)=(1-cos(a))/sin(a)=sin(a)/(1+cos(a)) 诱导公式 sin(-α) = -sinα cos(-α) = cosα tan (—a)=-tanα sin(π/2-α) = cosα cos(π/2-α) = sinα sin(π/2+α) = cosα cos(π/2+α) = -sinα sin(π-α) = sinα cos(π-α) = -cosα sin(π+α) = -sinα cos(π+α) = -cosα tanA= sinA/cosA tan（π/2+α）=－cotα tan（π/2－α）=cotα tan（π－α）=－tanα tan（π+α）=tanα 行列式求值 给出一个n阶行列式，求此行列式的值。#include #include using namespace std; const int N = 100; int n; double c[N][N]; void solve() { int flag = 0; double y, t = 1.0; for(int i = 0; i <= (n - 2); i++) { if(c[i][i] == 0) //判断主对角线上是否有0 { for(int m = i + 1; m < n; m++) { if(c[m][i] != 0) { for(int p = 0; p < n; p++) { c[i][p] += c[m][p]; c[m][p] = c[i][p] - c[m][p]; c[i][p] -= c[m][p]; } } } for(int q = i + 1; q < n; q++) //若有全0 列 { if(c[q][i] == 0) flag = 1; else flag = 0; } if(flag == 1) printf("行列式为0 \n"); } else if(!flag) { for(int j = i + 1; j <= (n - 1); j++) { y = c[j][i] / c[i][i]; //求出初等行变换时的系数 for(int k = i; k <= (n - 1); k++) c[j][k] = c[j][k] + (y * (-c[i][k])); //初等行变换 } } } if(!flag) { printf("上三角行列式为:\n"); for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) printf("%lf ", c[i][j]); printf("\n"); } for(i = 0; i < n; i++) t *= c[i][i]; printf("行列式为: %lf\n", t); } } int main() { while(~scanf("%d", &n)) { for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) scanf("%lf", &c[i][j]); solve(); } return 0; } 求n的n次方的最高位数字 #include #include int main() { double n; while(~scanf("%lf", &n)) { double a = n * log10(n); long long b = (long long)(a); double c = a - b; long long d = (long long)(pow(10, c)); printf("%lld\n", d); } return 0; } 输入输出外挂 /* 仅适合纯数字输入输出*/ #include int Scan() { //输入外挂 int res = 0, flag = 0; char ch; if((ch = getchar()) == '-') flag = 1; else if(ch >= '0' && ch <= '9') res = ch - '0'; while((ch = getchar()) >= '0' && ch <= '9') res = res * 10 + (ch - '0'); return flag ? -res : res; } void Out(int a) { //输出外挂 if(a < 0) { putchar('-'); a = -a; } if(a >= 10) Out(a / 10); putchar(a % 10 + '0'); } int main() { int T, n; scanf("%d", &T); while(T--) { n = Scan(); Out(n); printf("\n"); } return 0; } 把分数化为循环小数和把循环小数化为分数 1.输入m/n，如果m能被n整除，则直接输出商；否则，输出商以后再输出循环节。 #include #include const int MAXN = 100005; int a[MAXN], vis[MAXN]; int main() { int n, t, i, m; scanf("%d",&t); while(t--) { memset(vis, 0, sizeof(vis)); scanf("%d/%d",&m,&n); if(m > 0 && n < 0) { printf("-"); n = -n; } else if(m < 0 && n > 0) { printf("-"); m = -m; } if(m % n == 0) { printf("%d\n",m/n); continue; } else { if(m > n) { printf("%d.",m/n); m = m % n; } else printf("0."); } int s = m, num = 0; vis[s] = 1; while(1) { s *= 10; a[num++] = s / n; s %= n; if(vis[s] || s == 0) break; //余数再次出现或者余数为0（即可以整除） vis[s] = 1; } for(i = 0; i < num; i++) printf("%d", a[i]); printf("\n"); } return 0; } 2.把循环小数化成分数 对于纯循环小数（从小数点后第1位开始循环）x，假设循环节为R，它包括l个数字，则有10^l*x - x = R,因此x = R/(10^l - 1)。 例如，若x = 0.123 123 123…，则R = 123，l = 3, 因此x = 123/999 = 41/333。 对于混循环小数（不是从第一位就开始循环的小数）化成分数，这个分数的分子是第二个循环节以前的小数部分组成的数与小数部分中不循环部分组成的数的差。 分母的头几位数是9，末几位是0。9的个数与循环节中的位数相同，0的个数与不循环部分的位数相同。例如把0.166…化成分数时，分子为（16-1）=15，分母为90，化简后就是1/6。 计算某天是星期几的方法 1.基姆拉尔森计算公式 W= (d+2*m+3*(m+1）/5+y+y/4-y/100+y/400) mod 7 在公式中d表示日期中的日数+1，m表示月份数，y表示年数。 注意：用该公式时，需要把一月和二月看成是上一年的十三月和十四月，公式中的d是日期加1。所以计算结果就是实际的星期，不需要加1.，即是：“1”为星期1，……，“7”为星期日。 /*输入格式：年月日，日期在1600年1月1日到9600年1月1日之间，星期一到星期六用1-6表示，星期日用0表示*/ #include int main() { int y, m, d; while(~scanf("%d%d%d",&y,&m,&d)) { if(m == 1 || m == 2) { m += 12; y--; } int w = (d +1+ 2*m + 3*(m+1)/5 + y + y/4 - y/100 + y/400) % 7; printf("%d\n",w); } return 0; } 2.Week=(Day + 2*Month + 3*(Month+1）/5 + Year + Year/4 - Year/100 + Year/400) % 7 （其中的Year是4位数的，如2009。“%”号是等式除7取余数） 注意： i. 该公式中同样要把1月和2月分别当成上一年的13月和14月处理。 例如：2008年1月4日要换成2007年13月4日带入公式。 ii.该式与基姆拉尔森公式有点区别：“0”为星期1，……，“6”为星期日。 求最长回文子串长度（manacher算法） /*时间复杂度O(n)*/ #include #include #include using namespace std; const int N = 220005; char str[N]; int p[N]; void manacher(char *s, int len) { p[0] = 1; int mmax = 0, id = 0; for(int i = 1; i < len; i++) { p[i] = mmax > i ? min(p[id*2-i], mmax - i) : 1; while(s[i+p[i]] == s[i-p[i]]) p[i]++; if(i + p[i] > id + p[id]) { id = i; mmax = i + p[i]; } } } int main() { while(~scanf("%s",str)) { int len = strlen(str); for(int i = len; i >= 0; i--) { str[(i<<1) + 1] = '#'; str[(i<<1) + 2] = str[i]; } str[0] = '*'; //防止数组越界 len = len * 2 + 2; manacher(str, len); int ans = 0; for(int i = 0; i < len; i++) ans = max(ans, p[i]-1); printf("%d\n", ans); } return 0; } 大数运算 1./* 大整数加法，调用方式:add(a, b);，返回类型：string */ string add(string a, string b) { string s; reverse(a.begin(), a.end()); reverse(b.begin(), b.end()); int i = 0; int m, k = 0; while(a[i] && b[i]) { m = a[i] - '0' + b[i] - '0' + k; k = m / 10; s += (m % 10 + '0'); i++; } if(i == a.size()) { while(i != b.size()) { m = k + b[i] - '0'; k = m / 10; s += m % 10 + '0'; i++; } if(k) s += k + '0'; } else if(i == b.size()) { while(i != a.size()) { m = k + a[i] - '0'; k = m / 10; s += m % 10 + '0'; i++; } if(k) s += k + '0'; } reverse(s.begin(), s.end()); return s; } 2./* 大整数减法*/ #include #include #include #include using namespace std; string sub(string a, string b) { int i, j, k, s, flag = 1; int tmpa[10000], tmpb[10000], c[10000]; string ans; if(a.size() < b.size() || (a.size() == b.size() && https://www.doczj.com/doc/c916032573.html,pare(b) < 0)) { string tmp = a; a = b; b = tmp; flag = 0; } while(a.length() > b.length()) b = '0' + b; int len = a.length(); for(i = 0; i < len; i++) { tmpa[i] = a[i] - '0'; tmpb[i] = b[i] - '0'; } for(i = len - 1; i >= 0; i--) { if(tmpa[i] >= tmpb[i]) c[i] = tmpa[i] - tmpb[i]; else { c[i] = 10 + tmpa[i] - tmpb[i]; tmpa[i-1]--; } } for(i = 0; i < len - 1; i++) if(c[i] != 0) break; for(j = i; j < len; j++) ans = ans + (char)(c[j] + '0'); if(!flag) ans = '-' + ans; return ans; } int main() { string a, b; while(cin >> a >> b) { cout << sub(a, b) << endl; } return 0; } 3./* 大整数乘以小整数（可以用整型变量表示的整数）*/ string multi(string a, int k) { if(k == 0) return "0"; int len = a.length(), carry = 0; reverse(a.begin(), a.end()); for(int i = 0; i < len; i++) { int s = (a[i] - '0') * k + carry; a[i] = s % 10 + '0'; carry = s / 10; } while(carry != 0) { a = a + (char)(carry % 10 + '0'); carry /= 10; } reverse(a.begin(), a.end()); return a; } 4./* 两个不含前导0的大整数相乘*/ string multi_string_int(string a, int k) { if(k == 0) return "0"; int len = a.length(), carry = 0; reverse(a.begin(), a.end()); for(int i = 0; i < len; i++) { int s = (a[i] - '0') * k + carry; a[i] = s % 10 + '0'; carry = s / 10; } while(carry != 0) { a = a + (char)(carry % 10 + '0'); carry /= 10; } reverse(a.begin(), a.end()); return a; } string add(string a, string b) { string s; reverse(a.begin(), a.end()); reverse(b.begin(), b.end()); int i = 0; int m, k = 0; while(a[i] && b[i]) { m = a[i] - '0' + b[i] - '0' + k; k = m / 10; s += (m % 10 + '0'); i++; } if(i == a.size()) { while(i != b.size()) { m = k + b[i] - '0'; k = m / 10; s += m % 10 + '0'; i++; } if(k) s += k + '0'; } else if(i == b.size()) { while(i != a.size()) { m = k + a[i] - '0'; k = m / 10; s += m % 10 + '0'; i++; } if(k) s += k + '0'; } reverse(s.begin(), s.end()); return s; } string multi_string_string(string a, string b) { string ans = ""; for(int i = a.size() - 1; i >= 0; i--) { string tmp = multi_string_int(b, a[i] - '0'); for(int j = 0; j < a.size() - 1 - i; j++) tmp += '0'; ans = add(ans, tmp); } return ans; } 5.求大整数除以一个小整数的商： string division(string str, int x) { string ans = ""; int len = str.length(); int y = 0; for(int i = 0; i < len; i++) { ans += char((y * 10 + (str[i] - '0')) / x + '0'); y = (y * 10 + (str[i] - '0')) % x; } while(*(ans.begin()) == '0' && ans.size() > 1) ans.erase(ans.begin()); return ans; } 6.求一个大整数对一个小整数的余数： int Mod(string str, int x) { int len = str.length(); int y = 0; for(int i = 0; i < len; i++) y = (y * 10 + (str[i] - '0')) % x; return y; } 7.大数阶乘（n<=10000) #include #include const int maxn=40000; /*数组不能太小，小了存不下*/ int a[maxn]; int main() { int i,j,n; while(~scanf("%d",&n)) { memset(a,0,sizeof(a)); a[0]=1; for(i=2; i<=n; i++) { int c=0; /*保存进位*/ for(j=0; j { int s=a[j]*i+c; a[j]=s%10; c=s/10; } } for(j=maxn-1; j>=0; j--) /*去掉前导零*/ if(a[j]) break; for(i=j; i>=0; i--) printf("%d",a[i]); printf("\n"); } return 0; } 快速排序 每次把排序区间的第一个元素作为基准，把此区间内比基准大的元素放在基准右边，比基准小的元素放在基准左边（从小到大排序）。在理想情况下，时间复杂度为O(nlongn)；在最坏情况下，时间复杂度为O(n^2)。 #include int a[1000], sum; int Partition(int low, int high) { int tmp = a[low]; a[0] = a[low]; while(low < high) { while(low < high && a[high] >= tmp) --high; a[low] = a[high]; while(low < high && a[low] <= tmp) ++low; a[high] = a[low]; } a[low] = a[0]; return low; } void QuickSort(int low, int high) { sum++; //printf("Sort: %d -> %d\n", low, high); //记录递归排序的区间 if(low < high) { int loc = Partition(low, high); //printf("loc = %d\n", loc); QuickSort(low, loc-1); QuickSort(loc+1, high); } } int main() { int n, i; while(~scanf("%d",&n)) { sum = 0; //递归次数 for(i = 1; i <= n; i++) scanf("%d",&a[i]); QuickSort(1, n); for(i = 1; i < n; i++) printf("%d ", a[i]); printf("%d\n", a[n]); //printf("sum = %d\n", sum-1); } return 0; } 欧拉函数和最大公约数的组合应用 这种问题一般都是给出限制条件：给你一个数N（N一般很大）,使得在1~N之间能够找到X使得X满足gcd（X , N ）>= M，然后求解相关的问题。 分析：这是一种统计类型的问题。比较容易想到的解法就是枚举gcd(X,N)的值，对于枚举到的某个gcd(X,N) 的值d，如果令N = p * d，X = q * d，那么如果gcd(X,N) = d，一定有p，q 互质，又有X <= N，则q <= p，而这样的q 的个数正好对应p的欧拉函数，即满足gcd(X,N) = d 的X的个数为N/d 的欧拉函数值。 应用1：给出N和M，求有多少个X满足1<=X<=N 并且(X,N)>=M. 分析：对于这个问题，因为只需要求出满足题意的X的个数，所以可以枚举最大公约数d，而满足gcd(X,N) = d 的X的个数就是N/d的欧拉函数，把这些d对应的N/d的欧拉函数值求和即可。 #include #include int euler(int n) { int m = (int)sqrt(n+0.5); int ans = n; for(int i = 2; i <= m; i++) if(n % i == 0) { ans = ans / i * (i - 1); while(n % i == 0) n /= i; } if(n > 1) ans = ans / n * (n-1); return ans; } int main() { int t, n, m; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); int ans = 0; for(int i = 1; i * i <= n; i++) //枚举最大公因数 { if(n % i == 0) { if(i >= m) ans += euler(n/i); if(i * i != n && n / i >= m) ans += euler(i); } } printf("%d\n", ans); } return 0; } 应用2：给你一个数N,使得在1~N之间能够找到x使得x满足gcd（x, N）>= M，求解gcd(x,N)的和。分析：这个题要求gcd(X,N)的和，因为上一题已经求出了满足题意的个数，所以只需要在上一个应用的基础上乘以最大公约数就是最终答案。 #include #include typedef long long LL; LL euler(LL n) //n的欧拉函数值 { LL ans = n; for(LL i = 2; i * i <= n; i++) if(n % i == 0) { ans = ans / i * (i - 1); while(n % i == 0) n /= i; } if(n > 1) ans = ans / n * (n-1); return ans; } int main() { LL n, m; while(~scanf("%lld%lld",&n,&m)) { LL ans = 0; LL tmp = (LL)sqrt(n+0.5); for(LL i = 1; i <= tmp; i++) //枚举最大公因数 { if(n % i == 0) { if(i >= m) ans += euler(n/i) * i; if(i * i != n && n / i >= m) ans += euler(i) * (n / i); } } printf("%lld\n", ans); } return 0; } 应用3：给出N和M，求所有满足1<=X<=N and (X,N)>=M的X的和。 分析：这个题和前两个题基本上一样，只需要在枚举最大公约数d时，求出gcd(X,N) = d 的所有X的和即可。根据上面可以得出：满足条件的X个数有euler（N/d）个，所以只需要求出不超过N/d且与N/d互素的那些数的和，然后乘以d就是最大公约数为d时对应的部分结果。而不超过N/d且与N/d互素的那些数的和= N/d * euler(N/d) / 2,注意当N/d = 1时，结果是1而不是0。了解了这些，就可以解决这个题了。 除了1、2以外，所有数的欧拉函数都是偶数。 如果k <= n 并且(k,n) = 1, 那么(n-k, n) = 1; #include #define mod 1000000007 typedef long long LL; LL euler(LL n) //n的欧拉函数值 { LL ans = n; for(LL i = 2; i * i <= n; i++) if(n % i == 0) { ans = ans / i * (i - 1); while(n % i == 0) n /= i; } if(n > 1) ans = ans / n * (n-1); return ans; } LL euler_sum(LL n) //求和n互素的数的和{ if(n == 1) return 1; return n * euler(n) / 2; } int main() { int t; LL n, m; scanf("%d",&t); while(t--) { scanf("%lld%lld",&n,&m); LL ans = 0; for(LL i = 1; i * i <= n; i++) //枚举最大公因数 { if(n % i == 0) { if(i >= m) ans = (ans + euler_sum(n/i) * i) % mod; if(i * i != n && n / i >= m) ans = (ans + euler_sum(i) * (n / i)) % mod; } } printf("%lld\n", ans); } return 0; } 字典树 /* 动物统计：给出动物的名字，统计出现最多的动物*/ #include #include struct node { int num; struct node *next[26]; }; struct node *root; node *build() { struct node *p=(node *)malloc(sizeof(node)); p->num=1; for(int i=0; i<26; i++) p->next[i]=NULL; return p; } int insert(char *s) { struct node *p=root; int len=strlen(s); for(int i=0; i { if(p->next[s[i]-'a']==NULL) p->next[s[i]-'a']=build(); p=p->next[s[i]-'a']; } return p->num++; } int main() { int n,i,max=-1,a; char str[10],s[10]; root=build(); scanf("%d",&n); for(i=0; i { scanf("%s",str); a=insert(str); if(a>max) { max=a; strcpy(s,str); } 电子科技大学 期末解题报告 课程：《ACM算法与程序设计》学院： 学号： 姓名： 报告成绩：教师签名： 讨厌的青蛙 1、链接地址 https://www.doczj.com/doc/c916032573.html,/problem?id=2812 2、问题描述 在韩国，有一种小的青蛙。每到晚上，这种青蛙会跳越稻田，从而踩踏稻子。农民在早上看到被踩踏的稻子，希望找到造成最大损害的那只青蛙经过的路径。每只青蛙总是沿着一条直线跳越稻田，而且每次跳跃的距离都相同，如图1所示。稻田里的稻子组成一个栅格，每棵稻子位于一个格点上，如图2所示。而青蛙总是从稻田的一侧跳进稻田，然后沿着某条直线穿越稻田，从另一侧跳出去，如图3所示。 问题描述 青蛙的每一跳都恰好踩在一棵水稻上，将这棵水稻拍倒。可能会有多只青蛙从稻田穿越，有些水稻被多只青蛙踩踏，如图4所示。当然，农民所见到的是图5中的情形，看不到图4中的直线。 根据图5，农民能够构造出青蛙穿越稻田时的行走路径，并且只关心那些在穿越稻田时至少踩踏了3 棵水稻的青蛙。因此，每条青蛙行走路径上至少包括3 棵被踩踏的水稻。而在一条青蛙行走路径的直线上，也可能会有些被踩踏的水稻不属于该行走路径。在图5中，格点(2, 1)、(6, 1)上的水稻可能是同一只青蛙踩踏的，但这条线上只有两棵被踩踏的水稻，因此不能作为一条青蛙行走路径；格点(2, 3)、(3, 4)、(6, 6)在同一条直线上，但它们的间距不等，因此不能作为一条青蛙行走路径；格点(2, 1)、(2, 3)、(2, 5)、(2, 7)是一条青蛙行走路径，该路径不包括格点(2, 6)。请你写一个程序，确定在所有的青蛙行路径中，踩踏水稻棵数最多的路径上有多少棵水稻被踩踏。例如，图5的答案是7，因为第6 行上全部水稻恰好构成一条青蛙行走路径。 题目来源：福州大学acm网站 代码：fpcdq 一、入门 熟悉ACM竞赛规则以及程序提交注意事项 例题： Problem 1000 A+B Problem Time Limit: 1000 mSec Memory Limit : 32768 KB Problem Description Calculate a + b. Input The input will consist of a series of pairs of integers a and b,separated by a space, one pair of integers per line. Output For each pair of input integers a and b you should output the sum of a and b in one line,and with one line of output for each line in input. Sample Input 1 5 2 3 Sample Output 6 5 My answer： #include acm论文模板范文 ACM是全世界领域影响力最大的专业学术组织。而acm模板，你 们知道吗?这是 ___为大家了两篇acm论文，这样你们对模板会有直观的印象! [摘要] 鉴于ACM大学生程序设计竞赛(ACM/ICPC)在人才选拔和培养方面的显著作用，如何将ACM/ICPC竞赛活动嵌入常规教学，创新教学模式，结合专业教学，加强训练管理，提高培训效益，已成为人们关注的问题。针对这一应用需求，本文设计并开发了基于ACM/ICPC机制的大学生程序设计培训管理系统。系统采用B/S架构，以SQL Server xx作为后台管理数据库，Visual Studio 和https://www.doczj.com/doc/c916032573.html,为前端开发工具。在分析系统功能的基础上，着重阐述了 该系统设计与实现的关键技术。该系统实际运行稳定、可靠，为开展ACM/ICPC竞赛培训和教学提供了一种有效管理途径。 [关键词] ACM/ICPC;培训管理系统;Web开发;https://www.doczj.com/doc/c916032573.html,;数据库技 术 doi ： 10 . 3969 / j . issn . 1673 - 0194 . xx . 03. 015 [] TP311 [] A [] 1673 - 0194(xx)03- 0028- 03 1 引言 ACM国际大学生程序设计竞赛(ACM International Collegiate Programming Contest， ACM ICPC) 由美国计算机协会(ACM)主办，始于1970年，至今已经有40多年的，是世界公认的规模最大、水平最高、影响广泛的国际大学生程序设计竞赛，竞赛优胜者是各大IT企业和科研院所青睐和优先选拔的人才[1]。近些年来，伴随着ACM/ICPC大学生程序设计竞赛在国内如火如荼地开展，计算机界更加关注在人才培养方面，如何科学合理地引入、借鉴ACM/ICPC竞赛训练，将ACM/ICPC竞赛活动与常规专业课程教学有机结合起来，突破传统教学内容和，以有效培养学生的学习能力、创新意识和综合素质。这其中，如何有效组织开展ACM/ICPC竞赛训练，加强培训管理，提高培训效益，亦是人们关注的热点问题。 但就目前情况来看，组织开展此项竞赛活动的训练指导或教学培训还没有一个成熟通用的、基于ACM/ICPC竞赛机制的ACM/ICPC 训练和活动的教学管理平台。具体表现在：(1)尽管一些知名院校搭建了自己的在线测试平台[2-3]，但由于大多采用英文表述问题，对于水平不高的低年级本科生和专科学生来说，在翻译题目和理解内容方面会出现偏差，导致在这些平台上进行在线模拟测验的效果并不理想;(2)很多网站虽然提供了ACM/ICPC竞赛的相关资料，比如网上题库、相关赛题的题解等，但这些资料在网上分布得比较分散，使 ACM模板 [ 王克纯 2020年9月21日 最大子串 int maxSum(int * a,int n) { int sum = a[0],b = 0; for(int i=0;i 1、0-1背包 #include } } m[0][c]=m[1][c]; if(c>=w[0]) { if(m[0][c] 1111111杭电： 1000 A + B Problem (4) 1001 Sum Problem (5) 1002 A + B Problem II (6) 1005 Number Sequence (8) 1008 Elevator (9) 1009 FatMouse' Trade (11) 1021 Fibonacci Again (13) 1089 A+B for Input-Output Practice (I) (14) 1090 A+B for Input-Output Practice (II) (15) 1091 A+B for Input-Output Practice (III) (16) 1092 A+B for Input-Output Practice (IV) (17) 1093 A+B for Input-Output Practice (V) (18) 1094 A+B for Input-Output Practice (VI) (20) 1095 A+B for Input-Output Practice (VII) (21) 1096 A+B for Input-Output Practice (VIII) (22) 1176 免费馅饼 (23) 1204 糖果大战 (25) 1213 How Many Tables (26) 2000 ASCII码排序 (32) 2001 计算两点间的距离 (34) 2002 计算球体积 (35) 2003 求绝对值 (36) 2004 成绩转换 (37) 2005 第几天？ (38) 2006 求奇数的乘积 (40) 2007 平方和与立方和 (41) 2008 数值统计 (42) 2009 求数列的和 (43) 2010 水仙花数 (44) 2011 多项式求和 (46) 2012 素数判定 (47) 2014 青年歌手大奖赛_评委会打分 (49) 2015 偶数求和 (50) 2016 数据的交换输出 (52) 2017 字符串统计 (54) 2019 数列有序! (55) 2020 绝对值排序 (56) 2021 发工资咯：） (58) 2033 人见人爱A+B (59) 2037 今年暑假不AC (61) 2039 三角形 (63) 2040 亲和数 (64) 1、KMP 算法 /* * next[]的含义：x[i-next[i]...i-1]=x[0...next[i]-1] * next[i]为满足x[i-z...i-1]=x[0...z-1]的最大z值（就是x的自身匹配） */ void kmp_pre(char x[],int m,int next[]) { int i,j; j=next[0]=-1; i=0; while(i ACM Word Template for SIG Site 1st Author 1st author's affiliation 1st line of address 2nd line of address Telephone number, incl. country code 1st author's E-mail address 2nd Author 2nd author's affiliation 1st line of address 2nd line of address Telephone number, incl. country code 2nd E-mail 3rd Author 3rd author's affiliation 1st line of address 2nd line of address Telephone number, incl. country code 3rd E-mail ABSTRACT A s network speed continues to grow, new challenges of network processing is emerging. In this paper we first studied the progress of network processing from a hardware perspective and showed that I/O and memory systems become the main bottlenecks of performance promotion. Basing on the analysis, we get the conclusion that conventional solutions for reducing I/O and memory accessing latencies are insufficient for addressing the problems. Motivated by the studies, we proposed an improved DCA combined with INIC solution which has creations in optimized architectures, innovative I/O data transferring schemes and improved cache policies. Experimental results show that our solution reduces 52.3% and 14.3% cycles on average for receiving and transmitting respectively. Also I/O and memory traffics are significantly decreased. Moreover, an investigation to the behaviors of I/O and cache systems for network processing is performed. And some conclusions about the DCA method are also presented. Keywords Keywords are your own designated keywords. 1.INTRODUCTION Recently, many researchers found that I/O system becomes the bottleneck of network performance promotion in modern computer systems [1][2][3]. Aim to support computing intensive applications, conventional I/O system has obvious disadvantages for fast network processing in which bulk data transfer is performed. The lack of locality support and high latency are the two main problems for conventional I/O system, which have been wildly discussed before [2][4]. To overcome the limitations, an effective solution called Direct Cache Access (DCA) is suggested by INTEL [1]. It delivers network packages from Network Interface Card (NIC) into cache instead of memory, to reduce the data accessing latency. Although the solution is promising, it is proved that DCA is insufficient to reduce the accessing latency and memory traffic due to many limitations [3][5]. Another effective solution to solve the problem is Integrated Network Interface Card (INIC), which is used in many academic and industrial processor designs [6][7]. INIC is introduced to reduce the heavy burden for I/O registers access in Network Drivers and interruption handling. But recent report [8] shows that the benefit of INIC is insignificant for the state of the art 10GbE network system. In this paper, we focus on the high efficient I/O system design for network processing in general-purpose-processor (GPP). Basing on the analysis of existing methods, we proposed an improved DCA combined with INIC solution to reduce the I/O related data transfer latency. The key contributions of this paper are as follows: ?Review the network processing progress from a hardware perspective and point out that I/O and related last level memory systems have became the obstacle for performance promotion. ?Propose an improved DCA combined with INIC solution for I/O subsystem design to address the inefficient problem of a conventional I/O system. ?Give a framework of the improved I/O system architecture and evaluate the proposed solution with micro-benchmarks. ?Investigate I/O and Cache behaviors in the network processing progress basing on the proposed I/O system. The paper is organized as follows. In Section 2, we present the background and motivation. In Section 3, we describe the improved DCA combined INIC solution and give a framework of the proposed I/O system implementation. In Section 4, firstly we give the experiment environment and methods, and then analyze the experiment results. In Section 5, we show some related works. Finally, in Section 6, we carefully discuss our solutions with many existing technologies, and then draw some conclusions. 2.Background and Motivation In this section, firstly we revise the progress of network processing and the main network performance improvement bottlenecks nowadays. Then from the perspective of computer architecture, a deep analysis of network system is given. Also the motivation of this paper is presented. 2.1Network processing review Figure 1 illustrates the progress of network processing. Packages from physical line are sampled by Network Interface Card (NIC). NIC performs the address filtering and stream control operations, then send the frames to the socket buffer and notifies #include 目录 1.最小生成树 (2) 2.最短路算法 (7) 3.素数打表 (11) 4.最大匹配 (12) 5.线段树（敌兵布阵） (14) 6．线段树（逆序树） (16) 7.树形dp (18) 8.树状数组（段跟新） (20) 9.Kmp模板 (22) 10.线段树（点跟新） (26) 11.强连通 (28) 12.最小割 (31) 13.单源最短路（spfa） (34) 14.三分查找 (36) 15.字典树（统计难题） (38) 16.最大流入门题1273 (40) 17.状态压缩 (43) 18.匈牙利（HDU 2063）（最大匹配） (45) 19.凸包（HDU1348） (47) 20.树状数组(HDU1166) (50) 21.强连通 (52) 22.前向星 (55) 23.矩阵 (58) 24.并查集 (60) 25. SORT (61) 26. STL (63) 27. LCA (HDU 2874) (67) 28. 01背包 (70) 29. 状态压缩代码： (72) 30. 快速幂 (74) 31.矩阵快速幂 (75) 32.GCD & LCM (77) 33.ACM小技巧： (78) 34. /** 大数（高精度）求幂**/ (80) 35. /** 大数除法与求余**/ (82) 36. /** 大数阶乘**/ (84) 37. /** 大数乘法**/ (85) 38. /** 大数累加**/ (86) 1.最小生成树 要连通n个城市需要n－1条边线路。可以把边上的权值解释为线路的造价。则最小生成树表示使其造价最小的生成树。 prim算法（矩阵形式）： #define inf 0x3f3f3f3f int prim(int n,int sta)//n表示有n个顶点，sta表从sta这个顶点出发生成最小生成树{ int mark[M],dis[M]; int i,sum = 0; //sum是总的最小生成树边权值 for (i = 0;i < n;i ++) //初始化dis[i] 表从顶点sta到点i的权值 { dis[i] = mat[sta][i]; mark[i] = 0; } mark[sta] = 1; //sta 这个顶点加入最小生成树中 for (i = 1;i < n;i ++) //循环n-1次，每次找出一条最小权值的边 n个点的图 { //只有n-1条边 int min = inf; //inf 表无穷大 for (j = 0;j < n;j ++)//找出当前未在最小生成树中边权最小的顶点 if (!mark[j] && dis[j] < min) min = dis[j],flag = j; mark[flag] = 1; //把该顶点加入最小生成树中 sum += dis[flag]; //sum加上其边权值 for (j = 0;j < n;j ++) //以falg为起点更新到各点是最小权值 if (dis[j] > mat[flag][j]) dis[j] = mat[flag][j]; } return sum; //返回边权总和 } prim算法（边表形式）： struct Edge//frm为起点,to为终点，w为边权，nxt指向下一个顶点 { // int frm; int to,w,nxt; }edge[M]; int vis[M],head[M],dis[M]; void addedge (int cu,int cv,int cw)//生成边的函数 ACM Word Template for SIGCOMM Submissions 1st Author 1st author's affiliation 1st line of address 2nd line of address Telephone number, incl. country code 1st author's email address 2nd Author 2nd author's affiliation 1st line of address 2nd line of address Telephone number, incl. country code 2nd E-mail 3rd Author 3rd author's affiliation 1st line of address 2nd line of address Telephone number, incl. country code 3rd E-mail ABSTRACT In this paper, we describe the formatting guidelines for ACM SIG Proceedings. Categories and Subject Descriptors D.3.3 [Programming Languages]: Language Contructs and Features –abstract data types, polymorphism, control structures. This is just an example, please use the correct category and subject descriptors for your submission.The ACM Computing Classification Scheme: https://www.doczj.com/doc/c916032573.html,/class/1998/ General Terms Your general terms must be any of the following 16 designated terms: Algorithms, Management, Measurement, Documentation, Performance, Design, Economics, Reliability, Experimentation, Security, Human Factors, Standardization, Languages, Theory, Legal Aspects, Verification. Keywords Keywords are your own designated keywords. 1.INTRODUCTION The proceedings are the records of the conference. ACM hopes to give these conference by-products a single, high-quality appearance. To do this, we ask that authors follow some simple guidelines. In essence, we ask you to make your paper look exactly like this document. The easiest way to do this is simply to down-load a template from [2], and replace the content with your own material. 2.PAGE SIZE All material on each page should fit within a rectangle of 18 x 23.5 cm (7" x 9.25"), centered on the page, beginning 1.9 cm (0.75") from the top of the page and ending with 2.54 cm (1") from the bottom. The right and left margins should be 1.9 cm (.75”). The text should be in two 8.45 cm (3.33") columns with a .83 cm (.33") gutter. 3.TYPESET TEXT 3.1Normal or Body Text Please use a 10-point Times Roman font, or other Roman font with serifs, as close as possible in appearance to Times Roman in which these guidelines have been set. The goal is to have a 10-point text on 12-point leading, as you see here. Please use sans-serif or non-proportional fonts only for special purposes, such as distinguishing source code text. If Times Roman is not available, try the font named Computer Modern Roman. On a Macintosh, use the font named Times. Right margins should be justified, not ragged. 3.2Title and Authors The title (Helvetica 18-point bold), authors' names (Helvetica 12-point) and affiliations (Helvetica 10-point) run across the full width of the page –one column wide. We also recommend phone number (Helvetica 10-point) and e-mail address (Helvetica 12-point). See the top of this page for three addresses. If only one address is needed, center all address text. For two addresses, use two centered tabs, and so on. For more than three authors, you may have to improvise.1 3.3First Page Copyright Notice Please leave 3.81 cm (1.5") of blank text box at the bottom of the left column of the first page for the copyright notice. 3.4Subsequent Pages For pages other than the first page, start at the top of the page, and continue in double-column format. The two columns on the last page should be as close to equal length as possible. 1If necessary, you may place some address information in a footnote, or in a named section at the end of your paper. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Conference’04, Month 1–2, 2004, City, State, Country. Copyright 2004 ACM 1-58113-000-0/00/0004…$5.00.《ACM算法与程序设计》解题报告模板
ACM题目整理
acm论文模板范文
我的ACM算法模板
ACM动态规划问题简易模板(C++可编译)
整理出ACM所有题目及答案
整理acm模板
ACM的论文写作格式标准
acm-计算几何模板
ACM比赛模板
ACM Word Template for SIGCOMM Submissions
相关主题
文本预览