Bahuia-CSDN博客

转载 Stanford-parser依存句法关系解释

文章转自：http://blog.csdn.net/lihaitao000/article/details/51812618计算机语言学家罗宾森总结了依存语法的四条定理：一个句子中存在一个成分称之为根（root），这个成分不依赖于其它成分；其它成分直接依存于某一成分；任何一个成分都不能依存与两个或两个以上的成分；如果A成分直接依存于B成分，而C成分在句中位于A和B之间，那么C或者直接依存于B

2017-10-30 10:01:05 3163

原创 HDU 4421 2-SAT

题意：题目链接：http://acm.split.hdu.edu.cn/showproblem.php?pid=4421 按照题目所示的转移方式，问是否存在一个a数组可以转译成b矩阵。思路：因为都是位运算，b[x][y]只会由两个bool变量影响，其实只要将每个数字按位拆开来进行2-SAT即可。#include <bits/stdc++.h>using namespace std;const

2017-10-13 16:04:59 788

原创 Gym 101201B dp

题意：题目链接：http://codeforces.com/gym/101201/attachments 给出一个迷宫，以及一串上下左右的指令，机器人需要按照指令前进，问最少添加以及删除多少指令可以令机器人顺利从起点走到终点。如果机器人顺着指令遇到障碍或者边界，那么自动忽略这条指令留在原地。思路：好题。 dp[i][x][y]表示在前i个指令完成之后，机器人处于(x,y)的最少增加删除代价。

2017-10-13 15:59:09 787

原创 Gym 101201F 2-SAT

题意：题目链接：http://codeforces.com/gym/101201/attachments 给出一个方格，其中若干点上有灯，每盏灯可以选择在一行或者一列照亮以自己为中心长度为2*r+1的区间，但是要让同一行之间以及同一列之间的灯不能有照亮的重叠区域，问是否可行。思路：每盏灯有两种选择，2-SAT裸题。代码：#include <bits/stdc++.h>using namespac

2017-10-13 15:44:18 582

题意：题目链接：http://acm.split.hdu.edu.cn/showproblem.php?pid=5361 有n个点，每个点有一个可以到达点的范围[l,r]，传送一次距离为c，问从点1到所有点的最短距离是多少。思路：注意到从点1开始，如果利用优先队列选出将要到达的最近的点，那么每个点最多只需要更新一次，如果用传统的最短路，会浪费大量的时间在扫描那些已经更新过的点上，因此需要利用并查集

2017-10-11 15:29:14 720

原创 UVA 11987 并查集（虚拟节点）

题意：题目链接：https://vjudge.net/problem/UVA-11987 对集合三种操作，一种合并，一种求集合元素个数和总和，另一种是将其中一个集合的元素移动到另一个集合，输出询问个数和总和。思路：并查集，主要是转移这个操作，如果单纯将pa[x]=Find(y)，那么以x为祖先的结点都会被转移，因此这里需要为每个集合设置虚拟节点，所有集合的根一定都是虚拟节点，所有操作也都针对虚拟节

2017-10-10 17:27:46 528

原创 Gym 101490K dp

题意：题目链接：https://vjudge.net/problem/Gym-101490K 一个环上有L个点，每个两个相邻的点相距1个单位，现在要在这些点上插旗子，要求长度为S的区间内至少要有一个旗子，问方案数。思路：dp[x]表示长度为x的区间，首尾位置都插旗的合法方案数。很显然dp[i]=dp[i-1]+dp[i-2]+…+dp[i-s]；至于环如何处理，首先取一个任意的起点，然后枚

2017-10-08 16:17:29 477

原创 HDU 5618 CDQ分治（三维偏序）

题意：题目链接：http://acm.split.hdu.edu.cn/showproblem.php?pid=5618 给出n个有序对(a,,b,c)，对于每个(ai,bi,ci)找到满足aj <=ai，bj<=bi，cj<=ci的有序对有多少个。思路：典型的三维偏序问题，可以用CDQ分治来解决。首先将有序对按照a的大小排序，这样对区间[L,R)进行分治的时候就可以默认左半部分[L,M)的a

2017-10-06 22:49:13 601

原创 HDU 5649 线段树+二分

题意：题目链接：http://acm.split.hdu.edu.cn/showproblem.php?pid=5649 n个数的排列，两种操作，一种将[L,R]区间内的数递减排序，另一种将[L,R]中的数递增排序，问最后第k个位置的数字是多少。思路：好题。因为最后考虑的只是第k个位置的数字，二分答案。每次将序列中比x大的都标记为1，其余包括x标记为0，每次排序前，先查询区间中有多少个1和

2017-10-04 11:40:03 638

原创 HDU 4605 主席树

题意：题目链接：http://acm.split.hdu.edu.cn/submit.php?pid=4605 一棵二叉树，根节点为1，每个节点都有一个权值，给出q个询问，每次询问给出v和x，问数字x从根节点落下，到节点v的概率是多少。其中数x假如到达一个节点u： 1. 如果x==w[u]，则x留在该节点。 2. 如果x>w[u]，则x有1/8概率往左子树走，有7/8概率往右子树走。 3

2017-10-03 20:41:55 464

原创 HDU 5919 主席树

题意：题目链接：http://acm.split.hdu.edu.cn/showproblem.php?pid=5919 给出n个数字，q个询问，询问在[L,R]区间内，如果有k个不同的数字，那么第(k+1)/2个数字第一次出现的下标是多少。思路：一开始以为和spoj的那题一样，只要主席树计算区间种类数，然后二分即可，但是一直T。其实不用二分，如果按照计算种类数的方式建立可持久化线段树，那么每

2017-10-02 10:03:13 641

原创 SPOJ DQUERY 离线树状数组or主席树

题意：题目链接：http://acm.sdibt.edu.cn:8080/vjudge/problem/viewProblem.action?id=13725 给出n个数，问区间[L,R]中有多少不同的数。思路：经典题。可以离线+树状数组，离线保存查询，按照r排序，用last数组保存每个数最接近当前询问r的位置。也可以主席树，从右到左建树，pos保存每个数字的当前最左位置，每次在新版本的线

2017-10-01 22:34:58 448

原创 HDU 4417 主席树

题意：题目链接：http://acm.split.hdu.edu.cn/showproblem.php?pid=4417 给出n个数和m个询问，询问区间[L,R]中小于等于k的数有多少。思路：常见的主席树思路；但是在处理区间[L,R]的离散化时没有考了离散之后L大于R的情况，结果一直莫名其妙MLE了很久。代码：#include <bits/stdc++.h>using namespace s

2017-10-01 20:23:36 468

原创 HDU 3943 二分+数位dp

题意：题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3943 在区间[P,Q]中找到第k大的数位上还有x个4以及y个7的数。思路：二分+数位dp。代码：#include <bits/stdc++.h>using namespace std;typedef long long LL;LL p, q, x, y, k;int a[25];LL d

2017-09-30 08:43:12 489

原创 hihocoder 1259 推公式+数位dp（非dfs写法）

题意：题目链接：http://hihocoder.com/problemset/problem/1259?sid=1199888 给出f(x)的定义，给出n和k，求f(1)~f(n)中模k==（0~k-1)的个数的异或和。思路：首先推公式，可以得到f(2n)=f(n)*3,f(2n+1)=f(2n)+1；根据公式，写几个例子可以发现，对于一个数，比如5，二进制形式(101)，可以发现f(5)=

2017-09-29 16:36:31 536

原创 HDU 5896 CDQ分治+NTT

题意：题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5829 求n个点能构成的有环图的数目。思路：母题是HDU 5552：http://blog.csdn.net/Bahuia/article/details/78109301 两题思路一致，只是改变了所求结果，推导发生变化。代码：#include <bits/stdc++.h>using nam

2017-09-27 09:34:01 544

原创 HDU 5552 CDQ分治+NTT

题意：题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5829 统计n个点可以组成多少种不同的有环连通图，其中每条边可以染成m种颜色。思路：分别统计f(n)为n个点的连通图数目，g(n)为n个点能构成的图数目，h(n)为n个点能构成的树的数目，然后递推出公式，发现是个卷积形式，可以用FFT加速，这里会爆精度，改用NTT。代码：#include <bit

2017-09-27 09:30:07 833

原创 hihocoder 1580 枚举+dp+RMQ

题意：题目链接：http://hihocoder.com/problemset/problem/1580?sid=1195305 给出一个矩阵，让你将其中一个数的值变成p（必须修改一个，且仅能修改一个），然后求最大子矩阵和。思路：2017北京网络赛C题，这题最后没A真是好气啊。一开始被带偏榜，花了太多时间在D上，结果一直wa，后来C题过得多了再来看C题，秒出思路，然后一直WA到结束。只不过

2017-09-24 10:58:18 664

原创 HDU 4511 AC自动机+DP

题意：题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4511 中文题。思路：常见的思路，不过要注意x和y要用double，否则溢出。代码：#include <bits/stdc++.h>using namespace std;const double INF = 1e20;const int MAXN = 505;const int K =

2017-09-22 17:29:24 533

原创 HDU 5769 后缀数组+二分

题意：题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5769 求一个字符串中包含字符x的不同子串有多少个思路：处理出height数组，对于每个后缀i，二分得出i之后的第一个字符x的位置，max(x,sa[i]+height[i])之后的位置结尾得到的字符串都是唯一的，相见代码。代码：#include <bits/stdc++.h>using nam

2017-09-22 15:57:30 475

原创 POJ 2774 （最长公共子串）后缀数组+二分

题意：题目链接：http://poj.org/problem?id=2774 求两个字符串中最长的公共子串思路：将两个串合并成一个，然后二分长度，判断时要看同一组中属于前一串的后缀喝属于后一串的后缀是否都存在。代码：#include <cstdio>#include <cstring>#include <algorithm>using namespace std;typedef long

2017-09-22 15:21:56 375

原创 SPOJ DISUBSTR 后缀数组

题意：题目链接：https://vjudge.net/problem/SPOJ-DISUBSTR 求一个字符串中不相同的子串的个数思路：后缀数组水题代码：#include <bits/stdc++.h>using namespace std;typedef long long LL;const int MAXN = 1005;const int INF = 0x3f3f3f3f;int t

2017-09-22 14:40:04 214

原创 2017西安网络赛G题分类暴力

题意：题目链接：https://nanti.jisuanke.com/t/17120 给出一棵树，每个节点的有个价值，给q个询问(u,v,k)，若结点u到v的路径上的点为a0,a1,a2…am，问其中a0^ak^a2k^…apk的结果。思路：套路，按照k分类，首先求出LCA，k大于等于250时直接暴力求解，k小于250时保存从根结点到每个结点的异或和sum[u][x]，x表示每次走x步。代码：#i

2017-09-21 19:10:10 423

原创 HDU 6194 后缀数组+单调栈

题意：题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6194 找到一个字符串中恰好出现k次的子串的数目。思路：计算出height数组，根据height数组进行操作，因为子串恰好出现k次，很显然需要找到一个长度为k-1的区间，这个区间要满足区间两边的height都比区间内的最小值要小，这样利用单调栈求出每个height左右两边第一个比height小的位

2017-09-21 15:45:51 426

原创 POJ 3261 后缀数组+二分

题意：题目链接：http://poj.org/problem?id=3261 在一个字符串S中求至少出现k次的最长的字符串的长度。思路：经典题，后缀数组+二分注意此题需要离散化。代码：#include <cstdio>#include <vector>#include <algorithm>using namespace std;const int MAXN = 2e4 + 10;c

2017-09-20 19:06:23 258

原创 UVAlive 4975 Manacher+枚举

题意：题目链接：https://vjudge.net/problem/UVALive-4975 给出一个字符串，求形如XYXY的最长子串长度，其中Y时X的逆字符串。思路：一开始没仔细想上来就二分hash，后来发现并不满足二分条件。正解是manacher预处理，然后暴力枚举长度，枚举时有讲究，显然长度一定时4的倍数，然后再看左右两个子串的回文串范围。代码：#include <bits/stdc+

2017-09-20 15:25:28 334

原创 UVAlive 3490 AC自动机+（整数）高斯消元

题意：题目链接：https://vjudge.net/problem/UVALive-3490 给出一个字符串S和前n个英文大写字母，组成一个字符串，当构造出子串S时停止，则该字符串期望长度是多少。思路：AC自动机+高斯消元，与HDU 5955一个套路：http://blog.csdn.net/bahuia/article/details/53034010 这题坑的时直接用double的高斯消元

2017-09-20 10:43:15 526

原创 UVA 10829 后缀数组+技巧计数

题意：题目链接：https://vjudge.net/problem/UVA-10829 找出一个字符串中，形如UVU的且V长度为g的子串的个数，其中U非空。思路：可以用后缀数组也可以直接暴力，但该题重点是在计数方式上。后缀数组可以计算两个起点i,j的LCP，但是要保证中间要夹上正好长度为g的V，这需要枚举i,j，复杂度为O(n^2)，太高了。这里有一个技巧，考虑假设U的长度为L，那么对于

2017-09-20 09:15:36 489

原创 UVA 11488 字典树

题意：题目链接：https://vjudge.net/problem/UVA-11488 给出n个串，找出一个串的集合，使得集合中所有串的最长公共前缀与集合元素的个数的乘积最大。思路：字典树简单应用代码：#include <bits/stdc++.h>using namespace std;typedef long long LL;const int MAXN = 5e4 + 10;stru

2017-09-20 08:54:30 468

原创 POJ 1743 后缀数组+二分

题意：题目链接：http://poj.org/problem?id=1743 求一个串中长度最长两个不重叠的相似子串的长度，相似定义为两个串长度相同，且相同下标的数字差相同。如：1，3，2和7，9，8，差都是6。思路：两个串的相似，还可以理解为每个串相邻的两个数字差都相同，因此要把原串转化成差的串，然后对新串求height数组，二份答案，每个答案x，对height分组，看每一组中下标差是否大于等于

2017-09-19 11:07:36 434

原创 HDU 6208 AC自动机

题意：题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6208 给出n个字符串，要求找到一个字符串包含其他所有的字符串。思路：肯定是最长的那个字符串，如果存在两个不一样的额且长度都是最长的字符串，就肯定找不到。否则就用AC自动机跑一遍所有的串即可。代码：#include <bits/stdc++.h>using namespace std;#def

2017-09-18 15:59:06 834

原创 HDU 6215 链表

题意：题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6215 给出n个数的序列，每一轮需要删除当前这一轮比左边的数小或者比右边的数大的数字，然后再将剩下的部分合并，进行下一轮。最后序列变成非递减时结束，输出最后序列。思路：很显然每一轮就删掉一段递减的序列，比如，{1,2,3,7,6,5,8}删除的就是7,6,5，可以发现，每次删除一段后只会对这一段左

2017-09-18 15:25:55 827

原创 HDU 4821 字符串哈希

题意：给出m和L和一个字符串s，要求在s中找到一种子串，满足长度为m*l，且分成m段长度为l的小子串可以使得任意两个小子串不完全相同，问一共有多少个这样的子串。思路：字符串哈希。预处理出每个长度为L的子串的哈希值，并按照其起始位置%L的结果存在L个vector里，对于每个vector只要单纯看连续m个数是否有相同的数字即可，如果没有就更新答案。代码：#include <bits/stdc++.h

2017-09-16 10:29:26 317

原创 HDU 6199 dp

题意：题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6199 AB两个人玩游戏，n个数，从左到右依次选取。第一个人可以选择1个或者2个数，假设某一轮一个人选择了k个数，那么下一轮另一个人就要选择k个或者k+1个数，如果剩下的数字不够就不能选择，游戏终止。此时比较A-B的大小，问两个人都采取最优策略，都尽可能让自己所获得的数的总和大，最后A-B的最大值

2017-09-15 21:18:37 364

原创 HDU 6201 树形dp

题意：题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6201 给一棵n个节点的树，每个节点和边都有权值，求一条价值最大的路径。价值为该条路径终点的价值 - 起点的价值 - 路径上边的权重和。思路：树形dp，分别考虑祖先与后代以及兄弟之间的关系即可。细节比较多，详见代码。代码：#include <bits/stdc++.h>using namespa

2017-09-15 20:49:02 361

原创 HDU 6138 AC自动机

题意：题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6138 给出n个字符串，m个询问，询问x和y两个字符的最长公共子串的长度，而且要求这个子串为这n个字符串中任意一个（或多个）的前缀。思路：AC自动机。每个节点end数组都保存当前节点到根节点的距离。将n个字符串保加入AC自动机。然后对x在自动机上跑一边标记节点，然后再对y跑一遍，遇到标记的节点

2017-09-15 20:42:55 315

原创 HDU 4080 字符串哈希+二分

题意：题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4080 找到一个字符串中出现超过m次的最长的子串，以及该子串最有出现的起点。如果有多个相同的就选择最右端出现的。思路：二分长度，然后哈希统计子串出现次数。代码：#include <bits/stdc++.h>using namespace std;typedef unsigned long l

2017-09-15 20:35:17 521

原创 EOJ 3329 dp

题意：题目链接：http://acm.ecnu.edu.cn/problem/3329/ 中文题。但是题意有点迷，在计算子集个数时，对于同一个子集只计算一次，如{1,2,3,3}中存在两个{1,2,3}，但是计算的时候只算一个{1,2,3}。思路：dp，需要点优化，因为这里数的范围只有3500~4500，所以可以存这些数字的个数，注意到这里异或产生的质数最多只到8191。 dp[i][j]表示到

2017-09-15 20:29:01 394

原创 2017乌鲁木齐网络赛D题区间dp

题意：题目链接：https://nanti.jisuanke.com/t/16953 长度为L的线段上有n个点，每个点保存了该点的位置以及可以访问该点的最早时间，走过单位1的距离需要单位1的时间，现在需要将这n个点都访问，问所需的最短时间。（只有在规定访问时间后访问点才算访问成功）。思路：区间dp，很巧妙。与一般的区间dp不同的是，该题是长的区间向短的区间dp。dp[i][j][0/1]表示将

2017-09-13 19:28:36 521

原创 HDU 4758 AC自动机+状压dp

题意：题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4758 一个矩形从左上角走到右下角，向右移动用R表示，向下移动用D表示，要求满足移动序列中含有给出的两个规定子串，问一共有多少种方案？思路：还是经典的AC自动机+状压DP思路，类似HDU-2825：http://blog.csdn.net/bahuia/article/details/771490

2017-09-07 17:17:12 447

空空如也

空空如也