OI/ACM最全卡常大招
- 2019 年 10 月 3 日
- 筆記
NO.10: 循環展開：
在快取和暫存器允許的情況下一條語句內大量的展開運算會刺激 CPU 並發(蛤？這是個什麼原理，算了，反正寫了沒壞處就這麼寫吧)
NO.9: 特殊運算優化：(或許這真的沒用)
取模優化：
inline int inc(int x,int v,int mod){x+=v;return x>=mod?x-mod:x;}//代替取模+ inline int dec(int x,int v,int mod){x-=v;return x<0?x+mod:x;}//代替取模-
或者對於模數p進行#define宏定義
絕對值優化：
inline int Abs(int a){//絕對值優化
{ int b=a>>31; return (a+b)^b; }
NO.8: 前置++/–運算符：(有利無弊)
NO.7: if()else語句比()?():()語句慢(但慢的不多，在判斷較少的時候還是用if吧)。
網上很多說if比?:慢，但是其實不是這樣的。二者的彙編除了文件名不一樣其他都一模一樣。其實不是?:比if快而是?:比if-else快。
NO.6: 內聯：
函數內聯：比如說：
inline add(int u,int v) { star[++cnt].to=v; star[cnt].nxt=head[u]; head[u]=cnt; }
但要拒絕inline大遞歸函數，用的少的函數比如只用1次的就不要inline了，那樣反而更慢；
另類內聯：
struct haha{ int v,x; inline bool operator < (haha tar){//強制內聯 return v<tar.v; } }lala[MAXN+1];
NO.5:使用局部變數的效率比使用靜態變數要高。
因為局部變數是存在於堆棧中的，對其空間的分配僅僅是修改一次(esp)暫存器的內容即可.而局部變數存在於堆棧中最大的好處是，函數能重複使用記憶體，當一個函數調用完畢時，退出程式堆棧，記憶體空間被回收，當新的函數被調用時，局部變數又可以重新使用相同的地址。當一塊數據被反覆讀寫，其數據會留在(CPU)的一級快取（(Cache)）中，訪問速度非常快。而靜態變數卻不存在於堆棧中。
NO.4:優化STL
大部分的STL較慢的原因是在動態記憶體分配時對push_back()的函數大大的不友好；
我們可以手寫足夠大小的記憶體池來代替動態分配記憶體。
#include<bits/stdc++.h> using namespace std; #define reg register static char space[10000000],*sp=space; template<typename T> struct myalloc:allocator<T>{ myalloc(){} template<typename T2> myalloc(const myalloc<T2> &a){} template<typename T2> myalloc<T>& operator=(const myalloc<T2> &a){return *this;} template<typename T2> struct rebind{typedef myalloc<T2> other;}; inline T* allocate(size_t n){ T *result=(T*)sp;sp+=n*sizeof(T); return result; } inline void deallocate(T* p,size_t n){} };
list<int,myalloc<int> > L;vector<double,myalloc<double> > vec //容量的定義
但當記憶體過大時，不要套用此程式碼，因為該程式碼為了簡短並沒有釋放記憶體；
NO.3: I/O優化
scanf比cin快得多，printf比cout快得多，如果你不知道就……就現在知道了
普通版：(適用於正負int範圍內的數)
void read(int &x) { int f=1;x=0;char s=getchar(); while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} x*=f; }
提升版:(快是快，但在考試中的性價比並不高)
inline char get_char(){//超級快讀 static char buf[1000001],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++; } inline int read(){ int num=0; char c; while(isspace(c=get_char())); while(num=num*10+c-48,isdigit(c=get_char())); return num; }
NO.2: register
在定義一個變數時加一個register，其意義是將該變數放入暫存器中進行運算(如果可以的話),
它的效果在該變數不斷重複使用時間的優化極大，往往用時是不優化的40%；
NO.1: #pragma GCC optimize(2)（請勿在NOIP中作死）
這便是O2優化
它的作用極大，但如果程式碼不規範，它在優化時會改變某句程式碼的含義，所以在用時一定要小心從30%TLE變為100%WA;
實踐證明開了O2的莫隊快的飛起，模擬退火燒到了你上輩子的屁股；
