泛谈OI中的那些卡常（测试版）

team109 · 2020-03-26 11:55:23 · 个人记录

由于我的电脑不能代表所有电脑的表现（比如我的电脑cin比fread快）,所以部分内容需要大家帮忙验证。

同步在知乎。链接
知乎的TeX不好，而且没有Markdown，样式会略有区别。

我是定位ZJ的一名退役OIer，由于卡常而臭名昭著。下面分享一些技巧。主要为时间卡常。

本文共计[咕咕]字，阅读约需[咕咕]分钟。（由于还没完工所以不统计字数）

本文有些优化在开O2后还不如正常做法，会打上\color{red}\xcancel\colorbox{orange}{\color{white}{\textsf{O2}}}标志。
有些优化在不同机器下效果不同，可能还不如正常方法，会打上\colorbox{#eecc55}{\color{white}\text{谨慎}}标志。
有些优化我自己都没实现过，会打上\color{grey}{\boxed{\text{野心}}}标志。
有些优化兼容性不好，可能CE或有别的问题，会指出。
有些内容会大大降低代码可读性，请在保证答案正确后再深度优化。

因为我在役时也只有提高水平，可能有一些错误，而且不会那些高深的卡常，请大佬（或自称蒟蒻）指正。如果在某些机子上运行出问题或速度还不如正常方法或效率不稳定或可能被卡或不适用于特定场合或有任何其他的问题，请告知我。我目前初三，可能更新、处理反馈都很慢。

我太蒻了。部分较高深内容引自@huanghaox1212 的博客中的一些文章以及其他一些来源，会标注出。

转载请注明出处。(注为本文或知乎链接均可)并请勿用于商业用途。

1.压行

1.1 短路运算符和三目运算符

1.2 利用返回值

1.3 逗号表达式

1.4 还没取好名字

2.内存与缓存

3.位运算

4.inline，register及其他

5.利用中间变量

6.其他

7.应用实例——I/O优化

我只会用getchar/putchar。用fread请移步前面那位大佬的博客。streambuf请看这篇洛谷日报。更高深的mmap请自行找资源。

7.1 整数

7.1.0 关于cin的两个优化

(待更

7.1.1 read（这部分内容目前仅在自家机器(少部分还有洛咕IDE)上试过。请各位走过路过帮忙验证一下可靠性与效率）

先给出标配版，最兼容的版本，在任何时候不会炸。

inline int read()
{
    register char ch=getchar();
    register int x=0;
    register bool b=0;
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    (ch=='-')&&(ch=getchar(),b=1);
    while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=getchar();
    if(b)return -x;
    return x;
}

以下网络流传版本已被初步鉴定为负优化，不管是否O2

• 看到有人说isalpha比ch>='0'&&ch<='9'快。经测试发现并没有。
• 将if(b)return -x;变为b&&(x=-x);
• 将(ch=='-')&&(ch=getchar(),b=1);变成(ch=='-')&&(b=1,ch=getchar());或(b=ch=='-')&&(ch=getchar());。事实上，在(INT_MIN,INT_MAX)区间内随机数测试后，发现这个改动对效率影响不小。
• x=(x<<1)+(x<<3)+ch-48或x=x+(x<<2)<<1+ch-48。

以下是可行的优化，但未经充分验证

• x=x*10+(ch^48)
• (待更

但我们还不够。常数优化的一个关键词就是用牺牲兼容性来换取对特定情境中的高效。
于是就有了这些东西： （待续

7.1.2 print

待更

7.2 字符串