超出时间限制或TLE可能是导致竞争性编码人员感到沮丧的重要原因。 如果您正在尝试一种方法，则可能需要更改方法，但是如果您遇到了编码难题，并且无法想到解决问题的任何其他方法，则可以尝试使用这些技术来解决那些狡猾的测试用例。
C ++开发人员通常习惯于将std :: cin和std :: cout用于标准的I / O操作，但并不是最快的。 如果您懒于更改代码，则只需添加下面给出的语句即可享受速度的提升。
第一条语句禁用C和C ++样式I / O之间的同步，因此，如果将它们组合在一起，可能会导致未知错误。 对于竞争性编码，通常不需要同时使用两者，因此您可以毫无后顾之忧地使用它。
第二条语句将std :: cin与std :: cout结合在一起。 每当使用其中一个流时，都会刷新另一个流，但是当您解开它们时，它们将不再彼此刷新，这将导致更好的性能。 当然，您始终可以使用旧的C朋友， scanf和printf 。 它们比std :: cin和std :: cout快大约三倍，但是与不同步的std :: cin和std :: cout相比，它们的性能提升不多。
希望它更快？ 您要输入整数吗？ 哦，那你真幸运！ 只需复制此函数，即可以最快的线程安全方式获取整数输入。
上面给出的函数读取每个字符并将其转换为整数。 此方法免除了scanf必须进行的许多系统调用，例如推断输入类型。
您一定想知道为什么我写了“最快，线程安全的方法”。 好吧，因为有一种更快的方法，但是这使它成为线程不安全的。 要使用吗？ 用getchar_unlocked()替换getchar()并体验野兽。 在竞争性编程环境中，除非您正在执行与并发相关的任务，否则不必担心线程安全，因此请继续！
没有任何证据，您如何相信我所说的话？ 好吧，这是。 对不同的方法进行了基准测试，结果在下面给出。 如果您想查看基准测试中使用的代码，我已将其上载到GitHub存储库，可以在找到。
尽管向量由于其可扩展性而非常出色，但是相同的属性也使它们变慢。 std :: vector实现为动态数组，这意味着每次需要增加数组的大小时，它都会创建另一个数组，其大小增加一倍，然后从上一个数组中复制元素。 如果在添加项目之前知道向量的大小，则保留空间可消除复制元素所需的开销，因为它创建的数组至少与保留的大小一样大。
其中max是要存储在向量中的元素数。
添加一个保留使您的代码快约1.2倍。
同样，C样式数组或std :: array每天都比使用向量更快，但是必须在编译时知道其大小，因此使用起来并不总是可行的。 因此，向量是最好的选择，最好事先预留空间。
关于std :: vector的另一个令人惊讶的事情是at()函数。 它似乎和下标运算符[]做同样的事情，但是当测量性能时，它实际上慢了3.1倍。
这可能会严重破坏程序所花费的时间。 原因是at运算符已内置检查下标运算符没有的超出范围的值，因此，如果您给出的值超出范围，则可能会给您带来细分错误或导致未知错误而不告诉您什么在出错时会抛出异常。
关于std :: vector您应该了解的最后一件事是，永远不要使用循环和push_back()手动将std :: vector复制到另一个对象，而应该使用赋值运算符= 。 如下表所示，速度差异巨大。
造成这种性能差异的原因是，在执行分配时，它知道要复制的向量的大小，并且只需要调用一次内存管理器即可创建分配的向量的空间并复制所有元素，这与push_back()操作不同。呼叫每个要素的经理。
在C ++中使用字符串的最快方法是使用C样式字符串，即字符数组，与字符数组具有同等的性能，但是程序员经常犯的一个错误是使用+运算符附加到字符串上。 不适合使用的原因是，它创建了两个操作数字符串总大小的另一个字符数组，并将第一个字符数组复制到该数组，同时将另一个字符串连接到新创建的数组。 相反，您应该使用append()函数，或者等效的+
对于支持它的所有类，使用+ =运算符代替+运算符更好。 这有助于减少创建新对象并复制第一个对象然后向其添加第二个对象所花费的时间和内存。
另外，使用std :: string或任何其他类时，最好使用构造函数进行初始化，而不是使用赋值运算符进行初始化。
如果您不了解std :: list ，我们已经在这里完成了，但是如果您知道并且正在考虑使用它，请再考虑一下。 std :: list是一个双向链接的列表，因此它比std :: vector更具优势，因为它可以在恒定时间内删除和插入任何位置。 当您需要时，这似乎很棒，但是向量可以由处理器缓存，因此顺序访问比使用std
您可能会看到一个名为谓词的变量。 谓词是从向量中获取元素并返回布尔值的函数。 通常，每次从向量中删除一个项目时，其后的对象都会向前移动，但是如果使用了asel_if()构造，则在删除所有元素之后才进行移动，因此对于删除多个元素非常有用 。 下面给出了一个示例谓词。
如果在delete_if()表达式中使用上述函数：
它将从向量v中删除所有零。
如果要查看std :: vector和std :: list之间的综合基准，可以在 Baptiste Wicht的这篇精美文章。 阅读该文章后，您可能会想到一个问题：“如果std :: list比使用std :: vector更糟糕，那么为什么即使在标准库中也是如此？” 这是因为在某些地方列表会更好，例如，当存储在列表中的元素很大且缓存中无法容纳很多元素时，列表可能会优先于向量。
std :: map被维护为二进制搜索树，与unordered_map相比，使用map的主要优点是它根据键对元素进行排序。 使用std :: map而不是std :: unordered_map的另一个好处是，它支持开箱即用的对。 但是，O(log n)和O(1)之间的差异可能是TLE和AC解决方案之间的差异。 因此，让我们看一下如何为一对整数创建哈希函数。
此结构尝试为其获取的每对返回唯一的整数。 您只需要将此结构插入您的unordered_map中，瞧！ 您的哈希表现在支持std :: pair <int，int> 。
您可以使用Google的更多哈希函数来满足不同需求，并选择自己的风格。
另外，您也可以在std :: unordered_map中使用reserve。 在我的基准测试中，它加快了将元素添加到哈希表的过程1.3倍。
如果您想要一个比unordered_map更快的哈希表，并且您或您的CP平台使用g ++，则有个好消息。 您可以使用 ！ 它不是标准库的一部分，但具有与std :: unordered_map几乎相同的接口，但速度更快。
__gnu_pbds :: gp_hash_table比std :: unordered_map更快，因为它删除了STL必须保留的许多不必要的功能。 如果您想得到更好的解释，可以在查看评论，如果您想获得更多的见解，可以看到这篇文章。
您还可以对std :: unordered_map进行另一项优化，将其max_load_factor设置为0.25。 负载因子定义为哈希表中元素数与存储桶数之比。 将max_load_factor保持在0.25意味着至少3/4的存储桶将为空。 这样可以减少哈希表中的冲突； 因此，查找时间还会增加哈希表占用的空间。 使用它时，我找不到很多性能提升，但是如果std :: unordered_map的表现似乎比预期的要差，并且无法切换到gp_hash_table ，则可以尝试使用它。
使用fastscan()获取最快的整数输入，并使用std :: cin其余部分不同步。
使用赋值运算符复制矢量和运算符[]代替at()函数
在C ++中可以实现更多的优化。 一个小的一个例子将是使用，而不是乘以或由2的幂除比特移位运算符，如图 。
我鼓励您自己探索更多内容，对可能找到的任何此类技巧进行基准测试，并在下面进行评论。 我很高兴撰写这篇文章，希望您也能阅读愉快并学到新东西。
PS：我假设代码是在没有任何编译器优化的情况下编译的，因为本文的主要目标读者是有竞争力的编码人员。
一个数的约数也称为因子，比如1是6的因子，2是6的因子，6是6的因子。
质数只有两个因子，1和它本身
现在定义一种新的质数，三质数，三质数只有三个不同的因子。比如4是三质数，因为它有1 ,2, 4三个因子。比如6不是三质数，因为6有1 ,2, 3, 6四个因子。现在有一些数，你需要判断他们是不是三质数。
第一行一个整数T，表示有T组测试数据。
每组测试数据输入一个整数n
对于每组测试数据，判断是否是三质数，如果是输出YES，否则输出NO
本来是想：“OK简单直接打代码”，打完后。。。
我一开始的思路是求不同质子个数，就TLE了
后来想省去一些搜索质子步骤，好家伙结果就WA；
后来一个朋友启发了我：平方数！
只有三个因子的数只有平方数；
好，那么我们就可以将问题简化为（通过判断一个数的平方根是否为整数，来判断是否为三质数）
今天就没那啥很糙的草图了，作者觉得其实思路给了就OK了
小猛新：OK个P啊，怎么判断一个数的平方根是否为整数啊！
判断一个数的平方根是否为整数如上；
