算法竞赛代码片段记录

代码片段记录

代码加速相关

加速输入

int getin()
{
	int x=0;char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=getchar();
	return x;
}

高级输入输出

#include<bits/stdc++.h>
#define lson (o<<1)
#define rson (o<<1|1)
#define fi first
#define sc second
#define dbg(x) cout<<#x<<" = "<<(x)<<endl;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
using namespace std;
const double pi=acos(-1);
const double eps=1e-6;
inline int lowbit(int x){return x&(-x);}
inline int read(){
	int f=1,x=0;char ch;
	do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
	do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');
	return f*x;
}
template<typename T> inline T max(T x,T y,T z){return max(max(x,y),z);}
template<typename T> inline T min(T x,T y,T z){return min(min(x,y),z);}
template<typename T> inline T sqr(T x){return x*x;}
template<typename T> inline void checkmax(T &x,T y){x=max(x,y);}
template<typename T> inline void checkmin(T &x,T y){x=min(x,y);}
template<typename T> inline void read(T &x){
x=0;T f=1;char ch;do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
do x=x*10+ch-'0',ch=getchar();while(ch<='9'&&ch>='0');x*=f;
}
template<typename A,typename B,typename C> inline A fpow(A x,B p,C yql){
	A ans=1;
	for(;p;p>>=1,x=1LL*x*x%yql)if(p&1)ans=1LL*x*ans%yql;
	return ans;
}
struct FastIO{
	static const int S=1310720;
	int wpos;char wbuf[S];
	FastIO():wpos(0) {}
	inline int xchar(){
		static char buf[S];
		static int len=0,pos=0;
		if(pos==len)pos=0,len=fread(buf,1,S,stdin);
		if(pos==len)return -1;
		return buf[pos++];
	}
	inline int read(){
		int c=xchar(),x=0;
		while(c<=32&&~c)c=xchar();
		if(c==-1)return -1;
		for(;'0'<=c&&c<='9';c=xchar())x=x*10+c-'0';
		return x;
	}
}io;
//#define read io.read

STL拓展

StringStream分割字符串(首选，速度最快)

默认分割空格、tab、回车换行

#include <iostream>
#include <sstream>
#include <vector>
 
using namespace std;
 
int main() {
    string str = "hello world sperated by   spaces\tand\nhuiche";
 
    vector<string> arr;
    istringstream ss(str);
    string word;
    while(ss>>word) {
        arr.push_back(word);
    }
 
    for(size_t i=0; i<arr.size(); i++) {
        cout << arr[i] << endl;
    }
     
    return 0;
}

利用指定字符分割字符串

#include <iostream>
#include <sstream>
#include <vector>
 
using namespace std;
 
int main() {
        std::string data = "1_2_3_4_5_6";
        std::stringstream ss(data);
        std::string item;
        queue<string> q;
        cout << data << endl;
        while (std::getline(ss, item, '_')) 
            cout << item << ' ';  
}

//1_2_3_4_5_6
//1 2 3 4 5 6 

String分割函数模板(正则表达式较慢)

#include <iostream>
#include <vector>
#include <iterator>
#include <regex>
/* 
   用delim指定的正则表达式将字符串in分割，返回分割后的字符串数组
   delim 分割字符串的正则表达式 
 */
std::vector<std::string> s_split(const std::string& in, const std::string& delim) {
    std::regex re{ delim };
    // 调用 std::vector::vector (InputIterator first, InputIterator last,const allocator_type& alloc = allocator_type())
    // 构造函数,完成字符串分割
    return std::vector<std::string> {
        std::sregex_token_iterator(in.begin(), in.end(), re, -1),
        std::sregex_token_iterator()
    };
}

调用示例：

#include <iostream>
#include <vector>
#include <iterator>
#include <regex>
int main() {    
    auto s_result = s_split("hello,do you ;know the word?", "[\\s,;?]+"); // \s代表空格制表符换行等任意空白字符
    std::copy(s_result.begin(), s_result.end(), std::ostream_iterator<std::string>(std::cout, "\n"));

    auto c_result = c_split("hello,do you ;know the word?", "[\\s,;?]+");
    std::copy(c_result.begin(), c_result.end(), std::ostream_iterator<std::string>(std::cout, "\n"));

    // 设置locale使std::wcout支持中文输出
    std::wcout.imbue(std::locale(std::locale(), "", LC_CTYPE));

    auto ws_result = ws_split(L"lao ban 老板,来份 小龙虾,快点啊!?", L"[\\s,;?]+");
    std::copy(ws_result.begin(), ws_result.end(), std::ostream_iterator<std::wstring, std::wstring::value_type>(std::wcout, L"\n"));
}

前缀和STL函数

#include<iostream>
#include <vector>//vector
#include <numeric>
#include <time.h> //随机数
using namespace std;
//自定义方法
int func(int x, int y) { return x - y; }
void main()
{
	//定义容器
	vector<int>vec;
	srand(time(0));//随机数
	//赋值
	for (int i = 0; i < 5; i++)
	{
		int num = rand() % 100;
		vec.push_back(num);
	}
	//迭代器
	vector<int>::iterator vi;
	//输出
	cout << "vec : \n";
	for (vi = vec.begin(); vi < vec.end(); vi++) { cout << *vi << '\t'; } //输出
	cout << endl << endl;

	// 结果存放
	// 声明容器、数组，用于存放计算结果
	int arr[10] = { 0 };
	vector<int>vec2;
	vec2.resize(10);//设置容器的大小


	// 局部总和 第一个重载
	//partial_sum(容器要计算的起始位置，容器要计算的结束位置，结果存放的起始位置)
	partial_sum(vec.begin(), vec.end(), arr);
	cout << "1 arr : \n"; 
	for (int i = 0; i < 10; i++) { cout << arr[i] << '\t'; }//输出
	cout << endl << endl;
	
	//第二个重载
	// partial_sum(容器要计算的起始位置，容器要计算的结束位置，结果存放的起始位置，自定义函数)
	partial_sum(vec.begin(), vec.end(), arr, func);
	cout << "2 arr : \n";
	for (int i = 0; i < 10; i++) { cout << arr[i] << '\t'; }//输出
	cout << endl << endl;

	//第三个重载
	//partial_sum(容器要计算的起始位置，容器要计算的结束位置，结果存放的起始位置)
	partial_sum(vec.begin(), vec.end(), vec2.begin());
	cout << "3 vec2 : \n";
	for (int i = 0; i < 10; i++) { cout << vec2[i] << '\t'; }//输出
	cout << endl << endl;

	//第四个重载
	// partial_sum(容器要计算的起始位置，容器要计算的结束位置，结果存放的起始位置，自定义函数)
	partial_sum(vec.begin(), vec.end(), vec2.begin(), func);
	cout << "4 vec2 : \n";
	for (int i = 0; i < 10; i++) { cout << vec2[i] << '\t'; }//输出
	cout << endl<< endl;

	// 结果存放在容器自身
	partial_sum(vec.begin(), vec.end(), vec.begin());
	cout << "5 vec : \n";
	for (vi = vec.begin(); vi < vec.end(); vi++) { cout << *vi << '\t'; }//输出
}

STL太慢，正常前缀和+差分数列解法：

#include <cstdio>
using namespace std;
const int N = 100010;
int a[N], b[N];
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i ++ ) b[i] = a[i] - a[i - 1];       //b为a的差分数组
    while (m -- )
    {
        int l, r, c; //[l,r]之间每个数加上c
        scanf("%d%d%d", &l, &r, &c);
        b[l] += c, b[r + 1] -= c;                               //差分模板
    }
    for (int i = 1; i <= n; i ++ ) b[i] += b[i - 1];            //计算前缀和，（差分数列的前缀和就是原数列）
    //此时的b数组就是前缀和数组了，即要输出的变化后的数组a
    for (int i = 1; i <= n; i ++ ) printf("%d ", b[i]);
    return 0;
}