本文用来记录一些做题时看到的小技巧以及踩过的坑

技巧

bool可以直接作为参数传递：

1
2
3
4
5
6
7
8
9
10
11
bool f(int i,int j,int m,int n,int next){ 
	if(next>=8){
		s[i][j]=1;
		return 1; 
	}
	if(a[i+m][j+n]==k[next]) 
	    if(f(i+m,j+n,m,n,next+1)){
	    	s[i][j]=1; 
	    	return 1;
		}
	return 0;

清除缓冲区

printf(“字符串”);后面加fflush(stdout)；cout使用endl。

bool类型可以用bitset代替

C++ bitset用法_牛客博客

递归可以实现倒序

十进制转二进制输出

1
2
3
4
5
6
    int r;
    r = num%2;
    if(num>=2) toBin(num/2);
    if(r) cout<<1;
    else cout<<0;
}

使用递归解决了倒取余数的问题而递归条件是num>=2而不是0可以解决了判断num为1时不需要输出0的情况

取字符串首尾：

1
2
3
4
5
6
char s[10000];
int i = 0;
scanf("%s",s);
while(s[i] != 0) ++i;
printf("%c ",s[0]);
printf("%c",s[i-1]);

现在复习回来看到发现这个好像没什么用…
2023/10/05

while(cin>>a)：

重载操作符的返回值：由cin>>后续参数类型决定，其返回值类型为istream&类型，大多数情况下其返回值为cin本身（非0值），只有当遇到EOF输入时，返回值为0。

取余：

1、取余是为了防止溢出，
2、但是在取了余数之后，有可能成为负数，
例如：

1
2
fib[i] = fib[i - 1] * 2 - fib[i - k - 1];
fib[i] %= m;

所以要(fib[n] + m) % m
3、(a *= b)%=mod;<->a *= b;a %= mod;

原始字符串

c++实现多行输出
c++11标准规定了一个原始字符串： raw string literal
以 R”( 开头， )” 结束，是可以跨越多行的字符串字面值，转义字符如 \t\n 在raw string literal中是普通的文本，而不再是转义字符，
如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>

int main() {
	std::cout << R"(                ********
               ************
               ####....#.
             #..###.....##....
             ###.......######              ###            ###
                ...........               #...#          #...#
               ##*#######                 #.#.#          #.#.#
            ####*******######             #.#.#          #.#.#
           ...#***.****.*###....          #...#          #...#
           ....**********##.....           ###            ###
           ....****    *****....
             ####        ####
           ######        ######
##############################################################
#...#......#.##...#......#.##...#......#.##------------------#
###########################################------------------#
#..#....#....##..#....#....##..#....#....#####################
##########################################    #----------#
#.....#......##.....#......##.....#......#    #----------#
##########################################    #----------#
#.#..#....#..##.#..#....#..##.#..#....#..#    #----------#
##########################################    ############ )";
}


运行结果：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
                ********
               ************
               ####....#.
             #..###.....##....
             ###.......######              ###            ###
                ...........               #...#          #...#
               ##*#######                 #.#.#          #.#.#
            ####*******######             #.#.#          #.#.#
           ...#***.****.*###....          #...#          #...#
           ....**********##.....           ###            ###
           ....****    *****....
             ####        ####
           ######        ######
##############################################################
#...#......#.##...#......#.##...#......#.##------------------#
###########################################------------------#
#..#....#....##..#....#....##..#....#....#####################
##########################################    #----------#
#.....#......##.....#......##.....#......#    #----------#
##########################################    #----------#
#.#..#....#..##.#..#....#..##.#..#....#..#    #----------#
##########################################    ############

基于范围的 for 循环：

在 C++11 及更高版本中推荐的方法是迭代 a 的字符 std::string 使用基于范围的 for 循环。

1
2
3
4
5
6
string dq2 = "123456";
for (char &c : dq2) {
		cout << c << ' ';
}
使用引用可以节省复制字符串所需要的时间


注意在使用stl容器时定义了容器为string类型则不能使用char类型引用，会出现[错误] invalid initialization of reference of 类型 ‘char&’ 从 表达式 of type ‘std::__cxx11::basic_string‘
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <bits/stdc++.h>
using namespace std;
deque<string> dq1, dq2;


int main() {
	dq1.assign(5, "a");
	for (string &c : dq1) {
		cout << c << ' ';
	}
	return 0;
}
//如果使用char &，则会有
//nvalid initialization of reference of类型 'char&' 从 表达式 of type 'std::__cxx11::basic_string<char>'的错误提示

1
2
3
4
5
6
7
int v[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
for(auto & i : v){
    if(!(isBoundary[temp.first+i[0]][temp.second+i[1]]||isDraw[temp.first+i[0]][temp.second+i[1]])){
        isDraw[temp.first+i[0]][temp.second+i[1]] = true;
        q.emplace(temp.first+i[0],temp.second+i[1]);
    }
}

除此之外，像for (auto cur: {4, 2, 1})这样的也是合法的

加快cin cout的方法

对于大输入输出可以快2-3倍
注意不要和printf，scanf等C语言的输出输入函数混用

1
2
3
//解除与C语言的绑定，加快cincout执行速度
cin.tie(0), cout.tie(0);
ios::sync_with_stdio(false);

获取int最大值：

1
int ans = (unsigned)(-1) >> 1;

使用auto关键字代替冗长的定义如：

1
2
3
4
5
6
7
8
9
10
11
12
#include <bits/stdc++.h>
using namespace std;

int main() {
	list<int> l;
	l.push_back(1);
	l.push_back(2);
	l.push_back(3);
	for (auto p = l.begin(); p != l.end(); p++)//auto == list<int> ::iterator
		cout << *p << " ";
	return 0;
}

read快读

留坑待填
C/C++中最快、最简洁的read()快读(卡常数)方法
https://www.cnblogs.com/lingyunvoid/p/15204568.html

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
namespace wr {
    template<typename T>
    inline void read(T &x) {
        T a = 0, b = 1;
        char ch = 0;
        while (ch != '-' && (ch < '0' || ch > '9')) ch = (char) getchar();
        if (ch == '-') {
            b = -1;
            ch = (char) getchar();
        }
        while ('0' <= ch && ch <= '9') {
            a = ((T) a << 3) + ((T) a << 1) + (ch ^ '0');
            ch = (char) getchar();
        }
        x = a * b;
    }

    template<typename T>
    inline void write(T x, char c = '\0') {
        if (x < 0) {
            putchar('-');
            x = -x;
        }
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0');
        if (c != '\0') putchar(c);
    }
}
using namespace wr;

scanf可以加上一些参数使得读入的时候能够读取固定长度，如“%1d”

输入预处理（二分插入排序）

vectora;
a.insert(upper_bound(a.begin(),a.end(),x),x);//二分插入保证单调性

关于断环为链的思想

有时题目会要求让你处理一个环，也就是一个环形链表，但是比赛没有时间手搓链表，可以把环断开成为一条链，这样可以方便处理对于每一个k的情况。说通俗点就是在n后面再接上1—(n-1)的值，所以数组要开双倍长度（或者说长度是2n-1）。
如P2629 好消息，坏消息，这道题就是要开双倍的空间存储消息的好坏度

复杂的判断不建议使用~代替！表示非运算

比如这种情况：

1
2
!(isBoundary[x][y]||isDraw[x][y])
~(isBoundary[x][y]||isDraw[x][y])

这两个不是等价的
主要还是-1的情况，负数在C语言中是以补码的形式存在，-1按位取反之后就是0了
2023/07/01

max函数，min函数可以同时比较两个及以上的数

max({x,y,z})

用字符表示的0和1可以用异或一个1来反转

s[i] ^= 1;

树的叶子结点可以用出度为1来判断

bool数组的memset和bitset的reset的时间复杂度比较

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <bitset>
#include <cstring>
#include <chrono>

const int SIZE = 1000000; // 要处理的元素数量

void testBitset() {
    std::bitset<SIZE> bits;

    auto start = std::chrono::high_resolution_clock::now();

    for(int i = 1;i<=100;++i)bits.reset();
    //bits.reset();

    auto end = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);

    std::cout << "std::bitset reset time: " << duration.count() << " microseconds" << std::endl;
}

void testMemset() {
    bool arr[SIZE];

    auto start = std::chrono::high_resolution_clock::now();

    for(int i = 1;i<=100;++i)memset(arr,0,sizeof arr);
    //memset(arr,0,sizeof arr);

    auto end = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);

    std::cout << "memset time: " << duration.count() << " microseconds" << std::endl;
}

int main() {
    testBitset();
    testMemset();
    //处理大数据的情况下bitset要快8倍，在小范围内速度优势更为明显，快了近26倍
    return 0;
}

sort函数指定排序方式的三种写法

第一种就是写一个比较函数
第二种是运算符的重载

1
2
3
4
struct Node{
    double x,y;
    bool operator < (const Node &X)const {return x<X.x;}
}

第三种
1
sort(a+1,a+n+1,[&](st l,st r){return (l.x*l.x+l.y*l.y)<(r.x*r.x+r.y*r.y);});

几个常用的memset的赋值

memset是一个字节一个字节的赋值，所以赋值为128就会变成极小的数字，赋值为127就会变成极大的数字，赋值为255就会是-1

结构化绑定

https://blog.csdn.net/guangcheng0312q/article/details/109108472

return ….,void();

这条语句可以用来在void函数中return的时候加上一些附带的语句，例如return cout<<-1,void();

加快unordered_map的技巧

1
2
3
unordered_map<int, int> mp;
mp.reserve(1024);
mp.max_load_factor(0.25);

第一句话重新分配了容器的桶数，第二句话设置了容器的最大负载因子，元素数量/总的桶数超过了负载因子就增加桶数，这样写可以防止被对默认参数的hack，变得不那么容易退化成线性速度
还是少用吧有时候会爆内存…..
2023.11.13

染色法可以判断一棵无根树是否存在两个叶子结点之间的路径长度为奇数

范围不大的组合可以使用数组去一一映射

比如枚举一个1到3的数据对，并且每对数据中的两个元素不能相同（如（1,2）,(1,3)，像(2,2)就是不合法的）
可以使用两层for循环加上条件判断，也可以直接先手模一下写到一个数组中这样直接一个for循环就可以解决

形如$a,b,c\in \{1,2,3\} ,a\ne b\ne c,a+b+c=6$已知a,b,求c

利用恒等式：
c = 6-a-b，快速求出c而不需要两个for循环迭代加if条件判断遍历。

对于边长度固定的图（如等于1），那么BFS找到的从起点结点到任意节点的路径都是最短路

DAG的出栈顺序是反图的拓扑序，有向图SCC缩点后必定是DAG,缩完点之后的SCC最后一个出栈的必定是源点，但第一个出栈的不一定是汇点

判断一个DAG是否是一个连通图可以用是否只存在一个汇点（只有一个点出度为0）来判断

求最大公约数的时候可以写成a/gcd(a,b)*b这样可以防爆

（待验证）优先队列的初始化无序序列的时间复杂度要比直接插入元素的时间复杂度要小

上数据结构的时候发现堆有一个操作是将序列堆化，这个的操作好像时间复杂度更低一些，查了一下stl中的优先队列也有类似的操作。

因为优先队列的内部是通过堆来实现的，将一个无序序列堆化的复杂度是O(nlogn)实际上通常小于这个复杂度，接近于线性，但是插入的复杂度一般都能达到O(nlogn)

1
2
3
std::priority_queue<int> maxHeap;
std::vector<int> unorderedSequence = {1,2,3,4,5,6,2,2,4,34,56,4,2,31,3,345,}; 
maxHeap = std::priority_queue<int>(unorderedSequence.begin(),unorderedSequence.end());

排序后保留原数组中每一个元素的索引值

很多时候并不希望排序会影响索引值，因为会用到原先的索引值，一种做法是将其放在一个结构体里面，对结构体进行排序，实际上可以利用sort的自定义排序规则对一个新的索引值数组进行排序这样就不会影响到元素组中的内容
如[ABC331E] Set Meal，让你输出排序之后元素的下标等

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void solve() {
	cin >> n >> m >> op;
	vector<int> idx;
	for (int i = 1; i <= n; ++i) cin >> a[i];
	for (int i = 1; i <= m; ++i) cin >> b[i], idx.push_back(i);
	for (int i = 1, c, d; i <= op; ++i) {
		cin >> c >> d;
		h.insert(make_pair(c, d));
	}
	sort(all(idx), [&](int _a, int _b) {return b[_a] > b[_b];});
// idx数组存的是排序之后每个位置对应的初始元素的下标
    for (int i = 1; i <= n; ++i) 
		for (auto j : idx) 
			if (!h.count(make_pair(i, j))) {
				res = max(res, a[i] + b[j]);
				break;
			}
	cout << res << endl;
}

for(int j = 1;j<=n/i;++j)复杂度大概是ln级别的（比ln更大一些）

或者是形如for(int j = i;j<=n;j += i)等，就是一个调和级数画出反比例函数图像求其反常积分

当元素大小比较小的时候（比如都小于1e6）动态的查询数组有几个元素在一个范围内可以用树状数组，静态可以用前缀和

就是将tree数组，sum数组定义为一个桶，对桶进行RMQ

2的模乘逆元为(p+1)>>1

由费马小定理得，$2^{p-1} \equiv 1 \ (mod\ p)$,所以有$2^{p-2}\equiv2^{-1}\equiv \frac{p+1}{2}\ (mod\ p)$,那么有$2^{-1}\equiv \frac{p+1}{2}\ (mod\ p)$也就是说2的逆元除了与2的p-2次幂相同以外，还和(p+1)>>1相同，由于p是素数，素数一定是奇数，那么(p+1)/2不可能是分数，所以2的模乘逆元就是(p+1)>>1，类似的有4对于7的模意义下的逆元等于2（(7+1)/4 = 2，前提是一定要可以被整除）

寄巧

并查集的路径压缩

如果题目对于父结点没有什么特殊的要求那么最好还是加上，因为这个真的可以被卡掉，比如这道题：
不加路径压缩会在第八个点tle，同样的规模第七个点就能很短时间内通过，加了之后就通过了

关于对拍的数据强度问题

有一些题目如果只是单纯的随机生成数据，那么大多数情况下很有可能得到的结果和标程相同，像类似于这道题：

你会得到一个长度为 $n$ 的数组 $a$ ，进行以下操作：

选择两个数 $l,r$ 满足 $1\le l< r\le n$ 并且 $a[l]=a[r]$ ，将 $a[l…r]$ 替换为 $a[l+1,l+2,…r,l]$ 。

你还会得到一个长度为 $n$ 的数组 $b$ ，判断 $a$ 能否通过若干次操作变成 $b$ 。

正解是两个指针i,j，i指向$a_1$,j指向,$b_1$如果相同就++i,++j，不相同但满足b[j] == a[i - 1]并且之前有出现过没有对上的数和b[j]相同，那么j指针继续往后移动。
一开始写了一个假做法，认为每次查询之前有没有对上的数时只需要开一个队列，合法的数只有在队列的头和尾端，这个做法在后面对拍的时候发现了hack数据：

1
2
3
4
5
1
7
6 7 4 6 7 6 5
4 7 7 6 6 6 5
standout:YES

当时对拍对了好久也没找出hack，因为如果单纯的生成大数据然后对拍，很有可能是都是no,就比如只有特定的排列才会输出yes，那么大多数情况下生成的数据都会是no，所以这道题的正确对拍思路是写尽量多的组数，每组的序列长度适当的小，这样才能保证最后的答案有机会是yes，这样写一定要注意数组下标会不会越界。
这道题一开始对拍时每次序列的长度都是在[1,200000]里面取，跑了500多组，都没发现错误…

大常数对执行速度的影响

或者说是被卡常，有些题目由于使用了非正解，并且复杂度并不是特别好需要题目数据配合才能通过。这个时候要特别注意常数的影响，比如这道P1972 [SDOI2009] HH的项链，10的6次方的数据规模其实常数小可以用莫队卡过去：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>

#define N 1000006
using namespace std;
namespace wr {}
using namespace wr;

struct Node {
    int l, r, p;
} q[N];
int pos[N], a[N], res[N], pre[N], suf[N], flag[N];
int ans;

void solve() {
    int n, m;
    read(n);
    int block = (int) sqrt(n);
    block += n % block;
    for (int i = 1; i <= n; ++i) {
        read(a[i]);
        pos[i] = (i - 1) / block + 1;
    }
    read(m);
    for (int i = 1; i <= m; ++i) {
        read(q[i].l), read(q[i].r);
        q[i].p = i;
    }
    //for(int i = 1;i<=m;++i) cout<<q[i].l<<' '<<q[i].r<<' '<<q[i].p<<endl;
    sort(q + 1, q + 1 + m, [&](Node A, Node B) {
        return pos[A.l] == pos[B.l] ? (pos[A.l] & 1 ? A.r > B.r : A.r < B.r) : pos[A.l] < pos[B.l];
    });
    //for(int i = 1;i<=m;++i) cout<<q[i].l<<' '<<q[i].r<<' '<<q[i].p<<endl;
    int l = 1, r = 0;
    for (int i = 1; i <= n; ++i) pre[i] = flag[a[i]], flag[a[i]] = i;
    memset(flag, 0x3f, sizeof flag);
    for (int i = n; i >= 1; --i) suf[i] = flag[a[i]], flag[a[i]] = i;
    for (int i = 1; i <= m; ++i) {
        while (l > q[i].l) ans += suf[--l] > r;
        while (r > q[i].r) ans -= pre[r--] < l;
        while (r < q[i].r) ans += pre[++r] < l;
        while (l < q[i].l) ans -= suf[l++] > r;
        res[q[i].p] = ans;
    }
    for (int i = 1; i <= m; ++i) write(res[i], '\n');
}

signed main() {
    //freopen("input.txt", "r", stdin);
    //freopen("my.txt", "w", stdout);
    solve();
    return 0;
}

但如果另外一种贪心策略来移动双指针就会因为大常数过不去
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<bits/stdc++.h>

#define N 1000006
using namespace std;
namespace wr {}
using namespace wr;

struct Node {
    int l, r, p;
} q[N];
int pos[N], a[N], res[N], pre[N], suf[N], flag[N], cnt[N];
int ans, test;

void add(int x) {
    ++cnt[a[x]], test += cnt[a[x]] == 1;
}

void del(int x) {
    --cnt[a[x]], test -= cnt[a[x]] == 0;
}

void solve() {
    int n, m;
    read(n);
    int block = (int) sqrt(n);
    block += n % block;
    for (int i = 1; i <= n; ++i) {
        read(a[i]);
        pos[i] = (i - 1) / block + 1;
    }
    read(m);
    for (int i = 1; i <= m; ++i) {
        read(q[i].l), read(q[i].r);
        q[i].p = i;
    }
    //for(int i = 1;i<=m;++i) cout<<q[i].l<<' '<<q[i].r<<' '<<q[i].p<<endl;
    sort(q + 1, q + 1 + m, [&](Node A, Node B) {
        return pos[A.l] == pos[B.l] ? (pos[A.l] & 1 ? A.r > B.r : A.r < B.r) : pos[A.l] < pos[B.l];
    });
    //for(int i = 1;i<=m;++i) cout<<q[i].l<<' '<<q[i].r<<' '<<q[i].p<<endl;
    int l = 1, r = 0;
    for (int i = 1; i <= n; ++i) pre[i] = flag[a[i]], flag[a[i]] = i;
    memset(flag, 0x3f, sizeof flag);
    for (int i = n; i >= 1; --i) suf[i] = flag[a[i]], flag[a[i]] = i;
    for (int i = 1; i <= m; ++i) {
        while (l > q[i].l) ans += suf[--l] > r, add(l);
        while (r > q[i].r) ans -= pre[r--] < l, add(r);
        while (r < q[i].r) ans += pre[++r] < l, del(l);
        while (l < q[i].l) ans -= suf[l++] > r, del(r);
        res[q[i].p] = ans;
    }
    for (int i = 1; i <= m; ++i) write(res[i], '\n');
}

signed main() {
    //freopen("input.txt", "r", stdin);
    //freopen("my.txt", "w", stdout);
    solve();
    return 0;
}

可以发现只是for循环里面的语句数量多了几句就会超时，测试下来大概慢了3-4倍，差不多每次执行的时候多了2、3句话，原先600ms的数据多了这几句话就很危险（时限2s），所以在能决定复杂度的语句块内能少写就尽量少写…

在一些对精度有要求（比如控制在1e-6）的题目中不要用默认的cout输出

如果要用cout可以加上精度的控制，因为cout默认大概意思是保留6位有效数字比如

1
2
3
4
double a = 123.12315078765432134;
cout<<a;
output：
123.123

会出现精度的丢失

在c/c++里，a%b的正负与a有关

long long 类型的数据参与除法运算或使用floor、ceil、log2等函数原型的参数类型是double的时候可能会引起精度丢失

double的精度只有15-16位，如果题目最大1E17，然后是大于1E16的输入会出问题，比如1e16+9转成double类型再转回来就会变成1e16+8。
如果题目要求对一个long long类型除以二向上或者向下取整，最稳的办法是使用位运算

1
2
3
4
// 向上取整
(n>>1)+n&1
// 向下取整
n>>1

同理log2等函数也是最好先预处理再计算，函数尽量少用不太安全

手动开栈

有的时候直接将一些变量声明在局部可以避免初始化的麻烦，但是有的时候会爆栈虽然交上去不会有影响但是本地测试的时候就很麻烦要改数组大小等，这时候就需要手动开栈。
一些常见的调整栈大小的方法：
使用 GCC 或 Clang（Unix/Linux/macOS）:
可以使用 -Wl,-stack_size,<size> 选项来调整栈大小。

1
gcc -Wl,-stack_size,1024000000 -o program program.c

使用 CMake（clion）:
在 CMake 中，可以通过 target_link_options 或者 add_link_options 来设置编译选项，以调整栈大小。
1
target_link_options(untitled1 PRIVATE "-Wl,--stack=1024000000")

注意linux下可能会失败因为系统可能对进程的栈大小作出限制。
redpanda:
工具 → 编译选项 → 编译器选项 → 在编译时加入
1
-Wl,--stack=SIZE 1024000000

1024000000 大概分了1000MB，一般都是足够用的