一些日常工具集合（C++代码片段）
——工欲善其事，必先利其器
尽管不会松松松，但是至少维持一个比较小的常数还是比较好的
在此之前依然要保证算法的正确性以及代码的可写性
本文依然会持久更新，因为一次写不完
Tools1：算法
这个的重要性就不强调了，轻则多$log$，重则爆$n^2$，更令人窒息者为多项式和非多项式的区别
设计一个好的算法，首先不要想着如何去用$O(n^2)$碾压$O(n)$，而是先想如何实现$O(n)$才是比较好的
洛咕日报15期（霸占评论区三天2333），关于基数排序的
Tools2：IO
IO输出要么没有显著优化，要么直接从TLE优化到AC，在另一篇博客有介绍https://www.cnblogs.com/CreeperLKF/p/8448568.html
然后下面放上一些我平时用的贴在代码前面且具有不同功能的一些东西：
1. 短一些，只有一个小的工具包，没有使用要求
#include <cstdio>
#include <cctype>
#include <cstring>
//User's Lib
using namespace std;
], *pc = buf;
struct Main_Guard{
Main_Guard(){
fread(buf, , , stdin);
}
Main_Guard(const char *ins){
freopen(ins, "r", stdin);
fread(buf, , , stdin);
}
Main_Guard(const char *ins, const char *ous){
freopen(ins, "r", stdin);
freopen(ous, "w", stdout);
fread(buf, , , stdin);
}
~ Main_Guard(){
fclose(stdin), fclose(stdout);
}
};
static inline int read(){
;
;
while(isspace(c = *pc++));
) sf = -, c = *pc ++;
+ c - , isdigit(c = *pc++));
return num * sf;
}
namespace LKF{
template <typename T>
extern inline T abs(T tar){
? -tar : tar;
}
template <typename T>
extern inline void swap(T &a, T &b){
T t = a;
a = b;
b = t;
}
template <typename T>
extern inline void upmax(T &x, const T &y){
if(x < y) x = y;
}
template <typename T>
extern inline void upmin(T &x, const T &y){
if(x > y) x = y;
}
template <typename T>
extern inline T max(T a, T b){
return a > b ? a : b;
}
template <typename T>
extern inline T min(T a, T b){
return a < b ? a : b;
}
}
//Source Code
短
2. 长一些，分类讨论一些开关，然后不是所有东西保证效率，功能多
//Created By Creeper_LKF
//Caution::We used "pragma" in the code
#include <cstdio>
#include <cctype>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <iostream>
#ifdef __gnu_linux__
#include <fcntl.h>
#include <unistd.h>
#include <sys/mman.h>
#endif
#if __cplusplus < 201103L
#include <stdarg.h>
#endif
//Algorithm Heads
using namespace std;
//Debug Port
// #define DEBUG_PORT
#define DEBUG
#ifdef ONLINE_JUDGE
#undef DEBUG_PORT
#undef DEBUG
#endif
#ifdef DEBUG_PORT
#if __cplusplus >= 201103L
#ifdef DEBUG
template<typename T>
extern inline void Debug(T tar){
cerr << tar << endl;
}
template<typename Head, typename T, typename... Tail>
extern inline void Debug(Head head, T mid, Tail... tail){
cerr << head << ' ';
Debug(mid, tail...);
}
#else
template<typename Head, typename T, typename... Tail>
extern inline void Debug(Head, T, Tail...){
return ;
}
#endif
#else
# pragma message "Warning : C++11 Not Use"
#ifdef DEBUG
template <typename T>
extern inline void Debug(T tar){
cerr << tar << endl;
}
#else
template <typename T>
extern inline void Debug(T){
return ;
}
#endif
#endif
#else
template<typename Head, typename T, typename... Tail>
extern inline void Debug(Head, T, Tail...){
return ;
}
template <typename T>
extern inline void Debug(T){
return ;
}
#endif
const char file_name[] = "b";
#define NAME_SPACE
#define USING
#ifdef NAME_SPACE
namespace LKF{
#endif
#define SF_READ
#define EOF_READ
// #define ONLINE_JUDGE
#define WRITE_ENDL
// #define FAST_WRITE
#define SPLIT_WRITE
;
#define NEED_FILE
#ifdef FAST_WRITE
char outp[MAX_BUF_SIZE], *op = outp;
#endif
#ifdef ONLINE_JUDGE
#undef NEED_FILE
#endif
#ifdef FAST_WRITE
#ifndef WRITE_ENDL
#define WRITE_ENDL
#endif
#endif
extern inline void FILE_OPT(){
#ifdef NEED_FILE
#define FILE_NAME file_name
], OUT_FILE[];
strcpy(IN_FILE, FILE_NAME), strcpy(OUT_FILE, FILE_NAME);
strcat(IN_FILE, ".in"), strcat(OUT_FILE, ".out");
freopen(IN_FILE, "r", stdin);
freopen(OUT_FILE, "w", stdout);
#endif
}
#ifdef __gnu_linux__
char *pc;
struct Main_Guard{
Main_Guard(){
#ifndef ONLINE_JUDGE
FILE_OPT();
pc = (, , SEEK_END), PROT_READ, MAP_PRIVATE, , );
#endif
}
~ Main_Guard(){
#ifdef FAST_WRITE
fwrite(outp, , op - outp, stdout);
#endif
fclose(stdin), fclose(stdout);
}
};
#else
char buf[MAX_BUF_SIZE], *pc = buf;
struct Main_Guard{
Main_Guard(){
FILE_OPT();
fread(buf, , MAX_BUF_SIZE, stdin);
}
~ Main_Guard(){
#ifdef FAST_WRITE
fwrite(outp, , op - outp, stdout);
#endif
fclose(stdin), fclose(stdout);
}
};
#endif
inline char read_ch(){
char c;
while(isspace(c = *pc ++));
return c;
}
#ifdef EOF_READ
#ifdef SF_READ
template<typename T>
static inline void read(T &num){
num = ;
;
while(isspace(c = *pc++));
) sf = -, c = *pc ++;
+ c - , isdigit(c = *pc++));
num *= sf;
}
static inline int read(){
;
;
while(isspace(c = *pc++));
) sf = -, c = *pc ++;
+ c - , isdigit(c = *pc++));
return num * sf;
}
static inline double read_dec(){
, decs = ;
;
while(isspace(c = *pc ++));
, c = *pc ++;
+ c - , isdigit(c = *pc ++));
if(c != '.') return num * sf;
c = *pc ++;
), isdigit(c = *pc ++));
return num * sf;
}
#else
template<typename T>
static inline T read(T &num){
num = ;
char c;
while (isspace(c = *pc++));
+ c - , isdigit(c = *pc++));
return num;
}
static inline int read(){
;
char c;
while (isspace(c = *pc++));
+ c - , isdigit(c = *pc++));
return num;
}
static inline double read_dec(){
, decs = ;
char c;
while(isspace(c = *pc ++));
+ c - , isdigit(c = *pc ++));
if(c != '.') return num;
c = *pc ++;
) * (decs *= 0.1), isdigit(c = *pc ++));
return num;
}
#endif
#else
#ifdef SF_READ
template<typename T>
static inline void read(T &num){
num = ;
;
);
) sf = -, c = *pc ++;
+ c - , (c = *pc++) >= );
num *= sf;
}
static inline int read(){
;
;
);
) sf = -, c = *pc ++;
+ c - , (c = *pc++) >= );
return num * sf;
}
static inline double read_dec(){
, decs = ;
;
while(isspace(c = *pc ++));
, c = *pc ++;
+ c - , isdigit(c = *pc ++));
if(c != '.') return num * sf;
c = *pc ++;
), isdigit(c = *pc ++));
return num * sf;
}
#else
template<typename T>
static inline T read(T &num){
num = ;
char c;
);
+ c - , (c = *pc++) >= );
return num;
}
static inline int read(){
;
char c;
);
+ c - , (c = *pc++) >= );
return num;
}
static inline double read_dec(){
, decs = ;
char c;
while(isspace(c = *pc ++));
+ c - , isdigit(c = *pc ++));
if(c != '.') return num;
c = *pc ++;
) * (decs *= 0.1), isdigit(c = *pc ++));
return num;
}
#endif
#endif
#ifdef FAST_WRITE
template <typename T>
inline void Call_Write(char Split, T tar){
];
;
) *op ++ = ;
else {
) *op ++ = '-', tar = -tar;
, tar /= ;
;
}
*op ++ = Split;
}
template <typename T>
inline void Call_Write(T tar){
];
;
) *op ++ = ;
else {
) *op ++ = '-', tar = -tar;
, tar /= ;
;
}
}
#endif
#ifdef FAST_WRITE
extern inline void write(){
*op ++ = '\n';
}
template<typename T>
extern inline void write(T tar){
Call_Write(tar);
#ifdef WRITE_ENDL
write();
#endif
}
#if __cplusplus >= 201103L
template<typename T>
extern inline void write(char, T tar){
Call_Write(tar);
#ifdef WRITE_ENDL
write();
#endif
}
template<typename Head, typename T, typename... Tail>
extern inline void write(char Split, Head head, T mid, Tail... tail){
Call_Write(Split, head);
write(Split, mid, tail...);
}
#else
template <typename T>
extern inline void write(char Split, T tar){
Call_Write(tar);
#ifdef WRITE_ENDL
write();
#endif
}
#endif
#else
extern inline void write(){
cout << endl;
}
template<typename T>
extern inline void write(T tar){
cout << tar;
#ifdef WRITE_ENDL
write();
#endif
}
#if __cplusplus >= 201103L
template<typename T>
extern inline void write(char Split, T tar){
cout << tar << Split;
#ifdef WRITE_ENDL
write();
#endif
}
template<typename Head, typename T, typename... Tail>
extern inline void write(char Split, Head head, T mid, Tail... tail){
#ifdef SPLIT_WRITE
cout << head << Split;
#else
cout << head;
#endif
write(Split, mid, tail...);
}
#else
template <typename T>
extern inline void write(char Split, T tar){
cout << tar << Split;
#ifdef WRITE_ENDL
write();
#endif
}
#endif
#endif
template <typename T>
extern inline void upmax(T &x, const T &y){
if(x < y) x = y;
}
template <typename T>
extern inline void upmin(T &x, const T &y){
if(x > y) x = y;
}
#if __cplusplus >= 201103L
template<typename T>
extern inline T max(T tar){
return tar;
}
template<typename T>
extern inline T min(T tar){
return tar;
}
template <typename Head, typename T, typename... Tail>
extern inline Head max(Head head, T mid, Tail... tail){
Head tmp = max(mid, tail...);
return head > tmp ? head : tmp;
}
template <typename Head, typename T, typename... Tail>
extern inline Head min(Head head, T mid, Tail... tail){
Head tmp = min(mid, tail...);
return head < tmp ? head : tmp;
}
#else
template <typename T>
extern inline T max(T a, T b){
return a > b ? a : b;
}
template <typename T>
extern inline T min(T a, T b){
return a < b ? a : b;
}
#endif
template <typename T>
extern inline T abs(T tar){
? -tar : tar;
}
template <typename T>
extern inline void swap(T &a, T &b){
T t = a;
a = b;
b = t;
}
#ifdef NAME_SPACE
}
#endif
//Algorithm
#ifdef NAME_SPACE
namespace LKF{
#endif
template <class Tn, size_t ArraySize>
struct Queue{
size_t s, t;
Tn q[ArraySize];
Queue(){
s = , t = ;
}
inline void clear(){
s = , t = ;
}
inline bool empty(){
return s > t;
}
inline size_t size(){
;
}
inline void push(Tn tar){
q[++ t] = tar;
}
inline void pop_front(){
s ++;
}
inline void pop_back(){
t --;
}
inline Tn front(){
return q[s];
}
inline Tn back(){
return q[t];
}
};
template <class Tn, size_t ArraySize>
struct Stack{
size_t t;
Tn s[ArraySize];
Stack(){
t = ;
}
inline void clear(){
t = ;
}
inline bool empty(){
;
}
inline size_t size(){
return t;
}
inline void push(Tn tar){
s[++ t] = tar;
}
inline Tn top(){
return s[t];
}
inline void pop(){
t --;
}
};
#ifdef NAME_SPACE
}
#endif
#ifdef USING
#ifdef NAME_SPACE
using LKF::pc;
using LKF::read_ch;
using LKF::read_dec;
using LKF::read;
using LKF::write;
using LKF::upmax;
using LKF::upmin;
using LKF::max;
using LKF::min;
using LKF::abs;
// using LKF::swap;
#else
using ::pc;
using ::read_ch;
using ::read_dec;
using ::read;
using ::write;
using ::upmax;
using ::upmin;
using ::max;
using ::min;
using ::abs;
// using ::swap;
#endif
#endif
//Source Code
长
3. C++11下可以使用调试多参数调试 Debug(arg1, arg2...) ，建议搭配dot可以直接图论题中绘图，可以不删除调试代码交到Luogu上
#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
//User's Lib
using namespace std;
// #define DEBUG_PORT
#define DEBUG
#ifdef ONLINE_JUDGE
#undef DEBUG_PORT
#undef DEBUG
#endif
#ifdef DEBUG_PORT
#if __cplusplus >= 201103L
#ifdef DEBUG
template<typename T>
extern inline void Debug(T tar){
cerr << tar << endl;
}
template<typename Head, typename T, typename... Tail>
extern inline void Debug(Head head, T mid, Tail... tail){
cerr << head << ' ';
Debug(mid, tail...);
}
#else
template<typename Head, typename T, typename... Tail>
extern inline void Debug(Head, T, Tail...){
return ;
}
#endif
#else
# pragma message "Warning : C++11 Not Use"
#ifdef DEBUG
template <typename T>
extern inline void Debug(T tar){
cerr << tar << endl;
}
#else
template <typename T>
extern inline void Debug(T){
return ;
}
#endif
#endif
#else
template<typename Head, typename T, typename... Tail>
extern inline void Debug(Head, T, Tail...){
return ;
}
template <typename T>
extern inline void Debug(T){
return ;
}
#endif
], *pc = buf;
struct Main_Guard{
Main_Guard(){
fread(buf, , , stdin);
}
Main_Guard(const char *ins){
freopen(ins, "r", stdin);
fread(buf, , , stdin);
}
Main_Guard(const char *ins, const char *ous){
freopen(ins, "r", stdin);
freopen(ous, "w", stdout);
fread(buf, , , stdin);
}
~ Main_Guard(){
fclose(stdin), fclose(stdout);
}
};
static inline int read(){
;
;
while(isspace(c = *pc++));
) sf = -, c = *pc ++;
+ c - , isdigit(c = *pc++));
return num * sf;
}
namespace LKF{
template <typename T>
extern inline T abs(T tar){
? -tar : tar;
}
template <typename T>
extern inline void swap(T &a, T &b){
T t = a;
a = b;
b = t;
}
template <typename T>
extern inline void upmax(T &x, const T &y){
if(x < y) x = y;
}
template <typename T>
extern inline void upmin(T &x, const T &y){
if(x > y) x = y;
}
template <typename T>
extern inline T max(T a, T b){
return a > b ? a : b;
}
template <typename T>
extern inline T min(T a, T b){
return a < b ? a : b;
}
}
//Source Code
简单
4. 只能读非负整数，然后用的是更快的读入，但是在本地都开了文件输入输出
#include <cstdio>
#include <fcntl.h>
#include <unistd.h>
#include <sys/mman.h>
//User's Lib
using namespace std;
char *pc;
], *op = outp;
struct Main_Guard{
Main_Guard(){
pc = (, , SEEK_END), PROT_READ, MAP_PRIVATE, , );
}
Main_Guard(const char *ins){
freopen(ins, "r", stdin);
pc = (, , SEEK_END), PROT_READ, MAP_PRIVATE, , );
}
Main_Guard(const char *ins, const char *ous){
freopen(ins, "r", stdin);
freopen(ous, "w", stdout);
pc = (, , SEEK_END), PROT_READ, MAP_PRIVATE, , );
}
~ Main_Guard(){
fwrite(outp, , op - outp, stdout);
fclose(stdin), fclose(stdout);
}
};
inline int read(){
;
char c;
);
+ c - , (c = *pc ++) >= );
return num;
}
inline void Write(const char *tar){
, lim = strlen(tar); i < lim; i++)
*op ++ = tar[i];
}
inline void Write(const int &tar){//You Need To Write '-' and '\n' By Hand
if(!tar) return ;
Write(tar / );
*op ++ = (tar % ) ^ ;
}
namespace LKF{
template <typename T>
extern inline T abs(T tar){
? -tar : tar;
}
template <typename T>
extern inline void swap(T &a, T &b){
T t = a;
a = b;
b = t;
}
template <typename T>
extern inline void upmax(T &x, const T &y){
if(x < y) x = y;
}
template <typename T>
extern inline void upmin(T &x, const T &y){
if(x > y) x = y;
}
template <typename T>
extern inline T max(T a, T b){
return a > b ? a : b;
}
template <typename T>
extern inline T min(T a, T b){
return a < b ? a : b;
}
}
//Source Code
快速
5. C++11特性用，删掉了分类讨论
#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
//User's Lib
using namespace std;
#define DEBUG
#ifdef ONLINE_JUDGE
#undef DEBUG
#endif
#ifdef DEBUG
template<typename T>
extern inline void Debug(T tar){
cerr << tar << endl;
}
template<typename Head, typename T, typename... Tail>
extern inline void Debug(Head head, T mid, Tail... tail){
cerr << head << ' ';
Debug(mid, tail...);
}
#else
template<typename Head, typename T, typename... Tail>
extern inline void Debug(Head, T, Tail...){
return ;
}
#endif
], *pc = buf;
struct Main_Guard{
Main_Guard(){
fread(buf, , , stdin);
}
Main_Guard(const char *ins){
freopen(ins, "r", stdin);
fread(buf, , , stdin);
}
Main_Guard(const char *ins, const char *ous){
freopen(ins, "r", stdin);
freopen(ous, "w", stdout);
fread(buf, , , stdin);
}
~ Main_Guard(){
fclose(stdin), fclose(stdout);
}
};
static inline int read(){
;
;
while(isspace(c = *pc++));
) sf = -, c = *pc ++;
+ c - , isdigit(c = *pc++));
return num * sf;
}
namespace LKF{
template <typename T>
extern inline void upmax(T &x, const T &y){
if(x < y) x = y;
}
template <typename T>
extern inline void upmin(T &x, const T &y){
if(x > y) x = y;
}
template<typename T>
extern inline T max(T tar){
return tar;
}
template<typename T>
extern inline T min(T tar){
return tar;
}
template <typename Head, typename T, typename... Tail>
extern inline Head max(Head head, T mid, Tail... tail){
Head tmp = max(mid, tail...);
return head > tmp ? head : tmp;
}
template <typename Head, typename T, typename... Tail>
extern inline Head min(Head head, T mid, Tail... tail){
Head tmp = min(mid, tail...);
return head < tmp ? head : tmp;
}
template <typename T>
extern inline T abs(T tar){
? -tar : tar;
}
template <typename T>
extern inline void swap(T &a, T &b){
T t = a;
a = b;
b = t;
}
}
//Source Code
C++ 11
6. 最简单的快读
#include <cstdio>
using namespace std;
], *pc = buf;
struct Main_Guard{
Main_Guard(){
fread(buf, , , stdin);
}
Main_Guard(const char *ins){
freopen(ins, "r", stdin);
fread(buf, , , stdin);
}
Main_Guard(const char *ins, const char *ous){
freopen(ins, "r", stdin);
freopen(ous, "w", stdout);
fread(buf, , , stdin);
}
~ Main_Guard(){
fclose(stdin), fclose(stdout);
}
};
inline int read(){
;
char c;
);
+ c - , (c = *pc ++) >= );
return num;
}
//Source Code
快读
由于最近改了一下，所以可能还会有一点Bug
Main_Guard调用方法就是在main函数开头写 Main_Guard main_guard; 如果需要读入的话就在后面带括号和文件名，输出的话就带两个字符串
这样的好处就是一定会调用析构函数
Tools3：__builtin_
一个非常妙而且实用的工具，有些C++库函数会调用到，不过自己去学会调用肯定会比较妙，整个Builtin家族非常大（看文档https://gcc.gnu.org/onlinedocs/gcc/，具体可以在https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html#Other-Builtins查找），这里只介绍一些常用的。下面的函数的参数以及返回值对照了gcc文档。
二进制相关
（注意下面函数定义在unsigned int(或int)上，如果需要使用unsigned long long（或long long）版则可以在函数名后面加上ll，例如__builtin_ffsll接受long long的参数）（还有一个__builtin_clrsb看不懂什么玩意）。
- int __builtin_ffs (int x) ：查询x二进制最后一个1是第几位
- int __builtin_clz (unsigned int x) ：查询x有多少个前导0，If x is 0, the result is undefined.
- int __builtin_ctz (unsigned int x) ：查询x有多少个后缀0，If x is 0, the result is undefined.
- int __builtin_popcount (unsigned int x) ：查询x有多少个1，在洛谷日爆未来的某期内我还了解到了还可以加#pragma GCC target ("popcnt")直接把这玩意转化成指令加速，优化效果高达70%（网上某些题的实验）
- int __builtin_parity (unsigned int x) ：查询x的二进制奇偶校验，也就是x中1的个数模2
- uint16_t __builtin_bswap16 (uint16_t x) ：按照字节翻转二进制位，例如0xaabb翻转成为0xbbaa，然后16可替换为32,64，表示位数
CPU分支预测优化
long __builtin_expect (long exp, long c)
函数的作用就是引导CPU在分支预测的时候选择某个if分支执行，以前靠这个东西直接把一道题卡到了0ms，单点甩Rank2接近8ms，可见有些情况下效果还是不错的
食用方法：exp那里填写你希望预测的一个表达式，建议不要写的太复杂了，c填写你预测表达式大概率会是什么值，然后直接用在if内即可，例如 ))
效果：如果写的比较好的话有一些大优化，否则会导致CPU频繁罚时
例子：例如你知道某个数据结构它的体型庞大而且你有特意地防止node指针指向NULL，但是如果你不放心的话那么可以加一个这个。例如表达式$i%100000000==1$一般会比较难成立，可以优化，而$i%10==1$就不需要这样优化了
提前写入缓存
void __builtin_prefetch (const void *addr, ...)
就是提前把数据取到缓存
gcc的参数表最后面还有两个可选参数，rw和locality，表示使用这个数据是读或者写（1是写0是读），以及这个数据的时间局部性。
读或者写就不说了
时间局部性表示这个数据在被访问之后在一定时间内还会不会再次访问（而不是距离第一次访问还有多久），决定了这个数据在缓存中的“寿命”。0表示没有时间局部性，也就是很长时间内不再访问，而3表示高时间局部性，表示访问了时候很快又会访问。这个参数一定是个编译时候的常量，默认为3.
Tools4：细节
首先register和inline标记应该都会吧。register表示建议编译器将变量放在编译器中，C++11及以上为了防止滥用渐渐开始忽略这个东西，在C++17时你会被提醒这个东西已经不能用了。inline在我讲快读那篇文章的末尾有https://www.cnblogs.com/CreeperLKF/p/8448568.html
例如下面Luogu上两份A+B Problem（找LZL123测试的），代码相差无几，但是时间差了584ms，空间差了63971kb，差距竟然只有1000的数据范围
见提交记录https://www.luogu.org/record/show?rid=6205849和https://www.luogu.org/recordnew/show/5650350
代码区别：
584ms：
#include <cstdio>
<<];
int main()
{
;
;i<=<<;++i)
x[i]++,ans+=x[i];
scanf("%d%d",&a,&b);
printf("%d",a+b);
;
}
0ms：
#include <cstdio>
<<+];
int main()
{
;
;i<=<<+;++i)
x[i]++,ans+=x[i];
scanf("%d%d",&a,&b);
printf("%d",a+b);
;
}
关于register：这种东西比较奇怪，现代CPU确实先进了不少，但是某些OJ上是有效的，例如提交记录
可能存在干扰因素，有兴趣的可以自己去各大OJ调查一下（例如上次我在HDU加了优化之后还变慢了）
Tools5：强力Random工具
这个Random工具就是用mt19937（C++ Reference Wiki）加上Linux下的/dev/random和/dev/urandom以及某种非常高精度的时钟实现的，速度可观，可以在Windows下运行
然后测试效果海星，其中的宏也已经定义好，开袋即食，您的造数据好帮手
注意如果要大量生成数据的话不要使用/dev/random，否则会比较卡（如果必须的话你可以手动调节一下中间的Init_Rand_Buf）
注意某些函数可能会被成功inline，调试的时候如果发现这个函数“没有调用”不要慌
持续更新QWQ
//~~~~~~~~~~~~~~~~~~~~~~~~~~~Random_Part~~~~~~~~~~~~~~~~~~~~~~~~
//食用说明：在一开始需要调用Rand_Initialize
//如果需求量和速度要求不高的话可以打开DO_NOT_USE_URANDOM
//如果在Linux的话可以打开RAND_BUF
//这样可以让随机位取地比较好
//为什么要每8位取1次？因为发现如果8位取8个的话好像随机性不优？
#include <chrono>
#include <random>
#include <algorithm>
#ifdef __gnu_linux__
#define RAND_BUF
// #define DO_NOT_USE_URANDOM
#endif
#ifdef RAND_BUF
#include <fcntl.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/stat.h>
#endif
using namespace std;
mt19937 Generator;
#define BUF_SIZE 8193
#ifdef RAND_BUF
char rand_buf[BUF_SIZE], *p1 = rand_buf, *p2 = rand_buf;
int buf_times, rand_fd;
inline void Init_Rand_Buf(){
buf_times ++;
) p2 = (p1 = rand_buf) + read(rand_fd, rand_buf, sizeof(rand_buf));
|| p1 + BUF_SIZE != p2){
) buf_times = ;
; i < BUF_SIZE; i++) rand_buf[i] = Generator();
p2 = (p1 = rand_buf) + BUF_SIZE;
}
}
inline int Rand_Bit(){
if(p1 == p2) Init_Rand_Buf();
);
}
#endif
inline void Rand_Initialize(){
unsigned seed1 = chrono::system_clock::now().time_since_epoch().count();
#ifdef RAND_BUF
#ifdef DO_NOT_USE_URANDOM
rand_fd = open();
#else
rand_fd = open();
#endif
Init_Rand_Buf();
*(-- p2) = seed1 & 0xff;
*(-- p2) = (seed1 >> ) & 0xff;
*(-- p2) = (seed1 >> ) & 0xff;
*(-- p2) = (seed1 >> ) & 0xff;
p2 ++, p2 ++, p2 ++, p2 ++;
seed_seq seed2(p1, p2);
Generator = mt19937(seed2);
#else
Generator mt19937(seed1);
#endif
}
inline unsigned Rand(){
return Generator();
}
inline unsigned Rand(unsigned up){
;
}
inline unsigned Rand(unsigned down, unsigned up){
) + down;
}
inline double Rand_Float(){
return (double)Rand() / (unsigned)0xffffffff;
}
inline unsigned long long Rand_ull(){
return (unsigned long long)Rand() * Rand();
}
#ifndef RAND_BUF
inline int Rand_Bit(){
;
}
#endif
inline unsigned Rand_Number(unsigned up){
return Rand() % up;
}
template <typename Iterator_Type>
inline void Random_Shuffle(Iterator_Type __first, Iterator_Type __last){
random_shuffle(__first, __last, Rand_Number);
}
//~~~~~~~~~~~~~~~~~~~~~~~~~~~Random_Part~~~~~~~~~~~~~~~~~~~~~~~~
Tools6：其他的东西
//~~~~~~~~~~~~~~~~~~~~~~~Graph_Code~~~~~~~~~~~~~~~~~~~~
template <size_t VS, size_t ES>
struct __Graph_Base{
int tot;
int beginx[VS], endx[ES], nxt[ES];
__Graph_Base() : tot(){
memset(beginx, , sizeof(beginx));
}
inline void clear(){
tot = ;
memset(beginx, , sizeof(beginx));
}
};
template <size_t VS, size_t ES>
struct Graph : __Graph_Base<VS, ES>{
using __Graph_Base<VS, ES>::tot;
using __Graph_Base<VS, ES>::nxt;
using __Graph_Base<VS, ES>::beginx;
using __Graph_Base<VS, ES>::endx;
inline void clear(){
__Graph_Base<VS, ES>::clear();
}
inline void add_edge(const int &u, const int &v){
nxt[++ tot] = beginx[u], beginx[u] = tot, endx[tot] = v;
nxt[++ tot] = beginx[v], beginx[v] = tot, endx[tot] = u;
}
};
//~~~~~~~~~~~~~~~~~~~~~~~Graph_Code~~~~~~~~~~~~~~~~~~~~
//~~~~~~~~~~~~~~~~~~~~~~~Matrix_Code~~~~~~~~~~~~~~~~~~~
template <size_t Matrix_Size>
struct Matrix{
int a[Matrix_Size][Matrix_Size];
Matrix(){
memset(a, , sizeof(a));
}
Matrix(const int &tar){
memset(a, , sizeof(a));
; i <= MAX; i++)
a[i][i] = tar;
}
inline int * operator [] (const int &tar){
return a[tar];
}
inline const int * operator [] (const int &tar) const {
return a[tar];
}
inline Matrix operator * (const Matrix &tar) const {
Matrix ret;
; i <= MAX; i++)
; k <= MAX; k++)
; j <= MAX; j++)
ret[i][j] += a[i][k] * tar.a[k][j];
return ret;
}
inline Matrix & operator *= (const Matrix &tar){
return *this = (*this) * tar;
}
template <typename T>
inline Matrix operator ^ (register T tar) const {
Matrix ret(), tmp = *this;
while(tar){
) ret *= tmp;
tmp *= tmp;
tar >>= ;
}
return ret;
}
template <typename T>
inline Matrix & operator ^= (const T &tar){
return *this = (*this) ^ tar;
}
template <typename T>
inline Matrix pow(register T tar, Matrix Init_Matrix) const {
Matrix ret();
while(tar){
) ret *= Init_Matrix;
Init_Matrix *= Init_Matrix;
tar >>= ;
}
return ret;
}
};
//~~~~~~~~~~~~~~~~~~~~~~~Matrix_Code~~~~~~~~~~~~~~~~~~~
关于Graph：就是有时候同一道题可能会有很多张图，然后你要调试的话就可以把这个东西写开，然后为每一种图加一个Debug，或者是有时候需要同时维护有向图和无向图
关于Matrix：就不解释了QWQ