1、解决爆栈，手动加栈

用C++时，可以用这句代码进行手动加栈。（#pragma comment(linker, “/STACK:1024000000,1024000000”)）

而C时，我们则要用另外一句代码：#pragma GCC optimize (“O2”)
02表示一种状态，还有其他的状态
GCC的#pragma优化主要分为四种 -O0 -O1 -O2 -O3
-O0 表示无优化状态
-O1 表示对代码进行了优化
-O2 表示减小目标文件大小
-O3 表示减小代码段及栈空间的大小

对部分代码可以去除优化：

#pragma GCC push_options

#pragma GCC optimize (“O0”)

或者也可以增加优化

#pragma GCC pop_options

想要对代码进行进一步的优化，可以使用输入加速外挂，对C、C++均可行。

栈溢出

常常会遇到在main函数里最大开个10的5次方的数组，如果要开10的6次方及以上则就在全局变量分配数组。有个解决方法就是数组使用static关键字修饰。

static int arr[1000005] // 完美运行

全局变量在静态存储区分配内存，局部变量是在栈上分配内存空间的，这么大的数组放到栈上不溢出吗？
VC堆栈默认是1M，int a[1000000]的大小是4*1000000，将近4M，远远大于1M，编译连接的时候不会有问题，但运行是堆栈溢出，程序异常终止。
如果你真的需要在堆栈上使用这么大的数组，那么可以在工程选项链接属性里设置合适的堆栈大小。

注意：如果分配多个数组也会导致内存分配超限。

2、结构体利用初始化列表赋默认值

1
2
3
4
5
struct node {
    int x, y;
    node() : x(0), y(0) {}
    node(int s, int e) : x(s), y(e) {}
};

3、split函数

1
2
3
4
5
6
7
8
9
10
11
12
void SplitString(const string& s, vector<string>& v, const string& c)
{
    string::size_type pos1, pos2;
    pos2 = s.find(c);
    pos1 = 0;
    while (string::npos != pos2) {
        v.push_back(s.substr(pos1, pos2 - pos1));
        pos1 = pos2 + c.size();
        pos2 = s.find(c, pos1);
    }
    if (pos1 != s.length()) v.push_back(s.substr(pos1));
}

4、输入数字但是没有告诉输入的个数

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
inline void SplitStr(string& s, vector<int>& v, const string& c)
{
    string title;
    transform(s.begin(), s.end(), back_inserter(title), ::tolower);  // 转换为小写字母
    s = "";
    for (int i = 0; i < title.size(); i++) {
        if ((title[i] >= '0' && title[i] <= '9') || title[i] == ' ') {
            s += title[i];
        }
    }
    string::size_type pos1, pos2;
    pos2 = s.find(c);
    pos1 = 0;
    while (string::npos != pos2) {
        string str = s.substr(pos1, pos2 - pos1);
        int tmp = 0;
        for (int i = 0; i < str.size(); i++) tmp = tmp * 10 + str[i] - '0';
        v.push_back(tmp);

        pos1 = pos2 + c.size();
        pos2 = s.find(c, pos1);
    }
    if (pos1 != s.length()) {
        string str = s.substr(pos1);
        int tmp = 0;
        for (int i = 0; i < str.size(); i++) tmp = tmp * 10 + str[i] - '0';
        v.push_back(tmp);
    }
    return;
}

5、输出行末无空格

1
2
3
4
for (int i = 0; i < n; i++) 
{
    printf("%d%c", i, i == n - 1 ? '\n' : ' ');
}

6、输入加速外挂

cin和cout在大量使用的时候往往会超时，改用scanf和printf。

6-1、非负整数

1
2
3
4
5
void read(int &x){
    char ch = getchar();x = 0;
    for (; ch < '0' || ch > '9'; ch = getchar());
    for (; ch >='0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
}

6-2、什么是输入挂

scanf的输入速度不cin快得多，那么有没有比scanf更快的东西呢？这就是要用到输入挂了。

6-3、什么时候使用输入挂

当输入规模达到1x10^6次方的时候，就需要输入挂，否则很可能会超时。

6-4、代码实现

(一)整数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
inline bool scan_d(int &num)  
{
    char in;bool IsN=false;
    in=getchar();
    if(in==EOF) return false;
    while(in!='-'&&(in<'0'||in>'9')) in=getchar();
    if(in=='-'){ IsN=true;num=0;}
    else num=in-'0';
    while(in=getchar(),in>='0'&&in<='9'){
        num*=10,num+=in-'0';
    }
    if(IsN) num=-num;
    return true;
}

(二)浮点数

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
inline bool scan_lf(double &num)  
{
        char in;double Dec=0.1;
        bool IsN=false,IsD=false;
        in=getchar();
        if(in==EOF) return false;
        while(in!='-'&&in!='.'&&(in<'0'||in>'9'))
                in=getchar();
        if(in=='-'){IsN=true;num=0;}
        else if(in=='.'){IsD=true;num=0;}
        else num=in-'0';
        if(!IsD){
                while(in=getchar(),in>='0'&&in<='9'){
                        num*=10;num+=in-'0';}
        }
        if(in!='.'){
                if(IsN) num=-num;
                return true;
        }else{
                while(in=getchar(),in>='0'&&in<='9'){
                        num+=Dec*(in-'0');Dec*=0.1;
                }
        }
        if(IsN) num=-num;
        return true;
}

(三)加入一行代码

ios::sync_with_stdio(false); //false即0
cin.tie(0);
加到代码前面，可使cin cout与stdio的关联取消。
cin，cout之所以效率低，是因为先把要输出的东西存入缓冲区，再输出，导致效率降低，而这段语句可以来打消iostream的输入 输出缓存，可以节省许多时间，使效率与scanf与printf相差无几，还有应注意的是scanf与printf使用的头文件应是stdio.h而不是 iostream。

tie是将两个stream绑定的函数，空参数的话返回当前的输出流指针。

*std::cin.tie() << “This is inserted into cout\n”; // 空参数调用返回默认的output stream，也就是cout。

sync_with_stdio这个函数是一个“是否兼容stdio”的开关，C++为了兼容C，保证程序在使用了std::printf和std::cout的时候不发生混乱，将输出流绑到了一起。

(四)strtok和sscanf结合输入

1
2
3
4
5
6
7
8
9
10
11
12
/*
 *  空格作为分隔输入,读取一行的整数
 */
gets(buf);

int v;
char *p = strtok(but, " "); 
while (p)
{
    sscanf(p, "%d", &v);
    p = strtok(NULL," "); 
}

7、输出保留两位小数

1
2
#include <iomanip>
cout << fixed << setprecision(2) << ans << endl;

8、C++输出cout（bool类型）

通常，cout在显示布尔值之前将它转化为int，但使用 cout.setf(ios_base::boolalpha)可以设置一个标记，使cout显示true/ false。

1
cout << boolalpha << flag << endl;

9、unorder_map无法使用pair做键

map使用红黑树

10、hash表的实现方式

对于坐标点对(x,y)进行hash：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int vis[maxn][maxn];  
memset(vis, 0, sizeof(vis));    // 32位系统在栈中不能超过10^6的连续空间

int *vis[maxn] = new int[maxn];  // 用指针则可以分配堆中内存，则需要释放，也相当于是全局变量

vector<vector<int> > vis(maxv, vector<int>(maxv, 0));  // 这个也是连续空间

map<pair<int, int>, bool> vis;    // default false, unorder_map no pair重点注意

unordered_map<LL, int> HASH;     // 巧妙

for (int i = 0; i < N; i++) {
	cin >> X[i] >> Y[i];
        vis[make_pair(X[i], Y[i])] = true;
        HASH[X[i] * maxv + Y[i]] = 1;   // 这种方式就非常巧妙了，将序列对组成一个整数
    }

11、数组的多种表示方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 二维数组
int **arr = new int*[maxn];
for (int i = 0; i < maxv; i++) arr[i] = new int[maxn];   // 注意一定要再次分配空间

int arr[maxn][maxn];
memset(arr, 0, sizeof(arr));

vector<vector<int> > arr(maxn, vector<int>(maxn, 0));  // 赋初值

int maxn = 1005;
int **arr = new int*[maxn];
for (int i = 0; i < maxn; i++) arr[i] = new int[maxn];   // 注意一定要再次分配空间
arr[5][5] = 23;
memset(arr, 0, sizeof(arr));    // 使用指针这样赋值无效
cout << arr[5][5] << endl;

12、常见的ACM输入类型题

  • （1）不指定输入个数
    使用gets或者getline函数

  • （2）多行输入或者单行输入

  • （3）有空格行输入
  • （4）大量输入（黑科技）

13、大佬的一些骚操作

输入字符串偶尔会+1

1
2
3
4
5
6
7
8
char s[1005];
scanf("%s", s + 1);
int len = strlen(s + 1);

这是方便后面使用1访问第一位字符，汗。。。。
for (int i = 1; i <= len; i++) {
	cout << s[i];
}

判断的时候使用具体数值在前面

if (5 == i) break;

1
2
3
4
int N;
char A, B;
scanf("%d ", &N);  // 注意这里要有空格
scanf("%c%c", &A, &B);

14、关于ACM评测机的运行时间

B. 清点星辰
第B题解说时间复杂度控制在1E8，单侧点时间是2秒，难道1E8才是真正的1秒？？？
反正我一直把1E7当作是一秒。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
#define LL long long
using namespace std;

int main()
{
    LL sum = 0;
    for (int i = 0; i < 1e9; i++) sum += i;
    cout << sum << endl;
    return 0;
}

这样也看不出来，不过还是当作1E7去看待应该是不错的，毕竟做过那么多题，还是能看出一二点。
499999999500000000

Process returned 0 (0x0)   execution time : 2.904 s
Press any key to continue.

卡常数

程序被卡常数，一般指程序虽然渐进复杂度可以接受，但是由于实现/算法本身的时间常数因子较大，使得无法在OI/ICPC等算法竞赛规定的时限内运行结束。
常数被称为计算机算法竞赛之中最神奇的一类数字，主要特点集中于令人捉摸不透，有时候会让水平很高的选手迷之超时或者超空间。
普遍认为卡常数是埃及人Qa’a及后人发现的常数。也可认为是卡普雷卡尔(Kaprekar)常数的别称。主要用于求解括号序列问题。
解决卡常数的方法比较多样化，主要为重复交题，拼人品让测评机快一点。很多信息学竞赛的专家也在研究如何解决这一问题，所以类似ZKW线段树等可以有效减少常数的时间占用的方法也在不断被发现，今后还有很大的探索空间。

OI中卡常数技巧
ACM卡常数（各种玄学优化）

渐进时间复杂度

渐进时间复杂度是指对于一个算法来说，我们常常需要计算其复杂度来决定我们是否选择使用该算法。
对于一个算法，假设其问题的输入大小为n，那么我们可以用 O(n) 来表示其算法复杂度(time complexity)。那么，渐进时间复杂度（asymptotic time complexity）就是当n趋于无穷大的时候，O（n）得到的极限值。
可以理解为：我们通过计算得出一个算法的运行时间 T(n), 与T(n)同数量级的即幂次最高的O(F(n))即为这个算法的时间复杂度。例如：某算法的运行时间T(n) = n+10与n是同阶的（同数量级的），所以称T(n)=O(n)为该算法的时间复杂度。
算法的渐进分析就是要估计：n逐步增大时资源开销T(n)的增长趋势。

其实就是一般我们说一个算法的时间复杂度就是渐进时间复杂度，取得是无穷大时候的时间。

15、关于使cin/cout的时间跟scanf/printf一样

http://www.dooccn.com/cpp/
https://blog.csdn.net/yujuan_mao/article/details/8119529

1
2
3
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

在hihoCoder上只加这一句是能正常运行的。ios::sync_with_stdio(false);

1
2
3
4
5
6
7
8
9
10
11
12
struct Time {
    int year, month, day, hour, minute, second;
    void read() {
        scanf("%d-%d-%d %d:%d:%d", &year, &month, &day, &hour, &minute, &second);
    }
}st, se;

int main()
{
    st.read(), se.read();
    return 0;
}

00、其他

system(“pause”)语句执行系统环境中的pause命令，冻结屏幕，用户按任意键结束。