C++那些写起来简单方便的函数(转自电音抖腿不能改)

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

C++那些写起来简单方便的函数(转自电音抖腿不能改)

作者：

Cold , 2021-10-15 11:30:36 , 所有人可见 , 阅读 535

5

11

视频在这里
本文转载自 b 站知名 up 主电音抖腿不能改的总结

本人在文末又加入了一些相关的题目希望能对大家有所帮助

强力推荐大家有空翻一下侯捷老师翻译的鼎鼎大名的《STL源码剖析》

upper_bound、lower_bound

一般升序使用

sort unique

deque 也可以 sort

sort 不单纯是快排，内部很复杂。

STL的sort算法，数据量大时采用快排算法，分段归并排序。一旦分段后的数据量小于某个门槛，就改用插入排序。如果递归层次过深，还会改用堆排序。详见《STL源码剖析》 P389

所以，可能某些特殊情况下，手写快排会快，再加入一些奇怪的优化等会更快，例如随机化一下打乱有序列，小范围冒泡。

vector<int>a;
sort(a.begin(),a.end());
a.erase(unique(a.begin(),a.end()),a.end());

partial_sort()

stl_algo.h 4672-4691

  template<typename _RandomAccessIterator>
    inline void
    partial_sort(_RandomAccessIterator __first,
         _RandomAccessIterator __middle,
         _RandomAccessIterator __last)
    {
      // concept requirements
      __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
        _RandomAccessIterator>)
      __glibcxx_function_requires(_LessThanComparableConcept<
        typename iterator_traits<_RandomAccessIterator>::value_type>)
      __glibcxx_requires_valid_range(__first, __middle);
      __glibcxx_requires_valid_range(__middle, __last);
      __glibcxx_requires_irreflexive(__first, __last);

      std::__partial_sort(__first, __middle, __last,
              __gnu_cxx::__ops::__iter_less_iter());
    }

实现排序的平均时间复杂度为$O(NlogM)$，其中 N 指的是 [first, last) 范围的长度，M 指的是 [first, middle) 范围的长度。

vector<int>a;
dec(i,10,1)a.push_back(i);
partial_sort(a.begin(),a.begin()+3,a.end());
for(auto it:a)cout<<it<<" ";

1 2 3 10 9 8 7 6 5 4

可以像 sort 那样带上自定义函数

vector<int>a;
rep(i,1,10)a.push_back(i);
partial_sort(a.begin(),a.begin()+3,a.end(),greater<int>());
for(auto it:a)cout<<it<<" ";

10 9 8 1 2 3 4 5 6 7

nth_element

与上面用法类似，复杂度 $O(n)$，建议记 partial_sort

注意，最后 $n$-th 元素在 a.begin()+n 的位置，下标从 0 开始

srand(time(NULL));
vector<int>a;
rep(i,1,10)a.push_back(i);
random_shuffle(a.begin(),a.end());
nth_element(a.begin(),a.begin()+4,a.end(),greater<int>());
cout<<a[4]<<endl;

rbegin,back

vector<int>a;
rep(i,1,10)a.push_back(i);
cout<<a.front()<<endl;
cout<<a.back()<<endl;
cout<<*a.begin()<<endl;
cout<<*a.rbegin()<<endl;

set<int>b;
rep(i,1,10)b.insert(i);
cout<<*b.begin()<<endl;
cout<<*b.rbegin()<<endl;

min max

min(a,min(b,c))

min({a,b,c})

C++11，编译器会将其推导为initializer_list类型，产生一个initializer_list的临时对象。

max_element min_element

查找最大值、最小值对应的地址

int a[]={1,4,3,2};
int main()
{
    cout<<max_element(a,a+4)-a<<endl;
    return 0;
}

prev_permutation next_permutation

这个大家应该很熟悉了

值得强调的是时间复杂度，全遍历 $O(n!)$，单次最坏 $O(n)$

do
{

}while(next_permutation(a+1,a+n+1));

__int128

128位整数

输入输出要手写快读快写

如果有些题中间数据爆了 long long，可以强制转化成 __int128 进行处理

to_string

C++11，将逐个数字转化为字符串，支持double等，详见 basic_string.h 6413-6473

减少手写的时候，忘记特判 0 的尴尬

emplace_back

减少常数的写法

struct TSY
{
    int age;
    TSY(int x)
    {
        age=x;
    }
};
int main()
{
    vector<TSY>save;
    save.emplace_back(21);
    save.push_back(TSY{21});
    return 0;
}

__gcd

看内部实现，如果传__m, __n 的时候其中一个为 0，那么会返回另一个非 0 数

  template<typename _EuclideanRingElement>
    _EuclideanRingElement
    __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
    {
      while (__n != 0)
    {
      _EuclideanRingElement __t = __m % __n;
      __m = __n;
      __n = __t;
    }
      return __m;
    }

__lg

当前数有几位，或者可以说最高位是第几位，如 $12=(1100)_2$, __lg(12)=3

stl_algobase.h 997-1021

  inline _GLIBCXX_CONSTEXPR int
  __lg(int __n)
  { return sizeof(int) * __CHAR_BIT__  - 1 - __builtin_clz(__n); }

（clz表示Count Leading Zeros，统计前导零个数）

使用注意：__builtin_clz 当参数为0，结果未定义，所以 __lg(0)也会未定义

这个方法可以认为是O(1)的，而且效率比log2 高很多

详细说明：https://www.zhihu.com/question/35361094

rotate

vector<int>a;
rep(i,1,10)a.push_back(i);
rotate(a.begin(),a.begin()+2,a.end());
for(auto it:a)cout<<it<<" ";

效果

1 2 3 4 5 6 7 8 9 10
3 4 5 6 7 8 9 10 1 2

复杂度 $O(n)$

reverse

写字符串常用

string s;
cin>>s;
reverse(s.begin(),s.end());
cout<<s<<endl;

__builtin_popcount

__builtin 内建函数常数小的离谱

统计有多少个位为 1。它使用一张类似基于表的方法来进行位搜索。

shuffle

第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（南京）E.Evil Coordinate

https://ac.nowcoder.com/acm/contest/10272/E

一般比较多的写法：

srand(time(NULL));
random_shuffle(a+1,a+n+1);

复杂度 $O(n)$

也可以，random库里的：

unsigned seed=chrono::system_clock::now().time_since_epoch().count();
shuffle(save.begin(),save.end(),default_random_engine(seed));

memset fill

极其容易犯错~

这个东西估计很多人不知道怎么用，就知道 memset(a,0,sizeof(a))，想把数组a 中元素全设置成 1，写了个memset(a,1,sizeof(a))

我们要理解一下，memset是将某一块内存中的内容全部设置为指定的值是以字节为单位进行赋值的

int 32位 4字节

填充的时候，每个字节是 0x01，即$[00000001]_2$

所以不建议这么写，建议使用fill

int arr[maxn];
int main()
{
    fill(arr,arr+maxn,1);
    return 0;
}

iota

对 [arr,arr+n-1] 的元素赋值连续递增的值，这个 iota 在 GO 里也有类似含义，但是用法很不同

iota(arr,arr+n,0); // 0 1 2 3 4 5...

next prev

移动迭代器

大部分容器时间复杂度 O(n)

set<int>s;

int main()
{
    rep(i,1,3e5)s.insert(i);
    auto it=s.begin();
    auto newit=next(it,3e5-1);
    cout<<*newit<<endl;
    return 0;
}

isalpha isalnum isdigit

判断字符是否是字母，数字或字母，数字

random库

random库提供了均匀分布、伯努利分布、泊松分布、正态分布等多种分布类型，有兴趣可以自己查一下，不展开讲了

bit库

有很多处理二进制东西比较方便的函数，不过大多数环境跟不上，不展开讲了

https://www.apiref.com/cpp-zh/cpp/header/bit.html

### 字符串的部分复制
void strmncpy(char* s, int m, int n, char* t)
{
//字符串的部分复制，将s指向字符串从第m个字符开始的n个字符复制的t中
    char* p = s;
    char* q = t;
    int a = 0;
    p = p + m;
    while (a < n)
    {
        *q++ = *p++;
        a++;
    }
    *q = '\0';
}

AtCoder Beginner Contest 221 C - Select Mul

AC code

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 100;
int a[N];
typedef long long LL;

void strmncpy(char* s, int m, int n, char* t)
{
//字符串的部分复制，将s指向字符串从第m个字符开始的n个字符复制的t中
    char* p = s;
    char* q = t;
    int a = 0;
    p = p + m;
    while (a < n)
    {
        *q++ = *p++;
        a++;
    }
    *q = '\0';
}

int main()
{
    char s[N];
    scanf("%s",s);
    int len = strlen(s);

    for(int i = 0;s[i]; i ++)
    {
        a[i] = s[i] - '0';
    }
    sort(a,a + len);
    LL mmax = -0x3f3f3f3f;
    do{
        char new_per[N];
        for(int i = 0;i < len;i ++)
        {
            new_per[i] = a[i] + '0';
        }
        for(int i = 1;i < len;i ++)
        {
            char num_1[N]; char num_2[N];
            strmncpy(new_per,0,i,num_1); strmncpy(new_per,i ,len - i,num_2);//枚举所有的间断点
            int num1; int num2;
            sscanf(num_1,"%d",&num1);//通过sscanf 将字符串num_1转换成数字 读入至 num1 中
            sscanf(num_2,"%d",&num2);
            mmax = max(mmax,(LL)num1 * (LL)num2);
        }
    }while(next_permutation(a,a + len));

    printf("%lld",mmax);
    return 0;
}

D2 Half of Same

题目大意

可以对 n 个数进行减 k 的操作,问是否能通过操作将至少一半的数变为一样的数并且使得 k 尽可能的大

思路

两个数之间若能通过 k 变成一样的数说明 abs (a[i] - a[j]) % k == 0 即 k 是 abs (a[i] - a[j]) 的因子那么随机取两个数 a[i] 和 a[j],枚举 abs(a[i] - a[j])的因子作为 k ,判断 k 是否合法,更新答案即可那么随机化如何保证正确性呢 n 个数中至少有 1 / 2 的数属于答案的集合.那么随机取一个数,取到答案数的概率至少为 1 / 2,取出两个数倘若均不为答案的可能性为 3 / 4 那么 (3 / 4) ^ 1000 是非常小的因此此做法可行.

AC code

#include<bits/stdc++.h>
using namespace std;
const int N = 100;
int a[N];
int n; 

int check(int k)
{
    map<int,int> mp;
    for(int i = 1;i <= n;i ++)//统计 n 个数 mod k 的余数 
    {
        mp[(a[i] % k + k) % k]++;
    }
    for(auto i : mp)//倘若已经有超过一半的数 mod k 余数相同 那么方案成立
    {
        if(i.second*2>=n)return 1;
    }
    return 0;
}

void solve()
{
    scanf("%d",&n);
    for(int i = 1;i <= n;i ++) scanf("%d",&a[i]);
    map<int,int> mp;
    for(int i = 1;i <= n;i ++) mp[a[i]] += 1;

    int f = 0;
    for(auto it : mp)
    {
        if(it.second * 2 >= n) f = 1;
    }
    if(f) {puts("-1"); return ;}

    srand(time(NULL));
    int res = 0;
    for(int R = 1;R <= 1000;R ++)//随机 1000 轮
    {
        int rd1 = rand() % n + 1;//取出俩随机数
        int rd2 = rand() % n + 1;
        if(rd1 == rd2) continue;
        int x = abs(a[rd1] - a[rd2]);
        for(int j = 1;j * j <= x;j ++)//枚举其因子
        {
            if(x % j == 0) 
            {
                if(check(j)) res = max(res , j);
                if(check(x / j)) res = max(res , x / j);
            }
        }
    }
    printf("%d\n",res);
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T --)
    {
       solve();
    }
    return 0;
}