ACM论文
哈密顿回路问题
一、简介
哈密顿图是一个无向图，由天文学家哈密顿提出，由指定的起点前往指定的终点，途中经过所有其他节点且只经过一次。在图论中是指含有哈密顿回路的图，闭合的哈密顿路径称作哈密顿回路，含有图中所有顶点的路径称作哈密顿路径。
二、判定方法
1、包含个顶点的图, 如果任意两个顶点的度数之和都不小于n-1（即大于等于n-1）, 则存在哈密尔顿通路。
2、包含个顶点的图, 如果任意两个顶点的度数之和都不小于n（即大于等于n）, 则存在哈密尔顿回路。
三、问题引入：旅行商问题
“旅行商问题”常被称为“旅行推销员问题”，是指一名推销员要拜访多个地点时，如何找到在拜访每个地点一次后再回到起点的最短路径。规则虽然简单，但在地点数目增多后求解却极为复杂。以42个地点为例，如果要列举所有路径后再确定最佳行程，那么总路径数量之大，几乎难以计算出来。多年来全球数学家绞尽脑汁，试图找到一个高效的算法TSP问题在物流中的描述是对应一个物流配送公司，欲将n个客户的订货沿最短路线全部送到。如何确定最短路线。
四、现有解决方法：
1、枚举法
枚举法：枚举法主要采用深度优先策略，由于运算量太大不做介绍。
回溯法：假定集合Si的大小是mi，于是就有m=m1m2…Mn个n-元组可能满足函数P。所谓硬性处理是构造这m个n-元组并逐一测试它们是否满足P，从而找出该问题的所有最优解。而回溯法的基本思想是，不断地用修改过的函数Pi(x1,…Xi)（即限界函数）去测试正在构造中的n-元组的部分向量(x1,…,Xi)，看其是否可能导致最优解。如果判定(x1,…,Xi)不可能导致最优解，那么就可能要测试的后n-i个元素组成的向量一概略去。
分支界限法：分支限界法是在生成当前E-结点全部儿子之后再生成其它活结点的儿子，且用限界函数帮助避免生成不包含答案结点子树的状态空间的检索方法。在总的原则下，根据对状态空间树中结点检索的次序的不同又将分支限界设计策路分为数种不同的检索方法。在求解旅行商问题时，程序中采用FIFO检索（First In First Out），它的活结点表采用一张先进先出表（即队列）。可以看出，分支限界法在两个方面加速了算法的搜索速度，一是选择要扩展的节点时，总是选择选择一个最小成本的结点，尽可能早的进入最有可能成为最优解的分支；二是扩展节点的过程中，舍弃导致不可行解或导致非最优解的子结点。
贪心法：贪心法是一种改进了的分级处理方法。它首先旅行商问题描述，选取一种度量标准。然后按这种度量标准对n个输入城市排序，并按序一次输入一个城
市。如果这个输入和当前已构成在这种量度意义下的部分最优解加在一起不能产生一个可行解，则不把这个城市加入到这部分解中。这种能够得到某种量度意义下的最优解的分级处理方法成为贪心方法。
五、问题简化
问题：假设有12345，5个城市，城市与城市相通设为1，不同设为0，可以构建5*5的邻接矩阵，输入为这个邻接矩阵，输出所有可行的哈密顿回路。
简化后的问题忽略了权值，比起旅行商问题要简单很多，变成了纯粹的哈密顿回路问题，下面我选取了回溯法来解题
六、问题分析
回溯法最常见的应用就是杨鹏老师上课讲的迷宫问题，它一开始选取某一个初始位置不断向前探索下一个目标，当走到下一个地方走不下去了（其实就是不满足约束条件），就回头从上一个地方重新选择探索，就这样不停的回溯，探索，回溯，探索，直到找到满足条件的路为止。
对于这个问题我觉得可以用递归来实现，可以编写一个back函数,从第一个结点开始不断寻找下一个结点并加入一个路径数组，一直递归到找不到下一个和它相邻的结点为止，然后用一个test函数检查是否所有结点都在路径中并且收尾相连，如果不都在，说明这个回路不对，若果都在，打印出这条回路
七、程序实现
#include
#include
#define MAX 5
using namespace std;
typedef struct ArcCell//邻接矩阵，存储边的信息
{
int adj;
}ArcCell,AdjMatrix[MAX][MAX];
typedef struct//图结构，含有顶点信息，邻接矩阵，顶点数和边数
{
int vexs[MAX];
AdjMatrix arcs;
int vexnum,arcnum;
}MGraph;
int visitTag[MAX],x[MAX];//第一个用来记录顶点是否被访问，第二个用来记录路径
bool exist=0;//判断该路径是否已被打印过
int FirstAdjVex(const MGraph& G,int v){//查找v的第一个邻接点
for (int i=0;i { if(G.arcs[v][i].adj!=0) return i; } return -1; } int NextAdjVex(const MGraph&G,int v,int w){//查找v的下一个邻接点 for (int i=w+1;i { if (G.arcs[v][i].adj!=0) return i; } return -1; } void initStatus(){//初始化跟踪栈，把所有已经遍历过的并且已经符合条件的点都放在这 for (int i=0;i { visitTag[i]=0; x[i]=-1; } } bool testHami(const MGraph& G){//判断是不是哈密顿回路 for (int i=0;i { if (!visitTag[i]) return 0; } return 1; } void backtrack(const MGraph& G,int t,int idxsum){ int i; visitTag[t]=1; x[idxsum]=t;//将结点的坐标放到当前栈里 for (i=FirstAdjVex(G,t);i>=0;i=NextAdjVex(G,t,i)) { if (!visitTag[i]) backtrack(G,i,++idxsum); } if (testHami(G)&&!exist&&G.arcs[0][MAX]==1)//找到哈密顿通路并且首尾相连 { cout<<"图中存在的一条哈密顿回路是： "< for (i=0;i { if (x[i]>=0&&x[i]<=G.vexnum) cout< exist=1; } cout< } if(!testHami(G)) { visitTag[t]=0;//使它的访问标志为0，为了下一次访问 x[idxsum]=-1;//清空它，说明当前的点不是符合条件的 } } void Hami(const MGraph& G){ if (G.arcnum { cout<<"非连通图"< return; } for (int i=0;i { initStatus(); exist=0; backtrack(G,i,0);//尝试从i出发的回路 } } void CreatUDN(MGraph &G)//创建图 { int i,n,j; G.vexnum=5; for (i=0;i { G.vexs[i]=i+1; } for (i=0;i { for (j=0;j G.arcs[i][j].adj=0; } cout<<"请输入一个邻接矩阵：\n"; for (i=0;i { for (j=0;j cin>>G.arcs[i][j].adj; } cout< } void dispMGraph(MGraph &G)//确认图的正确性{ int i,j; cout<<"请确认:\n"; for (i=0;i { for (j=0;j cout< } } int main() { MGraph G; CreatUDN(G); dispMGraph(G); Hami(G); return 0; } 八、运行结果 九、算法分析 各函数功能介绍：函数FirstAdjVex()用来求出图的邻接矩阵的某一行存在的第一条边所对应的第一个顶点；函数NextAdjVex()用来求出第一个顶点的下一个邻接顶点；函数initStatus()初始化跟踪栈，把所有已经遍历过得并且当前已经符合条件的点都放在里面;函数backtrack()进行回溯;函数bool testHami()判断改图有没有哈密顿回路，;函数Hami（）通过调用函数backtrack()来实现层层递归。 示意图： 参考文献：百度百科；算法导论（第2版） 电子科技大学 实验报告 课程名称：ACM算法与程序设计学生姓名：闵天辰 学号：2014220701018 指导教师：杨鹏 实验时间：2015年5月26日 “分层图思想”及其在信息学竞赛中的应用 天津市南开中学肖天 【摘要】本文通过对几道信息学竞赛题的解决，提出了一种解决问题的建模思想——分层图思想。该思想通过挖掘问题性质，将原问题抽象得出的图复 制为若干层并连接形成更大的图，使本来难以用数学语言表达得图论模 型变得简明严谨，为进一步解决问题打下了良好的基础。 【关键字】分层图思想图论数学模型最短路信息学竞赛 【正文】 1 引论 人们在借助计算机解决一个实际问题时，无非就是详细地告诉计算机应该怎么做，使它能通过人们给定的输入得到人们想要的输出。由于一般的计算机只能处理数字信号，所以只有把实际问题转化为数学问题，计算机才能帮助我们。这一步就是建立数学模型。 数学模型的建立在通过计算机解决问题的过程中非常重要。它把计算机无法理解的问题加以转化，使一切事物量化，最终变为只含数学过程的问题。它是人脑与计算机沟通的桥梁。不仅如此，数学模型的好坏直接影响着人与计算机之间的信息交流，影响着计算机对问题的“理解”。好的数学模型能够抓住问题的本质，表述简捷明了，易于人们找到有效的解决方法，并通过编制程序的方式将解决方法告诉计算机；相反，对于同一个问题，如果数学模型不能抓住问题本质，人们就可能无法解决问题，或者找不到有效的方法，更不用提告诉计算机如何做了。 由于建立数学模型是为了解决问题，所以人们在做这项工作时往往希望把问题归结为已经很好解决的经典问题或若干这样问题的有机结合。这样，只要应用前人的研究成果就可以了。比如，排序、求图的单源最短路、网络流等等都是经典问题，前人不仅给出一般解法，而且对各种特殊情况和变形作了深入的研究。但事情并不总像人们希望的那样，有的问题即使可以归结为已有问题，在其中加入一些干扰因素后，原有性质就会发生改变，原来建立起的数学模型难以再用严谨的数学语言表达。这样问题中的部分图论问题可以用本文提出的“分层图思想”解决。 该思想注重对原问题性质的挖掘，通过对原问题数学模型的扩展，将干扰因素融入新的数学模型之中，恢复了模型的严谨性，进而与已解决问题产生联系，得到有效算法。 电子科技大学 期末解题报告 课程：《ACM算法与程序设计》学院： 学号： 姓名： 报告成绩：教师签名： 讨厌的青蛙 1、链接地址 https://www.wendangku.net/doc/5d18160138.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 行上全部水稻恰好构成一条青蛙行走路径。 取石子游戏 Time Limit:1S Memory Limit:1000K Total Submit:505 Accepted:90 Description 有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目，如果轮到你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。 Input 输入包含若干行，表示若干种石子的初始情况，其中每一行包含两个非负整数a和b，表示两堆石子的数目，a和b都不大于1,000,000,000。 Output 输出对应也有若干行，每行包含一个数字1或0，如果最后你是胜者，则为1，反之，则为0。 Sample Input 2 1 8 4 4 7 Sample Output 1 跳蚤 Time Limit:1S Memory Limit:1000K Total Submit:198 Accepted:44 Description Z城市居住着很多只跳蚤。在Z城市周六生活频道有一个娱乐节目。一只跳蚤将被请上一个高空钢丝的正中央。钢丝很长，可以看作是无限长。节目主持人会给该跳蚤发一张卡片。卡片上写有N+1个自然数。其中最后一个是M，而前N个数都不超过M，卡片上允许 有相同的数字。跳蚤每次可以从卡片上任意选择一个自然数S，然后向左，或向右跳S个单位长度。而他最终的任务是跳到距离他左边一个单位长度的地方，并捡起位于那里的礼物。 比如当N=2，M=18时，持有卡片(10, 15, 18)的跳蚤，就可以完成任务：他可以先向左跳10个单位长度，然后再连向左跳3次，每次15个单位长度，最后再向右连跳3次，每次18个单位长度。而持有卡片(12, 15, 18)的跳蚤，则怎么也不可能跳到距他左边一个单位长度的地方。 当确定N和M后，显然一共有M^N张不同的卡片。现在的问题是，在这所有的卡片中，有多少张可以完成任务。 Input 两个整数N和M(N <= 15 , M <= 100000000)。 Output 可以完成任务的卡片数。 Sample Input 求最值 时间限制(普通/Java) : 1000 MS/3000 MS运行内存限制: 65536 KByte 总提交: 9915 测试通过: 2804 比赛描述 给定N个整数（1<=N<=100），求出这N个数中的最大值，最小值。 输入 多组数据，第一行为一个整数N，第二行为N个不超过100的正整数，用空格隔开。 输出 对每组数据输出一行，包含两个整数，用一个空格隔开，分别表示N个数中的最大值和最小值 样例输入 5 4 6 7 3 1 4 4 3 5 1 样例输出 7 1 5 1 #include int max=-1; int min=101; if(0<=n&&n<=100) { for(i=0;i F n = F n - 1 + F n - 2 用文字来说，就是斐波那契数列由0和1开始，之后的斐波那契数就由之前的两数相加。首几个斐波那契数是： 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946，……………… 特别指出：0不是第一项，而是第零项。 在西方，最先研究这个数列的人是比萨的列奥纳多（又名斐波那契），他描述兔子生长的数目时用上了这数列。 ? 第一个月有一对刚诞生的兔子 ? 第两个月之后它们可以生育 ? 每月每对可生育的兔子会诞生下一对新兔子 ? 兔子永不死去 假设在n 月有新生及可生育的兔子总共a 对，n+1月就总共有b 对。在n+2月必定总共有a+b 对：因为在n+2月的时候，所有在n 月就已存在的a 对兔子皆已可以生育并诞下a 对后代；同时在前一月(n+1月)之b 对兔子中，在当月属于新诞生的兔子尚不能生育。 现请以较短的时间，求出斐波那契数列第n 项数值，0≤n ≤40。 输入 斐波那契数列项数n ，0≤n ≤40。 输出 动态规划算法的优化技巧 福州第三中学毛子青 [关键词] 动态规划、时间复杂度、优化、状态 [摘要] 动态规划是信息学竞赛中一种常用的程序设计方法，本文着重讨论了运用动态规划思想解题时时间效率的优化。全文分为四个部分，首先讨论了动态规划时间效率优化的可行性和必要性，接着给出了动态规划时间复杂度的决定因素，然后分别阐述了对各个决定因素的优化方法，最后总结全文。 [正文] 一、引言 动态规划是一种重要的程序设计方法，在信息学竞赛中具有广泛的应用。 使用动态规划方法解题，对于不少问题具有空间耗费大、时间效率高的特点，因此人们在研究动态规划解题时更多的注意空间复杂度的优化，运用各种技巧将空间需求控制在软硬件可以承受的范围之内。但是，也有一部分问题在使用动态规划思想解题时，时间效率并不能满足要求，而且算法仍然存在优化的余地，这时，就需要考虑时间效率的优化。 本文讨论的是在确定使用动态规划思想解题的情况下，对原有的动态规划解法的优化，以求降低算法的时间复杂度，使其能够适用于更大的规模。 二、动态规划时间复杂度的分析 使用动态规划方法解题，对于不少问题之所以具有较高的时间效率，关键在于它减少了“冗余”。所谓“冗余”，就是指不必要的计算或重复计算部分，算法的冗余程度是决定算法效率的关键。动态规划在将问题规模不断缩小的同时，记录已经求解过的子问题的解，充分利用求解结果，避免了反复求解同一子问题的现象，从而减少了冗余。 但是，动态规划求解问题时，仍然存在冗余。它主要包括：求解无用的子问题，对结果无意义的引用等等。 下面给出动态规划时间复杂度的决定因素： 时间复杂度=状态总数*每个状态转移的状态数*每次状态转移的时间[1] 下文就将分别讨论对这三个因素的优化。这里需要指出的是：这三者之间不是相互独立的，而是相互联系，矛盾而统一的。有时，实现了某个因素的优化，另外两个因素也随之得到了优化；有时，实现某个因素的优化却要以增大另一因素为代价。因此，这就要求我们在优化时，坚持“全局观”，实现三者的平衡。 三、动态规划时间效率的优化 3.1 减少状态总数 我们知道，动态规划的求解过程实际上就是计算所有状态值的过程，因此状态的规模直接影响到算法的时间效率。所以，减少状态总数是动态规划优化的重要部分，本节将讨论减少状态总数的一些方法。 题目来源：福州大学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 左偏树的特点及其应用 广东省中山市第一中学黄源河 【摘要】 本文较详细地介绍了左偏树的特点以及它的各种操作。 第一部分提出可并堆的概念，指出二叉堆的不足，并引出左偏树。第二部分主要介绍了左偏树的定义和性质。第三部分详细地介绍了左偏树的各种操作，并给出时间复杂度分析。第四部分通过一道例题，说明左偏树在当今信息学竞赛中的应用。第五部分对各种可并堆作了一番比较。最后总结出左偏树的特点以及应用前景。 【关键字】左偏树可并堆优先队列 【目录】 一、引言 (2) 二、左偏树的定义和性质 (2) 2.1 优先队列，可并堆 (2) 2.1.1 优先队列的定义 (2) 2.1.2 可并堆的定义 (2) 2.2 左偏树的定义 (3) 2.3 左偏树的性质 (4) 三、左偏树的操作 (5) 3.1 左偏树的合并 (5) 3.2 插入新节点 (7) 3.3 删除最小节点 (8) 3.4 左偏树的构建 (8) 3.5 删除任意已知节点 (9) 3.6 小结 (12) 四、左偏树的应用 (13) 4.1 例——数字序列（Baltic 2004） (13) 五、左偏树与各种可并堆的比较 (15) 5.1 左偏树的变种——斜堆 (15) 5.2 左偏树与二叉堆的比较 (16) 5.3 左偏树与其他可并堆的比较 (16) 六、总结 (18) 【正文】 一、引言 优先队列在信息学竞赛中十分常见，在统计问题、最值问题、模拟问题和贪心问题等等类型的题目中，优先队列都有着广泛的应用。二叉堆是一种常用的优先队列，它编程简单，效率高，但如果问题需要对两个优先队列进行合并，二叉堆的效率就无法令人满意了。本文介绍的左偏树，可以很好地解决这类问题。 二、左偏树的定义和性质 在介绍左偏树之前，我们先来明确一下优先队列和可并堆的概念。 2.1优先队列，可并堆 2.1.1优先队列的定义 优先队列(Priority Queue)是一种抽象数据类型(ADT)，它是一种容器，里面有一些元素，这些元素也称为队列中的节点(node)。优先队列的节点至少要包含一种性质：有序性，也就是说任意两个节点可以比较大小。为了具体起见我们假设这些节点中都包含一个键值(key)，节点的大小通过比较它们的键值而定。优先队列有三个基本的操作：插入节点(Insert)，取得最小节点(Minimum) 和删除最小节点(Delete-Min)。 2.1.2可并堆的定义 可并堆(Mergeable Heap)也是一种抽象数据类型，它除了支持优先队列的三个基本操作(Insert, Minimum, Delete-Min)，还支持一个额外的操作——合并操作： H ← Merge(H1,H2) Merge( ) 构造并返回一个包含H1和H2所有元素的新堆H。 前面已经说过，如果我们不需要合并操作，则二叉堆是理想的选择。可惜合并二叉堆的时间复杂度为O(n)，用它来实现可并堆，则合并操作必然成为算法的瓶颈。左偏树(Leftist Tree)、二项堆(Binomial Heap) 和Fibonacci堆(Fibonacci Heap) 都是十分优秀的可并堆。本文讨论的是左偏树，在后面我们将看到各种可并堆的比较。 acm论文模板范文 ACM是全世界领域影响力最大的专业学术组织。而acm模板，你 们知道吗?这是 ___为大家了两篇acm论文，这样你们对模板会有直观的印象! [摘要] 鉴于ACM大学生程序设计竞赛(ACM/ICPC)在人才选拔和培养方面的显著作用，如何将ACM/ICPC竞赛活动嵌入常规教学，创新教学模式，结合专业教学，加强训练管理，提高培训效益，已成为人们关注的问题。针对这一应用需求，本文设计并开发了基于ACM/ICPC机制的大学生程序设计培训管理系统。系统采用B/S架构，以SQL Server xx作为后台管理数据库，Visual Studio 和https://www.wendangku.net/doc/5d18160138.html,为前端开发工具。在分析系统功能的基础上，着重阐述了 该系统设计与实现的关键技术。该系统实际运行稳定、可靠，为开展ACM/ICPC竞赛培训和教学提供了一种有效管理途径。 [关键词] ACM/ICPC;培训管理系统;Web开发;https://www.wendangku.net/doc/5d18160138.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试题及答案 1001 Sum Problem ............................................. 错误!未定义书签。1089 A+B for Input-Output Practice (I) ...................... 错误!未定义书签。1090 A+B for Input-Output Practice (II) ..................... 错误!未定义书签。1091 A+B for Input-Output Practice (III) .................... 错误!未定义书签。1092 A+B for Input-Output Practice (IV) ...................... 错误!未定义书签。1093 A+B for Input-Output Practice (V) ...................... 错误!未定义书签。1094 A+B for Input-Output Practice (VI) ..................... 错误!未定义书签。1095 A+B for Input-Output Practice (VII) ..................... 错误!未定义书签。1096 A+B for Input-Output Practice (VIII) ................... 错误!未定义书签。2000 ASCII码排序............................................ 错误!未定义书签。2001计算两点间的距离........................................ 错误!未定义书签。2002计算球体积.............................................. 错误!未定义书签。2003求绝对值................................................ 错误!未定义书签。2004成绩转换................................................ 错误!未定义书签。2005第几天.................................................. 错误!未定义书签。2006求奇数的乘积............................................ 错误!未定义书签。2007平方和与立方和.......................................... 错误!未定义书签。2008数值统计................................................ 错误!未定义书签。2009求数列的和.............................................. 错误!未定义书签。2010水仙花数................................................ 错误!未定义书签。2011多项式求和.............................................. 错误!未定义书签。2012素数判定................................................ 错误!未定义书签。2014青年歌手大奖赛_评委会打分............................... 错误!未定义书签。 The Mailboxes Manufacturers Problem Time Limit:1000MS Memory Limit:65536K Total Submit:299 Accepted:227 Description In the good old days when Swedish children were still allowed to blowup their fingers with fire-crackers, gangs of excited kids would plague certain smaller cities during Easter time, with only one thing in mind: To blow things up. Small boxes were easy to blow up, and thus mailboxes became a popular target. Now, a small mailbox manufacturer is interested in how many fire-crackers his new mailbox prototype can withstand without exploding and has hired you to help him. He will provide you with k(1 ≤ k≤ 10) identical mailbox prototypes each fitting up to m(1 ≤ m≤ 100) crackers. However, he is not sure of how many firecrackers he needs to provide you with in order for you to be able to solve his problem, so he asks you. You think for a while and then say, “Well,if I blow up a mailbox I can’t use it again, so if you would provide me with only k = 1 mailboxes, I would have to start testing with 1 cracker, then 2 crackers, and so on until it finally exploded. In the worst case, that is if it does not blow up ev en when filled with m crackers, I would need 1 + 2 + 3 + … + m = m ×(m+ 1) ? 2 crackers. If m = 100 that would mean more than 5000 fire-crackers!” “That’s too many,” he replies. “What if I give you more than k = 1 mailboxes? Can you find a strategy that requires less crackers?” Can you? And what is the minimum number of crackers that you should ask him to provide you with? You may assume the following: 1.If a mailbox can withstand x fire-crackers, it can also withstand x? 1 fire-crackers. 2.Upon an explosion, a mailbox is either totally destroyed (blown up) or unharmed, which means that it can be reused in another test explosion. hdu试题分类 hdu题目分类 模拟题, 枚举 1002 1004 1013 1015 1017 1020 1022 1029 1031 1033 1034 1035 1036 1037 1039 1042 1047 1048 1049 1050 1057 1062 1063 1064 1070 1073 1075 1082 1083 1084 1088 1106 1107 1113 1117 1119 1128 1129 1144 1148 1157 1161 1170 1172 1177 1197 1200 1201 1202 1205 1209 1212(大数取模) 1216（链表）1218 1219 1225 1228 1229 1230 1234 1235 1236 1237 1239 1250 1256 1259 1262 1263 1265 1266 1276 1279 1282 1283 1287 1296 1302 1303 1304 1305 1306 1309 1311 1314 复杂模拟 搜索，递归求解 1010 1016 1026 1043(双广) 1044 (BFS+DFS) 1045 1067 1072 1104 1175 1180 1195 1208 1226 1238 1240 1241 1242 1258 1271 1312 1317 博奕 1079 动态规划 1003 1024 1025 1028 1051 1058 1059 1069 1074 1078 1080 1081 1085 1087 1114 1158 1159 1160 1171 1176 1181 1203 1224 1227 1231 1244 1248 1253 1254 1283 1300 数学，递推，规律 1005 1006 1012 1014 1018 1019 1021 1023 1027 1030 1032 1038 1041 1046 1059 1060 1061 1065 1066 1071(微积分) 1097 1098 1099 1100 1108 1110 1112 1124 1130 1131 1132 1134 1141 1143 1152 1155(物理题) 1163 1165 1178 1194 1196(lowbit) 1210 1214 1200 1221 1223 1249 1261 1267 1273 1290 1291 1292 1294 1297 1313 1316 数论 1164 1211 1215 1222 1286 1299 【题目 1】N皇后问题(含八皇后问题的扩展，规则同八皇后)：在N*N的棋盘上，放置N个皇后，要求每一横行 每一列，每一对角线上均只能放置一个皇后，问可能的方案及方案数。 【题目 2】排球队员站位问题 ┏━━━━━━━━┓图为排球场的平面图，其中一、二、三、四、五、六为位置编号，┃ ┃二、三、四号位置为前排，一、六、五号位为后排。某队比赛时，┃ ┃一、四号位放主攻手，二、五号位放二传手，三、六号位放副攻┠──┬──┬──┨手。队员所穿球衣分别为１，２，３，４，５，６号，但每个队 ┃ 四 │ 三 │ 二 ┃员的球衣都与他们的站位号不同。已知１号、６号队员不在后排，┠──┼──┼──┨２号、３号队员不是二传手，３号、４号队员不在同一排，５号、┃ 五 │ 六 │ 一 ┃６号队员不是副攻手。 ┗━━┷━━┷━━┛编程求每个队员的站位情况。 【算法分析】本题可用一般的穷举法得出答案。也可用回溯法。以下为回溯解法。 【题目 2】把自然数Ｎ分解为若干个自然数之和。 【参考答案】 n │ total 5 │ 7 6 │ 11 7 │ 15 10 │ 42 100 │ 190569291 【题目 3】把自然数Ｎ分解为若干个自然数之积。 【题目 4】马的遍历问题。在Ｎ＊Ｍ的棋盘中，马只能走日字。马从位置(x,y)处出发，把棋盘的每一格都走一次，且只走一次。找出所有路径。 【参考程序】 {深度优先搜索法} 【题目 5】加法分式分解。如：1/2=1/4+1/4.找出所有方案。 输入：Ｎ ＭＮ为要分解的分数的分母 Ｍ为分解成多少项 【题目 6】地图着色问题 【题目 7】在n*n的正方形中放置长为2,宽为1的长条块,问放置方案如何 【题目 8】找迷宫的最短路径。（广度优先搜索算法） 1、0-1背包 #include } } m[0][c]=m[1][c]; if(c>=w[0]) { if(m[0][c] 1999年 陈宏- 数据结构的选择与算法效率——从IOI98试题PICTURE谈起 来煜坤- 把握本质，灵活运用——动态规划的深入探讨 齐鑫- 搜索方法中的剪枝优化 邵铮- 数学模型的建立、比较和应用 石润婷- 隐蔽化、多维化、开放化──论当今信息学竞赛中数学建模的灵活性睢》?- 准确性、全面性、美观性——测试数据设计中的三要素 周咏基- 论随机化算法的原理与设计 2000年 陈彧- 信息学竞赛中的思维方法 方奇- 动态规划 高寒蕊- 递推关系的建立及在信息学竞赛中的应用 郭一- 数学模型及其在信息学竞赛中的应用 江鹏- 探索构造法解题模式 李刚- 动态规划的深入讨论 龙翀- 解决空间规模问题的几种常用的存储结构 骆骥- 数学模型的建立和选择 施遥- 人工智能在围棋程序中的应用 肖洲- 数据结构的在程序设计中的应用 谢婧- 规模化问题的解题策略 徐串- 论程序的调试技巧 徐静- 图论模型的建立与转化 杨江明- 论数学策略在信息学问题中的应用 杨培- 非最优化算法初探 张辰- 动态规划的特点及其应用 张力- 类比思想在解题中的应用 张一飞- 冗繁削尽留清瘦——浅谈信息的充分利用 2001年 高寒蕊- 从圆桌问题谈数据结构的综合运用 符文杰- Pólya原理及其应用 高岳- 中等硬度解题报告 江鹏- 从一道题目的解法试谈网络流的构造与算法 刘汝佳- 搬运工问题的启示 李益明- 计算几何的相关问题 李源- 树的枚举 骆骥- 由“汽车问题”浅谈深度搜索的一个方面——搜索对象与策略的重要性毛子青- 动态规划算法的优化技巧 俞玮- 基本动态规划问题的扩展 张一飞- 求N!的高精度算法 2002年 戴德承- 退一步海阔天空——“目标转化思想”的若干应用 大部分题目都来源于周涵学弟，感谢他的成果，希望大家不断a题，提升自己的能力，都能在校赛上取得好的成绩。 这次比赛很多童鞋都做的很好，不过通过做题也能反映出一些问题。 第一，读题。 很多童鞋交了发现自己的数据爆值，很多时候是因为没有好好读题。 int , long, long long 的范围应该都知道，如果只是因为没有好好读题而出错，这是毫无意义的罚时，所以一定好好好读题，看清数据范围。 第二，跟榜。 在正式的比赛中题目的难度并不是按照ABCD来排列的，简单的题目可能在中间，在最后，所以不要死一道题，而是看题目的通过人数，这是判断题目难度的最好方法，就是跟榜。 第三，扩充自己的知识面。 很多题目用你现有的知识可能很难做出来，但是用一些语言自带的函数或者容器就能简单的做出来了。这就需要不断学习，多多接受一些新的东西并用到题目当中，会有很好的收获的。 还发现了一些同学有抄袭现象，在正式比赛中所有的题目都是原创的，并且不可以上网寻求帮助，只能带纸质材料。所以还是珍惜每一次做题的机会，认真的去对待吧。 A：本道题目需要注意1<=n<=1000,而1既不是素数也不是合数，2是最小的素数 B：方法采用辗转相除法求的最大公约数，最小公倍数采用：给定的两数之积除以最大公约 数。 C：字符串比较大小问题，在C语言中可以调用头文件 D：此题为排序题，可以采用冒泡排序法，在C++直接有sort排序函数，可以直接调用。 E：学一下结构体排序的方法，顺便自学一波stirng类型 F：斐波那契数列采用递归计算法，应题目要求进行取余（因为在计算过程中可能为出现溢出） G：矩阵采用二位数组输入模式，根据二位数组索引值，得出计算规律。需要注意的是：可能出现10的10次方，所以不要用int。 H:对于每一个点遍历一遍这个点周围的点，然后开一个数组记录下来就好了，搜索的基本运用 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 COJ https://www.wendangku.net/doc/5d18160138.html,/oj/prepare.do?fun=viewProblem&pid=1011 https://www.wendangku.net/doc/5d18160138.html,/oj/prepare.do?fun=viewProblem&pid=1024 https://www.wendangku.net/doc/5d18160138.html,/oj/prepare.do?fun=viewProblem&pid=1034 https://www.wendangku.net/doc/5d18160138.html,/oj/prepare.do?fun=viewProblem&pid=1035 https://www.wendangku.net/doc/5d18160138.html,/oj/prepare.do?fun=viewProblem&pid=1036 https://www.wendangku.net/doc/5d18160138.html,/oj/prepare.do?fun=viewProblem&pid=1037 https://www.wendangku.net/doc/5d18160138.html,/oj/prepare.do?fun=viewProblem&pid=1038 https://www.wendangku.net/doc/5d18160138.html,/oj/prepare.do?fun=viewProblem&pid=1078 https://www.wendangku.net/doc/5d18160138.html,/oj/prepare.do?fun=viewProblem&pid=1137 https://www.wendangku.net/doc/5d18160138.html,/oj/prepare.do?fun=viewProblem&pid=1172 https://www.wendangku.net/doc/5d18160138.html,/oj/prepare.do?fun=viewProblem&pid=1190 https://www.wendangku.net/doc/5d18160138.html,/oj/prepare.do?fun=viewProblem&pid=1211 https://www.wendangku.net/doc/5d18160138.html,/oj/prepare.do?fun=viewProblem&pid=1230 https://www.wendangku.net/doc/5d18160138.html,/oj/prepare.do?fun=viewProblem&pid=1231 https://www.wendangku.net/doc/5d18160138.html,/oj/prepare.do?fun=viewProblem&pid=1249 https://www.wendangku.net/doc/5d18160138.html,:8080/COJ/prepare.do?fun=viewProblem&pid=1257 https://www.wendangku.net/doc/5d18160138.html,:8080/COJ/prepare.do?fun=viewProblem&pid=1260 FOJ Hotter Colder https://www.wendangku.net/doc/5d18160138.html,/problem.php?pid=1014 求线段的中位线，线段相交求交点，求凸多边形的面积， 无归之室 https://www.wendangku.net/doc/5d18160138.html,/problem.php?pid=1016 本题精度要求非常高，用三角函数的话，很容易就wa.. Reflections https://www.wendangku.net/doc/5d18160138.html,/problem.php?pid=1035 求一条射线遇到圆后的反射光， 即圆和直线求交点，求点关于交点法线的对称点。 Pipe https://www.wendangku.net/doc/5d18160138.html,/problem.php?pid=1088 求一条光线从管道口进入，最远能达到多远。 判断线段左右位置关系，求线段相交交点。 A Pilot in Danger! https://www.wendangku.net/doc/5d18160138.html,/problem.php?pid=1120 判断点在区域内 Area in Triangle https://www.wendangku.net/doc/5d18160138.html,/problem.php?pid=1195 在三角形内的气球膨胀，求膨胀后的面积。 分情况推公式 Triangle https://www.wendangku.net/doc/5d18160138.html,/problem.php?pid=1302 在给定的n（1<=n<=50000）个点中，取3个点组成三角形，求面积最大。国家集训队2004论文集 肖天
《ACM算法与程序设计》解题报告模板
ACM竞赛试题集锦
ACM常见题型个人解法
国家集训队2001论文集 毛子青
ACM题目整理
国家集训队2005论文集 黄源河
acm论文模板范文
Acm试题及答案
acm程序设计大赛题目
hdu试题分类
ACM题目
ACM动态规划问题简易模板(C++可编译)
历年国家集训队论文题目
ACM常见题型题解
整理acm模板
ACM计算几何题目总结及分类
- 国家集训队2004论文集 许智磊
- 国家集训队2009论文集分治算法在树的路径问
- 国家集训队2005论文集 黄源河
- 历年国家集训队论文题目
- 国家集训队2007论文集7.胡伯涛《最小割模型
- 国家集训队2004论文集_许智磊(后缀数组)
- 历年国家集训队论文题目
- 国家集训队2004论文集_林涛
- 国家集训队2003论文集 王知昆
- 国家集训队2004论文集_周源
- 国家集训队2001论文集 毛子青
- 国家集训队论文分类整理
- 国家集训队2004论文集_肖天
- 国家集训队1999论文集 邵铮
- 国家集训队2009论文集后缀数组——处理字符
- 国家集训队2009论文集浅谈数位类统计问题
- 国家集训队2004论文集_汪汀
- 国家集训队2009论文集浅谈如何解决不平等博
- 国家集训队2004论文集 肖天
- 国家集训队2009论文集slide