19-大数据一班-杨文冠

分类

学习(23) 未归档(1) 练习(1) 题解(137)

/ 注册

TA的专栏 96篇文章 0人订阅

[kuangbin带我飞]专题十五数位DP

11篇文章 891人学习

[kuangbin带我飞]专题十四数论基础

2篇文章 648人学习

8篇文章 749人学习

动态规划入门

7篇文章 923人学习

1篇文章 669人学习

二分图匹配

2篇文章 653人学习

[kuangbin带我飞]专题七线段树

8篇文章 797人学习

3篇文章 744人学习

线段树进阶

3篇文章 660人学习

codeforces补题

32篇文章 875人学习

莫比乌斯反演

6篇文章 577人学习

网络流初步

4篇文章 762人学习

6篇文章 722人学习

2021杭电多校

3篇文章 783人学习

全部文章（共23篇）

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 753

题解 | #校庆#

题解拍照从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 483

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 747

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 447

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 584

Increasing Subsequence

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

记忆化搜索 dp 期望dp

2021-08-15

1 509

I love exam 来自专栏

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

dp 0/1背包

2021-07-28

1 620

最长公共子序列

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

最长公共子序列 dp

2021-06-04

1 502

第十二届蓝桥杯省赛第一场C++B组

砝码称重 dp题 Code: #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 2e5 + 7, mod = 1e9 + 7; bitset<maxn>f;...

二分二分答案思维 dp

2021-06-03

1 740

C. Parsa's Humongous Tree 来自专栏

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

思维 dp

2021-05-26

2 728