最近刷题常常遇见的需要百度的知识点

对拍程序:

freopen("in.txt","r",stdin); //输入重定向,输入数据将从in.txt文件中读取
freopen("out.txt","w",stdout); //输出重定向,输出数据将保存在out.txt文件中

duipai.bat

@echo off
fc out.txt out1.txt
pause

随机数生成:

#include <cstdio>
#include <chrono>
#include <random>
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int main(){
    printf("%u
", rng());
    return 0;
}

特殊输入:

没告诉你一行有多少个数的,先用getline接受这一行,

之后复制到streamstring,之后用 >> 从streamstring中读取

getchar();
for (int i = 1; i <= n; i++) {
    string s, na;
    getline(cin, s);
    stringstream ss;
    ss.str(s);
    ss >> na;
    int v;
    while (ss >> v) g[i][v+1] = 1;
}

循环赋值:

memset最快, o2优化 + for赋值第二,fill最慢 验证在这里

STL的函数:

binary_search(Iterator first, Iterator last, const T& val)返回的是bool值,而不是位置或者下标(要二分查找返回值还是自己手撸吧

lower_bound( begin,end,num):从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字,找到返回该数字的地址,不存在则返回end。
upper_bound( begin,end,num):从数组的begin位置到end-1位置二分查找第一个大于num的数字,找到返回该数字的地址,不存在则返回end。

next_permutation (Iterator first, Iterator last, (cmp))/ prev_permutation 返回值是bool,当不存在上/下一个排列时返回的是false。

参数和sort类似,传入三个参数,数组首位,数组末位的后一个,以及比较函数,当比较函数省略时,默认为less

功能是生成当前这个数组里的排列的下一个或上一个,“下一个/上一个”是基于由比较函数定义出的字典序。

允许元素重复,比如1,1,2,1,1,调用next_permutation()后生成的是1,2,1,1,1

这两个函数最优时间复杂度是O(1),最坏时间复杂度是O(n),平均时间复杂度是O(n)

STL的容器:

vector

vector的clear函数不会释放内存,如果要释放内存的话需要vector<A>().swap(vec);或者vec.swap(vector<A>());

重点:如果vector容器的元素是指针,先遍历容器,delete每个元素指向的内存,然后再用swap
 
再简单说说vector的clear函数,调用之后vector的size会为0,所以他的下标也应该无法访问,会越界
(g++环境下用 [ ]去访问元素是可以打印出0的,这算是一个内部bug,所以建议用vector.at()来测试
 

string

假设你需要在一个string后面加上两个字符,你只能写成

string temp;
temp = temp + 'a' + 'b';
//或者
temp += 'a', temp += 'b';
//而不能写成
temp += 'a'+'b';

(具体原因就涉及到C语言内部的东西了不详谈)

 string 转大写小写

    string s = "AakoOO";
    transform(s.begin(), s.end(), s.begin(), ::toupper);
    cout<<s<<endl;
    transform(s.begin(), s.end(), s.begin(), ::tolower);
    cout<<s<<endl;

 string中find()返回值是字母在母串中的位置(下标记录),如果没有找到,那么会返回一个特别的标记string::npos。(返回值可以看成是一个int型的数)

//返回子串出现在母串中的首次出现的位置,和最后一次出现的位置
char
flag = "c"; int position = s.find_first_of(flag); position = s.find_last_of(flag);

查找某一给定位置后的子串的位置

//从字符串s 下标5开始,查找字符串b ,返回b 在s 中的下标
position=s.find("b",5);
cout<<"s.find(b,5) is : "<<position<<endl;

string中的replace

//用str替换指定字符串("")从起始位置0开始长度为3的字符
string line = ”this@ is@ a test string!”;    
line = line.replace(0, 3, “”);
//用substr的指定子串(从1位置数共3个字符)替换从0到5位置上的line   
string substr = ”12345”; 
line = line.replace(0, 5, substr, substr.find(”1”), 3); 

int转string
c++11标准增加了全局函数std::to_string:

string to_string (int val);
string to_string (long val);
string to_string (long long val);
string to_string (unsigned val);
string to_string (unsigned long val);
string to_string (unsigned long long val);
string to_string (float val);
string to_string (double val);
string to_string (long double val);

string转int/float/...

std::string str;
int i = std::stoi(str); 
stol(long), stof(float), stod(double), stoll(long long);

map

map如果要insert的话可以直接如下例(仅支持在c++11):

map<int, int> m;
m.insert({5,6});

如果是嵌套pair也可以使用这样的方法:

map<int, pair<int, int> > m;
m.insert({5,{6, 7}});

set

如果要对set进行二分查找的话,直接用set带的lower_bound/upper_bound/find函数会比使用STL的这三个函数快很多(沈阳区域赛惨痛的教训 

multiset

multiset的find函数,返回的是你第一个插入的查询数值的位置。

比如:

multiset<int> ms;
ms.insert(1001);
ms.insert(1001);

返回的是第一个插入1001的位置,即iterator

multiset<int>默认的是升序,即multiset<int, less<int> >

multiset<int, greator<int> >才是降序

如果要自定义类型排序的话,就直接在自定义类型里重载<运算符就好了(基本操作

multiset的erase函数,如果erase里面是数值的话,那么他会将multiset中此数值全部删除。

如果只想删掉一个的话,正确的做法是先调用multiset的find函数找到数值的pos(iterator)

之后erase(pos)即可

其他的一些好用知识:

__int128:

这个数据类型只能用自己写的函数来读入跟输出。

#include <bits/stdc++.h>
using namespace std;
inline __int128 read()
{
    __int128 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;
}

inline void write(__int128 x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)
        write(x/10);
    putchar(x%10+'0');
}

int main()
{
    __int128 a = read();
    write(a);
    return 0;
View Code

C++11:

lamda表达式非常的好用。在需要按找自定义要求sort时,lamda表达式的使用可以让代码非常的简洁。

一般来说都是需要先定义一个compare函数,之后再在sort中去调用。

但使用lamda表达式:

sort(v.begin(), v.end(), [](int a, int b){return a > b;});

一行就解决了。

还可以达到以下的效果:

sort(d , d + k, [](int a, int b){return v1[a] - v2[a] < v1[b] - v2[b];});

即a数组按照v1[i]-v2[i]的大小升序。

当然如果不懂什么是lamda表达式,建议还是去网上好好看看先。

关于for (auto i : container),map所返回的是pair类型的变量,所以需要通过.first与.second去调用

原文地址:https://www.cnblogs.com/Vikyanite/p/12885283.html