ACM 常用小 Trick

算法
字数统计: 782阅读时长: 4 min
 2018/07/28   Share
//{{{ #include
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#include <string>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <complex>
//}}}//#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef double db;
typedef pair<int,int> pii;
typedef vector<int> vi;

#define mp make_pair
#define fi first
#define se second
#define sf scanf
#define pf printf
#define pn printf("\n")
#define ls l,mid,rt<<1
#define rs mid+1,r,rt<<1|1
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define de(x) cout << #x << "=" << x << endl
#define dd(x) cout<< #x<<" = "<<x<<" "
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define mem(a,b) memset(a,b,sizeof(a))
#define sz(x) (int)(x).size()

const int INF=0x3f3f3f3f;
const double eps=1e-8;
const double PI=acos(-1.0);
const int N = 101010;

int sgn(double x){if(fabs(x)<eps)return 0;if(x<0)return -1;else return 1;}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}

// fast-pow
int Pow(ll x,ll t,int p) {ll r=1;for(;t;t>>=1,x=x*x%p)if(t&1)r=r*x%p;return r;}

// add-mod
const int MOD = 1e9 + 7;
void pp(int &x,int d) {if((x+=d)>=MOD) x-=MOD;}
// minus-mod -> pp(a , P - x);

// multiply-mod
int mul(int a,int b){ return ll(a)*b%MOD;}

// inversion
int inverse(int x,int p) {return Pow(x,p-2,p);} // p should be prime

// tree-dp
vi g[N];
int sz[N];
void dfs(int c,int par){
  sz[c] = 1;
  for(auto t : g[c]) if(t != par){ // c++11
    dfs(t , c);
    sz[c] += sz[t];
  }
}

// dsu
int fa[N];
int F(int x){ return fa[x] == x ? x : fa[x] = F(fa[x]);}
void M(int x,int y){ fa[F(x)] = F(y);}

int main(){
  // swap
  int u = 0, v = 1;
  std::swap(u , v); // swap
  set<int> A , B;
  std::swap(A , B); // O(1)

  // minimal & maximal
  int a[20] , n = 20;
  rep(i,0,n) a[i] = i;
  cout << *std::max_element(a , a + n) << endl;// [a , a+n)
  cout << *std::min_element(a , a + n) << endl;

  // discretization
  vi V;// about 10 int
  sort(all(V));V.erase(unique(all(V)),V.end());
#define rk(x) upper_bound(all(V) , x) - V.begin()

  // deal with same value
  for(int i=0,j=0;i<sz(V);i=j) {
    for(j=i;j<sz(V)&&V[j]==V[i];++j);
    // Cal(i , j) //[i , j)
  }

  // multiple-loops
  int g[10][10] , m = 10;
  rep(i,0,m) rep(j,0,m) scanf("%d",&g[i][j]);

  // __builtin_popcount()
  int cnt1[1<<6];
  rep(i,1,1<<6) cnt1[i] = cnt1[i >> 1] + (i & 1);

  // sort
  int cnt[20];
  sort(all(V),[&](int a,int b){return cnt[a]<cnt[b];}); // c++11 
  vector<vi> Vv;
  sort(all(Vv));

  // sort with id
  vector<pii> p;
  rep(i,0,20) p.pb(mp(rand(),i));
  sort(all(p));

  // deal with subsets
  rep(mask,0,1<<10)
    for(int j=mask;j;j=(j-1)&mask)
      ;// Cal

  // high-dimensional prefix-sum
  int f[1<<10];
  rep(i,0,10) rep(j,0,1<<10) if(j>>i&1) pp(f[j],f[j^(1<<i)]);

  // permutation
  rep(i,0,7) a[i] = i;
  do{
    // Cal;
  }while(next_permutation(a , a + 7));

  // fill function
  std::fill(a , a + 20 , 0);// fill any number

  // reference
  int &r=f[10];
  rep(i,0,10) r+=i;

  // ternary operator
  int C[10][10] = {{1}};
  rep(i,1,10) rep(j,0,i+1) C[i][j] = j ? (C[i-1][j-1] + C[i-1][j]) : 1;

  return 0;
}
原文作者：wywwzjj
原文链接：https://wywwzjj.top/2018/07/28/ACM-常用Trick/
发表日期：July 28th 2018, 11:07:56 pm
更新日期：May 15th 2021, 11:53:20 am
Next Post

Bugku Web 部分WP
Previous Post

Teach Yourself Programming in Ten Years
CATALOG
