半世blue-CSDN博客

原创后缀数组

后缀数组变量意义解释：sa[i]sa[i]sa[i]：第 iii 个后缀的排名rnk[i]rnk[i]rnk[i]：排名为 iii 的后缀在原字符串的位置，与 sasasa 数组意义相反tmp[i]tmp[i]tmp[i]：辅助数组height[i]height[i]height[i]：表示 sa[i]sa[i]sa[i] 和 sa[i−1]sa[i-1]sa[i−1] 两个后缀的 LC...

2019-07-28 22:06:27 124

传送门：https://codeforces.com/contest/1102/problem/FYou are given a matrix a, consisting of n rows and m columns. Each cell contains an integer in it.You can change the order of rows arbitrarily (inclu...

2019-01-11 22:12:40 642

原创 570D Tree Requests (dsu_on_tree)

传送门：https://codeforces.com/contest/570/problem/D 题目大意：给一棵树，每个节点有一个字母，问节点v的深度为h的儿子节点的所有字母能否组成一个回文串（深度是对于整棵树）很裸的一个树上合并，也可以使用二分来做//919ms#include<bits/stdc++.h>using namespace std;const int ...

2018-09-05 19:24:21 159

原创群论

将置换写成循环循环置换的分解循环置换的阶循环置换分解为对换置换的奇偶性http://www.doc88.com/p-905280660599.html

2018-08-29 21:03:02 702

原创 dsu_on_tree

大佬博客：https://codeforces.com/blog/entry/44351 使用范围：常用来求子树的信息，比如，如果一棵树上每个节点都有一种颜色，求一个子树中颜色c的出现次数复杂度分析：这个就是启发式合并，每一次合并都将小的集合合并到大的集合，每个元素的合并次数最多为lognlognlogn次，看起来像是n2n2n^2的合并，实际复杂度只有nlognnlognnlogn，如果使...

2018-08-29 20:57:50 335

原创 hdu多校第五场 G题

题意是给定一个随机数生成器，得到l, r, val表示将区间[l, r]内比val小的元素修改为val 解法有两种第一种是线段树解法，我们就用线段树维护一个区间最小值，当val比区间的minn还小那么就不更新，否则向下暴力更新。因为数据是随机生成的，所以暴力更新并不会被卡。开始的想法是将所有操作按val从大到小排序，那么我们每个点就只会被更新一次，但是由于操作次数太多，排序时间大于计算答案的...

2018-08-07 17:06:43 136

原创牛客多校第四场 J题 Hash Function（线段树建图优化+拓扑排序）

传送门：https://www.nowcoder.com/acm/contest/142/J 题目大意就是给你一个散列表，还原出字典序最小的原序列解法：通过推样例发现，一个数x如果不在x%n 的位置，那么从x%n 到当前数字位置i-1的区间内都已经被占满，那么考虑从x%n 到i-1 所有的点到i 建一条边，然后跑一次拓扑排序（这里渐变相当于是限制第i个数字一定比x%n 到i-1 的数字后出现...

2018-07-29 20:55:44 314

原创 HYSBZ - 3884 上帝与集合的正确用法

#include<bits/stdc++.h>using namespace std;const int maxn=1e7+5;typedef long long LL;int p[maxn],phi[maxn];bool prime[maxn];LL eular(LL x){ LL ret=1; for(int i=2;i*i<=x;i++){ ...

2018-07-29 14:27:53 189

原创杭电多校第一场补题记录

很菜，只能靠补题了，打的时候直接被1004的tle卡爆1001. Maximum Multiple打了个一百以内数的因子表，队友看出了规律 n|3的时候就是(n.3)^3 n|2&amp;amp;amp;&amp;amp;amp;n|4 的时候就是(n/2)*(n/4)^21003. Triangle Partition排个序就出来了1011. Time Zone把当前时间转化成UTC+0...

2018-07-24 10:55:58 304 2

原创 Codeforces Round #492 (Div. 2)

http://codeforces.com/contest/996A. Hit the Lottery解法：贪心一下就好了#include<bits/stdc++.h>using namespace std;int main(){ ios::sync_with_stdio(false); int n; cin>>n; i...

2018-07-08 21:47:58 194

原创 Educational Codeforces Round 46 (Rated for Div. 2)

A. Codehorses T-shirts题意：找出两份名单中不同衣服大小的个总件数解法：map模拟一下就行#include&lt;bits/stdc++.h&gt;using namespace std;typedef long long LL;map&lt;string,int&gt;mp,mp2;int main(){ int n; cin&gt;...

2018-07-08 21:18:49 326

原创 Codeforces Round #493 (Div. 2)

A. Balloons题意：两个人分气球，每个人至少有一个且两个人分到的气球个数不相等。解法：求出sum，找到一个数x，且2*x!=sum ，则把这个气球分给一个人，其他的给另一个人#include&lt;bits/stdc++.h&gt;using namespace std;#define maxn 100005int a[maxn];int main(){ ...

2018-07-07 20:06:18 160

原创 Codeforces Round #494 (Div. 3)

传送门：http://codeforces.com/contest/998A. Polycarp’s Pockets直接找出数字出现次数最多的次数#include<bits/stdc++.h>using namespace std;int a[106];int main(){ ios::sync_with_stdio(false); int n,...

2018-07-07 19:32:47 169

原创 hiho 1393 : 网络流三·二分图多重匹配

传送门：http://hihocoder.com/problemset/problem/1393描述学校的秋季运动会即将开始，为了决定参赛人员，各个班又开始忙碌起来。小Hi和小Ho作为班上的班干部，统计分配比赛选手的重任也自然交到了他们手上。已知小Hi和小Ho所在的班级一共有N名学生(包含小Hi和小Ho)，编号依次为1..N。运动会一共有M项不同的比赛，编号为1..M。第i...

2018-06-10 21:32:46 255

原创 51nod 1089 最长回文子串 V2（Manacher算法）

传送门：https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1089 回文串是指aba、abba、cccbccc、aaaa这种左右对称的字符串。输入一个字符串Str，输出Str里最长回文子串的长度。Input输入Str（Str的长度 &lt;= 100000)Output输出最长回文子串的长度L...

2018-05-27 17:22:16 115

原创 hdu 2639 Bone Collector II【01背包第k优解】

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=2639Problem DescriptionThe title of this problem is familiar,isn’t it?yeah,if you had took part in the “Rookie Cup” competition,you must have seem t...

2018-05-13 15:29:13 259

原创 hdu3033 I love sneakers!【分组背包】

传送门:http://acm.hdu.edu.cn/showproblem.php?pid=3033Problem DescriptionAfter months of hard working, Iserlohn finally wins awesome amount of scholarship. As a great zealot of sneakers, he decides ...

2018-05-13 11:33:06 148

原创 poj1170 Shopping Offers【状压+背包】

传送门：http://poj.org/problem?id=1170DescriptionIn a shop each kind of product has a price. For example, the price of a flower is 2 ICU (Informatics Currency Units) and the price of a vase is 5 ICU. ...

2018-05-10 19:09:02 244

原创 poj2728 Desert King【最优比率生成树】

传送门:http://poj.org/problem?id=2728DescriptionDavid the Great has just become the king of a desert country. To win the respect of his people, he decided to build channels all over his country to ...

2018-04-12 19:54:56 142

原创 bzoj2588 Spoj 10628. Count on a tree【主席树+lca】

传送门:https://www.lydsy.com/JudgeOnline/problem.php?id=2588 给定一棵N个节点的树，每个点有一个权值，对于M个询问(u,v,k)，你需要回答u xor lastans和v这两个节点间第K小的点权。其中lastans是上一个询问的答案，初始为0，即第一个询问的u是明文。Input第一行两个整数N,M。第二行有N个整数，其中第i个...

2018-04-03 20:31:39 157

原创 bzoj3524 Couriers【主席树裸题】

权限题传送门:https://szkopul.edu.pl/problemset/problem/Cs38m8lWFnOfDskXf43HR3lN/site/?key=statementDescription给一个长度为n的序列a。1≤a[i]≤n。 m组询问，每次询问一个区间[l,r]，是否存在一个数在[l,r]中出现的次数大于(r-l+1)/2。如果存在，输出这个数，否则输出...

2018-03-29 19:08:30 240

原创 bzoj3207 花神的嘲讽计划Ⅰ【主席树+hash】

传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3207Description背景花神是神，一大癖好就是嘲讽大J，举例如下： “哎你傻不傻的！【hqz：大笨J】” “这道题又被J屎过了！！” “J这程序怎么跑这么快！J要逆袭了！” …… 描述这一天DJ在给吾等众蒟蒻讲题，花神在一边做题无聊，就跑到了一边跟吾等众蒟...

2018-03-27 16:41:59 132

原创 hdu4417 Super Mario【主席树模板题】

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=4417Problem DescriptionMario is world-famous plumber. His “burly” figure and amazing jumping ability reminded in our memory. Now the poor princess i...

2018-03-22 21:32:45 358

原创 poj3061 Subsequence【尺取法】

传送门：http://poj.org/problem?id=3061DescriptionA sequence of N positive integers (10 < N < 100 000), each of them less than or equal 10000, and a positive integer S (S < 100 000 000) are ...

2018-03-22 19:42:51 85

原创 hdu 1724 Ellipse【自适应辛普森】

传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1724Problem DescriptionMath is important!! Many students failed in 2+2’s mathematical test, so let’s AC this problem to mourn for our lost youth.. Lo...

2018-03-18 11:26:28 183

原创卡特兰数

参见百度百科:https://baike.baidu.com/item/%E5%8D%A1%E7%89%B9%E5%85%B0%E6%95%B0 卡特兰数的前15项为：1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845 递推关系为：h(n)=h(n-1)*(4*n-2)/(n+1); 或者：h(n)=...

2018-03-18 10:54:13 112

原创 bzoj 2141 排队【分块】

http://www.lydsy.com/JudgeOnline/problem.php?id=2141 排排坐，吃果果，生果甜嗦嗦，大家笑呵呵。你一个，我一个，大的分给你，小的留给我，吃完果果唱支歌，大家乐和和。红星幼儿园的小朋友们排起了长长地队伍，准备吃果果。不过因为小朋友们的身高有所区别，排成的队伍高低错乱，极不美观。设第i个小朋友的身高为hi，我们定义一个序列的杂乱程度为：满足i...

2018-03-10 16:16:56 238

原创 codeforces 940f Machine Learning【带修改莫队+离散化】

http://codeforces.com/problemset/problem/940/F You are given an array a. You have to answer the following queries:You are given two integers l and r. Let ci be the number of occurrences of i in al:...

2018-03-07 18:37:51 390

原创 HDU 4632 Palindrome subsequence（区间dp）

http://acm.hdu.edu.cn/showproblem.php?pid=4632Problem DescriptionIn mathematics, a subsequence is a sequence that can be derived from another sequence by deleting some elements without changing

2018-01-27 14:10:37 101

原创 POJ 2955 Brackets 区间dp

http://poj.org/problem?id=2955DescriptionWe give the following inductive definition of a “regular brackets” sequence:the empty sequence is a regular brackets sequence, if s is a regular bracket

2018-01-27 13:57:19 128

原创双堆维护中位数

1，先把第一个数赋给mid 2，后来的数如果>=mid就插入到小顶堆3，每次插入新的值后都保证小顶堆的大小与大顶堆相等或大1 4，最后的中位数就是mid(n为奇数)，或者mid和小顶堆的堆顶元素的平均priority_queueint,vectorint>,greaterint> >smallseq;priority_queueint,vectorint>,lessint> >bigs

2018-01-25 18:00:31 808

原创 hdu1817 Necklace of Beads(polya定理)

http://acm.hdu.edu.cn/showproblem.php?pid=1817Problem DescriptionBeads of red, blue or green colors are connected together into a circular necklace of n beads ( n InputThe input has sever

2018-01-25 11:22:21 224

原创 codeforces 899e Segments Removal

Vasya has an array of integers of length n.Vasya performs the following operations on the array: on each step he finds the longest segment of consecutive equal integers (the leftmost, if there are seve

2017-12-25 14:17:27 480

原创 HYSBZ - 1036 树的统计Count (树链剖分)

树链剖分就是将一个树的路径转化成重链和轻链，对其节点或者边就行编号，从而可以转化成其他的数据结构问题来解决问题。树链剖分有些类似莫队，也就是相当于把树的路径进行了分块。数组的含义：fa[]每个节点的父节点 num[]每个节点子节点的个数（包含自己） son[v]与v在同一重链的重儿子 top[v]节点v所在链的顶端节点（v可以是一个单独的点，相当于自己组成一条重链） pos[v]节点v编号后

2017-12-12 14:04:11 240

原创 51NOD 1445 变色DNA(最短路)

有一只特别的狼，它在每个夜晚会进行变色，研究发现它可以变成N种颜色之一，将这些颜色标号为0,1,2…N-1。研究发现这只狼的基因中存在一个变色矩阵，记为colormap，如果colormap[i][j]=’Y’则这只狼可以在某一个夜晚从颜色i变成颜色j（一晚不可以变色多次），如果colormap[i][j]=‘N’则不能在一个晚上从i变成j色。进一步研究发现，这只狼每次变色并不是随机变的，它有一定

2017-12-02 14:35:43 172

原创树状数组的区间修改求和

差分数组：c[i]=a[i]-a[i-1] 然后可以发现 a[i]=a[1]+a[2]-a[1]+a[3]-a[2]+…+a[i]-a[i-1]=c[1]+c[2]+…+c[i]1，区间修改单点查询修改a[l]到a[r]值的时候，只需修改c[l]和c[r+1],然后求一次c[i]的前缀和就可以。 2，区间修改区间查询还是利用差分的思想。区间求和的公式为： sum(1,n) =

2017-11-02 19:07:57 378

原创 BZOJ3289 Mato的文件管理-莫队算法

Mato同学从各路神犇以各种方式（你们懂的）收集了许多资料，这些资料一共有n份，每份有一个大小和一个编号。为了防止他人偷拷，这些资料都是加密过的，只能用Mato自己写的程序才能访问。Mato每天随机选一个区间[l,r]，他今天就看编号在此区间内的这些资料。Mato有一个习惯，他总是从文件大小从小到大看资料。他先把要看的文件按编号顺序依次拷贝出来，再用他写的排序程序给文件大小排序。排序程序可以在1单

2017-11-01 20:19:45 246

原创 HYSBZ - 2038 小Z的袜子(hose)

作为一个生活散漫的人，小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天，小Z再也无法忍受这恼人的找袜子过程，于是他决定听天由命…… 具体来说，小Z把这N只袜子从1到N编号，然后从编号L到R(L 尽管小Z并不在意两只袜子是不是完整的一双，甚至不在意两只袜子是否一左一右，他却很在意袜子的颜色，毕竟穿两只不同色的袜子会很尴尬。你的任务便是告诉小Z，他有多大的概率抽到两只颜色相

2017-10-28 17:50:01 212

原创 1163 最高的奖励-51Nod

有N个任务，每个任务有一个最晚结束时间以及一个对应的奖励。在结束时间之前完成该任务，就可以获得对应的奖励。完成每一个任务所需的时间都是1个单位时间。有时候完成所有任务是不可能的，因为时间上可能会有冲突，这需要你来取舍。求能够获得的最高奖励。 Input 第1行：一个数N，表示任务的数量(2 <= N <= 50000) 第2 - N + 1行，每行2个数，中间用空格分隔，表示任务的最晚结束时间

2017-10-02 15:23:21 229

原创 1021 石子归并-51Nod

N堆石子摆成一条线。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的代价。计算将N堆石子合并成一堆的最小代价。例如： 1 2 3 4，有不少合并方法 1 2 3 4 => 3 3 4(3) => 6 4(9) => 10(19) 1 2 3 4 => 1 5 4(5) => 1 9(14) => 10(24) 1 2 3 4 => 1

2017-10-02 11:27:47 185

空空如也

空空如也