闲着没事研究一下 cf 大神 Neal 提交时使用的模版

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <cstdint>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <vector>
 
using namespace std;
template <class Fun>
class y_combinator_result
{
    Fun fun_;
 
public:
    template <class T>
    explicit y_combinator_result(T &&fun) : fun_(std::forward<T>(fun)) {}
 
    template <class... Args>
    decltype(auto) operator()(Args &&...args)
    {
        return fun_(std::ref(*this), std::forward<Args>(args)...);
    }
};
 
template <class Fun>
decltype(auto) y_combinator(Fun &&fun)
{
    return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}
 
template <typename A, typename B>
ostream &operator<<(ostream &os, const pair<A, B> &p)
{
    return os << '(' << p.first << ", " << p.second << ')';
}
 
template <typename T_container,
          typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type>
ostream &operator<<(ostream &os, const T_container &container)
{
    os << '{';
    string sep;
    for (const T &x : container)
        os << sep << x, sep = ", ";
    return os << '}';
}
 
void dbg_out()
{
    cerr << endl;
}
 
template <typename Head, typename... Tail>
void dbg_out(Head H, Tail... T)
{
    cerr << ' ' << H;
    dbg_out(T...);
}
 
#ifdef NEAL_DEBUG
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif
 
void run_case()
{
    //这里编写主代码块
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int tests;
    cin >> tests;
 
    while (tests-- > 0)
    {
        run_case();
    }
 
    return 0;
}
//手搓可能有部分与Neal写的有出入，大意一致

				

					
				
				

					
				
				

					
				
				

					
				
			

逐部分解析一下

算法常用头文件和使用命名空间，这里不用多说

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <cstdint>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <vector>
 
using namespace std;

				

					
				
				

					
				
				

					
				
				

					
				
			

算法常用头文件和使用命名空间，这里不用多说

y_combinator_result 类模板

template <class Fun>
class y_combinator_result
{
    Fun fun_;
 
public:
    template <class T>
    explicit y_combinator_result(T &&fun) : fun_(std::forward<T>(fun)) {}
 
    template <class... Args>
    decltype(auto) operator()(Args &&...args)
    {
        return fun_(std::ref(*this), std::forward<Args>(args)...);
    }
};

				

					
				
				

					
				
				

					
				
				

					
				
			

这个类模板实现了一个递归函数的固定点组合子（Y 组合子），用于实现递归匿名函数。

• 成员变量：fun_ 保存传入的函数对象。
• 构造函数：构造函数接受一个函数对象并进行完美转发（使用 std::forward），将其保存到 fun_ 中。
• operator() 运算符：该运算符重载接受任意参数，将自身的引用（std::ref(*this)）和参数一起传递给保存的函数对象 fun_，实现递归调用。

y_combinator 函数模板

template <class Fun>
decltype(auto) y_combinator(Fun &&fun)
{
    return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

				

					
				
				

					
				
				

					
				
				

					
				
			

这个函数模板用于创建 y_combinator_result 类的实例。

• decltype(auto)：自动推导返回类型。
• 函数参数：接受一个函数对象并进行完美转发。
• 返回值：返回一个 y_combinator_result 对象，保存传入的函数对象。

pair 类型的输出运算符重载

template <typename A, typename B>
ostream &operator<<(ostream &os, const pair<A, B> &p)
{
    return os << '(' << p.first << ", " << p.second << ')';
}

				

					
				
				

					
				
				

					
				
				

					
				
			

重载了 pair 类型的输出运算符，使得 pair 类型可以通过 ostream 进行输出。

• 参数：一个输出流对象 os 和一个 pair 对象 p。
• 返回值：将 pair 的两个成员 first 和 second 以 (first, second) 的形式输出到 os。

容器类型的输出运算符重载

template <typename T_container,
          typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type>
ostream &operator<<(ostream &os, const T_container &container)
{
    os << '{';
    string sep;
    for (const T &x : container)
        os << sep << x, sep = ", ";
    return os << '}';
}

				

					
				
				

					
				
				

					
				
				

					
				
			

重载了非 string 类型容器的输出运算符，使得容器类型可以通过 ostream 进行输出。

• 模板参数：
• T_container：容器类型。
• T：容器中的元素类型，通过 enable_if 确保 T_container 不是 string 类型。
• 参数：一个输出流对象 os 和一个容器对象 container。
• 返回值：将容器的元素以 {elem1, elem2, ...} 的形式输出到 os。

调试输出函数

void dbg_out()
{
    cerr << endl;
}
 
template <typename Head, typename... Tail>
void dbg_out(Head H, Tail... T)
{
    cerr << ' ' << H;
    dbg_out(T...);
}

				

					
				
				

					
				
				

					
				
				

					
				
			

这些函数用于调试输出。

• dbg_out()：无参数版本，输出换行符。
• dbg_out(Head H, Tail... T)：可变参数版本，将第一个参数输出到标准错误流，然后递归调用自身输出剩余参数。

调试宏

#ifdef NEAL_DEBUG
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

				

					
				
				

					
				
				

					
				
				

					
				
			

定义了一个调试宏 dbg，用于条件性地输出调试信息。

• #ifdef NEAL_DEBUG：如果定义了 NEAL_DEBUG，则启用调试输出。
• dbg(...)：将参数名及其值输出到标准错误流。

这个宏在调试模式下会输出参数的名字及其值，而在非调试模式下不会产生任何输出。

main 函数部分

ios::sync_with_stdio(false) 和 cin.tie(nullptr) 是用于优化 C++ 输入输出性能的两个常见语句。它们主要用来加快标准输入输出流的速度。下面是对这两行代码的解释：

ios::sync_with_stdio(false)

这行代码用于解除 C++ 标准流与 C 标准流（如 stdio）之间的同步。这种同步默认是开启的，以确保混合使用 C 和 C++ 输入输出时能够正确工作。但是，这种同步会带来性能损失。在不需要混合使用 C 和 C++ 输入输出的情况下，可以通过设置 ios::sync_with_stdio(false) 来提高输入输出的效率。

cin.tie(nullptr)

这行代码用于解除 cin 与 cout 之间的绑定。默认情况下，cin 是绑定到 cout 的，这意味着每次调用 cin 之前都会自动刷新 cout，以确保所有输出在进行输入操作之前被打印出来。这种机制有助于调试和交互式程序，但在某些情况下会影响性能。通过调用 cin.tie(nullptr)，可以解除这种绑定，从而提高性能。

• 适用场景：这种优化非常适用于竞赛编程或其他需要高效处理大量输入输出的场景。

如果你不需要同时使用 C 的 printf/scanf 和 C++ 的 cout/cin，或者不需要在输入前确保所有输出被刷新，那么这些设置通常是安全且有效的。