Question

ACM...C++(进来一下，不是做题，求方法而已)

做了几天的ACM了，但是每次提交都是超时，这些超时的题目，都是和循环有关，比如n等于号几万。。。由于我直接循环，所以照成超时。。请问这种题目一般这么做，找规律？

Answer 1

对。ACM考的题目许多都能用暴力枚举法解，但是用暴力枚举法解通常在遭遇到比较极端的测试数据的时候会超时。
正确的解决办法是优化算法，降低算法的时间复杂度。

Answer 2

ACM竞赛的大多数题目是考察有限时间内对算法的灵活和熟练的使用。正式比赛中除了照顾弱队的水题很少出现直接循环能一次性过的题目，除非是虽然解法简单/编码容易但是题干本身很复杂的题目（相对更侧重于考察读题的仔细和简化问题的能力）。
LZ既然能写得出代码并且有信心提交，那么对于题意理解和编码方面应该没什么问题。算法显然是决定因素——同样是循环，可能时间复杂度O(n^2)的算法需要比O(n)快10^5倍才能AC而不是TLE。如果常规方法总是超时，那么说明这个算法有问题，在循环内部优化是没多少用的，应该换个思路，例如归纳一些状态/推导出方程/使用DP（动态规划）。对于短时间提高而言，最有效的方法是记忆竞赛中常见的算法的实现思路（至于理解证明之类的要求更高，当然能做到就更好，方便举一反三临场发挥组合实现多个算法）。具体可以先看《算法导论》之类的经典算法书籍（不用全看完全理解，但至少要会复杂度分析以及熟悉典型的问题场景，例如能判断出什么时候选择什么样的排序容易正确实现且最省时间——包括写代码的时间），然后多看一些解题报告。最好能搞到别人用的模板代码参考，因为很多模板中除了有大量的适合实际比赛的代码以外，为了便于理解也会写一些简要的思路。
另外，LZ既然用C++，那么熟悉标准库的使用对此很有帮助。尤其是STL，实现一些算法非常省时间（许多用C代码要自己写的东西都被封装好了）。标准库中除了<cstdio>（比iostream效率高，有些题提示cin/cout直接输入/输出都会超时）、<cstring>、<cstdlib>、<cmath>等需要掌握外，应该着重于熟练<vector>、<set>、<map>、<stack>、<queue>和<string>等（拟）容器类（适配器）以及<algorithm>中的内容；<functional>、<iterator>之中一些编码技巧可以借鉴；对于其它<iostream>、<limits>、<numeric>等作基本了解，会使用即可；<new>、<stdexception>、<iosfwd>、<typeinfo>这类语言基础支持和<locale>、<clocale>、<csignal>这类特定移植性/系统相关的则基本上不用管。
====
[原创回答团]

Answer 3

计算机的计算速度大约1s10的8次方次，所以如果N=10000并且你用的是N^2的算法，那你的程序就必然超时了。所以，敲代码前要先估计一下自己算法的复杂度，如果计算的次数超过10的8次方（这里的计算代表了各种操作，赋值和判断可能放的更宽一点，如果是运算就不行了，如果是浮点数运算，那就更不行了），那就去思考有没有另外的比较好的方法去解决这个问题。尽量减少运算的次数，有时候减少重复计算（比如利用已经计算出来的结果）也是一个好办法。或者可以用空间的消耗去换取时间（比如字典树的操作），关于acm的题目，水题还是挺多的，通过不断积累你才能慢慢的摸到门路，这是一个比较缓慢的过程，方法的掌握不是一时半会就能学会的，做的题多了，知道的算法多了，你也就知道遇到这种题应该怎么办了，还是要多学多练啊。本人现在勉强算个老手，在oj上刷了五六百道题了，这只是我的一点经验。对于新手，应该从基础做起。

Answer 4

这叫人怎么回答，只能说这种题目不能暴力，要么找规律，要么想出更好的算法，或者把你原来的算法做适当的优化，涉及到优化，就够讲好几本书了。