wookaikaiko的博客

转载 卡特兰数详讲

点击打开参考原博客  一、关于卡特兰数       卡特兰数是一种经典的组合数，经常出现在各种计算中，其前几项为 : 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 656412...

转载 容斥原理详解

翻译：vici@cust对容斥原理的描述容斥原理是一种重要的组合数学方法，可以让你求解任意大小的集合，或者计算复合事件的概率。描述       容斥原理可以描述如下：  ...

原创 Codeforces Round #247 (Div. 2) C. k-Tree

*1600第二题，慢慢做，慢慢想。题目链接：点击打开原题目题意：给一个数字k，用它构造一棵树，构造方法是，从根节点开始往下，每个节点都有k个子节点（所以这棵树的深度是无限的，一开始没有读到这一点一直想不通样例），每条连接子节点的边的权值从1~k，现在要求从根节点出发的所有路径中，路径权值总和为n，且路径上至少有一条边的权值大于等于d的方案有多少种。思路：用 dp[i][j] 表示当前走...

原创 Codeforces Round #260 (Div. 1) A.Boredom

今天是下定决心好好练DP的第一天，从1600的DP开始做起。题目链接：点击打开原题目。题意：给一个长度位n的整数序列，每次选择一个数字删除，删除这个数的同时比这个数大1和小1的数全部被删掉，每次得到的值就是你当前选择的这个数的价值，问能得到的值的总和最大是多少。思路：在这个序列里面选数的限制条件就是当你选了a[i]，你就不能选择a[i]+1和a[i]-1了，因为已经在你选择a[i]的时...

原创 Gym 100203 I. WIN（网络流最大流）

题目链接:http://codeforces.com/gym/100203/problem/I题意：给一个由'W','I','N'三种字母组成的n*m的矩阵，现在要从中截取 'WIN' ，要求'I'一定要在'W'和'N'的中间，问最多能截取多少个'WIN'。当然截取的意思就是一个字母用了一次就没有了，一开始以为是搜索，后来wa了几次以后反应过来搜索是不可能搜索的，其实这是一道最大流的题，只...

转载 幂级数展开公式

原创 HDU6357——Hills And Valleys

点击打开原题目题意：给一串由n个数字组成的字符串，选择其中一个区间进行翻转，要求翻转后该字符串的最长非降子序列长度最长，输出这个最长非降子序列的长度以及翻转的区间的左右端点。题解：由于n的大小为1e5，如果直接枚举a中的翻转位置的话，那么复杂度肯定不行，但是这里有一种十分巧妙的做法。首先如果是求一个只有数字的串中的最长上升子序列长度的话，那就是这个串与 "0123456789" 这个串的最...

原创 hdu——6319- Ascending Rating

6319- Ascending Rating题意：有一个长度为n的数字序列，只给出前k项，后n-k项由给出的公式从前一项计算出，求每个长度为m的区间中的最大值和以区间第一个数开头的上升序列的长度与区间第一个数的位置下标的异或值的和分别是多少？通俗的讲，主要就是求区间最大值和固定起点的区间上升序列的长度。题解：本题考虑从后面往前面用滑动窗口加双向队列求解。从最后一个开始，如果当前的数比它后面...

原创 hdu 6321-Dynamic Graph Matching

6321-Dynamic Graph Matching题意：给定一个n 个点的无向图，m 次加边或者删边操作。在每次操作后统计有多少个匹配包含k = 1, 2, ..., n/2 条边。题解：状压DP。先放官方题解，我觉得讲的蛮清楚的。我再说一下我的理解，首先S表示的是一个集合，里面表示的是哪个点被选了哪个点没有，因为n最多10，所以我们可以用二进制来表示一个集合里面的情况，第i位...

原创 bzoj 2565——最长双回文串（manacher）

点击打开原题目链接题意：给一个字符串，求这个字符串中最长的双回文串的长度。（双回文串：一个能被分为两个回文串的字符串。）题解：最长回文串当然是直接上manacher，但是这道题和普通的manacher有区别，因为要判断的是两个连续的回文串的最长长度。首先还是用最原始的manacher处理出以每个位置为中心的回文串的长度len[i]。因为要求两个连续的回文串，那么一定满足第一个回文串的最后一...

原创 牛客多校第三场——E.Sort String

题意：给一个字符串S，定义一种操作为：从字符串首位置(0)开始将S0~Si的字符移到末尾得到一个新的字符串，直到每一个位置都遍历完成，如：abab—> (0开始)abab —>(0~1位置) baba —>(0~2位置) abab —>(0~3位置)baba所有得到的新的字符串从0~n编号，然后将完全一样的字符串分到一个组里面，要求输出有几个组，和每个组里面有几个字...

原创 牛客多校第三场

H.Diff-prime Pairs题意：给一个数n，求1~n有多少对数满足  和  都是质数，当 i1 ≠ i2 or j1 ≠ j2时(i1, j1) 和 (i2, j2)看做不同的一对数。题解：首先，两个质数的最大公约数是1，那么除以1以后是自己本身依然也是一个质数，所以任意两个质数之间都是满足要求的，这里得到了第一部分答案，假设1~n有num个质数，ans1=C( num,2)。那...

原创 2018牛客多校第二场

J.farm（二维树状数组）题意：给一个n*m的矩阵，每个格子里面都有一种植物（类型可能不同），进行q次操作，每次往给出的区域里面浇灌一种类型农药，如果农药和植物的类型不一样这个植物就会死掉，问进行了所有的操作以后死掉的植物的种类。题解：本来以为用二维树状数组或者线段树都会T所以比赛时候就没有做，但赛后发现都是可行的。每次喷农药的时候将这个区间内的植物的贡献都加一。 然后对于[1,n*m]...

原创 2018hdu多校第二场（hdu6312, hdu 6318, hdu 6315）

hdu 6312——Game题意：给一个数字n，就代表有一个1~n的序列，A和B两个人分别可以对这个序列进行操作，每次操作可以删去一个数及这个数所有的因子，轮到谁时谁无法再进行操作谁就输了，也就是刚好删除最后一个数的人赢。A先走，问A能不能赢。一看就能知道这是一道博弈论的题，先分析一下这个规则，从1-n，我们可以先不看1，因为删除任何一个数都可以顺便把1删除了，那么只从2~n中选择就一定有...

转载 BZOJ 1005 明明的烦恼

 题目大意 自从明明学了树的结构，就对奇怪的树产生了兴趣……给出标号为 1 到 N 的点，以及某些点最终的度数，允许在任意两点间连线，可产生多少棵度数满足要求的树？ Input　　第一行为 N(0<N<=1000)，接下来 N 行，第 i+1 行给出第 i 个节点的度数 Di，如果对度数不要求，则输入 -1Output　　一个整数

转载 莫队算法详解

[点击打开原博客](https://blog.csdn.net/thinfatty/article/details/72581276%20%E7%82%B9%E5%87%BB%E6%89%93%E5%BC%80%E5%8E%9F%E5%8D%9A%E5%AE%A2)莫队算法...

原创 2018杭电多校第一场(hdu 6299,hdu 6301)

hdu6299  Balanced Sequence题解：因为是从子序列里面选择括号，所以只要前面有一个左括号‘（ ’后面有一个右括号，那就能组成一个合法的括号组合，所以对字符串进行重新排序的时候，要满足让左括号尽量在前面，右括号尽量在后面，而一个字符串自己原串中能组成合法的括号就不用再次判断了。所以我们对每个字符串需要统计的有三个东西，它里面能配成对的对数，落单的左括号数，落单的右括号数。然...

原创 牛客多校第二场 G-transform

题意：在一条线上有n个点，第i个点的位置为Xi，并且这个点上有ai个物品，把一个物品从xi位置搬到yi位置的花费是2*abs(xi-yi),问在总花费不超过T的情况下最多能把多少个物品搬到同一个位置。题解：因为花费是由所有点到一个点的距离决定的，所以最后的答案一定是在一个连续的区间里面尽可能多的讲两边的物品移到中位点上。在知道总物品数量以后，可以考虑对答案进行二分，判断每个查找的答案是否合法。...

原创 HDU 6138——Fleet of the Eternal Throne（AC自动机）

题意：给出n个字符串，m次查询，每次查询给两个字符串的编号，输出满足是其它字符串的前缀（一个就行）的这两个字符串的最长公共子串的长度。题意是比较简单易懂了。题解：首先多个字符串又牵涉到匹配找公共子串的问题，就应该考虑AC自动机了，但这道题的问题不只是找最长公共子串，还要求这个子串是其它字符串的前缀。这里可以利用ac自动机fail指针的特点，回忆一下，fail指针是怎么来的，在trie树上查找单...

原创 位运算小技巧总结

1.    获得int型最大值int getMaxInt(){        return (1 << 31) - 1;//2147483647， 由于优先级关系，括号不可省略}第二种写法int getMaxInt(){       return ~(1 << 31);//2147483647}第三种写法int getMaxInt(...

原创 2018牛客多校第一场

E.Removal题意：给一个长度为n的数字序列，每个数字大小都不超过k，要删除其中m个数字问有多少种删除后的序列不相同的方案。题解：DP。设dp[i][j]表示从1~i 删除j个数字的方案有多少种。首先初始化，很容易想到dp[i][0]=1,同时dp[i][i]=1；转移方程是：dp[i][j]=dp[i-1][j]+dp[i-1][j-1] (前i-1个数字中删除j-1个再删除第i...

原创 2018牛客多校第一场

J-Different Integers题意：有n个数，q次查询，每次查询给出 L , R 两个数，求1~L 和R~n两个区间内共有多少不同的数。此题和SPOJ 3267相似，只是SPOJ 3267是直接求区间(L~R)内不同的数的个数，所以我们可以换个角度看看这道题的要求，如果将给出的数字序列扩大一倍，也就是在将整个序列复制到原序列后面，这样我们查询的原序列中的1~L和R~N就变成了新的...

原创 hdu 1298——T9（字典树）

题意：模拟手机九宫格输入法，输入w个字符串并给出每个字符串出现的次数，然后输入p组查询，每组的查询由一串数字组成，每输入一个数字输出到当前为止最有可能的字符串（如果不存在就输出MANUALLY），出现次数越多的字符串可能性越大。题解：看题意肯定是要在字典树上操作的，但是与一般字典树不同的是这里多了一项出现次数。并且查询的时候一个数字可能同时代表几个字母，要找出其中出现次数最多的一个。所以首先在...

原创 组合数（power oj-2419）

题意：给你 a,n,m, 求a^( C(n,m) ) )% mod，mod = 999911659。题解：组合数取模再加上题目的数据范围是肯定要用lucas定理的，但是根据 欧拉定理可知ans = a^( C(n, m) %(mod-1) + mod-1 ) %mod,因为这里mod是一个质数，所以mod-1就不是一个质数，而lucas要求取模的模数一定是质数，所以不好直接用lucas定理。那...

原创 HDU1520——Anniversary party（树形DP）

题意：有n个人，他们之间有上司和下属关系，每个人有自己的价值，现在要选一部分人使其满足上司和下属不同时被选到的情况下价值总和最大。更直接的讲就是，在一棵树中选价值总和尽量多的节点但是不能同时选到一个节点和它的直接父节点。题解：因为这里要求选的点的个数是不限定的，只需要满足价值总和尽量大。而对于每个点来说，只有选和不选两种状态，这种情况其实和01背包有一些类似，所以我们可以用背包的思想来做。...

原创 POJ - 3080——Blue Jeans （KMP）

点击打开题目链接题意：给m个长度不超过60的字符串，输出这些字符串共同的最长公共子串。（多组输入）当然，题目给的数据m<=10&&字符串长度不超过60，所以可以直接暴力做。这里只讲用KMP来写的解法。题解：枚举第一个串的所有子串，然后用KMP算法去匹配这个子串和所有其它串看是否在其它串中都出现过，如果都出现过那肯定就是大家共同的公共子串。为了简单我们可以直接从最长的往...

原创 51nod 1677——treecnt

题意：给你n个结点，n-1条边，要从这n个结点里面选出k个结点，再选出最少边使这些结点之间相互连通，问对于所有选择k个结点的最小选择边数的总和是多少。题解：因为每次选k个点其实是固定了的，所以撇开要确定的边，每次要选的k个点就是一个组合数问题，那怎么把点和边联系起来呢？对于任意一条边，它要不要被选入作为连接点的边是由它两边的点决定的。当只有这条边左边或者右边的点被选入时，这条边是不需要的，只有...

原创 Codeforces Round #469 (Div. 2) ——D. A Leapfrog in the Array

题意：1~n的数按顺序间隔排列，(1  2  3  4  ...  n) 中间的空格也要占一位，现在有一种操作，每次把序列最后面那个数移到离它最近的空格里面，直到前n个位置都被填满，没有空格了。给出q次查询，每次输入一个数 Xi，要求输出按照所给操作完成后的Xi位置上的数是多少。题解：题目上给的数据范围超级大(1e18),所以肯定是不能模拟的，一定有什么规律在里面。首先很容易发现，不是根本不用...

原创 Codeforces Round #469 (Div. 2)——C. Zebras

点击打开原题链接题意：给你一个只由0和1组成的字符串，求能分成多少个由0开头0结尾并且中间01交替排列的子序列。这里题意需要注意的是，如果原字符串中由1开头或由1结尾是不合法的，如果有两个1挨着也是不合法的。题解：由于要求输出的是每个子序列的长度以及其中数字在原字符串的位置，所以可以考虑用vector的二维数组储存分成的每个序列的元素的下标，每个一维的大小就是序列的长度。要分成的序列一定是...

原创 Cheapest Palindrome（POJ-3280）

题意：给一个长度为m的字符串s，其中含有n种字母，给出添加和删除某种字母所需要的代价，你可以通过添加或删除某些字母来使这个字符串变成回文串，求使当前这个字符串变成回文串需要的最少代价是多少。题解：典型的区间DP，可以通过小区间一点一点的推到大区间。定义dp[i][j]表示把区间(i,j)编为回文串所需要的最小代价，那么我们可以从以下几个方面来分析。首先对于一个区间dp[i][j]来说，如果s[i]...

原创 题解一

A. Buns（多重背包/01背包）点击打开题目链接题意：有n克面团，m种可以做不同馅饼的馅料，第i种馅料有ai克，可以用bi克馅料和ci克面团做一个价值为di的馅饼，也可以不用馅料只用c0克面团做价值为d0的饼。问用现有的面团可以做的面饼的价值最多是多少。因为是英文题所以可能读起来有一定难度，但是读懂了以后结合样例看一下就没问题了。解法：简单的多重背包问题，背包容量为面团的重量，有m种可供选择的...

原创 Codeforces Round #495 (Div. 2)-C. Sonya and Robots

题意：题目描述其实蛮复杂，反正就是找给出的序列里有多少组不同的<ai,aj>(i<j),a[i]和a[j]可以相同。题解：超级简单，只需要从后往前统计到每个位置为止有多少种不同的数，最后再从前往后遍历一次，对于每个不同的ai只需要找后面有多少个不同的bi就行了，也就是加上他后面不同的数的个数。附上代码：#include<bits/stdc++.h>typedef lo...

原创 HDU4638 Group （树状数组+离线处理）

在网上看了好多大神的博客，反正自己是绝对想不到怎么做的，好不容易感觉自己迷迷糊糊懂了个大概，就先记下来，免得以后忘记。有的地方思路很勉强甚至是错的，欢迎大家指教纠正。题意：给你一个1~n的排列序列，m次查询，每次给出一个区间，求这个区间内使每个分组里面的数字都是连续的最小的分组方法。（题目链接：点击打开原题链接）题解：因为求的是区间内的连续数字的分组，那么对于当前要查询的区间来说，它前面的数字就是...

原创 Codeforces Round #460 (Div. 2) C. Seat Arrangements

蛮早之前的cf的题，突然翻到了发现自己比赛过程中没做出来下来也并没有把它补出来，感觉div2我不应该做不出来啊哈哈哈蜜汁自信，就把这题补了。题意：给一个n*m的矩阵里面含有'*'和'.'两种字符，要你找横行和竖行中长度不小于k的连续' . '有多少种。记得当时我是以为要写dfs，也不知道为什么我这种dfs根本没入门的人有勇气现场写dfs，现在看一看完全就是暴力模拟就能做的题，因为题目要求必...

原创 Codeforces Round #340 (Div. 2)-E- XOR and Favorite Number(莫队算法)

点击查看题目题意：给你一串数字，若干个查询，每次查询的值是给出的查询区间里的子区间的异或值为k的个数。题目要求什么很好理解，直接说解法，由于本题只有询问没有修改，所以比较适合离线处理，而莫队算法是离线处理一类区间不修改查询类问题的算法，所以这里我们采用莫队算法来解这道题，莫队算法，一种优雅的暴力算法，算法本身非常的简单易懂，不懂的可以随便学习一下。明白了莫队算法以后，基本就可以做这道题了，...

原创 拓扑排序-HDU1285( 确定比赛名次 )

点击打开题目链接又是一道拓扑排序模板题，和POJ2637几乎一模一样的。题意就不用说了吧，就是中文题目要求什么也很清楚。这里要说一下，这道题除了要求输出拓扑排序后的顺序，还额外要求在符合题目条件的情况下，输出编号小的队伍在前面，这里我们可以用优先队列来实现，采用内定义优先级里面的最小值优先或者自定义一个优先级方式都行。AC代码:#include<stdio.h>#include<...

原创 拓扑排序模板题-POJ 2367(Genealogical tree )

点击打开题目链接本题是拓扑排序的模板题，如果还不知道什么是拓扑排序的同学，可以参看这位大神博客里面的手动模拟拓扑排序的过程，相信看完以后你就会懂了什么是拓扑排序了。（链接：https://blog.csdn.net/qq_35644234/article/details/60578189）回到这道题，都说了是一道模板题，所以肯定不是很难，但是题面是非常的磨人的，不仔仔细细看根本不知道要求什么，样例...

原创 ACM-ICPC 2017 Asia Xi'an——LOL(DP)

题意:模仿游戏LOL,己方选择5个英雄(能选择的前提是已经买了这个英雄)自己这一方选的英雄肯定不能一样,敌方也选择5个英雄但是可以随便选喜欢的然后己方和敌方可以分别各禁止5个英雄,总的英雄种类数是100个.题解:题意具体化到给出的输入数据来说就是给5行只由0和1组成的字符串，在每一行选择一个1,各行选的1不能在同一列。可以用DP来做，先把第一行的可选方案处理出来，也就是第一行...