题意

$n$ 支队伍一共参加了三场比赛。
一支队伍 $x$ 认为自己比另一支队伍 $y$ 强当且仅当 $x$ 在至少一场比赛中比 $y$ 的排名高。
求有多少组 $(x,y)$，使得 $x$ 自己觉得比 $y$ 强，$y$ 自己也觉得比 $x$ 强，$(x, y)$, $(y, x)$算一组。

solution

题意

一共有 $n$ 只牛在花坛旁边，第 $i$ 头牛每分钟破坏 $d_i$ 朵花，把第i头牛带回牛棚需要 $2 \times ti$ 这么多时间，每次只能带回一头牛，请问怎样能使得被破坏的花最少。

solution

以小化大，先考虑两头牛，先领 $a$ ，损失为：$2\times{t_a}\times{d_b}$，先领 $b$，损失为 $2\times{t_b}\times{d_a}$，故得到排序条件 ${a_t \times {b_d} < b_t \times {a_d}}$，最后模拟得出答案。

题意

$n$ 种面额货币，数量无限，问最多保留几种，使得原来可以组成的仍然可以组成。（$t<=20,n<=100,a[i]<=25000$）

solution

由于大的只会被小的组成，所以先排序，对于存在性问题就显然是完全背包了，dp[i] 表示是否能表示出 $i$ 价值，得到状态转移方程：$dp[i]|=dp[i-a[i]]$，对于已经可以表示出来对 $a[i]$，已经可以由小的组成，因此不需要在枚举。

题意

$n$ 栋建筑，第 $i$ 栋建筑需要 $s_i$ 时间修，截止到 $t_i$ 时间，问最多可以修多少建筑。

solution

我们可以类比成写作业，先截止的我们会先做，这是大体的贪心策略。但他并不是最优的，因为可能那一科会花你非常多的时间，够你做更多的科目，得不偿失。因此我们用优先队列维护做过的作业中花费时间最大的那份，当目前要做的作业时间不够的时候，与这个最大值比较看是否花的时间更少，可行的话就把这个塞进去，那个丢出来，这样做了同样多的作业却花了更少的时间，同时维护答案。

题意

给定一个 $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的和。