《ACM算法与数据结构设计》大作业

Online Judge 题号POJ 2002计算几何哈希表POJ 3320哈希表POJ3349哈希表codeforces 2A 哈希表codeforces 468A 构造POJ 1611并查集POJ 2524并查集HDU 1326排序POJ 1995快速幂HDU 1325并查集树HDU 2818并查集HDU 1856并查集POJ 2406KMP POJ 3461KMP POJ 2752KMP HDU 3746KMP HDU 1867KMP HDU 3336KMPPOJ 2785二分查找/倍增POJ 3104二分查找/倍增模拟POJ 2503(二分查找/倍增)(字典树)(哈希表)HDU 4430数学二分查找/倍增HDU 4768数学二分查找/倍增NOJ 1131图论基础POJ 1125最短路POJ 1502最短路POJ 2240最短路POJ 1860最短路POJ 3259最短路HDU5137最短路枚举codeforces 459A 排序codeforces 271B 数学二分查找/倍增codeforces 271D 字典树(后缀数据结构)HDU 1004(字典树)(哈希表)HDU 1800字典树HDU 1671字典树POJ 3264倍增RMQ HDU 3183倍增RMQ (贪心)POJ 1330倍增LCA 树HDU 2586倍增LCA树HDU 5135记忆化搜索状压DP HDU 5131暴力STL HDU 5137最短路枚举涉及知识今年区域赛网络赛容易题HDU5112排序HDU5122贪心HDU5119动态规划位运算HDU5078计算几何ZOJ5351枚举ZOJ3809暴力模拟ZOJ3818暴力字符串HDU4998线性代数矩阵HDU5007字符串暴力HDU5038数学暴力HDU5024枚举HDU5053数学题目地址/problem?id=2002/problem?id=3320/problem?id=3349/problemset/problem/2/A/problemset/problem/468/A/problem?id=1611/problem?id=2524/showproblem.php?pid=1326/problem?id=1995/showproblem.php?pid=1325/showproblem.php?pid=2818/showproblem.php?pid=1856/problem?id=2406/problem?id=3461/problem?id=2752/showproblem.php?pid=3746/showproblem.php?pid=1867/showproblem.php?pid=3336/problem?id=2785/problem?id=3104/problem?id=2503/showproblem.php?pid=4430/showproblem.php?pid=4768/acmhome/problemdetail.do?&method=showdetail&id=1131 /problem?id=1125/problem?id=1502/problem?id=2240/problem?id=1860/problem?id=3259/showproblem.php?pid=5137/problemset/problem/459/A/contest/271/problem/B/contest/271/problem/D/showproblem.php?pid=1004/showproblem.php?pid=1800/showproblem.php?pid=1671/problem?id=3264/showproblem.php?pid=3183/problem?id=1330/showproblem.php?pid=2586/showproblem.php?pid=5135/showproblem.php?pid=5131/showproblem.php?pid=5137/showproblem.php?pid=5112/showproblem.php?pid=5122/showproblem.php?pid=5119/showproblem.php?pid=5078/onlinejudge/showContestProblem.do?problemId=5351 /onlinejudge/showProblem.do?problemCode=3809 /onlinejudge/showProblem.do?problemCode=3818 /showproblem.php?pid=4998/showproblem.php?pid=5007/showproblem.php?pid=5038/showproblem.php?pid=5024/showproblem.php?pid=5053备注并查集入门题并查集入门题KMP next数组性质入门题KMP 字符串匹配入门题KMP next数组性质带括号为多种做法可选2012 Asia ChangChun Regional Contest2013 Asia Changchun Regional Online detail&id=1131最短路入门题注意模型转换灵活运用多种最短路算法2014 Asia Guangzhou Regional Contest字典树就可以过了。

一、综合处理题1、两倍- /problem?id=2807Description给定2到15个不同的正整数，你的任务是计算这些数里面有多少个数对满足：数对中一个数是另一个数的两倍。

比如给定1 4 3 2 9 7 18 22，得到的答案是3，因为2是1的两倍，4是2个两倍，18是9的两倍。

Input输入包括多组测试数据。

每组数据包括一行，给出2到15个两两不同且小于100的正整数。

每一行最后一个数是0，表示这一行的结束后，这个数不属于那2到15个给定的正整数。

输入的最后一行只包括一个整数-1,这行表示输入数据的结束，不用进行处理。

Output对每组输入数据，输出一行，给出有多少个数对满足其中一个数是另一个数的两倍。

Sample Input1 4 32 9 7 18 22 02 4 8 10 07 5 11 13 1 3 0-1Sample Output322、谁拿了最多奖学金 - /problem?id=2715Description某校的惯例是在每学期的期末考试之后发放奖学金。

发放的奖学金共有五种，获取的条件各自不同：1) 院士奖学金，每人8000元，期末平均成绩高于80分（>80），并且在本学期内发表1篇或1篇以上论文的学生均可获得；2) 五四奖学金，每人4000元，期末平均成绩高于85分（>85），并且班级评议成绩高于80分（>80）的学生均可获得；3) 成绩优秀奖，每人2000元，期末平均成绩高于90分（>90）的学生均可获得；4) 西部奖学金，每人1000元，期末平均成绩高于85分（>85）的西部省份学生均可获得；5) 班级贡献奖，每人850元，班级评议成绩高于80分（>80）的学生干部均可获得；只要符合条件就可以得奖，每项奖学金的获奖人数没有限制，每名学生也可以同时获得多项奖学金。

例如姚林的期末平均成绩是87分，班级评议成绩82分，同时他还是一位学生干部，那么他可以同时获得五四奖学金和班级贡献奖，奖金总数是4850元。

acm编程练习题ACM（即：美国计算机协会）编程练习题是指ACM国际大学生程序设计竞赛中的一些编程题目，旨在考察参赛选手在算法和数据结构等方面的能力。

这些题目常常要求选手设计和实现一个算法，在规定的时间和空间限制下解决实际问题。

ACM编程练习题具有一定的难度和挑战性，它的解题过程有时需要选手在理论基础上进行创新思维和灵活运用。

相比于传统的笔试或面试形式，ACM编程练习题更加贴近实际应用场景，能够真实地展现参赛选手的编程能力和逻辑思维能力。

为了更好地完成ACM编程练习题，选手需要熟练掌握常用的数据结构和算法，比如数组、链表、栈、队列、树、图等。

此外，对于一些经典的算法，如贪心算法、动态规划、分治法等，也有必要进行深入学习和理解。

在真实的竞赛环境中，选手还需要熟悉特定的编程语言和开发环境，比如C++、Java或Python等。

解决ACM编程练习题有着多种方法和思路。

选手需要熟悉各种问题的特点，根据问题所给条件进行合理的算法设计。

对于一些复杂的问题，可以利用数学方法进行简化和转化，从而找到更高效的解决方案。

在编程实现的过程中，要注重代码的可读性和可维护性，合理地使用注释和命名，避免代码冗余和错误。

ACM编程练习题的解题过程中，选手不仅需要具备扎实的编程基础和算法知识，还需要具备压力下的良好心态和团队合作精神。

在竞赛中，选手可能面临时间紧迫、出题者的陷阱、复杂场景等挑战，因此，选手们需要保持冷静、灵活应对，不断提升自己的解题能力和竞赛技巧。

总之，ACM编程练习题是一种非常有挑战性的编程竞赛形式，对选手的编程能力、算法思维和团队协作能力都提出了较高的要求。

通过积极参与练习和实战，选手们可以不断提升自己，在ACM竞赛中取得更好的成绩，并在实际工作中具备更强的编程能力。

（字数：413）。

备战ACM资料一：知识点数据结构：1，单，双链表及循环链表2，树的表示与存储，二叉树（概念，遍历）二叉树的应用（二叉排序树，判定树，博弈树，解答树等）3，文件操作（从文本文件中读入数据并输出到文本文件中）4，图（基本概念，存储结构，图的运算）数学知识1，离散数学知识的应用（如排列组合、简单的图论，数理逻辑）2，数论知识3，线性代数4，组合代数5，计算几何二算法1，排序算法（冒抛法，插入排序，合并排序，快速排序，堆排序）2，查找（顺序查找，二分发）3，回溯算法4，递归算法5，分治算法6，模拟法7，贪心法8，简单搜索算法（深度优先，广度优先），搜索中的剪枝，A*算法9，动态规划的思想及基本算法10，高精度运算三、ACM竞赛的题型分析竞赛的程序设计一般只有16种类型，它们分别是：Dynamic Programming （动态规划）Greedy （贪心算法）Complete Search （穷举搜索）Flood Fill （不知该如何翻译）Shortest Path （最短路径）Recursive Search Techniques （回溯搜索技术）Minimum Spanning Tree （最小生成树）Knapsack （背包问题）Computational Geometry (计算几何学)Network Flow （网络流）Eulerian Path （欧拉回路）Two-Dimensional Convex Hull （不知如何翻译）BigNums （大数问题）Heuristic Search （启发式搜索）Approximate Search （近似搜索）Ad Hoc Problems （杂题）四ACM竞赛参考书《实用算法的分析与程序设计》（吴文虎，王建德著，电子工业出版社，竞赛类的黑宝书）《青少年国际和全国信息学（计算机）奥林匹克竞赛指导）――组合数学的算法和程序设计》（吴文虎，王建德著，清华大学出版社，参加竞赛组合数学必学）《计算机算法设计与分析》（王晓东编著，最好的数据结构教材）《数据结构与算法》（傅清祥，王晓东编著，我所见过的最好的算法教材）《信息学奥林匹克竞赛指导――1997-1998竞赛试题解析》（吴文虎，王建德著，清华大学出版社）《计算机程序设计技巧》 D.E.Kruth著，算法书中最著名的《葵花宝典》，大师的作品，难度大）《计算几何》周陪德著《ACM国际大学生程序设计竞赛试题与解析（一）》（吴文虎著，清华大学出版社）《数学建模竞赛培训教材》共三本叶其孝主编《数学模型》第二版姜启源《随机规划》《模糊数学》《数学建模入门》徐全智《计算机算法设计与分析》国防科大五常见的几个网上题库常用网站：1）信息学初学者之家：/（2）大榕树编程世界：/~drs/program/default.asp（3）中国教育曙光网：/aosai/（4）福建信息学奥林匹克：/fjas/index.htm（5）第20届全国青少年信息学奥林匹克竞赛：/（6）第15届国际青少年信息学奥林匹克竞赛：/（7）全美计算机奥林匹克竞赛：/usacogate（8）美国信息学奥林匹克竞赛官方网站：/（9）俄罗斯Ural州立大学：http://acm.timus.ru/（10）西班牙Valladolid大学：http://acm.uva.es/problemset（11）ACM-ICPC：/icpc/（12）北京大学：/JudgeOnline/index.acm（13）浙江大学：/（14）IOI：http://olympiads.win.tue.nl/ioi/（15）2003年江苏省信息学奥林匹克竞赛夏令营：（16）（17）（18）（19）/downldmanag/index.asp（20） colin_fox/colin_fox五如何备战ACM/ICPC1，个人准备（算法书，习题集，网上做题和讨论）2，1000题=亚洲冠军=世界决赛3，做好资料收集和整理工作实验一：递归与分治1.二分查找2.合并排序3.快速排序实验二：回溯1.0-1背包问题2.装载问题3.堡垒问题（ZOJ1002）4.*翻硬币问题5.8皇后问题6.素数环问题7.迷宫问题8.*农场灌溉问题（ZOJ2412）9.*求图像的周长（ZOJ1047）10.*骨牌矩阵11.*字母转换（ZOJ1003）12.*踩气球（ZOJ1004）实验三：搜索1.Floodfill2.电子老鼠闯迷宫3.跳马4.独轮车5.皇宫小偷6.分酒问题7.*找倍数8.*8数码难题实验四：动态规划1.最长公共子序列2.计算矩阵连乘积3.凸多边形的最优三角剖分4.防卫导弹5.*石子合并6.*最小代价子母树7.*旅游预算8.*皇宫看守9.*游戏室问题10.*基因问题11.*田忌赛马实验五：贪心与随机算法1.背包问题2.搬桌子问题3.*照亮的山景4.*用随即算法求解8皇后问题5.素数测试实验一：递归与分治实验目的理解递归算法的思想和递归程序的执行过程，并能熟练编写递归程序。

acm大学生程序设计试题题目一：最大公约数（GCD）题目描述：给定两个正整数，求它们的最大公约数（GCD）。

输入两个正整数a和b（1 <= a, b <= 10^9），求它们的最大公约数。

输入格式：两个正整数，以空格分隔。

输出格式：输出一个整数，表示输入两个正整数的最大公约数。

示例：输入：14 21输出：7思路和分析：最大公约数（GCD）可以使用欧几里得算法来求解，即辗转相除法。

具体的步骤如下：1. 用较大的数除以较小的数，将得到的余数作为新的较大数。

2. 再用新的较大数除以较小数，将得到的余数作为新的较大数。

3. 如此重复，直到两个数可以整除，此时较小的数就是最大公约数。

代码实现：```cpp#include <iostream>using namespace std;int gcd(int a, int b) {if (b == 0)return a;return gcd(b, a % b);}int main() {int a, b;cin >> a >> b;int result = gcd(a, b);cout << result << endl;return 0;}```题目二：字符串反转题目描述：给定一个字符串，要求将其反转并输出。

输入一个字符串s（1 <= |s| <= 1000)，输出该字符串的反转结果。

输入格式：一个字符串s，只包含大小写字母和数字。

输出格式：一个字符串，表示输入字符串的反转结果。

示例：输入：HelloWorld123输出：321dlroWolleH思路和分析：字符串反转可以使用双指针的方法来实现。

初始时，左指针指向字符串的开头，右指针指向字符串的末尾，然后交换左右指针所指向的字符，并向中间移动，直到左指针不小于右指针。

代码实现：```cpp#include <iostream>using namespace std;string reverseString(string s) {int left = 0, right = s.length() - 1; while (left < right) {swap(s[left], s[right]);left++;right--;}return s;}int main() {string s;cin >> s;string result = reverseString(s); cout << result << endl;return 0;}```题目三：字符串匹配题目描述：给定一个字符串s和一个模式串p，判断s中是否存在与p相匹配的子串。

acm常用算法和数据结构1.引言1.1 概述概述部分是对整篇文章进行简要介绍，让读者了解本文的主题和内容。

下面是对1.1概述部分的内容的编写建议：概述部分旨在向读者介绍本文的主要内容和目的。

本文主要讨论ACM （算法竞赛）中常用的算法和数据结构。

ACM常用算法和数据结构是指在解决各类计算机编程竞赛或算法题目时经常使用的，被广泛验证和应用的算法和数据结构。

本文主要分为引言、正文和结论三个部分。

引言部分描述了本文整体的构架和目的，正文部分详细介绍了常用算法和数据结构的分类和特点，结论部分对本文进行总结，并探讨了这些常用算法和数据结构在实际应用中的前景。

在正文部分的常用算法中，我们将介绍一些经典的排序算法，如冒泡排序、插入排序和快速排序等，同时还会讨论一些常见的查找算法，如顺序查找和二分查找等。

这些算法都有着不同的时间复杂度和空间复杂度，以及各自适用的场景。

在数据结构部分，我们将详细介绍数组和链表这两种最基础的数据结构。

数组是一种线性存储结构，可以用于存储同一类型的一组数据，并且支持随机访问。

链表则是由一系列节点组成的，每个节点包含数据和指向下一个节点的指针，链表常用于实现队列、栈和链表等数据结构。

最后在结论部分，我们将对本文进行总结，强调常用算法和数据结构在实际应用中的重要性和价值。

并探讨这些算法和数据结构在日常编程工作中的应用前景，以帮助读者更好地理解和应用这些常用算法和数据结构。

通过本文的学习，读者将能够掌握ACM竞赛中的常用算法和数据结构的基本原理和应用方法，进一步提升算法思维和编程能力，为解决实际问题提供高效的解决方案。

文章结构部分的内容可以包括以下内容：文章结构旨在为读者提供对整篇文章内容的整体把握，方便读者在需要时能够快速定位和浏览特定的内容部分。

以下是本文的整体结构：1. 引言1.1 概述1.2 文章结构1.3 目的2. 正文2.1 常用算法2.1.1 排序算法2.1.2 查找算法2.2 数据结构2.2.1 数组2.2.2 链表3. 结论3.1 总结常用算法和数据结构3.2 应用前景在本文中，首先在引言部分对整篇文章进行了概述，说明了文章的目的和内容。

ACM算法题使用C++实现在做这些题目之前必须了解vector（数组），list（链表）、deque（双端队列）、queue（队列）, priority_queue（优先队列）Stack（栈）、set（集合）、map（键值对），mutilset、mutilmap。

stack堆栈，没有迭代器，支持push()方法。

后进先出,top()返回最顶端的元素,pop()剔除最顶元素deque双端队列，支持迭代器，有push_back()方法，跟vector差不多，比vector多了个pop_front,push_front方法queue队列，先进先出，不支持迭代器，有push()方法，pop()剔除第一个元素,front()返回第一个元素vector使用vector是C++标准模板库中的部分内容，它是一个多功能的，能够操作多种数据结构和算法的模板类和函数库。

vector之所以被认为是一个容器，是因为它能够像容器一样存放各种类型的对象，简单地说vector是一个能够存放任意类型的动态数组，能够增加和压缩数据。

为了可以使用vector，必须在你的头文件中包含下面的代码：#include <vector>vector属于std命名域的，因此需要通过命名限定，如下完成你的代码：using std::vector; vector<int> v;或者连在一起，使用全名：std::vector<int> v;建议使用全局的命名域方式：using namespace std;1.vector的声明vector<ElemType> c; 创建一个空的vectorvector<ElemType> c1(c2); 创建一个vector c1，并用c2去初始化c1vector<ElemType> c(n) ; 创建一个含有n个ElemType类型数据的vector;vector<ElemType> c(n,elem); 创建一个含有n个ElemType类型数据的vector,并全部初始化为elem;c.~vector<ElemType>(); 销毁所有数据,释放资源;2.vector容器中常用的函数。

ACM程序设计试题及参考答案猪的安家Andy和Mary养了很多猪。

他们想要给猪安家。

但是Andy没有足够的猪圈，很多猪只能够在一个猪圈安家。

举个例子，假如有16头猪，Andy建了3个猪圈，为了保证公平，剩下1头猪就没有地方安家了。

Mary生气了，骂Andy没有脑子，并让他重新建立猪圈。

这回Andy建造了5个猪圈，但是仍然有1头猪没有地方去，然后Andy又建造了7个猪圈，但是还有2头没有地方去。

Andy都快疯了。

你对这个事情感兴趣起来，你想通过Andy建造猪圈的过程，知道Andy家至少养了多少头猪。

输入输入包含多组测试数据。

每组数据第一行包含一个整数n (n <= 10) – Andy 建立猪圈的次数，解下来n行，每行两个整数ai, bi( bi <= ai <= 1000), 表示Andy建立了ai个猪圈，有bi头猪没有去处。

你可以假定(ai, aj) = 1.输出输出包含一个正整数，即为Andy家至少养猪的数目。

样例输入33 15 17 2样例输出16答案:// 猪的安家.cpp : Defines the entry point for the console application.//#include "stdafx.h"#include "iostream.h"void main(){int n;int s[10][2];bool r[10];char ch;cout<<"请输入次数:"<<endl;cin>>n;for (int i=0;i<n;i++){cout<<"请输入第"<<i+1<<"次的猪圈个数和剩下的猪:，用--分开，"<<endl;cin>>s[i][0]>>ch>>ch>>s[i][1];}for (i=0;i<10;i++)r[i]=true;for (int sum=1;;sum++){for (i=0;i<n;i++)r[i]=(sum%s[i][0]==s[i][1]);for (i=0;i<n;i++){if (r[i]==0)break;}if (i==n)break;}cout<<"猪至少有"<<sum<<"只。