标签：输出 GCC int optimize 运算符 pragma 杂项

位运算加速技巧

乘/除以 \(2^n\)，改为 << n 或 >> n
交换两个数，swap(a, b) 改为 a ^= b, b ^= a, a ^= b
小数转整数，(int)3.14 改为 3.14 >> 0
正负号转换，x = -x 改为 x = ~x + 1
当 \(x=2^n\) 时，% x 改为 & (x - 1)
检查是否整除 \(2\) 时，i % 2 改为 i & 1
求绝对值，abs(x) 改为 (x ^ (x >> 31)) - (x >> 31)
比较两数值是否同号，a * b > 0 改为 a ^ b > 0

运算符优先级

优先级从大到小排列：

单目运算符：包括但不限于 !、~、++、--
乘除模：*、/、%
加减：+、-
左右移：<<、>>
比较运算符：>、>=、<、<=、==、!=
按位运算符：&、^、|
逻辑运算符：&&、||
三目运算符：?:
赋值运算符：包括但不限于 =、+=、%=、<<=、&=

快读快写

inline int read() {
	int 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 << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	return x * f;
}

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

火车头

#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")

对拍

#include <bits/stdc++.h>
using namespace std;

int main() {
	while (true) {
		system("data.exe > data.in");
		system("手写.exe < data.in > mine.out");
		system("标程.exe < data.in > stdd.out");
		if (system("fc mine.out stdd.out")) {
			system("pause");
			return 0;
		}
	}
}

2024/7/11 upd.

我们不管是使用 mt19937 还是 rand()，我们的随机种子使用 time(0) 的话，由于它是以秒为单位的，所以一秒之内生成的随机数据是一样的，会影响我们对拍的效率。使用以下的随机数种子可以生成毫秒级别的随机数。
struct _timeb T;
_ftime(&T);
mt19937 wdz(T.millitm);
这样的话，我们就可以做到在一秒之内运行 wdz() 依然能生成不同的随机数。

但是，该函数不能在 Linux 下运行。所以如果你在比赛的时候把它用到正式代码里面导致 CE 0pts，不要怪我。——2024/7/27 upd.

2024/7/30 upd.

遗憾地，我们不能在 Linux 环境下使用毫秒级别随机数。但这是否意味着 Linux 下不能随机化乱搞呢？当然不是的。

我们有了一个更好的随机数函数：random_device。它的用法更为简单：
random_device wdz;
此时调用 wdz() 就可以生成真随机数了。但注意，这个函数需要用到一个叫做熵池的高级东西，所以它在 Windows 下生成的随机数效果和不开 srand(time(0)) 的 rand() 是一样的。不过经过测试，它在 Linux 下确能生成真随机数。

位运算

快速幂模板

求 \(a^b\bmod{p}\)，其中 \(1\le a,b,p\le 10^9\)。

代码前加入 #define int long long

inline int power(int a, int b, int p) {
	int res = 1;
	while (b != 0) {
		if (b & 1) res = res * a % p;
		a = a * a % p;
		b >>= 1;
	}
	return res % p;
}

时间复杂度 \(O(\log{b})\)。

快速乘模板

求 \(a\times b\bmod{p}\)，其中 \(1\le a,b,p\le 10^{18}\)。

inline int mul(int a, int b, int p) {
	int res = 0;
	while (b != 0) {
		if (b & 1) res = (res + a) % p;
		a = (a << 1) % p;
	}
	return res % p;
}

时间复杂度 \(O(\log{b})\)。

二分

在单调递增序列 \(\boldsymbol a\) 中查找 \(\boldsymbol x\) 或 \(\boldsymbol x\) 的后继

while (l < r) {
	int mid = (l + r) >> 1;
	if (a[mid] >= x) r = mid;
	else l = mid + 1;
}
return a[l];

在单调递增序列 \(\boldsymbol a\) 中查找 \(\boldsymbol x\) 或 \(\boldsymbol x\) 的前驱

while (l < r) {
	int mid = (l + r + 1) >> 1;
	if (a[mid] <= x) l = mid;
	else r = mid - 1;
}
return a[l];

Hack

卡 unordered_map：GCC 6 以前频繁插入 \(126271\)，GCC 7 以后频繁插入 \(107897\)。
卡 pb_ds：频繁插入 \(2^{16}\) 的倍数。

防止被卡：见 CF 大神的两篇文章。

https://codeforces.com/blog/entry/62393

https://codeforces.com/blog/entry/60737

C++ 输出变量类型

我们可以用 typeid 关键字查看变量类型，用法：

int a = 0;
cout << typeid(a).name() << '\n';

输出：

类似地，bool 类型输出 b，long long 类型输出 x，char 类型输出 c，string 类型输出 Ss。对于任何类型的数组，都会输出 A + 你的数组大小 + _ + 上述类型的值，例如 int a[100005] 会输出 A100005_i。

然而，在输出 STL 相关类型时，typeid 会输出乱码。例如，vector<int> a 输出了 St6vectorIiSaIiEE。此时需要用以下方式将其输出解密：

#include <cxxapi.h> // 不包含在万能头中
...
auto tp = typeid(a).name(); // a 是你要输出的变量名
int tmp; // tmp 没什么用，只是函数参数需要
auto realname = abi::__cxa_demangle(tp, 0, 0, tmp); // realname 实际上是 char * 类型
cout << realname << '\n';

此时若给一个 vector<int> a，程序会输出 std::vector<int, std::allocator<int> >。这就是人能看懂的形式了。其他的 STL 也类似。

标签：输出,GCC,int,optimize,运算符,pragma,杂项
From： https://www.cnblogs.com/laoshan-plus/p/18365118

杂项