传送门 题意: 有一个n行m列的整数矩阵，其中1到 n∗m  n ∗ m 之间的每个整数恰好出现一次。如果一个格子比所有相邻格子（相邻是指有公共边或公共顶点）都小，我们说这个格子是局部极小值。给出所有局部极小值的位置，判断有多少个可能的矩阵。   (1≤n≤4,1≤m≤7)  ( 1 ≤ n ≤ 4 , 1 ≤ m ≤ 7 )  Solution: 显然我们把矩阵所有的状态存下来是不行的，所以说我们考虑减少我们需要存储的状态：我们的局部极小值最多只会有8个 那么我们也可以对这8个极小值进行状压 考虑将值从小到大填： f[i][S]  f [ i ] [ S ] 表示有S状态的局部极小值已经被填...

传送门 题意： 给出n，求出 { 1,...,n}  { 1 , . . . , n } 的所有满足以 下条件的子集数量：若 x 在该子集中，则 2x 和 3x 不能在该子集中。   n≤100000  n ≤ 100000  Solution: 没见过类似做法的人见到这道题真的是毫无思路啊… 构造矩阵形如  ⎛⎝⎜⎜⎜⎜⎜⎜1248...361224...9183672...2754108216..................⎞⎠⎟⎟⎟⎟⎟⎟  ( 1 3 9 27 . . . 2 6 18 54 . . . 4 12 36 108 . . . 8 24 72 216 . . . . ....

传送门 题意： 有一个长度为 n 的 01 串，你可以每次将相邻的 k 个字符合并，得到一个新的字符并获得一定分数。得到的新字符和分数由这 k 个字符确定。你需要求出你能获得的最大分数。  1≤n≤300,0≤ci≤1,1≤wi≤109,k≤8  1 ≤ n ≤ 300 , 0 ≤ c i ≤ 1 , 1 ≤ w i ≤ 10 9 , k ≤ 8  Solution: 姑且算是一个套路吧…  f[i][j][S]  f [ i ] [ j ] [ S ] 表示把区间 [i,j]  [ i , j ] 合并成S的状态所能得到的最大分数 可以发现我们将所有合并操作展开后不会有操作字符相交的情况出现...

传送门 题意： 给定一个 R∗C  R ∗ C 的01 矩阵，要求计算出这个 01 矩阵中有多少个双十字。 双十字由两条水平的和一条竖直的“1”线段组成，要求满足以下几个限制： 1.两条水平的线段不能在相邻的两行。 2.竖直线段上端必须严格高于两条水平线段，下端必须严格低于两条水平线段。 3.竖直线段必须将两条水平线段严格划分成相等的两半。 4.上方的水平线段必须严格短于下方的水平线段。 输出双十字的个数 mod 1,000,000,009 的值。  R,C,N≤10000,R∗C≤1000000  R , C , N ≤ 10000 , R ∗ C ≤ 1000000  Solution： ...

传送门 题意： n种生物，每种生物i有k个属性 ai,j  a i , j ，两种生物之间的友好程度为  Friendliness=(∑k−1i=1Ci∗di)−CK∗dK  F r i e n d l i n e s s = ( ∑ i = 1 k − 1 C i ∗ d i ) − C K ∗ d K  其中  Ci  C i 是非负常数，  di  d i 是属性 i 的差别。求出关系最友好的那对生物是哪一对以及它们之间的友好程度是多少？  2≤N≤100000,2≤K≤5,0≤Ci≤100  2 ≤ N ≤ 100000 , 2 ≤ K ≤ 5 , 0 ≤ C i ≤ 100  Sol...

传送门 题意： 一棵含有n个叶子节点的二叉树通过如下方式生成： 每次等概率的随机选择一个叶子节点，将这个节点加上左右两个子节点 求： 1.叶子节点平均深度的期望 2.树深度的期望  n≤100  n ≤ 100  Solution: 第一问很好处理：设 fx  f x 表示有x个叶子节点的树的叶子节点平均深度 我们考虑在一个有x-1个叶子节点的树里随机选择一个叶子节点展开，那么树的叶子节点深度总和会增加 fx−1+2  f x − 1 + 2  所以 fx=fx−1∗(x−1)+fx−1+2x=fx−1+2x  f x = f x − 1 ∗ ( x − 1 ) + f x − 1 + 2 x...

本来给了13个D类名额，我排12，但是由于一个学校最多只能有两个D所以被卡了学校名额QAQ（还是自己太菜啊） 退役后就去搞文化课了，明年高考完可能会再继续更新博客 翘了一年文化课不知道从何补起QAQ 人生不如意十之*** 你好，文化课生活。

题目大意： 传送门 长度为  n n n 的数列，第  i i i 个数可能的值为 [ l i , r i ] [l_i,r_i] [li​,ri​]，求数列为不严格单调递减数列的期望。 （ 2 ≤ n ≤ 50 , 0 ≤ l i ≤ r i ≤ 1 e 9 ） （2\leq n \leq 50,0 \leq l_i \leq r_i \leq 1e9） （2≤n≤50,0≤li​≤ri​≤1e9） Solution: 我们把这些区间分割成两两之间不互相覆盖的若干块，把这些分割后的区间从左到右标上号，可以得到如下结论：对于任意两个数  i < j i \lt j i<j， i i...

先看CF的这道题： 题意： 传送门 有n个点，每个点有一个权值 a i a_i ai​，任意两点之间边的权值是这两点权值的异或和，求最小生成树  n ≤ 2 e 5 , a i < 2 30 n \leq 2e5, a_i< 2^{30} n≤2e5,ai​<230 Solution: 首先需要先介绍一种叫做Boruvka的最小生成树算法，算法流程类似Kruskal，对于每个连通块，在他和其他连通块之间找一个最小的边相连，因为每次都会合并一半的连通块，所以复杂度为 O （ m log ⁡ n ） O（m \log n） O（mlogn） 那么这个算法在这道题里面怎么用呢？ 我...

传送门 题意： 定义一个无根树的权值为所有点的度数的平方和，求有标号的n个点形成的所有森林的权值的和。  T ≤ 5000 , N ≤ 5000 T\leq 5000,N \leq 5000 T≤5000,N≤5000 Solution: 比赛时脑抽，考完五分钟后过了… 由prufer序列的结论可得，对于n个点的无根树，可以形成 n n − 2 n^{n-2} nn−2个不同的树，我们记他的值为 s t n st_n stn​,那么对于n个点的森林的个数 f n f_n fn​，我们可以求得DP式子：  f ( n ) = ∑ i = 0 n − 1 C n − 1 i f ( n − i −...

这是我新搭建的博客，以后大部分文章会在这里更新（csdn应该也会同步

题意： T次询问，每次给出A,B,K,W，求满足下面条件的(x,y)对数： 1.x,y是整数 2. x ∈ [ 0 , A ] , y ∈ [ 0 , B ] x \in [0,A],y\in[0,B] x∈[0,A],y∈[0,B] 3. ∣ x − y ∣ ≤ K |x-y|\leq K ∣x−y∣≤K 4. x   x o r   y ≤ W x~ xor~ y\leq W x xor y≤W  A , B , K , W ≤ 1 0 9 , T ≤ 2000 A,B,K,W\leq10^9,T\leq2000 A,B,K,W≤109,T≤2000 Solution: 首先我们把条件3拆...

Codeforces 1485E Move and Swap-DP 传送门 题意： 一棵n个节点的树，叶子节点的深度都相同，每个节点有一个权值 a i a_i ai​，有红蓝两个棋子，初始在根节点1，每轮进行三步操作： 1.红棋子移动到当前所在节点的儿子上 2.蓝棋子移动到当前节点层数+1的任意一个节点 3.交换红蓝两个棋子（可选） 移动到叶子节点后终止移动 每轮移动后获得的分数为棋子所在位置的权值差的绝对值，求最大分数和。  n ≤ 2 ∗ 1 0 5 n\leq 2*10^5 n≤2∗105 Solution： 我们分层进行处理  d p i dp_i dpi​表示在进行完三步操作后，红节...

Codeforces 1485F-Copy or Prefix Sum-DP 传送门 题意 给你一个n个数的序列 b b b 求有多少个序列 a a a满足对于每个 i ( 1 ≤ i ≤ n ) i(1\leq i\leq n) i(1≤i≤n)，至少满足以下两个条件之一： 1. b i = a i b_i=a_i bi​=ai​ 2. b i = ∑ j = 1 i a j b_i=\sum_{j=1}^ia_j bi​=∑j=1i​aj​  n ≤ 2 ∗ 1 0 5 n\leq 2*10^5 n≤2∗105 Solution 最朴素的DP：  d p i , j dp_{i,j} dp...