19-大数据一班-杨文冠

分类

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

/ 注册

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

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

11篇文章 896人学习

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

2篇文章 652人学习

8篇文章 754人学习

动态规划入门

7篇文章 926人学习

1篇文章 673人学习

二分图匹配

2篇文章 658人学习

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

8篇文章 801人学习

3篇文章 750人学习

线段树进阶

3篇文章 663人学习

codeforces补题

32篇文章 882人学习

莫比乌斯反演

6篇文章 581人学习

网络流初步

4篇文章 767人学习

6篇文章 727人学习

2021杭电多校

3篇文章 791人学习

全部文章（共173篇）

Making the Grade 来自专栏

题意：给定长度为的序列，构造一个长度为的序列，满足：非严格单调，即不递增或者不递减。最小化思路：这题数据弱，只考虑不递减的情况就可以过，但还要考虑不递增的情况比如我代码中的数据。引理：在满足最小化的前提下，一定存在一种构造序列的方案，使得中的数值都在中出现过。状态表示在完成前个数的构...

线性DP dp

2021-04-17

1 637

LCIS 来自专栏

思路：表示与可以构成以为结尾的的长度。当时，当时，，显然需要满足，因为是以为结尾的。最后枚举为结尾的的长度，找最大的。 MyCode: #include <iostream> #include <cstdio> #include <cstring> #inclu...

线性DP 最长公共上升子序列 dp

2021-04-17

1 643

Mr. Young's Picture Permutations 来自专栏

题目对案例3 2 1解释中，他没有把每个数隔开，注意点就好。思路：满足条件的排列是往右往后都是递减的，求所有的排列数。就像上面图片画的那样，我们对学生的身高降序编号，最高的人编号为，最低的人编号为。那么就是一个简单的填数问题，从依次填入，那么任意时刻每一行中已经填了数一定是从左端开始的连续若干位置...

线性DP dp

2021-04-17

1 900

Telephone Lines

思路：如果号点到号点是连通的，那么一定可以完成，反之一定不能完成，输出-1；解法一：分层图最短路图中的每个节点不仅限于“整数编号”，可以扩展到二维，用二元组代表一个节点，表示该点的编号以及第几层，显然在同层移动需要支出费用，向高层移动不需要支出费用。从到有长度为的边，表示端点为的电缆需要付费；从...

分层图最短路二分答案双端队列循环队列 BFS

2021-04-17

1 603

Divide by Zero 2021 and Codeforces Round #714 (Div. 2) 来自专栏

A. Array and Peaks 思路：构造个峰需要个元素，所以如果那么无法构成，否则可以从第二个位置开始放最大的数，每隔一个位置再放一个差值为1的数，放满k个，然后从头往后依次将没有填数的位置填上，依次从剩余的中没有的取掉的数从小到大取。 MyCode: #include <bits...

贪心思维构造分类最小生成树 kruskal算法

2021-04-15

1 828

P7492 序列来自专栏

思路：区间或、求区间最大连续字段和。求区间最大连续字段和就是一个板子，用经典做法线段树维护一个分别表示从左开始的最大子段和，右边开始的，区间的和，区间的答案。因为一个数的二进制位只有30位，而或操作只有将至少一个0变成1才对某个值有影响，所以有效的操作最多只会影响30n次改变，每次区间修改用单点修...

最大连续子段和线段树区间或

2021-04-10

2 801

Parallel Sort

题意：给定长度为n的排列，一次操作你可以选择任意个下标数对：(x1,y1)，(x2,y2)，…(xn,yn)。要求每个下标最多只出现一次。问最少需要几次操作能够将排列恢复为原排列，同时输出每次操作选择的下标。思路：之间连一条边，如果不形成环，那么一次操作就行，如果环上只有两个点，那么也只需要一次...

第45届ICPC昆明思维

2021-04-08

3 658

Cities

题意：把一段相同的形状变成其它任意一个形状，需要使用一次魔法，问最少使用多少魔法能使全是同一个形状。思路：先把连续的缩成一个连续段，假设缩点后有m个段，如果每个互不相同，答案显然是m-1，不管怎样合都对答案没有影响。如果在合并两个区间时，两个区间的左、右端点的值相同，那么可以通过将中间的值赋值成该...

第45届ICPC昆明 dp 区间dp 石子合并

2021-04-08

8 588

Gift

题意：2021年，n个人过生日，做蛋糕需要天，生日那天给第i个人有个好感度，也可以选择送礼物，需要花元，获得个好感度，每个礼物最多买一次。在生日当天做蛋糕，如果只要一天也能赶上。思路：2021年不会出现2月29假设给i个人做蛋糕，j个人发礼物是最优的我们可以爆搜求出表示给j个人发礼物能得到的最大好...

背包第45届ICPC昆明爆搜 dp

2021-04-07

3 620

M.Stone Games

题意：每次询问给出L,R，问[L,R]中选择一个子集求和，无法凑出的最小正整数是多少；思路：首先，如果没有1，那么;假设现在能组成，且内有，那么就能凑出，即凑出,然后继续凑;反之若内不存在，则无法凑出的最小正整数就是x的增长速度是指数级的，因此最多次就出来了。询问两个区间总和之差，需要用区间权值...

第45届ICPC昆明可持久化线段树

2021-04-06

9 796