acm模板

1.二分模板

c++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
求最小值
int binary()
{
    int l = 0, r = ll, mid;
    while(l < r)
      {
        mid = (l + r) >> 1;
        if(check(mid)) r = mid;  //大多数题只要改改check()即可
        else l = mid + 1;
      }
    return l;
}
求最大值
int binary()
{
    int l = 0, r = ll, mid;
    while(l < r)
      {
        mid = (l + r + 1) >> 1;
        if(check(mid)) r = mid - 1;
        else l = mid;
      }
    return l;
}

面对整数时的万能二分（近似万能）
int binary(int n)
{
    int l = 1, r = maxn, ans = 0;
    while(l <= r)
      {
        int mid = (l + r) >> 1;
        if(c[mid] > a[n]) ans = mid, l = mid + 1;  //判断条件与ans记录位置因题而异
        else r = mid - 1;
      }
    return ans;
}
cpp
1
2
3
4
5
6
7
8
9
10
11
12
//便于记忆方法（浮点也可以）
int binary()
{
    int l = -1, r = ll, mid; //l在前一位
    while(l < r)
      {
        mid = (l + r) >> 1;
        if(check(mid)) r = mid;  //大多数题只要改改check()即可，r或l =mid
        else l = mid;
      }
    return r;  //最后取r，
}

3.最大公约数gcd

c++
1
2
3
4
5
// Version 1
int gcd(int a, int b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}

头中的 std::gcd 与 std::lcm (最小公倍数)

4.字典树

c++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
struct trie {
  int nex[100000][26], cnt;
  bool exist[100000];  // 该结点结尾的字符串是否存在

  void insert(char *s, int l) {  // 插入字符串
    int p = 0;
    for (int i = 0; i < l; i++) {
      int c = s[i] - 'a';
      if (!nex[p][c]) nex[p][c] = ++cnt;  // 如果没有，就添加结点
      p = nex[p][c];
    }
    exist[p] = 1;
  }

  bool find(char *s, int l) {  // 查找字符串
    int p = 0;
    for (int i = 0; i < l; i++) {
      int c = s[i] - 'a';
      if (!nex[p][c]) return 0;
      p = nex[p][c];
    }
    return exist[p];
  }
};

5. 遍历组合

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<int> a(100);
int n,k;
int ans=0;
vector<int> cho(100);
void C(int start,int choiced)
{
    if(choiced==k)
    {
        if(check())
        {
            ans+=1;
        }
        return;
    }
    int end=n-k+choiced;
    for(int i=start;i<=end;i++)
    {
        cho[choiced]=i;
        C(i+1,choiced+1);
    }
}