题意

给定一个 $1-n$ 排列，求长度为奇数子串以 $b$ 为中位数的子串个数。

solution

由于求的是中位数，所以我们只需要关心这个数和 $b$ 的大小关系就好了，大于 $b$ 看作 1，小于 $b$ 看作 -1，等于 $b$ 看作 0，问题转化为求包含 0 且和为 0 的子串有多少个。

题意

一共有 $n$ 个数，第 $i$ 个数是 $x_i$ 可以取 $[l_i , r_i]$ 中任意的一个值。设 $S = \sum{ {x_i}^2}$，求 $S$ 种类数。（0 ~ n,l,r ~ 100）

Solution

$dp[i][j]$ 表示前 $i$ 个数能不能组成 $j$，可以得到转移方程：$dp[i][j]=dp[i-1][j-x^2]$，最后统计 $dp[n]$ 层组成的 $j$ 的数量即可。因为 dp 的值只有 0 和 1 ，因此使用 bitset 优化，把第二维看成二进制位，这样就可以用位移的形式来表示加法运算，得到转移方程：dp[i]=dp[i-1] << (j*j)，复杂度 $10^{10}/64$。

题意

无向图 $n$ 个点，每次必须跳两个，至少需要加多少条边可以遍历所有点。

solution

首先，如果图不联通，那么需要加联通分量 - 1 条边使图联通，然后发现一点，只要这个图存在奇数环，就一定能全部走完，不存在的话，随便加一条边生成奇数环即可。

题意

一共12道题，你有 $a_i$ 的概率做对第 $i$ 题，有 $b_i$ 的概率抄到左边的，有 $c_i$ 的概率抄到右边的，问做对 $0-12$ 题的概率是多少。

solution

做对的概率不太好求，可以反过来求做错的概率，即 $(1-a[i])\times(1-b[i])\times(1-c[i])$，然后 $dp[i][j]$ 表示前 $i$ 道题做对 $j$ 道的概率，设 $dp[0][0] =1$，得到状态转移方程：$dp[i][j]=dp[i-1][j-1]\times(ac=(1-wa))+dp[i-1][j]*wa$ 。

题意

有一颗二叉树，树的每一个节点都有一个值，设他的中序遍历为（l,2,3,…,n），其中数字1,2,3,…,n为节点编号。

任一棵子树subtree（也包含tree本身）的加分计算方法如下：

题意

给定 $i$ 和 $i+1$两点的距离和 $i$ 点的货物数量，$m$ 次询问将 $[l,r]$ 所有物品搬到 $x$ 点的总费用（区间内每个物品各自离 $x$ 点距离和）。（$n,m <= 200000 , 0 <= ai,bi <= 2000000000$）

soltuion

前缀和维护：$sum1$ 表示每个储物点离原点0的距离，$sum2$ 表示前 $i$ 个储物点共有多少货物，$sum3$ 表示前 $i$ 个储物点的所有物品到原点0的和。

题意

有 N 部电影，每部电影有不同的放映时常，和若干个放映起始时间。
Bessie 可以在一部电影播放过程中的任何时间进入或退出放映厅。每部电影她最多看1次且她不能在看一部电影的过程中，换到另一个正在播放相同电影的放映厅。

Bessie 能不能从0到L分钟连续不断地观看电影？如果能，计算她最少看几部电影。

题意：

桥长度为$L$ ，分布有$n$ 个石子，青蛙每次可以跳 $[S,T]$ 的距离,问青蛙过桥至少要踩多少个石子。

$(1<=S,T<=10,m<=100,a_i<=10^9, a_i 表示第i个石子的位置)$

solution

题意

给定n个城市坐标，每个城市可以多次到达，问一共到m次，最短花费。给出起始位置，并且起始位置不在城市上。

solution

不难猜到要么就是一条路走到黑要么就是在路上找的两个城市然后一直往返。因此我们从原来的位置，往左右两边一直走下去，顺便枚举路上每两座城市之间横跳的花费，维护最小花费，同时注意边界情况。

Big Three（拷贝构造，拷贝复制，析构）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class String 
{
  public:
    String (const char* cstr = 0);    // 构造函数，默认初值为0
    String (const String& str);       // 接受的值为类本身，因此为拷贝构造函数
    String& operator=(const String& str);  // = 号重载，拷贝赋值函数
    ~String();        // 析构函数，类死亡时自动调用
    char* get_c_str() const { return m_data; }

  private:
    char* m_data; 
}

int main()
{
  String s1();
  String s2("hello");

  String s3(s1);      // 拷贝构造，类还未存在
  cout << s3 << endl;
  s3 = s2;            // 拷贝赋值，类已经存在

  cout << s3 << endl;
}