在平时比赛中，除了大家经常会遇到的各种算法外，还有很多思路实现具有模板化的代码，他们不是算法，但是由于出现频率非常高，所以我进行了整理，希望对大家可以提供些许帮助

后续自己也会不断跟新的

1，倍数遍历

• (1) acwing28场周赛B题
• (2) codeforce 1614D1 Divan and Kostomuksha (easy version) 2100分
• (3) 代码源 2022.3.22.平方表示
• (4) codeforce ed2 125 For Gamers. By Gamers.
• (5) codeforce d2 1627 D Not adding

• 具体问题:

  • 1, 给定n个数,预处理出对于1~N的每一个数,初始的n个数中，有多少数是该数的倍数
    这道题不是单纯的倍数遍历，其中还带有了dp的思想
    dp[i][j]表示j被小于等于i的因子的集合

  • 1)的引申，如果初始n件商品，每个商品有价值，且有价格，你只有C元，同时你只能购买一件商品，求价值的最大值
    因为倍数遍历的结果，只会遍历到这个数是初始数的整数倍，或者是初始数倍数的整数倍
    而codeforce ed2 125这道题只会由初始状态去更新

  • 2, 在固定的数据集合里面，判断有多少数是刚开始那些数的倍数
    在固定的数据集合里面，判断有多少数不可以被刚开始的那些数里面的gcd表示
  • 3，枚举出所有约数的和

 cnt[n]表示数值等于n的数的个数
 for(int i=1;i<=n;i++)
 {
     cin>>x;cnt[x]++;//预处理出开始时每一个数的个数
 }
 for(int d=2;d<N;d++)
      for(int j=d*2;j<N;j+=d)
           cnt[d]+=cnt[j];
  /*因为是在枚举倍数，
     所以前面的数不会对后面的数产生影响，
     所以我们选择从小到大的顺序*/

2，枚举出所有数的约数之和

for(int i=1;i<=n;i++)
    for(int j=2;j<=n/i;j++)
        sum[i*j]+=i;

3,集合判等的实现 acwing28场周赛C题

vector<int> v1,v2;
开始是先把一堆元素push_back进v1
再然后把第二堆元素push_back进v2
再然后sort(v1) sort(v2)
最后判断v1==v2

4,分解质因数完成之后，如何枚举所有约数

void dfs(int u, int p)
{
    if (u == cntf)
    {
        divider[cntd ++ ] = p;
        return;
    }

    for (int i = 0; i <= factor[u].second; i ++ )
    {
        dfs(u + 1, p);
        p *= factor[u].first;
    }
}

5，求解大于一个数的最小的2的整数次幂
* codeforce 1617E. Christmas Chocolates

y = (1 << int(ceil(log2(x))))

6，k路归并
* Acwing 3995

for(int i=1;i<=k1+k2;i++)
{
    auto t=q.top();
    q.pop();
    t--;
    q.push(t);
}

7，去除掉相邻元素的代码

• acwing 3957

可以先用双指针，扫描一遍，把要去掉的点，设为不可能的值
然后再开一个vector，扫描一遍
for(int i=1,j=1;i<=n;i++,j++)
{
    while(j+1<=n&&arr[j+1]==arr[i]) arr[j+1]=INF,j++;
    i=j;
}

8，给定n个数,预处理出对于1~N的每一个数,初始的n个数中，有多少数是该数的约数
* acwing 1291 轻拍牛头

    for(int i=1;i<=n;i++)
    {
        int x;cin>>x;
        cnt[x]++;
    }
    for(int i=1;i<=maxn;i++)
    {
        if(!cnt[i]) continue;
        for(int j=i;j<=maxn;j+=i)
        {
            s[j]+=cnt[i];
        }
    }

9, 分解质因数，比试除法快十倍左右
* acwing 200 Hankson的趣味题

    首先欧拉筛，筛出所有质数
    for(int i=0;prime[i]<=t/prime[i];i++)
        {
            if(t%prime[i]==0)
            {
                int s=0;
                while(t%prime[i]==0)  t/=prime[i],s++;
                factor[fcnt++]={prime[i],s};
            }
        }
    if(t>1) factor[fcnt++]={t,1};

10，求1~n中第i位上出现了多少个1

    for(int i=0;i<=2e5+500;i++)
    {
        for(int j=0;j<21;j++)
        {
           if(i>>j&1) cnt[i][j]++;
        }
    }
    for(int i=1;i<=2e5+500;i++)
    {
        for(int j=0;j<21;j++)
        {
            cnt[i][j]+=cnt[i-1][j];

11,将一个正整数依次取出放在vector中

    vector<int> num;
    while (n)
    {
        num.push_back(n%10);
        n/=10;
    }

12，双指针求数组内，一对数范围在[L,R]中的个数
codeforce 1322B present

int calculate(int L,int R)
{
    if(L>R) return 0;
    int ans=0;
    for(int i=n,l=0,r=0;i>=1;i--)
    {
        while(l<n&&(b[i]+b[l+1])<L) l++;
        while(r<n&&(b[i]+b[r+1])<=R) r++;
        ans+=(r-l-((l+1)<=i&&i<=r));
    }
    return (ans>>1)%2;
}

13,进制转化成十进制代码

int change(string& s,int B)
{
    int res=0;
    for(int i=0;i<s.size();i++)
    {
        res=res*B+s[i]-'0';
    }
    return res;

}

14，区间筛选

 for (int i = 0; i < N; i ++ )
        if (!st[i])
        {
            int j = i + 1;
            while (j < N && !st[j]) j ++ ;
            cout << format(i) << " - " << format(j) << endl;
            i = j;
        }

    for(int i=1;i<=n;i++)
    {
        if(s[i]=='1')
        {
            int j=i+1;
            while(j<=n&&s[j]=='1') j++;
            cout<<i<<" "<<j-1<<endl;
            i=j-1;
        }
    }