5 aozil_yang

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 6k+

POJ 3580 SuperMemo (Splay)

思路:区间的一系列操作, 还有翻转什么的,显然Splay主要说一下 那个循环右移的操作吧次数先对总长度取模, 因为相当于有循环节。然后  这个操作 相当于 把一个区间分成两个子区间, 把后面挪到前面。假设两个区间是 [s1, e1]和 [s2, e2]那么先把s2-1 转到根, e2+1 转到根的下面, 将e2转到e2+1的下面,将 e2+1的左子树 切下来。这样就把后

2017-10-12 16:52:51

HDU 3487 Play with Chain(Splay)

题意:操作1:将区间[a,b]切下来放到c位置后面。操作2:将区间[a,b]翻转。输出最后的数列。思路 :显然Splay。翻转就是加一个 翻转标记即可。正常操作。简单说一下 切割区间。先把a-1 转到根, 在把b+1 转到根的下面, 将根右儿子的左儿子切下来(保证子树是区间[a,b])pushup一下在把c转到根, c + 1 转到根的下面, 根右儿子 左儿

2017-10-10 10:29:58

HDU 6196 happy happy happy (2017沈阳网赛 - 搜索 + dp + [黑科技。。。])

题意:儿子和爸爸选牌, 每一次每个人只能从最左边选择或者在最右边选择, 儿子的决策是 选左边 和 右边最大的那个位置, 如果一样大, 选择左边, 爸爸的决策是为了让儿子赢, 问你 如果儿子能赢 爸爸与儿子的最小分数差是多少, 如果无论如和 爸爸都赢儿子 输出The child will be unhappy...思路:很乱搞的一个题目。。我们先预处理出两个dp 来, dp1[i][

2017-09-14 14:26:14

HDU 6199 gems gems gems (2017沈阳网赛 - dp)

题意:有一堆数, 两个人轮流取, 只能从最左边开始选择, 假设上一个人选了k 个牌, 那么下一个人只能选择k 或 k + 1 张牌。 第一个人得分为A, 第二个人得分为B, 求A- B, 每个人的策略都想使自己得分尽可能的高。思路:是UVA 10891 的变形把。我们令dp[i][j] 表示从i 位置开始选择, 能选j 个牌的最大分数差值。那么直接根据j 来转移即可。总共两

2017-09-13 19:31:39

HDU 6202 cube cube cube (2017沈阳网赛 - 魔方模拟)

题意:给你一个八面八轴的魔方, 问你是否 3步内还原。思路:真的太恶心的一个题目。。。。其实理清了 很 简单, 虽然写起来很麻烦。看题目中的图片描述的话, 底面是可以转的, 且有八个面, 首先就有8种旋转底面的操作。图中还介绍了旋转中间轴, 中间轴的话 是 两个面确定一个中间轴, 一共8面, 因此有四个中间轴。因此 有8 + 4 = 12 种旋转操作, 加上逆时

2017-09-12 17:42:36

HDU 6205 card card card (2017沈阳网赛 - 最大连续子序列和)

题意:给你两堆数 a 和 b, 每次都是从头开始选择, 选到a-b的和小于0为止, 问你当a 的和最大时,最少操作是多少, 每次操作,可以将头上的a 和b 挪到最后。思路:一开始想各种数据结构之类的骚操作。其实就是一个维护最大连续子序列和。类似HDU 1003直接求和a-b  当a-b小于0 时 重新计数, 否则就根据a 的和 来更新答案 和 所在的位置。#in

2017-09-11 16:42:54

HDU 6201 transaction transaction transaction (2017沈阳网络赛 - spfa最长路)

题意:给你一棵树, 树上有点权, 要求选择起点S和终点T, 要求T-S-sum 最大, sum为S到T的边权。思路:根据题意就可以建图建立源点和汇点。源点连所有的树上点, 边权为 a[i], 所有树上点在连接 汇点, 边权为-a[i]. 然后在根据树建图。 spfa跑个最长路即可。#include #include #include #include #incl

2017-09-11 09:35:56

HDU 6197 array array array (2017沈阳网赛- 最长上升子序列)

题意:告诉你n 个数, 问你是否去掉k 个数后, 原序列变成非严格递增序列或者非严格递减序列。 思路:显然求一遍LIS , 倒过来在求一边LIS, 比较ans 和 k 的关系即可。#include #include #include using namespace std;int T;const int maxn = 100000 + 10;int a[maxn],

2017-09-11 08:38:21

HDU 6194 string string string (2017沈阳网赛-后缀数组)

题意:告诉你一个字符串和k , 求这个字符串中有多少不同的子串恰好出现了k 次。思路:后缀数组。我们先考虑至少出现k 次的子串, 所以我们枚举排好序的后缀i (sa[i]) 。k段k 段的枚举。假设当前枚举的是 sa[i]~sa[i + k -1]那么假设这一段的最长公共前缀  是L 的话。那么就有L 个不同的子串至少出现了k次。我们要减去至少出现k + 1次的

2017-09-11 08:20:00

POJ 3252 Round Numbers (数位dp)

题意:求区间内  二进制  0 的个数大于等于 1  的 个数。思路:显然数位dp。但要考虑二进制 0 和1 的个数。不太好做。我们平常写数位dp 都是十进制的。如果我们直接按二进制直接数位dp  就和十进制一样了。。令dp[i][j][k] 表示 第i位,  目前有j 个0  k 个1的方案数。然后就是很基本的数位dp了。#include #include

2017-09-07 19:41:25

HDU 6148 Valley Numer (数位dp)

题意:求区间内满足非波峰数的个数。 其中波峰 是  先上升 在 下降,  平滑不会影响前面的状态。思路:很明显数位dp 令dp[i][j][k] 表示  枚举到数的第i 位, 前一个数字是j  , 状态为k 的数量。其中k = 0 表示平滑状态, k = 1 表示上升状态, k = 2 表示下降状态。因为前导0 是不合法的, 因此可以在开一个变量 lead 表示是否有前导0

2017-09-07 16:37:11

UVA - 1076 || LA 4126 Password Suspects (AC自动机 + 状压DP + 打印解)

题意:让你构造一个长度为n 的串, 告诉你m个串, 要求长度为n 的串 必须包含m 个串, 问你有多少种方案。如果方案数 思路:不看输出方案。很明显一个自动机  + 状压的题目。令dp[i][j][k]  表示 构造字符串的第i 位, 目前在自动机的j 结点, 包含m 个串的状态为k 的方案数。那么直接转移就好了。但是要打印解 。 感觉这里比较乱 想了好久。因为自己

2017-09-06 20:23:43

UVA - 11468 Substring (AC自动机 + 概率dp)

题意:给出一些字符和各自对应的选择概率,随机选择L次后将得到一个长度为L的随机字符串S(每次独立随机)。给出K个模板串,计算S不包含任何一个模板串的概率(即任何一个模板串都不是S的连续子串)。思路:多模式匹配,显然的Ac自动机, 每个字符都有一个概率, 就是很显然的自动机 + dp了令dp[i][j] 表示构造字符串的第i 位, 在自动机节点j 不包含病毒串的概

2017-08-31 21:16:30

Gym - 101190E Expect to Wait(数形结合 , 二分, 查分)

题意:告诉你n 个操作过程, + 代表 在t 时刻来了k 个车,  - 代表在t 时刻 来了k 个人,  每个人都要开走车, 没车的话 一直在队列里等, 告诉你每一天开始有多少辆车, 求所有人的等待时间总和, 如果有人拿不到车就输出 inf。思路:数形结合的思想。n 个操作可以分成n-1 段, 记录每一段的人和 等待时间。那么一开始有x 辆车的话, 那么只需要将大于x

2017-08-30 09:38:41

HDU 4758 Walk Through Squares (AC自动机 + 状压dp)

题意:给你一个矩阵, 给你两个串, 问你从左上角走到右下角的路径中,包含这两个串的路径的方案数。思路:就是路径必须要匹配两种串。可以考虑自动机上 状压。很容易想到的是dp[i][j][k][l][m]表示走第i 步, 在自动机j 结点, 目前有k 个D, l 个R, 包含两个串的状态为m的方案数。但这样无论是 空间上 还是时间上 都无法承受。那就只能把第一维删掉了

2017-08-29 12:02:10

HDU 2825 Wireless Password (AC自动机 + 状压dp)

题意:给你m(m 思路:很像那种 构造一个串  不包含m 个串的方案数那种 , 但这种是包含。 这个题串很小, 最多10个, 因此可以考虑状压dp。那么很好想到了。令dp[i][j][k] 表示目前构造串的第i 位, 在自动机 j 结点,  m 个串中选择的状态k 的方案数。很好转移, 大家自己想想把。不过写完之后TLE了。= =然后就加了一堆小小优化。

2017-08-28 12:01:06

HDU 3341 Lost's revenge (AC自动机 + dp[优化好多= =])

题意:给你n 个DNA 串,  最后给你一个匹配串, 问你匹配串随便排列后 最多能匹配多少DNA串?思路:一个串匹配多个串, 是AC自动机。考虑dp因为是随便排列, 因此就得考虑 用x1 个A, x2 个C, x3 个G, x4 个T 能匹配多少个串, 这样不会有顺序问题。刚开始考虑的是 dp[i][j][k] 表示构造串的第i 位, 目前在自动机的j 结点,  ACGT数

2017-08-28 08:48:14

UVA - 1326 Jurassic Remains (折半搜索)

题意:给你n 个串(仅包含 大写字母), 要求选择尽可能多的串,使得 所有的字母出现次数均为偶数次。思路:真的蜜汁题意, 比赛结束都没读懂。。。。18s 时间很充足, 2^24 直接爆可以过。。记录一下 折半搜索。总共24个串, 暴力是2^ 24我们可以先枚举前一半,把前一半的答案 存起来。  在枚举后一半 , 直接看对应的答案是否存在即可。对于这个

2017-08-27 21:45:37

HDU 6161 (2017多校9 - STL模拟 + dp)

题意:给你一个n (n 1. 查询经过节点x 的最大权值链。2. 改变x 的权值为v思路:n是1e8,没法建树。但他是一个完全二叉树,一条链就log n 个点。那么我们每次修改权值时 , 维护一下这条链的信息。 那么我们只需要n log n 的空间就足够了。所有 我们令dp[x]表示 从x 往下走 最大权值是多少。val[x]表示 x 这个点权值

2017-08-25 08:06:59

HDU 2296 Ring (AC自动机 + dp[类似于背包])

题意:给你m 个喜欢的串, 每个串都有一个权值, 一个字符串的权值为 每个喜欢的串的权值 乘以 出现次数。 问你长度为1~n 的字符串中 权值最大的串是什么, 权值一样输出长度最短,长度一样输出字典序最小。思路:匹配多种串, 显然ac自动机。答案要求权值最大, 权值一样长度最小, 长度一样 字典序最小。 显然是那种类似于背包的套路。 用int dp[][] 记录答案, string

2017-08-24 09:42:20

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!