ACM个人零散知识点整理

ACM个人零散知识点整理

杂项：

1.输入输出外挂

//读入优化 int 整数
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*10+ch-'0';
        ch=getchar();
    }
    return x * f;
}

2.关闭c+++输入输出限制流

ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

---

图论：

1.链式前向星模板

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;
//init()
struct edgenode {
    int w,next,to;
    edgenode () {
        next=w=to=0;
    }
} edges[maxn];
int head[maxn];
int cnt=0;
//双向边调用两次即可
void addedge(int u, int v, int w) {
    edges[cnt].to=v;
    edges[cnt].w=w;
    edges[cnt].next=head[u];
    head[u]=cnt;
    cnt++;
}
//遍历
void ask(int x) {
    for(int i=head[x];i!=-1;i=edges[i].next) {

    }
}
void init() {
    memset(head,-1,sizeof(head));
}
int main() {

    return 0;
}

2.最近公共祖先

• tarjan离线

  #include <bits/stdc++.h>
  using namespace std;
  const int maxn = 500001;
  const int maxm = 1000001;
  struct enode {
  int next,to;
  } edges[maxm];
  struct qnode {
  int next,id,to;//id第几次查询
  } que[maxm];
  int head_e[maxn];//前向星 edges
  int head_q[maxn];//前向星 查询
  int vis[maxn];
  int f[maxn];//并查集父亲数组
  int res[maxn];//结果
  int cnte=0;
  int cntq=0;
  int n,m,s;
  inline void addedge(int u, int v) {
  edges[cnte].to=v;
  edges[cnte].next=head_e[u];
  head_e[u]=cnte++;
  }
  inline void addque(int u, int v, int id) {
  que[cntq].to=v;
  que[cntq].id=id;
  que[cntq].next=head_q[u];
  head_q[u]=cntq++;
  }
  //并查集访问父亲
  int find(int x) {
  return x==f[x] ? x : f[x] = find(f[x]);//压缩
  }
  void tarjan(int s) {
  vis[s]=1;//先标记，不能在回溯时标记，因为双向边
  f[s]=s;
  for(int i=head_e[s]; i!=-1; i=edges[i].next) {
      if(!vis[edges[i].to]) {
          tarjan(edges[i].to);
          f[edges[i].to]=s;
      }
  }
  for(int i=head_q[s]; i!=-1; i=que[i].next) {
      if(vis[que[i].to]==1) {
          res[que[i].id]=find(que[i].to);
      }
  }
  }
  inline void init() {
  memset(vis,0,sizeof(vis));
  memset(head_e,-1,sizeof(head_e));
  memset(head_q,-1,sizeof(head_q));
  for(int i=1; i<=n; ++i) f[i]=i;
  }
  int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin>>n>>m>>s;
  init();
  int u,v;
  for(int i=1; i<n; ++i) {
      cin>>v>>u;
      addedge(v,u);
      addedge(u,v);
  }
  for(int i=1; i<=m; ++i) {
      cin>>v>>u;
      addque(u,v,i);
      addque(v,u,i);
  }
  tarjan(s);
  for(int i=1; i<=m; ++i) cout<<res[i]<<endl;
  return 0;
  }

• ST倍增在线

  #include <iostream>
  #include <stdio.h>
  #include <string.h>
  #include <math.h>
  using namespace std;
  const int maxn = 100005;
  struct node {
  int to,next;
  } edges[maxn<<1];
  //注意head[]数组初始化
  int head[maxn],cnt,dp[maxn][15],dep[maxn];
  void add(int u, int v) {
  edges[cnt].to=v;
  edges[cnt].next=head[u];
  head[u]=cnt++;
  }
  //节点 父亲节点
  void dfs(int s, int x) {
  dp[s][0]=x;
  dep[s]=dep[x]+1;
  int t;
  //跟新到根节点一路上的祖先
  for(int i=1; (1<<i)<=dep[x]; ++i) dp[s][i]=dp[dp[s][i-1]][i-1];
  for(int i=head[s]; i!=-1; i=edges[i].next) {
      t=edges[i].to;
      if(t==x) continue;
      dfs(t,s);
  }
  }
  int lca(int u, int v) {
  if(dep[v]>dep[u]) swap(u,v);
  for(int i=14; i>=0; --i) {
      if((dep[u]-dep[v])>=(1<<i)) {
          u=dp[u][i];
      }
  }
  //此时深度一定相同
  if(u==v) return u;
  for(int i=14; i>=0; --i) {
      if((1<<i)<=dep[u]&&dp[u][i]!=dp[v][i]) {
          u=dp[u][i];
          v=dp[v][i];
      }
  }
  //循环过程中不加判断可能会超过最近公共祖先，所以跟新到lca的儿子节点即可
  return dp[u][0];
  }
  int main() {
  int n,m,u,v;
  scanf("%d %d",&n,&m);
  cnt=0;
  memset(head,-1,sizeof(head));
  for(int i=1; i<n; ++i) {
      scanf("%d %d",&u,&v);
      add(u,v);
      add(v,u);
  }
  dep[0]=1;
  dfs(1,1);
  for(int i=1; i<=m; ++i) {
      scanf("%d %d",&u,&v);
      printf("%d\n",lca(u,v));
  }
  return 0;
  }

  数论：

  1.快速幂（矩阵快速幂略）

  int pow(int base,int num){
  int ans=1;
  while(num!=0){
      if(num&1!=0)
      　　ans*=base;
      base<<=1;
      b>>=1;
  　 }
  return ans;
  }

  2.位数公式

  x=log(n)+1//求n有多少位

  3.莫比乌斯函数

• 在线

  ll mubi(ll n) {
  ll mu=1;
  for(ll i=2;i*i<=n;++i) {
      if(n%i==0) {
          mu*=-1;
          ll k=0;
          do {
              k++;
              if(k>1) {
                  mu=0;break;
              }
              n/=i;
          }while(n%i==0);
      }
  }
  if(n>1) mu*=-1;
  return mu;
  }

• 离线

  mu[1]=1;
  for(i=2;i<=n;i++)
  {
  if(!not_prime[i])
  {
      prime[++tot]=i;
      mu[i]=-1;
  }
  for(j=1;prime[j]*i<=n;j++)
  {
      not_prime[prime[j]*i]=1;
      if(i%prime[j]==0)
      {
          mu[prime[j]*i]=0;
          break;
      }
      mu[prime[j]*i]=-mu[i];
  }
  }

  4.最小正整数逆元（ex_gcd）

  #include <bits/stdc++.h>
  using namespace std;
  typedef long long ll;
  ll exgcd(ll a, ll b, ll &x, ll &y) {
  if(!b) {
      x=1;y=0;return a;
  }
  ll ans=exgcd(b,a%b,x,y);
  ll temp=x;
  x=y;
  y=temp-a/b*y;
  return ans;
  }
  int main() {
  ios::sync_with_stdio(false);
  ll m,n;
  cin>>m>>n;
  ll x,y;
  exgcd(m,n,x,y);
  cout<<((x%n)+n)%n<<endl;
  return 0;
  }