_Ackerman

导航

统计

2019年8月21日 #

树链剖分模版

摘要:1 #include <stdio.h> 2 #include <cstring> 3 #include <iostream> 4 #include <string> 5 #include <algorithm> 6 #include <queue> 7 #include <vector> 8 #include <math.h> 9 #include <map> 10 11 #define LL 阅读全文

posted @ 2019-08-21 21:29 _Ackerman 阅读 (3) 评论 (0) 编辑

二维ST表

摘要:二维ST表 既然查询对象是个二维矩阵,那么我们能不能维护一个二维的ST STST表呢?答案显然是肯定的。 预处理:我们让 dp[i][j][k][l] 为新的ST表,表示以 (i,j) 为左上角,右下角为 (i + 2^k -1 , j + 2^l - 1) 的矩阵中的最大值,那么我们可以看出预处理 阅读全文

posted @ 2019-08-21 10:07 _Ackerman 阅读 (3) 评论 (0) 编辑

2019年8月20日 #

划分树

摘要:划分树,类似线段树,主要用于求解某个区间的第k 大元素(时间复杂度log(n)),快排本也可以快速找出,但快排会改变原序列,所以每求一次都得恢复序列。 什么是划分树? 划分树是一种基于线段树的数据结构,也利用了分治的思想,却比线段树高效很多,这是为什么?因为划分树又多了一个性质:在划分时不是随意划分 阅读全文

posted @ 2019-08-20 22:09 _Ackerman 阅读 (4) 评论 (0) 编辑

Count Color (线段树区间染色➕二进制状态压缩)

摘要:题目链接:https://vjudge.net/problem/POJ-2777 题意: 有L个画板,30种颜色,o个操作:P a b :询问a-b 种有多少种颜色不同的,C a b c:把a-b全部涂成c的颜色(覆盖掉) 阅读全文

posted @ 2019-08-20 10:05 _Ackerman 阅读 (4) 评论 (0) 编辑

2019年8月18日 #

B - Amr and The Large Array

摘要:题目链接:http://codeforces.com/problemset/problem/558/B 题意: 一个序列的美丽程度与其中某个数重复次数的最大值有关。求最短的子序列(连续的一段)使得其美丽程度与原序列相等。 阅读全文

posted @ 2019-08-18 11:38 _Ackerman 阅读 (4) 评论 (0) 编辑

D. Easy Problem

摘要:题目链接:http://codeforces.com/problemset/problem/1096/D 题意: 现在有一个由小写字母组成的字符串,去掉这个字符串的第i个位置会有a[i]的代价,问去掉一些字符使得该字符串中不包含一个子序列为hard的最小代价和。 思路: 这题一看就是一个 dp 的问 阅读全文

posted @ 2019-08-18 09:52 _Ackerman 阅读 (3) 评论 (0) 编辑

A. Vasya and Book

摘要:题目链接:http://codeforces.com/problemset/problem/1082/A 题意: 有一本书,页码是1到n。当前页的页码是x,要翻到第y页。规定:每次只能翻d页,向前向后翻均可。注:翻向第一页或者翻向最后一页的翻页操作可以无视上述规定。 思路: 这题其实就一个简单的模拟 阅读全文

posted @ 2019-08-18 09:42 _Ackerman 阅读 (4) 评论 (0) 编辑

B. Curiosity Has No Limits

摘要:题目链接:http://codeforces.com/problemset/problem/1072/B 题意: 给出长度为n-1的两个数组a和b,要求找出一个长度为n的数组t,使得t[i]|t[i+1]=a[i] && t[i]&t[i+1]=b[i],问是否存在这样的数组t 第一行输入一个n ( 阅读全文

posted @ 2019-08-18 09:35 _Ackerman 阅读 (4) 评论 (0) 编辑

A. Link/Cut Tree

摘要:题目链接:http://codeforces.com/problemset/problem/614/A 题意: 给你一个范围[l,r],求k的i次方在那个范围的数 思路: 这题的坑点就在于long long 可能会发生溢出,如果溢出的话我们就停止 阅读全文

posted @ 2019-08-18 00:29 _Ackerman 阅读 (3) 评论 (0) 编辑

C. Yuhao and a Parenthesis

摘要:题目链接:http://codeforces.com/problemset/problem/1097/C 题意: 有n个只含有'('和')'的字符串,现在要字符串两两拼接,如果一个拼接后的字符串中的括号都配对了就称为完美匹配,问最多有几个完美匹配。(())就算一个完美匹配,))((或者())就不算。 阅读全文

posted @ 2019-08-18 00:27 _Ackerman 阅读 (3) 评论 (0) 编辑

博聚网 //一下两个链接最好自己保存下来,再上传到自己的博客园的“文件”选项中
博聚网