专栏文章

常数优化技巧

UUnionRE
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mioz8i5w
此快照首次捕获于
2025/12/03 03:34
3 个月前
此快照最后确认于
2025/12/03 03:34
3 个月前
查看原文

卡常

这个其实很多人写过了，汇总一下。

STL

STL大部分比较慢。所以我们可以优化。

map

O(nlog⁡n)O(n\log n)，比较慢了。
因此可以优化。
常见的就是unordered_map优化。这是一种哈希，所以可能被卡。
当然还有pb_ds (Policy-Based Data Structures\text{Policy-Based Data Structures}) 优化。
CPP
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace __gun_pbds;
pb_ds提供两种哈希，cc_hash_table和gp_hash_table。
其中cc开头为拉链法，gp开头为探测法，个人实测探测法稍微快一些。啥？操作？其实就和map差不多，支持[ ]和find。
map的总时间复杂度是O(nlog⁡n)O(n\log n)的，而hash_table的总时间复杂度仅为O(n)O(n)！
   \qquad\qquad\qquad\qquad\qquad\qquad ——[《比STL还STL？——平板电视》](比STL还STL？——平板电视 - 洛谷专栏)
cc_hash_table在随机数据下的表现较差，时间约为3倍gp_hash_table，空间约为8倍。
这两种哈希直接替换map即可，支持[]和find()，不支持count()。
定义方法同map。
顺便一说，《关于NOI系列活动中编程语言使用限制的补充说明》，使得使用pb_ds有法可依。体现了规则不是一成不变的，良法需要体现社会发展规律……

set / multiset

已经很好了。

priority_queue

还是pb_ds。 #include<ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/priority_queue.hpp> __gnu_pbds::priority_queue<Type, Compare, Tag, Allocator>//不要using namespace，不然会歧义(std::priority_queue)
  • Compare:大根堆less<Type>，小根堆greater<Type>。
  • Tag: pairing_heap_tag thin_heap_tag binomial_heap_tag rc_binomial_heap_tag binary_heap_tag
paring_heap_tag最快。
pushpopmodifyeraseJoin
pairing_heap_tagO(1)O(1)最坏 Θ(n)1\Theta(n)\small ^1 均摊 Θ(log⁡(n))\Theta(\log(n))最坏 Θ(n)\Theta(n) 均摊 Θ(log⁡(n))\Theta(\log(n))最坏 Θ(n)\Theta(n) 均摊 Θ(log⁡(n))\Theta(\log(n))O(1)O(1)
binary_heap_tag最坏 Θ(n)\Theta(n) 均摊 Θ(log⁡(n))\Theta(\log(n))最坏 Θ(n)\Theta(n) 均摊 Θ(log⁡(n))\Theta(\log(n))Θ(n)\Theta(n)Θ(n)\Theta(n)Θ(n)\Theta(n)
binomial_heap_tag最坏 Θ(log⁡(n))\Theta(\log(n)) 均摊 O(1)O(1)Θ(log⁡(n))\Theta(\log(n))Θ(log⁡(n))\Theta(\log(n))Θ(log⁡(n))\Theta(\log(n))Θ(log⁡(n))\Theta(\log(n))
rc_binomial_heap_tagO(1)O(1)Θ(log⁡(n))\Theta(\log(n))Θ(log⁡(n))\Theta(\log(n))Θ(log⁡(n))\Theta(\log(n))Θ(log⁡(n))\Theta(\log(n))
thin_heap_tagO(1)O(1)最坏 Θ(n)\Theta(n) 均摊 Θ(log⁡(n))\Theta(\log(n))最坏 Θ(log⁡(n))\Theta(\log(n)) 均摊 O(1)O(1)最坏 Θ(n)\Theta(n) 均摊 Θ(log⁡(n))\Theta(\log(n))Θ(n)\Theta(n)
【注】：
1:1: Θ(g(x))\Theta(g(x)) 时间复杂度表示方法，表示确界。
  • Allocator 空间配置器，一般不填。

常规操作

以下内容中，AA>BB 表示AA比BB快。（除>和>>外）
  1. i++→\to++i其实不必要。
  2. 矩阵乘法，for ikj比for ijk快得多。
  3. #define>constexpr>const（表示常量时）。
  4. 快读快输。
CPP
#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc _getchar_nolock
#define pc _putchar_nolock
#endif
inline int read(){
  int x=0,f=1;char ch=getchar();
  while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
  while (ch>='0'&&ch<='9'){x=(x << 1) + (x << 3)+ch-48;ch=getchar();}
  return x*f;
}//快读
inline void write(int x){
  if(x<0){putchar('-');x=-x;}
  if(x>9)write(x/10);
  putchar(x%10+'0');
}//快输
OI wiki
CPP
void write(int x) {
  static int sta[35];
  int top = 0;
  do {
  sta[top++] = x % 10, x /= 10;
  } while (x);
  while (top) putchar(sta[--top] + 48);  // 48 是 '0'
}
不同type输出时，用这个(先不要#define int long long)
CPP
namespace fast_io{
	const int fread_cnt=(1<<20);
	const int fwrite_cnt=(1<<20);
	class fast_read{
	private:
		char buf_in[fread_cnt],*p1,*p2;
		inline char gc(){return (p1==p2&&(p2=(p1=buf_in)+fread(buf_in,1,fread_cnt,stdin),p1==p2)?EOF:*p1++);}
		inline bool read_bool(){char ch=gc();while(ch<'0'||ch>'1'){ch=gc();}return (ch=='1');}
		inline char read_ch(){char ch=gc();while(ch==' '||ch=='\r'||ch=='\n'||ch=='\t'){ch=gc();}return ch;}
		inline string read_string(){
			string s;char ch=gc();while(ch==' '||ch=='\r'||ch=='\n'||ch=='\t'){ch=gc();}
			while(ch!=' '&&ch!='\r'&&ch!='\n'&&ch!='\t'){s+=ch;ch=gc();}return s;
		}
		template <typename T>
		inline T read_int(){
			T x=0,f=1;char ch=gc();
			while(ch<'0'||ch>'9'){f=(ch=='-')?-f:f;ch=gc();}
			while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
			return x*f;
		}
		template <typename T>
		inline T read_unsigned(){
			T x=0;char ch=gc();while(ch<'0'||ch>'9'){ch=gc();}
			while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
			return x;
		}
		template <typename T>
		inline T read_float(){
			T x=0,f=1,c=1;char ch=gc();
			while(ch<'0'||ch>'9'){f=(ch=='-')?-f:f;ch=gc();}
			while(ch>='0'&&ch<='9'){x=x*10+(ch^48);ch=gc();}
			if(ch=='.'){ch=gc();while(ch>='0'&&ch<='9'){c/=10;x+=c*(ch^48);ch=gc();}}
			return x*f;
		}
	public:
		fast_read& operator >> (bool &valx){valx=read_bool();return *this;}
		fast_read& operator >> (char &valx){valx=read_ch();return *this;}
		fast_read& operator >> (string &valx){valx=read_string();return *this;}
		fast_read& operator >> (float &valx){valx=read_float<float>();return *this;}
		fast_read& operator >> (double &valx){valx=read_float<double>();return *this;}
		fast_read& operator >> (long double &valx){valx=read_float<long double>();return *this;}
		fast_read& operator >> (short &valx){valx=read_int<short>();return *this;}
		fast_read& operator >> (int &valx){valx=read_int<int>();return *this;}
		fast_read& operator >> (long &valx){valx=read_int<long>();return *this;}
		fast_read& operator >> (long long &valx){valx=read_int<long long>();return *this;}
		fast_read& operator >> (unsigned short &valx){valx=read_unsigned<unsigned short>();return *this;}
		fast_read& operator >> (unsigned int &valx){valx=read_unsigned<unsigned int>();return *this;}
		fast_read& operator >> (unsigned long &valx){valx=read_unsigned<unsigned long>();return *this;}
		fast_read& operator >> (unsigned long long &valx){valx=read_unsigned<unsigned long long>();return *this;}
	}fin;
	class fast_write{
	private:
		char buf_out[fwrite_cnt],*p=buf_out;
		inline void write_bool(bool x){char ch=(x==1)?'1':'0';pc(ch);}
		inline void write_ch(char x){char ch=x;pc(ch);}
		inline void write_string(string s){for(string::iterator it=s.begin();it!=s.end();it=next(it)){pc(*it);}}
		template <typename T>
		inline void write_int(T x){
			if(x<(T)0){pc('-');x=-x;}
			if(x>=10){write_int(x/10);}pc((x%10)^48);
		}
		template <typename T>
		inline void write_unsigned(T x){
			if(x>=10){write_unsigned(x/10);}pc((x%10)^48);
		}
		template <typename T>
		inline void write_float(T x){
			if(x<(T)0)pc('-'),x=-x;
			write_int((int)x);pc('.');x-=(int)x;
			while(x!=0){x*=10;pc((int)x^48);x-=(int)x;}
		}
	public:
		inline void pc(char ch){if(p-buf_out==fwrite_cnt){fwrite(buf_out,1,fwrite_cnt,stdout),p=buf_out;}*p=ch;++p;}
		inline void flush(){fwrite(buf_out,1,p-buf_out,stdout);p=buf_out;}
		inline fast_write& operator << (bool valx){write_bool(valx);return *this;}
		inline fast_write& operator << (char valx){write_ch(valx);return *this;}
		inline fast_write& operator << (string valx){write_string(valx);return *this;}
		inline fast_write& operator << (float valx){write_float<float>(valx);return *this;}
		inline fast_write& operator << (double valx){write_float<double>(valx);return *this;}
		inline fast_write& operator << (long double valx){write_float<long double>(valx);return *this;}
		inline fast_write& operator << (short valx){write_int<short>(valx);return *this;}
		inline fast_write& operator << (int valx){write_int<int>(valx);return *this;}
		inline fast_write& operator << (long valx){write_int<long>(valx);return *this;}
		inline fast_write& operator << (long long valx){write_int<long long>(valx);return *this;}
		inline fast_write& operator << (unsigned short valx){write_unsigned<unsigned short>(valx);return *this;}
		inline fast_write& operator << (unsigned int valx){write_unsigned<unsigned int>(valx);return *this;}
		inline fast_write& operator << (unsigned long valx){write_unsigned<unsigned long>(valx);return *this;}
		inline fast_write& operator << (unsigned long long valx){write_unsigned<unsigned long long>(valx);return *this;}
		inline fast_write& operator << (fast_write& (*func)(fast_write&)){return func(*this);}
	}fout;inline fast_write& endl(fast_write& fastout){fastout.pc('\n');fastout.flush();return fastout;}
}using namespace fast_io;
5. bitset
逆天时间复杂度，洛谷测评机 O(n32)O(\frac{n}{32}) 。STL神器！
6. 位运算
(l+r)>>1 > (l+r)/2。
  1. 手写内置函数
CPP
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...