编译时期计算数组

cpp

#include <iostream>
#include <array>
using namespace std;

constexpr int N = 1000000;
constexpr int f(int x) { return x*2; }

typedef array<int, N> A;

template<int... i> constexpr A fs() { return A{{ f(i)... }}; }

template<int...> struct S;

template<int... i> struct S<0,i...>
{ static constexpr A gs() { return fs<0,i...>(); } };

template<int i, int... j> struct S<i,j...>
{ static constexpr A gs() { return S<i-1,i,j...>::gs(); } };

constexpr auto X = S<N-1>::gs();

int main()
{
        cout << X[3] << endl;
}

在编译时期计算一个数组里面的元素,这种方法在\(N\)较大的时候会出现constexpr递归深度较大的问题。这种线性的求法似乎不能很好的处理当\(N\)较大的情况。所以这时候可以通过二分所求的\(N\)来解决这个问题。这样最大的递归深度就从\(N\)变成了\(logN\)了。 排名第一的回答中代码是这样写的:

2015多校Contest 5. 1003. Hotaru's problem

一个N-sequence由三个部分组成,并符合:

  1. 第一部分和第三部分相同。
  2. 第一部分和第二部分回文。

求最长的N-sequence的长度。

N-sequence的特征是第一部分和第三部分相同,并且第一部分和第二部分回文。那么条件可以转化成:第一部分第二部分 回文,并且第二部分第三部分 回文。那么问题就转化成了:两个回文串的重合问题。

Operator new 的重载

new作为关键字是不能被重载的。当new作为关键字的时候的行为是:

  1. 调用operator new分配内存。
  2. 调用构造函数生成对象。
  3. 返回相应的指针。

new的行为是不能被改变的,但是这里的operator new的行为是可以改变的。也就是对operator new的重载。

UVALive 5848. Soju

1 题目大意

给定两个平面上的点集,求两个点集中距离最近的两个点的距离。(这里的距离说的是曼哈顿距离。)题目中保证了左边点集的点都一定在右侧的点集的左侧。也就是任意一个在左侧集合的点的横坐标都小于任意一个在右侧集合的点。

主席树

主席树我的理解是可持久化线段树的一种应用吧。本质上就是可持久化线段树,不过我们在查询的时候用到了他们之间可以相减的性质。

首先介绍一下可持久化线段树。