Cristime 的小站

零、序言

随着时代的发展，CCF 终于摒弃了使用多年的 Noi Linux v1，转而使用基于 Ubuntu 20.04 LTS 的 Noi Linux v2。其中的 C++ 编译器由 g++ 4.8.4 更新为 g++ 9.3.0，其默认语言标准也由 C++98 转为 C++14，这意味着 C++11 以上的优良新特性可以在竞赛时使用，大大方便了我们代码的编写。

然而，很多老师仍然推荐使用老旧的 Dev-C++ 编写竞赛代码。Dev-C++ 作为算法竞赛编辑器，其最大优势便是支持单文件编译及便捷调试。但其自带的 C++ 编译器仍使用 gcc 4.9.2，仅支持 C++11 特性并且仅部分支持 C++14 标准；其代码编辑界面也简陋至极，一些新字体竟然不支持 Ligature（如 JetBrains Mono，Fira Code 等）；作为一款 IDE，其代码补全功能仅为半残且经常出现 bug。可见 Dev-C++ 已经完全落后于时代 （ps，国人重新开发的 小熊猫 Dev-C++ 是一个高效的算法竞赛 IDE，可以尝试）

一、引入

先举一个小栗子。

一数组有 $n$ 个元素，有 $m$ 次询问（$n, m <= 10^5$）。对于每次询问给出 $l, r$，求出 $[l, r]$的区间和。

有的同学说，这很简单啊！直接前缀和不就行了吗？确实如此，示例代码如下：

int n, m; cin >> n >> m;
vector< int > sum( n + 10 );
fill( sum.begin(), sum.end(), 0 );
for ( int i = 1, x; i <= n; ++i ) {
    cin >> x;
    sum[ i ] = sum[ i - 1 ] + x;
}
while ( m-- ) {
    int l, r; cin >> l >> r;
    l = min( l, r ); r = max( l, r );
    cout << sum[ r ] - sum[ l - 1 ] << endl;
}

本人为 AH 蒟蒻一枚，直接上游记

Day -1

白天喝了咖啡睡不着，晚上十二点爬起来打了个高精板子（我还是太弱了qwq

Day 0

上了一天课，中午和下午放学被班主任喊去辅导她女儿，教她怎么装虚拟机、用 NOI Linux（我真是无语了，第二天就比赛了，到现在连比赛环境都不熟悉）浪费了我宝贵的睡觉时间。

放学后晚上坐高铁到了 WH，随便水几道模板吧。

一、起因

下午，我打开 noi 官网准备报名 csp j/s，一看官网展板：“noi linux 2.0 发布” 我就兴奋了起来。（9 月 1 日起开始使用，
也就意味着 csp j/s 使用 noi linux 2.0）

一、深度优先搜索是什么

在一个求解问题答案的过程中，有几种求解的方法。最为暴力的就是枚举法。枚举法枚举每一个答案即会产生一个状态，这些状态就会构成一棵解答树。当然，对于大多数题目而言，这些状态大多是无用的，这也就决定了枚举法的低效。

那么，难道就没有方法进行优化了吗？

答案是有的。因为枚举法产生了太多无用状态，所以我们就应该从解答树中去除这些无用的状态。这种方法被称作剪枝。搜索就是剪枝的一种方法。