演算法競賽（ACM、NOI）中有哪些奇技淫巧？
利於演算法的時間、空間優化的方法？
- #include&
using namespace __gnu_cxx;
2. #include&
using namespace __gnu_pbds;
3. set, map, hash_map, cc_hash_table, gp_hash_table, bitset
4. __builtin_clz, __builtin_popcount
5. #define J (") 首頁 - Tsinsen 清橙網路自動評測系統 - 清橙 清橙風格分100 不知道現在還好不好用了
6.
7. #ifndef ONLINE_JUDGE#define Dbg(x) cout&
#ifdef _WIN32
#define Scanl(x) scanf("%I64d",x)
#else
#define Scanl(x) scanf("%lld",x)
#endif
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
int t1=clock();
#endif
8.
inline int min_fast(int x,int y){int m=(y-x)&>&>31;return ym|x~m;}
好像開O2就沒用/變慢了
9. 大家提到的打表
inline int LOG2(uint x){ //x=2^k
static int tb[32]={31,0,27,1,28,18,23,2,29,21,19,12,24,9,14,3,30,26,17,22,20,11,8,13,25,16,10,7,15,6,5,4};
return tb[x*263572066&>&>27];
}
10.
long double//ll: long long
inline ll mul_mod_ll(ll a,ll b,ll p){ //a*b%p
ll ans=0;a%=p;
while (b){
if (b1){
ans+=a;
if (ans&>=p)ans-=p;
}
a+=a;
if (a&>=p)a-=p;
b&>&>=1;
}
return ans;
}
inline ll mul_mod_ll_(ll x,ll y,ll p){ //x*y%p
x%=p;y%=p;ll T=(ll)ceil(sqrt(p)+0.5);if(T*T&
if (res&<0)res+=p;return res;
}
inline ll mul_mod_ll_asm(ll a,ll b,ll p){ //a*b%p
ll ret=0;
__asm__("movq %1,%%rax
imulq %2
idivq %3
":"=d"(ret):"m"(a),"m"(b),"m"(p):"%rax");
return ret;
}
第二和第三個精度忘了，大概十五六位吧。
11. __float128
大家查查比賽能不能用。不過好慢的。
12.
template&
void Calldfs(T *p,int a){
int *Stack=new int[stack_size],bak;
__asm__ __volatile__
(
"mov %%esp,%0
"
"mov %1,%%esp
"
:"=g"(bak)
:"g"(Stack+stack_size-1)
:
);
(*p)(a);
__asm__ __volatile__
(
"mov %0,%%esp
"
:
:"g"(bak)
:
);
delete[] Stack;
}
比賽就別用了。
13. 樹狀數組
記得當年知道這個的人不多，不知道為什麼。 14. 補一個 最後給個彩蛋。 15. #define if(_) if(!(_))int findkth(int k){
int ans=0,cnt=0;
for (int i=20;i&>=0;--i){
ans+=1&=n||cnt+c[ans]&>=k)ans-=1&
答主比較菜，這裡用親身經歷提供一個非正確解法的奇技淫巧。
追求正解的聚聚們可以不要看了……
有一天我在你谷上發現有這樣一道題：P4001 [BJOI2006]狼抓兔子。
第一眼看出來是一道網路流的題目，然後就順手把Dinic的板子敲了一遍。
交上去的時候發現只有90分（這裡是評測結果），最後一個點MLE了（題解好像有最大流過了但是我可能比較菜一直是90分）。
然後我又讀了一遍題目，woc這不是對偶圖跑SPFA求出最小割嗎，不會對偶圖怎麼辦啊T_T。
於是我靈機一動，開始改我的存圖方法，既然我存不下所有的反向邊，那麼我就存一部分反向邊，結果看人品，然後在存反向邊的過程中都加上了一句：
if (rand() * rand() 1) add_edge(id + 1, id, x);
本來只是抱著試一試的心態，沒想到交了幾遍之後竟然A掉了……（評測結果戳我）
可能是人品問題吧（逃
完整代碼如下（再次提醒非正解）
#include &
const int inf = 0x7fffffff;
const int maxn = 1000010;
const int maxm = 10000060;
int iter[maxn], fi[maxn], vis[maxn];
int v[maxm], w[maxm], nx[maxm];
int cnt = -1;
int n, m, s, t;
inline void add_edge(int ui, int vi, int wi) {
v[++cnt] = vi, w[cnt] = wi, nx[cnt] = fi[ui], fi[ui] = cnt;
v[++cnt] = ui, w[cnt] = 0, nx[cnt] = fi[vi], fi[vi] = cnt;
}
int bfs() {
memset(vis, 0, sizeof vis);
std::queue& q;
q.push(s);
vis[s] = 1;
while (!q.empty()) {
int u = q.front(); q.pop();
for (int i = fi[u]; ~i; i = nx[i]) {
if (w[i] (!vis[v[i]])) {
vis[v[i]] = vis[u] + 1;
q.push(v[i]);
}
}
}
return vis[t];
}
int dfs(int u, int flow) {
if (u == t) return flow;
for (int i = iter[u]; ~i; i = nx[i]) {
if (vis[v[i]] == vis[u] + 1 w[i]) {
int d = dfs(v[i], std::min(flow, w[i]));
if (d &> 0) {
w[i] -= d;
w[i ^ 1] += d;
return d;
}
}
}
return 0;
}
inline int dinic() {
int ans = 0, d;
while (bfs()) {
for (int i = 1; i &<= n; ++i) iter[i] = fi[i];
while (d = dfs(s,inf)) ans += d;
}
return ans;
}
int main() {
srand(time(0));
memset(fi, -1, sizeof fi);
memset(nx, -1, sizeof nx);
int x;
scanf("%d%d", n, m);
s = 1, t = n * m;
for (int i = 1; i &<= n; ++i) {
for (int j = 1; j &< m; ++j) {
scanf("%d", x);
int id = (i - 1) * m + j;
add_edge(id, id + 1, x);
if (rand() * rand() 1) add_edge(id + 1, id, x);
}
}
for (int i = 1; i &< n; ++i) {
for (int j = 1; j &<= m; ++j) {
scanf("%d", x);
int id = (i - 1) * m + j;
add_edge(id, id + m, x);
if (rand() * rand() 1) add_edge(id + m, id, x);
}
}
for (int i = 1; i &< n; ++i) {
for (int j = 1; j &< m; ++j) {
scanf("%d", x);
int id = (i - 1) * m + j;
add_edge(id, id + m + 1, x);
if (rand() * rand() 1) add_edge(id + m + 1, id, x);
}
}
n = n * m;
printf("%d", dinic());
return 0;
}
1.打表看出dp規律2.暴搜算出幾個，丟進excel裏，求回歸方程，O(1)複雜度。
能打表的千萬別瞎搞
瞎搞策略1:模擬退火
瞎搞策略2:打表找dp
瞎搞策略3:隨機查找
瞎搞策略4:上廁所
瞎搞策略5:暴力剪枝
瞎搞策略6:cout&
推薦閱讀：
