搜档网
当前位置:搜档网 › ACM解题报告

ACM解题报告

ACM解题报告
ACM解题报告

题目一:

Description

Some positive integers can be represented by a sum of one or more consecutive prime numbers. How many such representations does a given positive integer have? For example, the integer 53 has two representations 5 + 7 + 11 + 13 + 17 and 53. The integer 41 has three representations 2+3+5+7+11+13, 11+13+17, and 41. The integer 3 has only one representation, which is 3. The integer 20 has no such representations. Note that summands must be consecutive prime

numbers, so neither 7 + 13 nor 3 + 5 + 5 + 7 is a valid representation for the integer 20.

Your mission is to write a program that reports the number of representations for the given positive integer.

Input

The input is a sequence of positive integers each in a separate line. The integers are between 2 and 10 000, inclusive. The end of the input is indicated by a zero. Output

The output should be composed of lines each corresponding to an input line except the last zero. An output line includes the number of representations for the input integer as the sum of one or more consecutive prime numbers. No other characters should be inserted in the output.

Sample Input

2

3

17

41

20

666

12

53

Sample Output

1

1

2

3

1

2

1.算法

通过筛法找出10000以内所有的素数,存到数组里。然后对每个输入的数num,尝试用连续的比num小的素数,用num减去这个这些连续的素数,如果结果是零,则在结果上加上1,最后输出结果。

2.实现

(1)对于数组初始化的时候,int a[10]={1}只能对数组的第一个字符进行初始化,但是int a[1 0]={0}可将整个数组进行初始化。

(2)注意在函数传参数的时候的指针和引用的用法。

3.代码:

#include

void creat_primes(int* prime,int& size);

int calculate(int* prime,int size,int num);

int main()

{

int prime[10000];

int size_of_primes = 0 ;

//生成素数表

creat_primes(prime,size_of_primes);

//读取和计算

int num = 0;

scanf("%d",&num);

while(num!=0)

{

if(int result = calculate(prime,size_of_primes,num))printf("%d\n",result); else printf("0\n");

scanf("%d",&num);

}

return 0 ;

}

/*生成一个素数表*/

void creat_primes(int* prime,int& size)

{

int notPrime[10001] = {false};

for (int i = 2;i<10001;i++)

{

int x = i*2;

while(x<10001)

{

notPrime[x]=true;

x+=i;

}

}

for(int i=2;i<10001;i++)

{

if(!notPrime[i]) prime[size++]=i;

}

}

/*计算这个num有几种表现方式*/

int calculate(int* prime,int size,int num)

{

int result = 0;

for(int i = 0;i

{

if (prime[i]>num) break;

int n = num;

int index = i;

while(n>0)

{

n-=prime[index];

index++;

}

if (n==0)result++;

}

return result;

}

题目二:

Standard web browsers contain features to move backward and forward among the pages recently visited. One way to implement these features is to use two stacks to keep track of the pages that can be reached by moving backward and forward. In this problem, you are asked to implement this.

The following commands need to be supported:

BACK: Push the current page on the top of the forward stack. Pop the page from the top of the backward stack, making it the new current page. If the backward stack is empty, the command is ignored.

FORWARD: Push the current page on the top of the backward stack. Pop the page from the top of the forward stack, making it the new current page. If the forward stack is empty, the command is ignored.

VISIT : Push the current page on the top of the backward stack, and make the URL specified the new current page. The forward stack is emptied.

QUIT: Quit the browser.

Assume that the browser initially loads the web page at the URL https://www.sodocs.net/doc/ae16696478.html,/

Input

Input is a sequence of commands. The command keywords BACK, FORWARD, VISIT, and QUIT are all in uppercase. URLs have no whitespace and have at most 70 characters. You may assume that no problem instance requires more than 100 elements in each stack at any time. The end of input is indicated by the QUIT command.

Output

For each command other than QUIT, print the URL of the current page after the command is executed if the command is not ignored. Otherwise, print "Ignored". The output for each command should be printed on its own line. No output is produced for the QUIT command.

Sample Input

VISIT https://www.sodocs.net/doc/ae16696478.html,/

VISIT https://www.sodocs.net/doc/ae16696478.html,/acmicpc/

BACK

BACK

BACK

FORWARD

VISIT https://www.sodocs.net/doc/ae16696478.html,/

BACK

BACK

FORWARD

FORWARD

FORWARD

QUIT

Sample Output

https://www.sodocs.net/doc/ae16696478.html,/

https://www.sodocs.net/doc/ae16696478.html,/acmicpc/

https://www.sodocs.net/doc/ae16696478.html,/

https://www.sodocs.net/doc/ae16696478.html,/

Ignored

https://www.sodocs.net/doc/ae16696478.html,/

https://www.sodocs.net/doc/ae16696478.html,/

https://www.sodocs.net/doc/ae16696478.html,/

https://www.sodocs.net/doc/ae16696478.html,/

https://www.sodocs.net/doc/ae16696478.html,/

https://www.sodocs.net/doc/ae16696478.html,/

Ignored

题目大意:

给一些命令来处理网页,有visit,back,forward,exit(这个54)4种命令。Visit命令就是把当前页压到backward栈中,当前页为visit的网站,并清空forward栈。Back命令是把当前页压到forward栈里,当前页变成backward栈的最上边的网页,并将这个页弹出栈。For ward和back相反,是把当前页压到backward栈里,然后当前页变成forward栈的最上边的网页,并将这个页弹出栈。输出的是执行每条命令的后当前的网页,如果backward或forw ard栈为空,则输出‘Ingored’。

题目分析:

解决这道题还得于ACM队在课上所讲模板。记得有位学长讲到了STL,我课后到图书馆查询了资料。看到了有关栈方面的内容。当看到这道题目时,我想到了用栈,就到图书馆仔细看了有关的资料,还到网上查询了一些。这道题目中就是要把浏览过网站压入栈中,在需要时出栈。用到两个栈就是为了实现能够后退而且能够保留前进的信息。

源代码:

#include

#include

#include

#include

using namespace std;

int main()

{

stack forward;

stack backward;

string cmd, url, current;

/* 当前页面*/

current = "https://www.sodocs.net/doc/ae16696478.html,/";

while(1)

{

cin >> cmd;

if (cmd == "VISIT")

{

/* 当前页面入后退栈*/

backward.push(current);

/* 更新当前页面*/

cin >> url;

current = url;

/* 打印当前页面*/

cout << current << endl;

/* 清空前进栈*/

while(!forward.empty()) forward.pop();

}

else if (cmd == "BACK")

{

/* 无法后退*/

if (backward.empty())

{

cout << "Ignored" << endl;

}

else

{

/* 当前页面入前进栈*/

forward.push(current);

/* 更新当前页面*/

current = backward.top();

backward.pop();

/* 打印当前页面*/

cout << current << endl;

}

}

else if (cmd == "FORW ARD")

{

/* 无法前进*/

if (forward.empty())

{

cout << "Ignored" << endl;

}

else

{

/* 当前页面入后退栈*/

backward.push(current);

/* 更新当前页面*/

current = forward.top();

forward.pop();

/* 打印当前页面*/

cout << current << endl;

}

}

else if (cmd == "QUIT")

{

break;

}

}

//system("pause");

return 0;

}

题目三:

Description

A color reduction is a mapping from a set of discrete colors to a smaller one. The s olution to this problem requires that you perform just such a mapping in a standard twenty-four bit RG

B color space. The input consists of a target set of sixteen RGB color values, and a collection of arbitrary RGB colors to be mapped to their closest color in the target set. For our purposes, an RGB color is defined as an ordered trip le (R,G,B) where each value of the triple is an integer from 0 to 255. The distance b etween two colors is defined as the Euclidean distance between two three-dimensional points. That is, given two colors (R1,G1,B1) and (R2,G2,B2), their distance D is give n by the equation

Input

The input is a list of RGB colors, one color per line, specified as three integers from 0 to 255 delimited by a single space. The first sixteen colors form the target set of colors to which the remaining colors will be mapped. The input is terminated by a line containing three -1 values.

Output

For each color to be mapped, output the color and its nearest color from the target set.

If there are more than one color with the same smallest distance, please output the color given first in the color set.

Sample Input

0 0 0

255 255 255

0 0 1

1 1 1

128 0 0

0 128 0

128 128 0

0 0 128

126 168 9

35 86 34

133 41 193

128 0 128

0 128 128

128 128 128

255 0 0

0 1 0

0 0 0

255 255 255

253 254 255

77 79 134

81 218 0

-1 -1 -1

Sample Output

(0,0,0) maps to (0,0,0)

(255,255,255) maps to (255,255,255)

(253,254,255) maps to (255,255,255)

(77,79,134) maps to (128,128,128)

(81,218,0) maps to (126,168,9)

题目分析:这是一道简单题,只是需要按照公式进行计算即可,再记录使得D 取得最小值的RGB值最后输出即可,没有什么难的内容!

源代码:

#include

#include

using namespace std;

int main()

{double s,D;

int i,j,min,flag,target[16][3],color[3];

for(i=0;i<16;i++)

for(j=0;j<3;j++)

cin>>target[i][j];

while(1)

{min=500;

for(j=0;j<3;j++)

cin>>color[j];

if(color[0]==-1)

break;

for(i=0;i<16;i++)

{

for(j=0;j<3;j++)

s=(color[j]-target[i][j])*(color[j]-target[i][j]);

D=sqrt(s);

if(D

{min=D;

flag=i;}}

cout<<"("<

}

return 0;}

转这篇文章不是说做ACM的有多牛B,只是想说对于每个ACMer来说切忌浮躁,踏踏实实的做好每一步才是成功之道。

做算法和作技术哪个难? 都很难, 没有可比性. 但是算法做得好的可以转行做技术, 技术做得好的想转行做算法却很困难.

我是08年下半年将近期末的时候加入华理ACM队的. 我高中的时候没有编程经验, 数学也不好, 高考数学刚及格. 因为第二工业大学的网络工程专业的分数是最低的, 所以就比较巧合地步入了计算机行业. 大一有一门C++课程, 当时我在第一次上机的时候就深深的被C++迷住了. C++是一门极其优美的语言, 相比于高中计算机课上一笔带过的VB, 我最喜欢C++的花括号. 因为学校比较差, 周围的学生没几个专心读书的, 所以对于一个稍微想要学点东西的学生来说, 这样的学校里的硬件资源就显得异常丰富了, 图书馆里很多计算机经典书都是新的, 而且自修室人也很少, 整个大一除了谈谈恋爱解解闷以及陪室友打打魔兽以外, 我大多数时间都在图书馆或者自修室, 虽然在那里的时候不总是做些学习方面的事情...我也会经常无聊的在网上乱逛或者到处下载资料做收藏家. 但正是这个时候我接触到了C++的圣经[The C++ Programming Language], 当时我看了一段时间的电子版, 因为不方便作笔记, 很不爽, 于是在08年1月的时候买了中译本. 之后的大一下学期我又陆陆续续看了部分[Effective C++], [More Effective C++], 还有一些数据结构方面的东西. 然后学期中期的时候我集中精力做了一段时间的数学建模竞赛. 大一结束的时候我通过插班生考试从第二工业大学转来华理, 很不巧, 插班生考试数学又是刚及格. 在暑假期间我去上了CCNA和CCNP 的部分课程, 因为感觉这种纯操作工一样的"背诵"活很不适合我, 于是半途而废了, 暑假在家的时候做了很多windows下的网络编程, 自己写发包程序, 写SYN攻击很有意思.

大二刚来到华理的时候自我感觉很牛B, 因为我自学过的东西几乎都没有人能来跟我做做讨论. 于是我自以为很了不起, 也没怎么在意学校的课程, 除了上课, 平时我几乎都在图书馆或者自修室. 这期间我接触了设计模式, 以及.NET开发. 大约在开学不久, 08年的Regional 还没有开始的时候, 我听说了ACM这种东西. 当时对这个东西我是完全没概念的, 在某个晚上我去奉贤311找了罗老师, 当时咏天也在, 是ACM队准备召新的时候, 罗老师跟每个同学谈了话, 我是最后一个, 跟他哗啦啦地说了很多以前我看过的书, 做过的东西. 被罗老师赞赏了一番之后我更加自以为是了, 并以非正式的身份进了ACM队.

但是直到学期结束, 我也没做什么题. 学期将尽的时候我跟室友展开了一个旧书交易网站的建设, 然后我就一股脑地完全投入进去了, 用了将近五个月的时间, 其中占用了我整个寒假, 我用https://www.sodocs.net/doc/ae16696478.html,+https://www.sodocs.net/doc/ae16696478.html,框架写了一个自以为有很高技术含量的简单的旧书信息发布平台, 全站单页面, 无刷新, 所有操作都用AJAX技术完成, 并且我自己设计了一个貌似很牛B的内存数据库. 结果在09年的上海市计算机应用能力大赛中, 我的作品只获了一个优胜奖. 貌似还有很多同学沉迷于这些, 以为这就是编程. 备受打击的我在迷茫了一阵子之后想起来ACM, 于是在大概3月底的时候开始在PKU切题.

以上都是之前的一些学习经历, 关于ACM的部分从这里开始.

ACM是个很有意思的东西. 起初, 我有点看不起这个东西, 相信很多过早接触技术开发方面的同学都有这样类似的想法, 于是就有了诸如"做算法和做技术哪个难"的问题. 今天再让

我来回答这个问题的话, 我只能说, 都很难, 并且没有可比性. 但是我要补充一点, 大学生可以做技术, 不上大学同样可以做技术. 再要我说得明白一点的话就是, 一年前我用了将近一个星期的时间, 看着MSDN和CSDN写了一个windows下的扫雷程序, 并且在之前我用了若干个星期积累了SDK编程的一些知识, 而今天虽然我已经忘记了几乎所有SDK编程的细节, 不知道怎么去画一个自定义的按钮, 但是给我一台能上网的电脑和一天的时间, 我能把当时的那个扫雷程序写出来, 并且让它的代码量精简掉一半以上.

另外一个事实就是, 绝大多数的ACMer以及几乎所有成功的ACMer的数学都非常好, 不论他们是原来就很好还是后来变得很好.

以下说一些实质性的东西.

编码能力

在ACM的世界里, 编码能力和数学功底是绝对的王道, 硬要分个先后的话, 编码能力就是王道中的王道. ben在学校的时候几乎不看算法类书籍, 最多也就是看看网上零散的知识点, 但是他的成绩是大家有目共睹的, 其中最重要的一点就是他的编码能力至少在华理, 那是令人发指的强. 写一个容斥原理你要多久? 或者给你入射光和球的相关参数, 要你编码求出反射光的运动参数, 你又要写多久? 更有甚者, 在今年暑期的个人赛第一场最后一题, 给你一个扫雷过程中的状态, 要你计算出所有能够确定的雷, 这题ben用了不到半个小时就AC了.

今年的上海赛区同样对编码能力要求很高, 其中我们没有过的I题, 当时ben打印出来的代码有4张纸, 也正是因为这么长的代码, 我跟sky连去纠错的信心都没有, 结果ben自己也没有能够在赛场上把错误找出来.

编码能力的培养的捷径就是做题, 尤其是搜索, 模拟, 计算几何等类型的题目尤其锻炼编码能力. 我能够很快适应ACM, 很大程度上也是得益于大一期间积累的编码能力和C++语言基础.

在锻炼编码能力时, 特别要注意做题要限制时间, 这点跟自己做一些小项目, 小程序完全不同, 不能拖拖拉拉一做就是几天. 最好的方法是在写代码的同时把自己做这题的开始和结束时间都标注上去, 这点在后面关于解题报告的部分我还会说到. 如果觉得有时自己会记不住记录开始时间, 那就养成一个习惯, 每看到一题就先随便submit几个字母, 让它CE一次, 这样以后再回过头来看历史记录就可以知道自己做这题用了多少时间了. 限制做题时间又一个很明显的作用就是可以自我认识, 即了解自己对于某一方面的知识掌握程度, 如果平时遇到某一类型的一般题目(没有特别恶心的trick, 没有特别恶心的输入), 自己需要花超过2个小时去AC, 那么就几乎可以肯定你在赛场上是不太可能把这题做出来的, 换句话说, 如果你在赛场上遇到这种类型的题目就可以暂时先放一放了.

编码能力的一个很关键的地方就是编码风格问题, 一些普遍适应的原则诸如"不要把复杂的语句写在[]里", "不要在if里写复杂的语句", "把if里复杂的逻辑拆分开", "全局变量要特殊命名"等等, 这里不可能一一列举, 唯一的办法就是每次自己在这里吃到苦头的时候把它记录下来. 具体的可以参考ben的方法, 例如把PKU的每次提交情况都粘贴进一个文本文件里, 然后在每次提交记录后面都加上一些注释, 比如"++i写成i++", 或者"dis数组忘记初始化"之类的东西, 这样即使不能保证此类错误以后不会再犯, 也至少可以降低你犯此类错误的概

率. 关于降低犯错的概率还有一个生理学上的解释, 即记忆的编码并不是纯粹的把东西原封不动地放进脑子里, 而是会被我们的神经系统先分解, 储存在大脑各处, 并且其中夹杂了大量记忆的场景, 即记忆发生时的环境. 当我们再次处于类似的环境时就有更大的概率把相关的事情回忆起来, 所谓的联想记忆也是这么一回事. 所以当我们犯错误时就应该尽可能地增加可以勾起我们回忆的材料, 比如写下一些箴言形式的语句加深记忆.

解题报告

上面说到错误记录可以降低我们犯错的概率, 同样的, 解题报告也是基于这一原理, 并且它往往比错误记录更加有效.

我们常常可以看见一些大牛blog上的学术类文章写得非常风趣, 有时里面会参杂一些很搞笑的例子, 于是他们的文章较之纯理论的文章更容易被我们记住. 这仍然是基于上述的生理学原理, 我们用来会议的材料越丰富, 或者这些材料越投我们所好, 我们就越容易联想起来与这些材料相关的东西. 这个原理应该用到些解题报告上来, 那就是尽量把自己关于这题的, 一些有意思的想法记录下来. 另外, 记录自己在解决这题时的思维过程也是非常有益的. 如果你还不知道思维过程的重要性, 那么请去看看波利亚的[How To Solve It](中文译名"怎样解题"), 这是每一个理工科学生的必读读物之一, 甚至你可能会在看完此书的若干年以后才会突然体会到其中的一些条款的极端正确性, 所以, 越早看这本书越好.

关于思维过程, 并不是十分容易被记录下来, 并且, 在你能够明明白白把你对于某题的思维过程叙述出来之前, 你对于这题的解决始终都是不完整的, 即下次遇到此类题目的变种, 十有八九还是无从下手(某些大牛可能因为语文水平不足而无法很好用语言表达, 这是特例...).

写解题报告的另一个好处当然是有助于自己复习. 尤其是在比赛之前看看解题报告是非常有益的, 一般情况下, 就拿我来说, 在两个月内做过的题目, 只要扫一眼解题报告, 一般我能马上把它原样地用代码实现出来.

如果不是很确定自己能坚持写解题报告, 或者担心自己的解法的正确性(很多时候AC了的代码不一定是正确的), 那么就去写blog吧, 把解题报告贴到blog上吧, 也许会有人用很尖锐的言语指出你的错误, 但, 那不正是你想要的吗? 另外贴到blog上也方便了自己日后的搜索.

关于图论

论资格, 我绝对在ACM队是派不上号的, 切题数也十分寒酸, 于是当你处于这种情况的时候就应该考虑主攻某一方面, 毕竟ACM是一项团队比赛, 一把瑞士军刀总也没有几把专业的刀具功能强大. 我在队里主要负责的是图论, 所以我在这里着重说一下图论方面的东西.

ACM题目类型主要分为DP, 图论, 搜索, 数据结构, 模拟, 计算几何, 字符串, 组合数学, 数论等, 其中前两个是重头戏, 我做过的每场比赛里, 前两种题目都是必然会出现的, DP很大程度上需要依靠YY, 即它与IQ的关系很大, 这几乎是一个毋庸置疑的事实...并且DP的某些思想贯穿大部分ACM题目, 很容易于其它类型题目融合起来, 想要掌握它非一朝一夕之事. 而图论相对来说并没有DP那么可怕, 比较容易入门, 并且很多图论类题目可以套模板, 但是相对的, 图论题目也可以出得令人发指的难, 并且其数学模型往往隐藏在搜索, 计

算几何, 字符串等类型的题目后面, 即表面上看起来不是图论, 但实际上这题考的却是图论原理.

图论的变形繁多, ACM题目中尤以Dijkstra最多, 看似简单的Dijkstra, 其变形程度是相当可怕的, 比如会消耗汽油的车的最短路问题, 这就是一个相对简单的二维Dijkstra, 而更加复杂的, 例如08年哈尔滨赛区的H, 一道隐藏在搜索背后的三维Dijkstra, 全场没有队伍出. 解决这类问题的一个根本性方法就是充分理解Dijkstra的定标技术, 以及规范的状态表示. 何为规范? 即当状态维数增高时, 需要对应的结构定义其状态, 并且此结构体切不可与存入堆的结构相混淆, 只要明确了Dijkstra的状态表示以及在某些限制条件下的状态转移(即图中的"边"), 则高维Dijkstra就不再是无法攻克的拦路虎了.

图论的另一个大头就是网络流, 这是图论中最容易套模板的一部分, 也是极其困难的一部分. 说容易套模板是因为往往这类题目在赛场上本身就是中等题或难题, 如果再不能套模板, 八成就变成了无人能出的大自然题了...网络流的变形数量几乎可以赶的上Dijkstra了, 如果算上匹配类的题目则就是有过之而无不及.网络流基本可以分为最大流, 限制流, 费用流三种, 其中最大流可以变形为二分匹配, 费用流可以变形为带权匹配. 其中最大流的算法是其它几种流算法的基础, 主流算法可以分类增广路类和预流推进类, 这两类算法几乎没有联系, 对于ACM, 只要学习前一种就足够了.

网络流类题目, 包括匹配类题目的核心思想就是增广路, 在匹配类题目中特化为交错轨, 这也是增广路类算法的核心. 各种增广路类算法的区别大都在于如何快速找到一条增广路, 其中比较简单的EK就是每次BFS找到一条增广路, 我就不多说了, 而高级一点的ISAP和Dinic都属于SAP, 两者都是基于分层图的思想, 实现分层图的方法只要为每个顶点标记所在层号即可, 其中Dinic是通过一次BFS建立分层图, 然后按照建立好的分层图进行多次DFS找到多条增广路, 从而不用像EK那样每条增广路都做一次BFS. 而ISAP则是在DFS 的同时建立分层图, 即遇到DFS前进不了的时候对下一顶点重新标号, 于是这张分层图是逐步建立的, 建立后可以被后面的DFS所利用, 从而降低寻找增广路的消耗. Dinic和ISAP 都可以用"当前弧"技术进行优化, 而ISAP还有一个进需要添加一行代码的GAP优化, 具体实现很容易在网上搜到. 这里要特别说一下Dinic和ISAP的适用范围, ISAP是万金油, 几乎可以应付绝大部分最大流和限制流的题目, 而Dinic特别适用于有向无环图, 即画在纸上可以分层的题目, 此时Dinic往往只总共需要做一次BFS(因为没有可以回退的边), 这时Dinic 往往会比ISAP快很多. 要知道网络流是一个极度悲观的世界, 任何已知的算法都没有能突破O(n^3), 所以最大流算法写得不好很容易超时. 至于费用流, 可以基于EK算法, 只要将BFS改为SPFA就可以应付几乎所有的费用流问题了, 少量需要用到消负环算法的题目只要用SPFA找负环即可. 而限制流则只是一个定式的建图, 没什么特别的地方. 最后还有一种限制费用流, 如果遇到, 几乎肯定就是大自然题, 可以直接无视之. 关于而分图匹配的算法, 网上资料很多, 核心思想还是基于最大流, 只是可能不用最大流来解释也是可以的. 其中用于带权匹配的KM算法只要准备好模板即可, 一般不会有太大变形.

上面一段说的是既有的算法, 大部分都可以模板化, 其中要注意准备模板的时候最要准备针对整数和浮点数的两种, 对于C++程序员来说, 相应的只要写成函数模板, 然后传入比较函数对象即可, 代码量几乎不会有什么增加.

下面要说说网络流类题目真正的难点之一, 建图. 网络流类题目难在它往往伴随着一个不太

直观的建图, 其中有些利用到最大流最小割定理的建图已经有了套路, 比如说限制流的建图, 最大权闭合图等, 具体可以参见国家IO集训队2007年胡伯涛的论文. 另外一些建图则很有技巧性. 比如"比赛"类题目, 有很多场比赛, 要你求得分能否达到某种条件等, 这时需要把每场比赛看成顶点, 然后两条流进来, 只有一条可以出去, 这种题目的特色是存在大量容量1的边. 还有拆点建图, 这类题目往往一个顶点上包含了2种"属性", 而网络流算法中, 属性是体现在连在边上的, 尽量要使每个顶点表示的属性单一化, 于是就把一个点拆分成两个点, 然后把属性分配出去, 比如PKU有一题说企鹅在冰块上跳来跳去, 冰块就有两个属性, 一个是冰上的企鹅数量, 另一个是冰块再被起跳多少次后会碎掉, 这时就需要把两个属性拆分开来, 拆点的另一个应用就是求最小点隔集, 其中的思想就是像这题冰上企鹅一样, 把出度和入度两个属性分离开. 另外一些更加巧妙的建图可能涉及逆向思维等技高技巧性的思维方法, 这里就不一一列举了.

网络流的难点之二是算法变形, 特别是有的题目在增广路上做文章. 有一种叫做"连续增广路"的技术, 需要深入理解增广路的原理, 今年的上海赛区F题就是基于连续增广路的二分匹配加搜索, 虽然之前做过一个基于最大流算法的连续增广路, 但是很遗憾, 当时没有能想到这个算法. 另外, 与字典序相关的最大流题目往往需要枚举删边, 如字典序最小边割集. 与其它类型题目相结合的算法变形就多不胜数了, 最常见的当属二分答案判可行性, 很多貌似运输类的问题很多都可以归结到这种方法上.

刚才说道了二分答案, 这也是所有图论类(应该说不仅仅是图论)题目最常见的变形, "最(大)小值最大(小)"是这类题目的最一般特征. 这类题目常常跟分数规划联系在一起, 比如最优比率生成树, 最优比率环等.

另外图论的一些经典算法可以衍生出很多强大的应用, 比如差分约束就是Bellman-Ford或SPFA的一个最好的应用, 这类题目的建图关键是找出差分式子. 一个需要特别注意的地方是[算法导论]上对于不连通图上添加顶点的讨论, 最好的方法是不用添加顶点, 开始时直接将dis数组清0, 然后所有顶点入队即可.

生成树类的题目也有很多变形, 如欧几里得生成树, 往往需要利用平面图上的一些几何性质建图, 如曼哈顿距离生成树, 限制度生成树等等, 此类题目套路不多, 且知识点比较散乱, 需要多做题来熟练.

图的连通性也是一个常见的考点. 割点, 桥, 强连通, 双连通问题的求解不仅要准备模板, 还要充分理解模板. 一些地图上的题目(二维的方格阵), 往往有些特殊的性质, 不仅需要你一些建图的敏感度, 偶尔需要在模板中添加一些巧妙的代码.

图论还可以与组合数学和计算几何等产生紧密的联系, 比如生成树和图的计数, 最简单的诸如n个顶点可以产生多少个不同的无向连通图, 这时一些组合数学中的基础原理往往十分有用, 最典型的就是容斥原理.

图论中还有茫茫多的定理, 性质等. 我所知道的最雷人要数08年哈尔滨赛区那道赤裸裸的Havel定理了. 这些定理和性质可能会在一些意想不到的地方发挥作用.

最后图论中的一些NP问题或非NP但是代码不好写的问题, 如旅行商, 同构, 支配集, 最大

团, 以及由树所引申出的一大堆树形DP问题不好准备模板, 但可以考虑准备一些具有代表性的解题报告的纸版材料. 其中树形DP是一个很容易写错的重头戏, 它往往还和背包问题联系在一起, 尤其是泛化物品的背包, 关于泛化物品, 请参见DD牛的[背包九讲].

关于工具

ACM的学习, 对于我们一个弱校来说, 没有牛B的教练, 没有严格的教学, 最主要的学习方式莫过于收集和记录, 不论是外部知识的搜索收集, 还是内部知识的记录整理, 最离不开的当属Google.

搜索我就不用说了, 这里关于知识的记录和整理, 我要推荐如下几个工具: Google Docs, Google Desktop, Google Calender, Everything.

前两个都是辅助你记录和复习你的解题报告, 第三个用于时间管理以及任务计划, 详情请自己去用Google搜索去.

最后一个Everything是windows平台下特别针对NTFS文件系统的一个神奇的搜索工具, 它可以仅仅使用约5MB的内存在1秒内搜索出你的所有NTFS盘上任何一个文件名跟输入关键字匹配的文件, 其原理据说是基于NTFS文件系统的一个特殊的记录表的.

这个东西的一个最有趣的应用可以是这样: 把你硬盘上的所有文件和文件夹都加上标签吧, 用"[]"括起来, 然后用","隔开, 然后任何时候你都可以通过标签搜索到你想要的东西, 一切图片, 论文, 软件等等, 比如PKU的1001题我就可以加上"[java,BigDecimal,浮点数,高精度]"之类的字样.

甚至更精细一点, 定义一些特殊的tag, 比如"tag.r"表示"需要review", "tag.h"表示"我是在别人的help下做出的题目", "tag.p"表示"这题我还有未解决的problem"等等.

关于学习

我所知道的关于学习, 90%来自于[https://www.sodocs.net/doc/ae16696478.html,](李笑来的blog), 和[https://www.sodocs.net/doc/ae16696478.html,](刘未鹏的blog), 把里面关于学习方法的文章看完, 你就升华了. 在此特别感谢上海第二工业大学的王学长告诉我Google Reader的存在, 大二开始的时候我因为这个接触到blog这种东西, 让我对学习方法有了一个相对清醒的认识. 也许很多所谓的方法我们早就知道了, 可就是"很多道理我们其实我们老早就知道, 只是需要一个权威人士告诉我们它确实是正确的".

这里特别要说一些关于学习效率和顺序的问题.

大二就去看什么人工智能, 自然语言处理, 对于绝大多数人来说, 那就是低效, 甚至你在看这些书的时候连笔记都不知道该怎么记, 更何况还有那么多人看书都没有记笔记的习惯. 但是即使你用心做了笔记, 也不一定能学到什么东西, 比如我当时就将近记了一大本的关于人工智能, 心理学之类的东西, 可现在回头看看一恰的笔记几乎已经不敢相信那是我自己写的了, 完全不认识. 究其原因有二, 一是先导知识储备不足, 二是没有及时回顾笔记. 这两点在很多人的学习过程中都在不断重复上演着, 其结果就是浪费了大量时间却学不到什么东西. 所谓的"做开发"也是如此, 连关系数据库的几个范式都不知道是什么就去弄什么SQL

Server, 搞什么ORM, 全都是空谈, 充其量也就是会用用工具而已.

就我目前的经历来看, 我认为作为一个软件方向的CS学生, 相对高效的学习方案应该是学基础课时学好高数和英语(我现在就特别想再去重学高数), 闲暇时间搞搞C++, Java, 等各种语言, 至少做到一个了解的程度, 个别的要熟练, 与计算机软件关系不是很大的理科课程成绩搞到90+就行, 比如物理, 比如电路, 线性代数很简单, 概率论要特别认真学, 特别是经常要拿起来复习复习, 这是一门终身受用的学科. 然后其余的时间可以用来啃算法导论, 相信我, 这本书普通人大学四年根本不可能啃完. 总之数学类的书看的再多都嫌少. 另外可以扩展出去接触一些人文类书籍, 特别是传记类, 励志类的东西.

关于修养

我刚上大学的时候有这么一个习惯, 拿一些自己心中已经知道答案的问题去请教老师, 以显得自己很好学, 很牛 B. 记得我有过在软件工程选修课上跑去问我们学校有没有关于"设计模式"的课程, 或者问ben一些明显Google一下就能知道答案的问题...等等等等都是内心浮躁的表现.

自我修养是一种很要紧的东西, 对于一个性格内向的ACMer来说, 这往往不会有什么问题, 这是由性格决定的, 但不是每个人都性格内向, 不是每个人都能保持内敛. 一旦你有装B(一切骄傲, 或者因为自己的某方面才能而沾沾自喜, 或者想要显露自己, 不管和不合适, 暂且用"装B"来代替吧)的行为或者想法, 或者仅仅是潜意识, 那就预示着你会被大多数人看不起, 会大量浪费自己的时间, 会降低自己的学习效率, 会使自己成为井底之蛙. 不过完全不装B 倒也不太好做到, 比如我以为自己写blog多少有些显露自己的意思, 自我分析一下, 动机大概有如下几条: 想让日后身边的某人突然发现我说:"啊, 你就是Answeror啊!", 想让我以前女朋友在若干年后突然发现我的blog说:"原来我以前男朋友这么好学, 这么有修养有文化!", 想让我被某些大学教授或者公司里的人认识, 想结交志同道合朋友, 想让别人给我的解题报告挑错...

写blog这件事情也就算了, 毕竟是件利人利己的好事, 偶尔装装B也就算了. 但是像我在本文开头说的那样, 刚进华理仅仅因为自己有点C++和网络工程知识的皮毛就装出一副很牛B 的样子, 那种装任谁都无法忍受. 尤其是第一次跟罗老师的谈话, 简直就是装到了极点, 以至于我后来就有这么一个想法: 反正我可以做技术活, 干嘛非要搞ACM, 我可以自由地去学心理学, 学人工智能, 学.NET, 我牛B着呢, ACM算个屁. 然后我就傻BB地搞了5个月的.NET, 然后到大三上数据库原理的时候发现当时花了一个星期学的种种东西现在只是一节课的事情, 直到那时我还在装B, 跟旁边的同学说我上述的体会, 仿彿就是在告诉他说:"你看我牛B吧, 我老早就知道这是什么东西了, 还做过它的开发", 时至今日, 我仍然有时会忍不住在同学讨论C++种种语言特性时上去插插嘴, 装装B. 高中的一个好友曾这样形容我: "他这个人啊, 只要看了什么书或者电影之类的, 就要马上在他的文章里体现出来".

听起来很好笑吧, 请正在看这些文字的你不妨停下来反思一下自己最近一个星期有没有类似的行为?

作为一个ACMer, 改掉这些吧.

我们做ACM的, 本来在这个学风不正的计算机学院里就是一群特殊人群, 我们需要做的仅

仅是不停地补充知识, 完善自己, 没必要费尽心机去博得他人的一两句赞美之辞. 我是谁? 我就是华理的一个ACMer. 我每天窝在机房里为的不是哪天去比赛有小MM来找我们签名, 而是让自己精通各种算法, 提升自己的数学修养, 增强自己解决问题的能力, 培养自己内敛的人格, 然后在某日某公司的面试时让面试官打心地里认为我是个人才, 然后用我以前长期积累的知识写出卓越的软件.

希望你我都能早日问心无愧地说出上面的话.

ACM题

求体积 #include #include #define PI 3.1415927 int main() { double x; while(scanf("%lf",&x)!=EOF) { printf("%.3lf\n",(4.0*PI*x*x*x)/3.0); } return 0; } 求a+b II. #include #include #define N 1005 char A[N],B[N],sum[N]; int main() { int T,i,j,k,x,sign; while(scanf("%d",&T)!=EOF) { for(i=0;i

{ sum[x]=(A[j]-'0')+(B[k]-'0')+sign-10; sign=1; } } #include using namespace std; int main() { int a, b; while(cin >> a >> b) cout << a + b << endl; return 0; 求a+b #include using namespace std; int main() { int a,b,s; while(cin>>a>>b) { s=a+b; cout< #include int main() { char s[3],a,b,c,temp; while(scanf("%s",s)!=EOF) { a=s[0];b=s[1];c=s[2]; if(a>b) { temp=a; a=b;

ACM竞赛试题集锦

取石子游戏 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

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 main() { long a,b; while((scanf("%ld%ld",&a,&b))!=EOF) { printf("%ld\n",a+b); } } 详情参考https://www.sodocs.net/doc/ae16696478.html,/faq.php 二、ACM分类 主流算法: 1.搜索//回溯 Problem 1019 猫捉老鼠 Time Limit: 1000 mSec Memory Limit : 32768 KB Problem Description 一只猫和一只老鼠在10*10的迷宫中。迷宫中的每个方格可以是空的,或者含有障碍。猫和老鼠可以进入任意一个空的方格中。当他们相遇时,猫和老鼠在同一个方格中。但是,无论猫或老鼠都不能进入有障碍的方格。我们可以用字符组成的二维数组表示迷宫,如下图所示。

Acm试题及答案

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青年歌手大奖赛_评委会打分............................... 错误!未定义书签。

ACM题目

【题目 1】N皇后问题(含八皇后问题的扩展,规则同八皇后):在N*N的棋盘上,放置N个皇后,要求每一横行 每一列,每一对角线上均只能放置一个皇后,问可能的方案及方案数。 【题目 2】排球队员站位问题 ┏━━━━━━━━┓图为排球场的平面图,其中一、二、三、四、五、六为位置编号,┃ ┃二、三、四号位置为前排,一、六、五号位为后排。某队比赛时,┃ ┃一、四号位放主攻手,二、五号位放二传手,三、六号位放副攻┠──┬──┬──┨手。队员所穿球衣分别为1,2,3,4,5,6号,但每个队 ┃ 四 │ 三 │ 二 ┃员的球衣都与他们的站位号不同。已知1号、6号队员不在后排,┠──┼──┼──┨2号、3号队员不是二传手,3号、4号队员不在同一排,5号、┃ 五 │ 六 │ 一 ┃6号队员不是副攻手。 ┗━━┷━━┷━━┛编程求每个队员的站位情况。 【算法分析】本题可用一般的穷举法得出答案。也可用回溯法。以下为回溯解法。 【题目 2】把自然数N分解为若干个自然数之和。 【参考答案】 n │ total 5 │ 7 6 │ 11 7 │ 15 10 │ 42 100 │ 190569291 【题目 3】把自然数N分解为若干个自然数之积。 【题目 4】马的遍历问题。在N*M的棋盘中,马只能走日字。马从位置(x,y)处出发,把棋盘的每一格都走一次,且只走一次。找出所有路径。 【参考程序】 {深度优先搜索法} 【题目 5】加法分式分解。如:1/2=1/4+1/4.找出所有方案。 输入:N MN为要分解的分数的分母 M为分解成多少项 【题目 6】地图着色问题 【题目 7】在n*n的正方形中放置长为2,宽为1的长条块,问放置方案如何 【题目 8】找迷宫的最短路径。(广度优先搜索算法)

整理出ACM所有题目及答案

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)

acm ZOJ刷题推荐

初学者题: 1001 1037 1048 1049 1051 1067 1115 1151 1201 1205 1216 1240 1241 1242 1251 1292 1331 1334 1337 1338 1350 1365 1382 1383 1394 1402 1405 1414 1494 1514 1622 1715 1730 1755 1760 1763 1796 1813 1879 1889 1904 1915 1949 2001 2022 2099 2104 2108 2172 2176 2201 2208 2321 2345 2351 2376 2388 2405 2417 2433 模拟问题: 1006 1009 1012 1016 1019 1023 1026 1028 1038 1042 1045 1051 1056 1057 1058 1061 1065 1066 1068 1072 1073 1078 1087 1088 1097 1098 1099 1103 1111 1121 1124 1126 1128 1133 1138 1146 1152 1154 1160 1175 1178 1187 1194 1207 1222 1224 1244 1259 1267 1274 1275 1277 1278 1279 1281 1282 1294 1295 1300 1308 1317 1324 1339 1351 1362 1392 1393 1397 1398 1399 1400 1402 1432 1434 1444 1452 1475 1487 1493 1497 1517 1526 1527 1530 1531 1552 1569 1573 1592 1601 1610 1623 1631 1641 1652 1657 1659 1682 1692 1700 1702 1707 1708 1712 1728 1732 1737 1746 1747 1750 1752 1754 1758 1764 1768 1774 1797 1799 1804 1807 1811 1822 1824 1831 1834 1837 1838 1842 1844 1845 1854 1858 1862 1870 1881 1884 1889 1896 1906 1921 1951 1969 1978 2000 2022 2040 2046 2047 2051 2072 2084 2101 2112 2131 2133 2138 2148 2153 2156 2160 2164 2172 2178 2184 2185 2187 2189 2193 2196 2201 2204 2208 2211 2212 2220 2229 2233 2239 2240 2261 2262 2269 2277 2288 2301 2309 2311 2312 2316 2320 2321 2322 2328 2330 2350 2389 2405 2410 2414 2420 2421 2483 2508 2560 2569 2572 2593 2613 2617 2680 2681 2731 2732 2743 动态规划:

部分ACM题目与答案

1001 Sum Problem (2) 1089 A+B for Input-Output Practice (I) (3) 1090 A+B for Input-Output Practice (II) (3) 1091 A+B for Input-Output Practice (III) (3) 1092 A+B for Input-Output Practice (IV) (3) 1093 A+B for Input-Output Practice (V) (3) 1094 A+B for Input-Output Practice (VI) (3) 1095 A+B for Input-Output Practice (VII) (3) 1096 A+B for Input-Output Practice (VIII) (3) 2000 ASCII码排序 (3) 2001计算两点间的距离 (3) 2002计算球体积 (3) 2003求绝对值 (3) 2004成绩转换 (3) 2005第几天? (3) 2006求奇数的乘积 (3) 2007平方和与立方和 (3) 2008数值统计 (3) 2009求数列的和 (3) 2010水仙花数 (3) 2011多项式求和 (3) 2012素数判定 (3) 2014青年歌手大奖赛_评委会打分 (3) 2015偶数求和 (3) 2016数据的交换输出 (3) 2017字符串统计 (3) 2019数列有序! (3) 2020绝对值排序 (3) 2021发工资咯:) (3) 2033人见人爱A+B (3) 2039三角形 (3) 2040亲和数 (3)

ACM部分练习题目答案

ACM部分习题答案: A + B Problem Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 100972 Accepted Submission(s): 33404 Problem Description Calculate A + B. Input Each line will contain two integers A and B. Process to end of file. Output For each case, output A + B in one line. Sample Input 1 1 Sample Output 2 # include Int main() {int x,y,s; while(scanf("%d %d",&x,&y)!=EOF) {s=x+y; printf("%d\n",s);} return 0; } Sum Problem Time Limit: 1000/500 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 85964 Accepted Submission(s): 19422 Problem Description Hey, welcome to HDOJ(Hangzhou Dianzi University Online Judge). In this problem, your task is to calculate SUM(n) = 1 + 2 + 3 + ... + n. Input The input will consist of a series of integers n, one integer per line. Output For each case, output SUM(n) in one line, followed by a blank line. You may assume the result will be in the range of 32-bit signed integer. Sample Input 1 100 Sample Output 1 5050 # include int main() {int n; long int s;

北大 poj acm题目推荐50题

-北大poj acm题目推荐50题 POJ == 北京大学ACM在线评测系统https://www.sodocs.net/doc/ae16696478.html,/JudgeOnline 1. 标记难和稍难的题目大家可以看看,思考一下,不做要求,当然有能力的同学可以直接切掉。 2. 标记为A and B 的题目是比较相似的题目,建议大家两个一起做,可以对比总结,且二者算作一个题目。 3. 列表中大约有70个题目。大家选做其中的50道,且每类题目有最低数量限制。 4. 这里不少题目在BUPT ACM FTP 上面都有代码,请大家合理利用资源。 5. 50个题目要求每个题目都要写总结,养成良好的习惯。 6. 这50道题的规定是我们的建议,如果大家有自己的想法请与我们Email 联系。 7. 建议使用C++ 的同学在POJ 上用G++ 提交。 8. 形成自己编写代码的风格,至少看上去美观,思路清晰(好的代码可以很清楚反映出解题思路)。 9. 这个列表的目的在于让大家对各个方面的算法有个了解,也许要求有些苛刻,教条,请大家谅解,这些是我们这些年的经验总结,所以也请 大家尊重我们的劳动成果。 10. 提交要求:一个总文件夹名为bupt0xx (即你的比赛帐号), 这个文件夹内有各个题目类别的子目录(文件夹),将相应的解题报告放入对应 类别的文件夹。在本学期期末,小学期开始前,将该文件夹的压缩包发至buptacm@https://www.sodocs.net/doc/ae16696478.html,。 对于每个题目只要求一个POJxxxx.cpp 或POJxxxx.java (xxxx表示POJ该题题号) 的文件,注意不要加入整个project 。 11. 如果有同学很早做完了要求的题目,请尽快和我们联系,我们将指导下一步的训练。 下面是一个解题报告的范例: 例如:POJ1000.cpp

acm题库[大全]

acm题库[大全] 座位调整 题目描述: 百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现,员工如果可以在自己喜欢的美食旁边工作,工作效率会大大提高。因此,百度决定进行一次员工座位的大调整。 调整的方法如下: 1 ( 首先将办公区按照各种零食的摆放分成 N 个不同的区域。(例如:可乐区,饼干区,牛奶区等等)。 2 ( 每个员工对不同的零食区域有不同的喜好程度(喜好程度度的范围为 1 —100 的整数,喜好程度越大表示该员工越希望被调整到相应的零食区域)。 3 ( 由于每个零食区域可以容纳的员工数量有限,人力资源部希望找到一个最优的调整方案令到总的喜好程度最大。 数据输入: 第一行包含两个整数 N , M ,( 1<=N , M<=300 )。分别表示 N 个区域和M 个员工。 第二行是 N 个整数构成的数列 a ,其中 a[i] 表示第 i 个区域可以容纳的员工数, (1<=a[i]<=M , a[1]+a[2]+..+a[N]=M) 。 紧接着是一个 M*N 的矩阵 P , P ( i , j )表示第 i 个员工对第 j 个区域的喜好度。 答案输出: 对于每个测试数据,输出可以达到的最大的喜好程度。 3 3

1 1 1 100 50 25 100 50 25 100 50 25 输出样例 175 3 10 2 4 4 100 50 25 100 50 25 100 50 25 100 50 25 100 50 25 100 50 25 100 50 25 100 50 25 100 50 25 100 50 25 2006 年百度之星程序设计大赛初赛题目 4 2007-05-14 17:39 剪刀石头布 N 个小孩正在和你玩一种剪刀石头布游戏。 N 个小孩中有一个是裁判,其余小孩分成三组(不排除某些组没有任何成员的可能性),但是你不知道谁是裁判,也不知道小孩们的分组情况。然后,小孩们开始玩剪刀石头布游戏,一共玩 M 次,

淅大acm题性分类

浙江大学(ZJU):https://www.sodocs.net/doc/ae16696478.html,/ DP: 1011 NTA 简单题 1013 Great Equipment 简单题 1024 Calendar Game 简单题 1027 Human Gene Functions 简单题 1037 Gridland 简单题 1052 Algernon\'\'s Noxious Emissions 简单题 1409 Communication System 简单题,但是很容易看错~~~ 1425 Crossed Matchings 简单题 1438 Asteroids! 简单题 1459 String Distance and Transform Process 简单题 1462 Team Them Up! 简单题 1556 Heroes Of Might And Magic 简单题,不过背景蛮有意思的…… 1520 Duty Free Shop 简单题 1524 Supermarket 简单题 1301 The New Villa 简单题 1303 Jury Compromise 其实不是很难,但是很容易错,555…… 1345 Best Deal 简单题,但是也很容易错……555…… 1360 Radar Installation 简单题 1396 The Umbrella Problem: 2054 简单题 1058 Currency Exchange 简单题 1076 Gene Assembly 简单题 1092 Arbitrage 简单题 1093 Monkey and Banana 简单题 1094 Matrix Chain Multiplication 简单题 1536 Labyrinth 简单题 1100 Mondriaan\'\'s Dream 简单题,DP可以过,不过据说有复杂的组合公式1103 Hike on a Graph 简单题 1134 Strategic Game 简单题 1147 Formatting Text 简单题 1148 The Game 简单题 1161 Gone Fishing 简单题 1180 Self Numbers 简单题 1192 It\'\'s not a Bug, It\'\'s a Feature! 简单题 1196 Fast Food 简单题 1107 FatMouse and Cheese 简单题,不过题目描述有些混乱 1136 Multiple 简单题,BFS 1276 Optimal Array Multiplication Sequence 简单题 1255 The Path 简单题 1250 Always On the Run 简单题 1213 Lumber Cutting 简单题 1206 Win the Bonus 简单题

2014ACM大赛题目

题目描述 恶魔猎手尤迫安野心勃勃.他背叛了暗夜精灵,率深藏在海底的那加企图叛变:守望者在与尤迪安的交锋中遭遇了围杀.被困在一个荒芜的大岛上。为了杀死守望者,尤迪安开始对这个荒岛施咒,这座岛很快就会沉下去,到那时,刀上的所有人都会遇难:守望者的跑步速度,为17m/s,以这样的速度是无法逃离荒岛的。庆幸的是守望者拥有闪烁法术,可在1s内移动60m,不过每次使用闪烁法术都会消耗魔法值10点。守望者的魔法值恢复的速度为4点/s,只有处在原地休息状态时才能恢复。 现在已知守望者的魔法初值M,他所在的初始位置与岛的出口之间的距离S,岛沉没的时间T。你的任务是写一个程序帮助守望者计算如何在最短的时间内逃离荒岛,若不能逃出,则输出守望者在剩下的时间内能走的最远距离。注意:守望者跑步、闪烁或休息活动均以秒(s)为单位。且每次活动的持续时间为整数秒。距离的单位为米(m)。 输入 输入文件escape.in仅一行,包括空格隔开的三个非负整数M,S,T。 输出 输出文件escape.out包含两行: 第1行为字符串"Yes"或"No" (区分大小写),即守望者是否能逃离荒岛。 第2行包含一个整数,第一行为"Yes" (区分大小写)时表示守望着逃离荒岛的最短时间 第一行为"No" (区分大小写) 时表示守望者能走的最远距离。 样例输入 39 200 4 样例输出 No 197 提示 7 180 9 Yes 30%的数据满足: 1 <= T<= 10,1 <=S<= 100 50%的数据满足: 1 <= T <= 1000,1 <= S <= 10000

100%的数据满足: 1 <= T <= 300000,0 <= M<=1000 1 <=S <= 10^8 题目描述 A group of friends has just completed their CS assignments, and because of the nice weather, they decide to go to Joe's house for a BBQ. Unfortunately, after all that coding, they are too tired to walk. Fortunately, between them they have enough cars to take everyone. Joe remembers that he needs to stop off at the supermarket along the way to buy some burgers and pop. Jenn proposes that they stop at her house to get a frisbee. Jim decides that he doesn't like burgers, and wants to grab a pizza along the way. After having spent so long in the computer lab, Jerry's eyes have become very sensitive to sunlight, so he needs to stop at his house for his sunglasses. And so it goes: each person needs to run a little errand along the way. At this rate, the friends worry that it will be dark by the time they get to Joe's house. They launch into a heated discussion to about who should go in which car to minimize the time needed for everyone to reach Joe's house. The discussion itself, of course, wastes precious time that could be better spent at the BBQ. To help the group, you will write a program to settle the discussion by computing an optimal assignment of people to cars. The overall travel time is the maximum of the

(整理)ACM大量习题题库及建议培养计划.

//别人总结的,确实很多,但有信心就能学完! 一.基本算法: (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必做50题——高精度

1 POJ 1001 Exponentiation 高精度数的计算,以前在网上看到过一个计算大数阶乘比如10000000!的算法,总体思想就是将结果用数组保存起来,然后将结果的每一位与乘数相乘,当然还有进位... 有了这个算法的思想,这个题思路就可以是:先将输入的小数转换成一个整数,当然这个整数肯定能够用int类型的变量保存,比如1.2345, 通过函数removeDot()将它转化成12345,然后利用大数阶乘的思想计算12345*12345.....*12345, 最后的就是输出了,这个要考虑的情况比较多,因为这个也W A了5次才AC(笨的要死), 情况虽多,但不难. 这道题是高精度计算的,不算很难,但是很繁琐,尤其是对输入输出的要求。被这道题搞了好久,耐心来,一点一点调试,总会成功的。 #include #include #include using namespace std; char ans[10]; char res[2][205]; __int64 ps;//有几位小数点 int len;//长度,R的有效长度 //计算c = b * a void Multiply(char * b,int bt,char * a,int at,char * c) { int i,j; int up=0; for(i=0;i=10) { up=t/10; t=t%10; c[i+j]=t+48; if(j==(bt-1) )

部分ACM题目与答案解析

1001 Sum Problem (3) 1089 A+B for Input-Output Practice (I) (6) 1090 A+B for Input-Output Practice (II) (9) 1091 A+B for Input-Output Practice (III) (13) 1092 A+B for Input-Output Practice (IV) (15) 1093 A+B for Input-Output Practice (V) (19) 1094 A+B for Input-Output Practice (VI) (22) 1095 A+B for Input-Output Practice (VII) (24) 1096 A+B for Input-Output Practice (VIII) (27) 2000 ASCII码排序 (30) 2001计算两点间的距离 (33) 2002计算球体积 (35) 2003求绝对值 (38) 2004成绩转换 (40) 2005第几天? (43) 2006求奇数的乘积 (47) 2007平方和与立方和 (49) 2008数值统计 (52) 2009求数列的和 (55) 2010水仙花数 (57) 2011多项式求和 (61)

2012素数判定 (64) 2014青年歌手大奖赛_评委会打分 (67) 2015偶数求和 (70) 2016数据的交换输出 (74) 2017字符串统计 (78) 2019数列有序! (80) 2020绝对值排序 (84) 2021发工资咯:) (87) 2033人见人爱A+B (90) 2039三角形 (94) 2040亲和数 (96)

整理出ACM所有题目及答案

1000 A + B Problem Problem Description Calculate A + B. Input Each line will contain two integers A and B. Process to end of file. Output For each case, output A + B in one line. Sample Input 1 1 Sample Output 2 Author HDOJ 代码: #include int main() { int a,b; while(scanf("%d %d",&a,&b)!=EOF) printf("%d\n",a+b); } 1001 Sum Problem Problem Description Hey, welcome to HDOJ(Hangzhou Dianzi University Online Judge). In this problem, your task is to calculate SUM(n) = 1 + 2 + 3 + ... + n.

Input The input will consist of a series of integers n, one integer per line. Output For each case, output SUM(n) in one line, followed by a blank line. You may assume the result will be in the range of 32-bit signed integer. Sample Input 1 100 Sample Output 1 5050 Author DOOM III 解答: #include main() { int n,i,sum; sum=0; while((scanf("%d",&n)!=-1)) { sum=0; for(i=0;i<=n;i++) sum+=i; printf("%d\n\n",sum); } }

acm 大赛 英语版 题目

////////////////////////////////////////////// The Mailboxes Manufacturers Problem 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 an d 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 n ot blow up even 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.

相关主题