19-大数据一班-杨文冠

题解

学习(23) 未归档(1) 练习(1)

/ 注册

全部文章 / 题解（共20篇）

Codeforces Round #757 (Div. 2) 来自专栏

D1. Divan and Kostomuksha (easy version) 记dpidp_idpi表示把gcd⁡{\gcd}gcd为i{i}i的一组数放到前面的贡献，cnti{cnt_i}cnti表示含有因子i{i}i的数的个数。状态转移方程有：dpi=max(dpi,dpd+cnti∗...

dp gcd

2021-11-29

1 775

题解 | #校庆#

题解拍照从1∼n{1\sim n}1∼n和从n∼1{n\sim 1}n∼1分别跑一遍最长上升子序列，枚举最高的人i{i}i时，计算1∼i{1\sim i}1∼i和n∼i{n\sim i}n∼i之和，取和最大的i{i}i。（枚举最高的人i{i}i时要保证i{i}i被选到，所以要分别从前和从后跑一遍...

dp 最长上升子序列 ac自动机最大流最小割线段树二分 KM 括号匹配

2021-11-23

2 490

E. Arena 来自专栏

假设dp[n][x]{dp[n][x]}dp[n][x]为有n{n}n个人活着，每个人的体力值范围为1∼x{1\sim x}1∼x的方案数。考虑以下几种情况：当n==2{n==2}n==2时，只有两个人的体力值相同时才满足条件，dp[n][x]=x{dp[n][x]=x}dp[n][x]=x 当...

DP dp

2021-11-05

1 758

E. Pchelyonok and Segments 来自专栏

我们发现k{k}k可以是答案的前提是线段的长度总和不超过n{n}n。即k∗(k+1)2≤n\frac{k*(k+1)}{2}\le n2k∗(k+1)≤n，k≤447k\le 447k≤447 令dpi,jdp_{i,j}dpi,j表示长度为jjj的段的最大和，同时我们已经考虑了后缀iii上所有...

dp

2021-10-27

1 457

Korney Korneevich and XOR（F1&F2）来自专栏

求递增子序列所有不同的异或值显然，对于递增子序列x<y<z,ax XOR ay XOR az=Ax<y<z,a_x\ XOR\ a_y\ XOR\ a_z = Ax<y<z,ax XOR ay&nb...

dp 递增子序列

2021-10-25

1 605

Increasing Subsequence

思路方法一状态方程：状态方程中的表示的是数组的下标，即位置。，表示上一步选了，上一步选了，这一轮是选择，从上一轮开始游戏进行的回合数的期望（即从选开始计数）；，表示上一步选了，上一步选了，这一轮是选择，从上一轮开始游戏进行的回合数的期望（即从选开始计数）状态转移方程：表示事件发...

记忆化搜索 dp 期望dp

2021-08-15

1 529

I love exam 来自专栏

思路：标程奇奇怪怪，有点绕，搞了半天才勉强看懂，还有数据水了先背包求出，表示花天学第门课最多能得多少分。设表示前门课花天学习挂科门能最多能得到的分数，那么有：如果第门课学天，并且不及格，那么有如果第门课学天，并且及格，那么有其实第一维是可以滚掉的，得到，那么有：如果第门课学天，并且不及格，那么...

dp 0/1背包

2021-07-28

1 632

最长公共子序列

第一个问题应该都是会的，主要分析第二问。定义表示对应的状态长度等于的公共子序列的数量。1.如果，则表示可以由推出。2.如果，则表示可以由推出。3.如果，则表示可以由推出。4.如果，那么，即2、3都会满足，并且都包含，所以此时需要减去一个。还需要滚动数组。 Code: #include <bi...

最长公共子序列 dp

2021-06-04

1 510

C. Parsa's Humongous Tree 来自专栏

首先每个顶点的值。如果,证明如下：假设有个靠近顶点的顶点满足假设有个靠近顶点的顶点满足那么当时，将减小到会使得整棵树的美丽值增大当时，将增大到会使得整棵树的美丽值增大当时，将变成或会使得整棵树的美丽值不变或增大定义表示时，的子树的美丽值之和，同理。 MyCode: #include <bit...

思维 dp

2021-05-26

2 744

E. Partition Game 来自专栏

思路：设表示前个数分成段的最小花费，那么显然有一个满足决策单调性的充要条件是：对于两个决策点，若在处优于，则在处都优于。定理：若满足四边形不等式，则满足决策单调性。定义：若二元函数满足，则称其满足四边形不等式。推论，若只与有关，即，则必然符合四边形不等式。且此时，该类适宜用单调队列优化。而这题是...

莫队决策单调 dp

2021-05-25

1 551