ACM中使用JAVA
ACM题目整理
题目来源：福州大学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模板 [ 王克纯 2020年9月21日
最大子串 int maxSum(int * a,int n) { int sum = a[0],b = 0; for(int i=0;i 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)//生成边的函数 <字符串> KMP #include i = j = 0; while (j < n) { while (i > -1 && x[i] != y[j]) { i = kmpNext[i]; } i++; j++; if (i >= m) { //OUTPUT(j - i); /* found one, do next if required*/ tot++; i = kmpNext[i]; } } return tot; } int main() { int T; //freopen("in.txt","r",stdin); scanf("%d\n",&T); while(T--) { gets(t); gets(s); printf("%d\n",KMP(t,strlen(t),s,strlen(s))); } return 0; } 通配符匹配 int wildcard(const char * pat, const char * str) { while(*str && *pat) { if(*pat=='?') { if(wildcard(pat+1, str+1)) return 1; str++; pat++; ACM 算法模板集Contents 一.常用函数与STL 二.重要公式与定理 1. Fibonacci Number 2. Lucas Number 3. Catalan Number 4. Stirling Number(Second Kind) 5. Bell Number 6. Stirling's Approximation 7. Sum of Reciprocal Approximation 8. Young Tableau 9. 整数划分 10. 错排公式 11. 三角形内切圆半径公式 12. 三角形外接圆半径公式 13. 圆內接四边形面积公式 14. 基础数论公式 三.大数模板，字符读入 四.数论算法 1. Greatest Common Divisor最大公约数 2. Prime素数判断 3. Sieve Prime素数筛法 4. Module Inverse模逆元 5. Extended Euclid扩展欧几里德算法 6. Modular Linear Equation模线性方程(同余方程) 7. Chinese Remainder Theorem中国余数定理(互素于非互素) 8. Euler Function欧拉函数 9. Farey总数 9. Farey序列构造 10. Miller_Rabbin素数测试，Pollard_rho因式分解 五.图论算法 1. 最小生成树(Kruscal算法) 2. 最小生成树(Prim算法) 3. 单源最短路径(Bellman-ford算法) 4. 单源最短路径(Dijkstra算法) 5. 全源最短路径(Folyd算法) 6. 拓扑排序 7. 网络预流和最大流 8. 网络最小费用最大流 9. 网络最大流(高度标号预流推进) 10. 最大团 11. 二分图最大匹配(匈牙利算法) 12. 带权二分图最优匹配(KM算法) 13. 强连通分量(Kosaraju算法) 14. 强连通分量(Gabow算法) 15. 无向图割边割点和双连通分量 16. 最小树形图O(N^3) 17. 最小树形图O(VE) 六.几何算法 1. 几何模板 2. 球面上两点最短距离 3. 三点求圆心坐标 4. 三角形几个重要的点 七.专题讨论 1. 树状数组 2. 字典树 3. 后缀树 4. 线段树 5. 并查集 6. 二叉堆 7. 逆序数(归并排序) 8. 树状DP 9. 欧拉路 10. 八数码 11. 高斯消元法 12. 字符串匹配(KMP算法) 13. 全排列,全组合 14. 二维线段树 15. 稳定婚姻匹配 16. 后缀数组 17. 左偏树 18. 标准RMQ-ST 19. 度限制最小生成树 20. 最优比率生成树(0/1分数规划) 21. 最小花费置换 22. 区间K大数 23. LCA - RMQ-ST 目录 一、数学问题 (4) 1.精度计算——大数阶乘 (4) 2.精度计算——乘法（大数乘小数） (4) 3.精度计算——乘法（大数乘大数） (5) 4.精度计算——加法 (6) 5.精度计算——减法 (7) 6.任意进制转换 (8) 7.最大公约数、最小公倍数 (9) 8.组合序列 (10) 9.快速傅立叶变换（FFT） (10) 10.Ronberg 算法计算积分 (12) 11.行列式计算 (14) 12.求排列组合数 (15) 13.求某一天星期几 (15) 14.卡特兰(Catalan) 数列原理 (16) 15.杨辉三角 (16) 16.全排列 (17) 17.匈牙利算法----最大匹配问题 (18) 18.最佳匹配KM 算法 (20) 二、字符串处理 (22) 1.字符串替换 (22) 2.字符串查找 (23) 3.字符串截取 (24) 4.LCS-最大公共子串长度 (24) 5.LCS-最大公共子串长度 (25) 6.数字转换为字符 (26) 三、计算几何 (27) 1.叉乘法求任意多边形面积 (27) 2.求三角形面积 (27) 3.两矢量间角度 (28) 4.两点距离（2D、3D） (28) 5.射向法判断点是否在多边形内部 (29) 6.判断点是否在线段上 (30) 7.判断两线段是否相交 (31) 8.判断线段与直线是否相交 (32) 9.点到线段最短距离 (32) 10.求两直线的交点 (33) 11.判断一个封闭图形是凹集还是凸集 (34) 12.Graham 扫描法寻找凸包 (35) 13.求两条线段的交点 (36) 四、数论 (37) 1.x 的二进制长度 (37) 2.返回x 的二进制表示中从低到高的第i 位 (38) 3.模取幂运算 (38) 4.求解模线性方程 (39) 5.求解模线性方程组(中国余数定理) (39) 6.筛法素数产生器 (40) 7.判断一个数是否素数 (41) 8.求距阵最大和 (42) 8.求一个数每一位相加之和 (43) 10.质因数分解 (43) 11.高斯消元法解线性方程组 (44) 五、图论 (45) 1.Prim 算法求最小生成树................................................. 45 2.Dijkstra 算法求单源最短路径.. (46) 3.Bellman-ford 算法求单源最短路径 (47) 4.Floyd-Warshall 算法求每对节点间最短路径 (48) 5.解欧拉图 (49) 六、排序/查找 (50) 1.快速排序 (50) 2.希尔排序 (51) 3.选择法排序 (52) 4.二分查找 (52) 七、数据结构 (53) 1.顺序队列 (53) 2.顺序栈 (56) 3.链表 (59) 4.链栈 (63) 5.二叉树 (66) 八、高精度运算专题 (68) 1.专题函数说明 (68) 2.高精度数比较 (69) 3.高精度数加法 (69) 4.高精度数减法 (70) 5.高精度乘10 (71) 6.高精度乘单精度 (71) 7.高精度乘高精度 (72) 8.高精度除单精度 (72) 9.高精度除高精度 (73) 九、标准模板库的使用 (74) 1.计算求和 (74) 2.求数组中的最大值 (76) 3. sort 和qsort (76) 十、其他 (78) 1.运行时间计算 (78) 目录 目录 (1) 一．扩展的欧几里德和不定方程的解 (2) 二．中国同余定理 (3) 三．原根 (5) 四．积性函数 (6) 五．欧拉函数性质 (7) 六．线性求1-max的欧拉函数值 (9) 七．求单个欧拉函数，求最小的x(phi（n）%x==0),使得2^x =1(mod n) (10) 一．扩展的欧几里德和不定方程的解 解不定方程ax + by = n的步骤如下: (1)计算gcd(a, b). 若gcd(a, b)不能整除n，则方程无整数解；否则，在方程的两边同除以gcd(a, b)，得到新的不定方程a'x + b'y = n'，此时gcd(a', b') = 1 (2)求出不定方程a'x + b'y = 1的一组整数解x0, y0，则n'x0，n'y0是方程a'x + b'y = n'的一组整数解。 (3)根据扩展欧几里德定理，可得方程a'x + b'y = n'的所有整数解为： x = n'x0 + b't y = n'y0 - a't (t为整数) 这也就是方程ax + by = n的所有整数解 利用扩展的欧几里德算法，计算(a, b)和满足gcd = (a, b) = ax0 + by0的x0和y0，也就是求出了满足a'x0 + b'y0 = 1的一组整数解。因此可得： x = n/gcd * x0 + b/gcd * t y = n/gcd * y0 - a/gcd * t (t是整数) int extend_Euclid(int a, int b, int &x, int &y) { if (b == 0){ x = 1; y = 0; return a; } int gcd= extend_Euclid ( b, a % b, x, y ); int temp = x; x = y; y = temp - (a / b) * y; return gcd; } 最小表示法 最小表示法在解决判断“同构”一类问题中有很大作用。 循环同构问题：给出两个串：s1 = “babba”和s2 = “bbaba”，其中两者均看成环状的，即首尾是相接的，问：从s1的哪里断开可以得到和s2一样的串或者两者不会相同？本题就是从s1的第2个字符’a’后面断开，可以得到与s2一样的串。这个问题就是同构问题。 1.朴素算法(O(nm))：即尝试s1的n个断开点，与s2进行比较，如果相同则找到同构位置，否则找不到。该算法仅适用于n, m规模较小情况，对于n, m 都在10000规模的长度，明显速度太慢。 2.转换为模式匹配：对于此类问题，已经有一个很好的转换思路了，即：首先构造新的模型：S=s1+s1为主串，s2为模式串。如果s1和s2是循环同构的，那么s2就一定可以在S中找到匹配。否则找不到匹配则两则不能同构。而在S中寻找s2的匹配是有很多O(N+M)级的算法了，KMP算法就是这样一个优秀的算法，所以本问题转换为模式匹配后应用KMP算法，可以在O(n+m)的时间内获得问题的解。 3.下面再来看看“最小表示法”在此类问题中的应用（算法思路来源于国家队的一位队员），它也可以在O(n+n)时间内求解，更大的优势还有无需KMP算法的Next数组，仅需要两个指针即可。 解析过程： 问题：有两列数a1,a2…an和b1,b2…bn ，不记顺序，判断它们是否相同。eg：{an} = {2, 3, 5, 7}；{bn} = {2, 7, 5 3}。一眼可见两者是相同的，但是对于计算机来说，如果采用枚举算法，那么比较次数将是：n*(n-1)*(n-2)….*2*1 = n! 量级。阶乘增长之快，时间上是无法忍受的。抓住问题的本质：如果两列数相同，那么它们排序之后从头到尾肯定一样！则问题在O(nlogn)时间解决。可见这个问题的本质就在于排序（非降序）之后的序列是原序列的“最小表示”，如果两个序列的“最小表示”相同则两者就相同，否则就不相同。 启示：当两个对象有多种形式且需判断它们在某种变换规则下是否相同时，可转换为比较可以通过变换规则得到的所有表示的“最小表示”是否相同。例如本问题是不计顺序的规则，最小表示就是非降序排列后的序列。当然对于其它问题就不能简单的排序了，需要满足“在变换规则下可以达到的表示形式”。 a.首先定义一个变换规则f，判断两个事物s和t是否互为f本质相同，方法就是：将s，t转换为规则f下的最小表示形式，再比较是否相同。 b.返回到本节一开始提到的字符串循环同构问题，规则f就是“循环移动”，最直接最简单的方法就是分别求出s1, s2的最小表示，再比较两者是否相同，但是可以发现这明显也是一个O(n^2)思路。 c.换一种思路，令Min(s)返回值为：从s的第Min(s)个字符引起的s的一个循环表示的最小表示，若有多个值则返回下标最小的一个。例如s = {bbbaab}，那么Min(s) = 3 --下标从0算起。Min(s)的求法在后面部分具体阐述，这个问题仅仅用到这个概念，不必直接求，因为当找到循环同构时实际就是Min(s)。 d.先类似于模式匹配方法将两者加倍：u = s1 + s1，w = s2 + s2，指针i，j 分别指向u, w的第一个位置0，i，j指针滑动可以得到两种情况： <1>.若i，j分别指向Min(s1)和Min(s2)时，一定有u[i…i+|s1|-1] = w[j… //别人总结的，确实很多，但有信心就能学完！ 一.基本算法: (1)枚举.(poj1753,poj2965) (2)贪心.(poj1328,poj2109,poj2586) (3)递归和分治法. (4)递推. (5)构造法.(poj3295) (6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996) 二.图算法: (1)图的深度优先遍历和广度优先遍历. (2)最短路径算法.(dijkstra,bellman-ford,floyd,heap+dijkstra) (poj1860,poj3259,poj1062,poj2253,poj1125,poj2240) (3)最小生成树算法.(prim,kruskal) (poj1789,poj2485,poj1258,poj3026) (4)拓扑排序.(poj1094) (5)二分图的最大匹配(匈牙利算法).(poj3041,poj3020) (6)最大流的增广路算法(KM算法).(poj1459,poj3436) 三.数据结构. (1)串.(poj1035,poj3080,poj1936) (2)排序(快排、归并排(与逆序数有关)、堆排).(poj2388,poj2299) (3)简单并查集的应用. (4)哈希表和二分查找等高效查找法.(数的Hash,串的Hash) (poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503) (5)哈夫曼树.(poj3253) (6)堆. (7)trie树(静态建树、动态建树).(poj2513) 四.简单搜索 (1)深度优先搜索.(poj2488,poj3083,poj3009,poj1321,poj2251) (2)广度优先搜索.(poj3278,poj1426,poj3126,poj3087.poj3414) (3)简单搜索技巧和剪枝.(poj2531,poj1416,poj2676,1129) 五.动态规划 (1)背包问题. (poj1837,poj1276) (2)型如下表的简单DP(可参考lrj的书page149): 1.E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533) 2.E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最长公共子序列) (poj3176,poj1080,poj1159) 3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最优二分检索树问题) 六.数学 (1)组合数学: 1.加法原理和乘法原理. 2.排列组合. 3.递推关系. (POJ3252,poj1850,poj1019,poj1942) (2)数论.整理出ACM所有题目及答案
整理acm模板
ACM的论文写作格式标准
acm-计算几何模板
ACM比赛模板
字符串ACM模板
上海交通大学ACM算法模板gai
ACM大赛必备_常用函数整理_ACM模板
ACM数论模板
ACM-ICPC之最小表示法模板
(整理)ACM大量习题题库及建议培养计划.