何事秋。 level
获赞
1
粉丝
11
关注
14
看过 TA
20
青岛大学
2022
后端工程师
IP属地：北京
暂未填写个人简介
私信
关注
发布(463) 评论 刷题 收藏
2020-09-04 14:35
青岛大学 后端工程师
斜率优化dp：
一、任务安排1： 有 N 个任务排成一个序列在一台机器上等待执行，它们的顺序不得改变。 机器会把这 N 个任务分成若干批，每一批包含连续的若干个任务。 从时刻0开始，任务被分批加工，执行第 i 个任务所需的时间是 Ti。 另外，在每批任务开始前，机器需要 S 的启动时间，故执行一批任务所需的时间是启动时间 S 加上每个任务所需时间之和。 一个任务执行后，将在机器中稍作等待，直至该批任务全部执行完毕。 也就是说，同一批任务将在同一时刻完成。 每个任务的费用是它的完成时刻乘以一个费用系数 Ci。 请为机器规划一个分组方案，使得总费用最小。 输入格式 第一行包含整数 N。 第二行包含整数 S。 接下...
0 点赞 评论 收藏
分享
2020-09-04 14:35
已编辑
青岛大学 后端工程师
概率/期望dp：
一、Acwing 217. 绿豆蛙的归宿： 给出一个有向无环的连通图，起点为1，终点为N，每条边都有一个长度。 数据保证从起点出发能够到达图中所有的点，图中所有的点也都能够到达终点。 绿豆蛙从起点出发，走向终点。 到达每一个顶点时，如果有K条离开该点的道路，绿豆蛙可以选择任意一条道路离开该点，并且走向每条路的概率为 1/K 。 现在绿豆蛙想知道，从起点走到终点所经过的路径总长度的期望是多少？ 输入格式 第一行: 两个整数 N， M，代表图中有N个点、M条边。 第二行到第 1+M 行: 每行3个整数 a, b, c，代表从a到b有一条长度为c的有向边。 输出格式 输出从起点到终点路径总长度的期望...
0 点赞 评论 收藏
分享
2020-09-04 14:34
已编辑
青岛大学 后端工程师
划分树：
话说这个东西大概要退出历史的舞台了吧。。。 专用功能，静态查询区间第k大，主席树完全可以搞定啊，还能搞点别的。 不过思想还是要学一下的。 以下转自：https://blog.csdn.net/Akatsuki__Itachi/article/details/80030929 有这样一类题目，求的是区间内的第k大数。 划分树的定义就是对整体的区间进行划分，把相对于原来序列中较小的值放在左子树，较大的放在右子树，最后按照它的性质进行查询以此找到要查询的区间里的第k大数。 logn 查询。 例图（图是偷的~~~）  1.建树 建树是一个不停递归的过程 第一步： 首先我们要根据排序后的数组找到当前层数...
0 点赞 评论 收藏
分享
2020-09-04 14:34
青岛大学 后端工程师
线段树动态开点：
貌似权值线段树动态开点用的比较多。 例题： I Hate It HDU - 1754 很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。 这让很多学生很反感。 不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。 Input 本题目包含多组测试，请处理到文件结束。 在每个测试的第一行，有两个正整数 N 和 M ( 0<N<=200000,0<M<5000 )，分别代表学生的数目和操作的数目。 学生ID编号分别从1编到N。 第二行包含N个整数，代表这N个学生的初始成绩，其...
0 点赞 评论 收藏
分享
2020-09-04 14:33
已编辑
青岛大学 后端工程师
权值线段树：
维护当前节点代表值出现的次数。 题目描述 您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作： 1。插入x数 2。删除x数(若有多个相同的数，因只删除一个) 3。查询x数的排名(排名定义为比当前数小的数的个数+1。若有多个相同的数，因输出最小的排名) 4。查询排名为x的数 5。求x的前驱(前驱定义为小于x，且最大的数) 6。求x的后继(后继定义为大于x，且最小的数) 输入格式 第一行为n，表示操作的个数,下面n行每行有两个数opt和x，opt表示操作的序号( 1≤opt≤6 ) 输出格式 对于操作3,4,5,6每行输出一个数，表示对应答案 输入输出样例 输入 #1 复制...
0 点赞 评论 收藏
分享
2020-09-04 14:33
青岛大学 后端工程师
线段树合并：
某一天马学长给我看了一个lca的题目，然而确实是lca+树上差分，但是仅仅有lca和树上差分解决不了，然后我就去面向题解编程了。 可是这个线段树合并是个什么东东。。。 然而今天看书，突然看到了这个线段树合并。 就写一下了。 %mmh。 P4556 [Vani有约会]雨天的尾巴： 题目背景 深绘里一直很讨厌雨天。 灼热的天气穿透了前半个夏天，后来一场大雨和随之而来的洪水，浇灭了一切。 虽然深绘里家乡的小村落对洪水有着顽固的抵抗力，但也倒了几座老房子，几棵老树被连根拔起，以及田地里的粮食被弄得一片狼藉。 无奈的深绘里和村民们只好等待救济粮来维生。 不过救济粮的发放方式很特别。 题目描述 首先村落里...
0 点赞 评论 收藏
分享
2020-09-04 14:33
已编辑
青岛大学 后端工程师
离线分治算法：
一、基于时间的分治算法 --------CDQ分治 例题：AcWing 254. 天使玩偶 Ayu在七年前曾经收到过一个天使玩偶，当时她把它当做时间囊埋在了地下。 而七年后的今天，Ayu却忘了她把天使玩偶埋在了哪里，所以她决定仅凭一点模糊的记忆来寻找它。 我们把Ayu生活的小镇看做一个二维平面直角坐标系，而Ayu会不定时的记起可能在某个点(x,y)埋下了天使玩偶。 或者Ayu会询问你，假如她在(x,y)，那么她离最近的天使玩偶可能埋下的地方有多远。 因为Ayu只会沿着平行坐标轴的方向来行动，所以在这个问题里我们定义两个点之间的距离为曼哈顿距离： dist(A,B)=|Ax−Bx|+|Ay−By...
0 点赞 评论 收藏
分享
2020-09-04 14:32
青岛大学 后端工程师
基环树：
把树再加一条边，形成一个环。 处理基环树的方法，一般就是找出环，并且把环当成广义上的树根，处理树，然后处理环。 一、AcWing 358. 岛屿： 你准备有限一个公园，该公园由 N 个岛屿组成，当地管理部门从每个岛屿出发向另外一个岛屿建了一座桥，不过桥是可以双向行走的。 同时，每对岛屿之间都有一艘专用的往来两岛之间的渡船。 相对于乘船而言，你更喜欢步行。 你希望所经过的桥的总长度尽可能的长，但受到以下的限制： 可以自行挑选一个岛开始游览。 任何一个岛都不能游览一次以上。 无论任何时间你都可以由你现在所在的岛S去另一个你从未到过的岛D。由S到D可以有以下方法： （1）步行：仅当两个岛之间有一座桥...
0 点赞 评论 收藏
分享
2020-09-04 14:32
已编辑
青岛大学 后端工程师
可持久化Trie（可持久化字典树）：
构建可持久化Trie所需的空间和时间复杂度都是字符串的总长度的线性函数。 比例系数为字符集大小。 例题：AcWing 256. 最大异或和： 给定一个非负整数序列 a，初始长度为 N。 有 M 个操作，有以下两种操作类型： 1、”A x”：添加操作，表示在序列末尾添加一个数 x，序列的长度 N 增大1。 2、”Q l r x”：询问操作，你需要找到一个位置 p，满足l≤p≤r，使得：a[p] xor a[p+1] xor … xor a[N] xor x 最大，输出这个最大值。 输入格式 第一行包含两个整数 N，M，含义如问题描述所示。 第二行包含 N 个非负整数，表示初始的序列 A。 接下来...
0 点赞 评论 收藏
分享
2020-09-04 14:32
青岛大学 后端工程师
二叉查找树与平衡树初步（Treap）：
例题：洛谷 P3369 【模板】普通平衡树 题目描述 您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作： 1。插入x数 2。删除x数(若有多个相同的数，因只删除一个) 3。查询x数的排名(排名定义为比当前数小的数的个数+1。若有多个相同的数，因输出最小的排名) 4。查询排名为x的数 5。求x的前驱(前驱定义为小于x，且最大的数) 6。求x的后继(后继定义为大于x，且最小的数) 输入格式 第一行为n，表示操作的个数,下面n行每行有两个数opt和x，opt表示操作的序号( 1≤opt≤6 ) 输出格式 对于操作3,4,5,6每行输出一个数，表示对应答案 输入输出样例 输入...
0 点赞 评论 收藏
分享

创作者周榜

更多
关注他的用户也关注了：
牛客网
牛客网在线编程
牛客网题解
牛客企业服务