C++ 终极时间优化模板

2018-09-04

今天考试的时候遇到一题背包题目,我直接打了暴力的 0/1 背包,理论复杂度是 \Theta (N^3\ast W),大概是 10^9 这个级别……时限 1s,交上去就全部 TLE 了……然后我就想起了这个终极优化模板,加上以后居然全 A 了!时间居然只有 200ms 左右……

10^9 级别居然都可以压过去!!!

Read more...


   

(转)C++ 中 Vector 的使用总结

2018-07-12

在c++中,vector 是一个十分有用的容器。它能够像容器一样存放各种类型的对象,简单地说,vector是一个能够存放任意类型的动态数组,能够增加和压缩数据。
vector 在C++ 标准模板库中的部分内容,它是一个多功能的,能够操作多种数据结构和算法的模板类和函数库。

Read more...


   

C++中的128位整型 __int128

2018-07-11

C++里有普通的 32 位整数类型 int 和 64 位整数类型 long long,但是如果我们要存一个128位的整数,前两个似乎就无能为力了。这时候我们就要用到 __int128这种类型了。

Read more...


   

(转)C++内联函数(inline)

2018-03-26

在C语言中,我们使用宏定义函数这种借助编译器的优化技术来减少程序的执行时间,那么在C++中有没有相同的技术或者更好的实现方法呢?答案是有的,那就是内联函数。内联函数作为编译器优化手段的一种技术,在降低运行时间上非常有用。我们将从:

  • 什么是内联函数
  • 为什么要使用内联函数
  • 内联函数优缺点分析
  • 何时使用内联函数

这四个方面对内联函数进行介绍。

Read more...


   

POJ1723 士兵排队 题解

2018-03-13

POJ题目链接

N soldiers of the land Gridland are randomly scattered around the country.
A position in Gridland is given by a pair (x,y) of integer coordinates. Soldiers can move - in one move, one soldier can go one unit up, down, left or right (hence, he can change either his x or his y coordinate by 1 or -1).

Read more...


   

SPFA算法总结

2018-01-08

SPFA真是最好的单源最短路算法,没有之一。

SPFA全称是Shortest Path Faster Algorithm,直译过来就是“最短路更快算法”,从这个名称就能看出SPFA效率很高。SPFA加上SLF优化以后被称作单源最短路的“无敌”,时间复杂度可以达到O(ke)(k表示平均每个节点入队次数,k≤2,e表示边数),可以刷负边权。

Read more...


   

C++STL中集合的使用总结

2017-12-14

C++STL里的set,顾名思义就是集合。和数学里的集合一样,C++STL里的集合也具有互异性,即每个元素最多只出现一次。如果需要某个值出现多次就可以用multiset。

集合的好处是,集合里存的元素都是从小到大排好序的。这和插排不同,集合的复杂度是log2(n),对解决一些题目十分有用。

Read more...