何事秋。 - 个人主页动态 - 牛客网

发布(463) 评论刷题收藏

2020-09-04 14:41

已编辑

青岛大学后端工程师

POJ - 2279：Mr. Young‘s Picture Permutations（线性dp）

Mr. Young wishes to take a picture of his class. The students will stand in rows with each row no longer than the row behind it and the left ends of the rows aligned. For instance, 12 students could be arranged in rows (from back to front) of 5, 3, 3 and 1 students. X X X X X X X X X X X X In additi...

0 点赞评论收藏

分享

2020-09-04 14:41

青岛大学后端工程师

POJ - 2127 Greatest Common Increasing Subsequence（线性dp，最长公共上升子序列）

POJ - 2127 Greatest Common Increasing Subsequence You are given two sequences of integer numbers. Write a program to determine their common increasing subsequence of maximal possible length. Sequence S 1 , S 2 , . . . , S N of length N is called an increasing subsequence of a sequence A 1 , A 2 , . ...

0 点赞评论收藏

分享

2020-09-04 14:40

已编辑

青岛大学后端工程师

曼哈顿最小生成树：

Object Clustering POJ - 3241 We have N (N ≤ 10000) objects, and wish to classify them into several groups by judgement of their resemblance. To simply the model, each object has 2 indexes a and b (a, b ≤ 500). The resemblance of object i and object j is defined by dij = |ai - aj| + |bi - bj|, and th...

0 点赞评论收藏

分享

2020-09-04 14:40

青岛大学后端工程师

最大团问题：

无向图的最大团等于其补图的最大独立集 无向图的最大独立集等于其补图的最大团。 一、Maximum Clique HDU - 1530 ： Given a graph G(V, E), a clique is a sub-graph g(v, e), so that for all vertex pairs v1, v2 in v, there exists an edge (v1, v2) in e. Maximum clique is the clique that has maximum number of vertex. Input Input contains multiple tes...

0 点赞评论收藏

分享

2020-09-04 14:39

青岛大学后端工程师

树上分治：

一、点分治。 题目① Tree POJ - 1741： Give a tree with n vertices,each edge has a length(positive integer less than 1001). Define dist(u,v)=The min distance between node u and v. Give an integer k,for every pair (u,v) of vertices is called valid if and only if dist(u,v) not exceed k. Write a program that will...

0 点赞评论收藏

分享

2020-09-04 14:39

青岛大学后端工程师

树链剖分：

这真是个神奇的东西。 一、模板例题： P3384 【模板】树链剖分： 题目描述 如题，已知一棵包含N个结点的树（连通且无环），每个节点上包含一个数值，需要支持以下操作： 操作1： 格式： 1 x y z 表示将树从x到y结点最短路径上所有节点的值都加上z 操作2： 格式： 2 x y 表示求树从x到y结点最短路径上所有节点的值之和 操作3： 格式： 3 x z 表示将以x为根节点的子树内所有节点值都加上z 操作4： 格式： 4 x 表示求以x为根节点的子树内所有节点值之和 输入格式 第一行包含4个正整数N、M、R、P，分别表示树的结点个数、操作个数、根节点序号和取模数（即所有的输出结果均对此取...

0 点赞评论收藏

分享

2020-09-04 14:39

青岛大学后端工程师

最近公共祖先lca（2）：

之前学习过一次lca，是用暴力，倍增，tarjan离线处理的。 之前就知道lca还有其他两种写法，不过那个时候还不会树剖，就没学。 今天学习树剖之后，发现lca树剖写法不就是个裸的树剖吗。 预处理 O（n） 查询logn 比倍增还优秀一点。 今天就补上没学的那两种lca的写法了。 P3379 【模板】最近公共祖先（LCA）： 题目描述 如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。 输入格式 第一行包含三个正整数N、M、S，分别表示树的结点个数、询问的个数和树根结点的序号。 接下来N-1行每行包含两个正整数x、y，表示x结点和y结点之间有一条直接连接的边（数据保证可以构成树）。...

0 点赞评论收藏

分享

2020-09-04 14:38

青岛大学后端工程师

单调队列：

O（n） 一、ACwing 输入一个长度为n的整数序列，从中找出一段长度不超过m的连续子序列，使得子序列中所有数的和最大。 输入格式 第一行输入两个整数n,m。 第二行输入n个数，代表长度为n的整数序列。 同一行数之间用空格隔开。 输出格式 输出一个整数，代表该序列的最大子序和。 数据范围 1≤n,m≤300000 输入样例： 6 4 1 -3 5 1 -2 3 输出样例： 7 #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include&lt...

0 点赞评论收藏

分享

2020-09-04 14:38

青岛大学后端工程师

一、一维RMQ： 前两天学lca的时候学了这个东西，今天再来系统的学一下。 P3865 【模板】ST表： 题目背景 这是一道ST表经典题——静态区间最大值 请注意最大数据时限只有0.8s，数据强度不低，请务必保证你的每次查询复杂度为 O(1) 题目描述 给定一个长度为 N 的数列，和 M 次询问，求出每一次询问的区间内数字的最大值。 输入格式 第一行包含两个整数 N, M 分别表示数列的长度和询问的个数。 第二行包含 N 个整数依次表示数列的第 i 项。 接下来 M行，每行包含两个整数 l, r，表示查询的区间为 [ l, r] 输出格式 输出包含 M行，每行一个整数，依次表示每一次询问的结果...

0 点赞评论收藏

分享

2020-09-04 14:38

已编辑

青岛大学后端工程师

哈夫曼树，哈夫曼编码：

一、哈夫曼树： ①、 P1090 合并果子： 题目描述 在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。 每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过 n-1次合并之后， 就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。 因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为 1 ，并且已知果子的种类 数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。 例如有3 ...

0 点赞评论收藏

分享

2020-09-04 14:37

青岛大学后端工程师

环形结构上的动态规划问题的两种基本处理方式：

一、 执行两次DP，第一次在任意位置把环断开成链，按照线性问题求解。 第二次通过适当的条件和赋值，保证计算的状态等价于把断开的位置强制相连。 Naptime POJ - 2228： Goneril is a very sleep-deprived cow. Her day is partitioned into N (3 <= N <= 3,830) equal time periods but she can spend only B (2 <= B < N) not necessarily contiguous periods in bed. Due to her ...

0 点赞评论收藏

分享

2020-09-04 14:37

青岛大学后端工程师

有后效性的状态转移方程：

一、 实际上无后效性是动态规划算法的前提之一，然后有些题， 我们设计出状态表示和状态转移方程之后才发现，其似乎不满足无后效性这一特点。 以 以下 期望dp为例，在很多的题目中，动态规划的状态转移分阶段带环， 我们需要把dp和高斯消元相结合，在整体层面采用动态规划框架，在局部 使用高斯消元解出互相影响的状态。 事实上，多数的期望dp都会采用倒推的方式执行。 Broken robot CodeForces - 24D： You received as a gift a very clever robot walking on a rectangular board. Unfortunately, ...

0 点赞评论收藏

分享

2020-09-04 14:37

已编辑

青岛大学后端工程师

数据结构优化dp：

写在前面： 一般的，只要决策的候选集合只扩大，不缩小，我们就可以仅用一个变量维护最值，不断与新加入候选集合的元素比较，即可直接得到最优决策，O（1）的进行转移。 在更加复杂的情况下，我们就要用更加高级的数据结构，而不仅仅是一个变量维护dp的决策候选集合，以便快速执行插入元素，删除元素，查询最值等操作，把朴素的在取值范围中枚举的时间优化为维护数据结构的时间。 一、Cleaning Shifts POJ - 2376： Farmer John is assigning some of his N (1 <= N <= 25,000) cows to do some cleaning c...

0 点赞评论收藏

分享

2020-09-04 14:36

青岛大学后端工程师

写在前面： 这一类dp特别要求不重不漏。统计对象的可能情况一般比较多，通常需要精确的划分和整体性计算。因此，使用动态规划抽象出问题中的子结构和推导的阶段，将有助于我们准确而高效的进行求解。 在求解计数类动态规划的问题时，通常要找到一个基准点，围绕这个基准点构造一个不可划分的整体，以避免子问题之间的重复。 一、Gerald and Giant Chess CodeForces - 559C： Giant chess is quite common in Geraldion. We will not delve into the rules of the game, we’ll just say ...

0 点赞评论收藏

分享

2020-09-04 14:36

青岛大学后端工程师

倍增优化dp：

写在前面： 用倍增优化的动态规划算法求解问题时，一般分为两部分，第一部分是预处理，用阶段成倍增长的DP，计算出若干与2的整数次幂相关的代表状态。第二部分是拼凑，基于二进制拆分思想，用上一部分得到的代表状态组合成最终答案。 一、P1081 开车旅行： 题目描述 小 A 和小 B 决定利用假期外出旅行，他们将想去的城市从 1到 N 编号，且编号较小的城市在编号较大的城市的西边，已知各个城市的海拔高度互不相同，记城市 i的海拔高度为Hi，城市 i和城市 j之间的距离 d[i,j]恰好是这两个城市海拔高度之差的绝对值，即d[i,j]=|Hi - Hj| 旅行过程中，小 A和小 B 轮流开车，第一天小 ...

0 点赞评论收藏

分享

创作者周榜

更多

关注他的用户也关注了：

牛客网
牛客网在线编程
牛客网题解
牛客企业服务