aozil_yang-CSDN博客

原创 2017团体程序设计天梯赛CCCC杭州决赛总结

CCCC决赛参赛总结 4月15日，阳光明媚，心情舒畅，是一个外出旅游的好日子，集训队三十余人动身去杭州参加C4的决赛，清点完人数后，坐上了大巴前往青岛北车站。11点钟坐上了前往杭州的绿皮火车。火车上相当热闹，气氛非常活跃，总之大家放松的非常好。第二天到站好时间非常紧，由于杭州一号地铁线比较特别，是分叉的地铁，地铁一来，没有看清是哪一叉的，我就带着部分人上错了地铁，幸亏可以在分

2017-04-22 22:55:25 2233

原创 2017 CCCC预赛总结

CCCC预赛总结很开心学校能够打进决赛。在比赛前一天晚上才想到还有CCCC的比赛，顿时就方了，虽然有很多水题，但还是很方，根据以往打CCCC的经验，CCCCL2阶段必然有一个二叉树之类的数据结构，晚上就看了看二叉树和堆之类的数据结构，结果一个也没考到，失望了许久。总之，比赛前一天晚上看了一些数据结构题，算是有所准备了。第二天，被教主喊醒，好困啊！抓紧洗刷后赶到集合地点，

2017-03-26 01:36:57 1293 2

原创 2016亚洲区域赛（大连站）总结[需要更加努力~]

2016亚洲区域赛大连站总结ACM第一块银牌，一个良好的开端！周五下午就匆匆忙忙的赶去大连，路途很长，先赶到了烟台，在从烟台做的轮船到了大连，一路上虽然很累，但都在聊各种话题，还是比较开心愉快的。先说些题外话，到了大连才4：30，大清早的就赶去大连海事大学，可是早餐都不开门，只能六个人在超市里吃泡面（现在想想还是很搞笑= =），然后一上午等着报道，吃午餐，中午没有睡觉1点左

2016-10-20 09:02:37 1974 2

原创 2016团体程序设计天梯赛CCCC 决赛总结

CCCC总结周六能够参加CCCC决赛感到很幸运，又发衣服，又合影的，很高兴，但是比赛打的并不理想，现在总结反思一下：成绩情况是做出了第一阶段的题目和第三阶段完全二叉树的一部分分，总共是143分，很低很低，和自己预想的差很多。第二阶段做不出题目的原因很大一部分在于第一阶段的影响，第一阶段的题目都不是算法题目，想一想随便写写就可以过，但就是这些题目，有一部分题目卡了自己很久很久

2016-07-18 11:05:38 1476 1

原创 POJ 3580 SuperMemo （Splay）

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

2017-10-12 16:52:51 479

原创 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 515

原创 HDU 6196 happy happy happy （2017沈阳网赛 - 搜索 + dp + [黑科技。。。]）

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

2017-09-14 14:26:14 732

原创 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 516

原创 HDU 6202 cube cube cube （2017沈阳网赛 - 魔方模拟）

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

2017-09-12 17:42:36 1220

原创 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 453

原创 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 1140 1

原创 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 751

原创 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 2610

原创 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 328 1

原创 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 350

原创 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 984

原创 UVA - 11468 Substring （AC自动机 + 概率dp）

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

2017-08-31 21:16:30 287

原创 Gym - 101190E Expect to Wait（数形结合，二分，查分）

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

2017-08-30 09:38:41 635

原创 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 412

原创 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 383

原创 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 415

原创 UVA - 1326 Jurassic Remains （折半搜索）

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

2017-08-27 21:45:37 295

原创 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 472

原创 HDU 2296 Ring （AC自动机 + dp[类似于背包]）

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

2017-08-24 09:42:20 391

原创 HDU 1625 Censored! （AC自动机 + 大数 + dp）

题意：给定你n 种字符，和p 个禁止串，问你长度为m 的串有多少种不包含禁止串？思路：AC自动机是显然的。矩阵快速幂也可以，dp 也可以。但是这是个大数。极限答案有85位左右。我用快速幂写了一发，不是爆内存就是因为内存开的过大小样例都出不来。只能考虑dp了。dp 状态很好想:令dp[i][j] 表示目前走第i 位长度，在自动机上j 节点的方案

2017-08-24 08:25:27 343

原创 UVA 10075 Airlines (Floyd + 数学转换)

题意：告诉你n个点的经度和纬度，告诉你m 个有向边， q 个查询，求两点的最短路。思路：显然裸floyd就是这个两点之间距离比较恶心了。我们直接以球心为圆点，建立XYZ直角坐标系。球心连接经度 0 的位置。然后就好求任意点的xyz 坐标了。假设纬度是wd（弧度），经度是jd（弧度）那么X = R * cos（wd） * cos（jd）

2017-08-23 18:50:14 268

原创 HDU 6166 Senior Pan （2017多校9 - Dijkstra + 二进制枚举 [神题]）

题意：给你一个有向图，告诉你选择的K个点，问这K个点中最近点对的最短路是多少？思路：大开脑洞一个题目。。。假设我们能够把K个点分成两个集合的话，我们一遍Dijkstra 就可以求出两个集合的最近距离。求完这两个集合后，那么两个集合中除了最近点对外，其余点对都不用在算了，因为都不如这个最近点对最优。因此如和合理的划分集合是关键。因为每一个点的数值都是不同的

2017-08-22 21:44:44 1195

原创 HDU 6162 Ch’s gift （2017多校9 - 树链剖分 + 线段树）

题意：给一棵树， q 个查询，每个查询输出一条链中点权在指定范围内的加和。思路：链中的操作，显然是用树链剖分。但是有个很难处理的问题，如和求一个链中的点权在制定范围内的加和。用线段树就可以了。维护区间内最小值，最大值，和总和。如果区间最小值，最大值都在范围内，那么肯定整个区间都在制定范围内了，就不用在向下找了。如果区间最大值小于制定

2017-08-22 20:07:00 573

原创 ZOJ 3228 Searching the String （AC自动机）

题意：给你一个模板串，和n 个要匹配的串，匹配串有两种类型，第一种可以在模板串中重叠出现，另一种不可以重叠，问每个串的两种形式所出现的数量。思路：很明显ac自动机。我们先把所有匹配串插到自动机中，第一种很简单，可以重叠出现，直接循环一边模板串，不断的走fail 指针，找到一个加一个就行了。不可重叠也很简单，直接在开一个last数组，表示这个单

2017-08-22 09:44:06 384

原创 UVA 11354 Bond （最小生成树 + 树链剖分）

题意：给你一个图， q 个查询，每个查询输出两点之间的路径中最大值的最小值。思路：要想路径最大值最小，边肯定在最小生成树上。先把图建成最小生成树。那么问题就是输出树上两点之间的边权最大值。赤裸裸的树剖。可惜比赛时脑残没有想到最小生成树。#include #include #include #include using namespac

2017-08-21 17:41:43 264

原创 UVA - 12083 Guardian of Decency （匈牙利算法求最大独立集）

题意：给你 n 个人的性别身高，喜欢的运动和音乐。告诉你一些两个人能在一起的条件，问最多多少人在一起？思路：有性别之分。可以建成一个二分图。然后反向建边，如果男i 和女j 不能再一起就连一条边。然后这样，二分图的最大独立集就是答案。所有人都不连边，所有人都可以在一起。总数 - 最大匹配数即是答案。#include #include

2017-08-21 16:27:10 331

原创 HDU 2243 考研路茫茫——单词情结（AC自动机 + 矩阵快速幂）

题意：给你n 个非法串，求长度为1~m 的串至少包含一个非法串的个数。思路：经典AC自动机问题。和POJ 2778 是一样的。我们可以先求长度为1~m 不包含非法串的个数。求长度为m 的串种类数是矩阵的m 次方。这里就是 A^1 + A ^ 2 + A ^ 3.... + A^m倍增法求矩阵和或者构造一个大矩阵在求和都行。如和构造矩阵看那一篇文

2017-08-21 08:18:53 386

原创 HDU 4511 小明系列故事——女友的考验（AC自动机 + dp）

题意：给你n个点，你在1号点，要到n 号点，有m 种路径不能走，求1到n 的最短路长度。思路：m 种路径不能走，很容易想到AC自动机。求距离最短。还是将m 种路径建立成自动机，一个结点非法，不仅他是m 种路径的末尾，还包括m 种路径子串的话也是非法的。我们令dp[i][j] 表示在目前在i 点， j 状态的最短距离。（j 为自动机上的结点）那么转移就很

2017-08-20 13:08:54 354

原创 POJ 2778 DNA Sequence （AC自动机 + 矩阵快速幂）

题意：给你n个病毒串，要求组成一个长度为n 的字符串，使得字符串中不包含病毒串，求字符串的方案数。思路：先给n 个病毒串建立AC自动机，标记处病毒节点来。然后构造一个矩阵。a[i][j] 表示从i 节点到 j 节点走一步的方案数。那么根据离散知识（听别人说的= =）矩阵的n 次方就是 i 到 j 走n 步的方案数。那么答案就是 a[0][0] + a

2017-08-19 22:11:47 308

原创 HDU 2457 || POJ 3691 DNA repair （AC自动机 + dp）

题意：给了你n 个病毒DNA串，和一个模板串，要求模板串上改尽量少的字符使得模板串不包含病毒串。思路：AC自动机 + dp多个串匹配，很容易想到是AC自动机，然后又是改少的字符，也比较容易想到 dp 上。令dp[i][j] 表示使模板串前i 个字符在自动机的j 节点，不包含病毒串的最小修改数量。那么我们直接枚举第i-1 个字符所在的节点，然后向下

2017-08-19 09:44:08 256

原创 HDU 3065 病毒侵袭持续中 (AC自动机)

思路：也是个ac自动机裸题给每个节点维护编号和数量就好。因为一个节点可能会重复匹配一个病毒多次，所以不能清空维护的数量。#include #include #include #include #include using namespace std;const int maxn = 50000 + 10;int ans[maxn];struct Trie

2017-08-18 08:22:57 266

原创 HDU 2896 病毒侵袭（AC自动机）

思路：ac自动机裸题。虽然输出是乱搞，但也得注意一下时间。输出一开始建立了1000 个set 来保存答案。但是T了。所以必须只用一个数组来简单优化一下。但是数组还有重复的问题，在自动机中加个标记，标记了之后就不存了就可以了还有一个很恶心的是数组开小了返回我的是wa 。。。#include #include #include

2017-08-18 07:50:58 93

原创 HDU 6138 Fleet of the Eternal Throne （2017多校8 - AC自动机）

题意：给你n 个串， q个查询，每个查询输出串x 和串y 的最大公共子串且这个串是其他某些串的前缀。输出长度。思路：因为场上读错题，以为是个极水的后缀数组。= =其实是ac自动机我们给n 个串建立ac自动机。字典树中每个节点维护一个到根的距离（即是前缀的长度）然后给串x 跑一遍自动机，把经过的点的标记出来，表示这个点即是 x 的子串，又是某个串的

2017-08-17 21:05:26 917

原创 HDU 6129 Just do it（多校7，组合数规律）

题意：给你一个数列， m次变换，每次变换b[i] = a[1]~a[i]的异或值。求最后的序列。思路：一个找规律的题目。考虑每一个数对后面的数的贡献。先考虑a1：第一次变换： 1 1 1 1 1第二次变换： 1 2 3 4 5第三次变换： 1 3 6 10 15第四次变换： 1 4 10 20 35不难发现每一行是杨辉三角的斜边。所

2017-08-17 10:48:19 358

原创 HDU 4417 Super Mario （树状数组 + 离线）

题意：给你一堆数， m 次询问，每次询问问你区间里小于等于x 的数有多少个？思路：很容易往数据结构 + 离线上想。一开始写了一发发现想偏了。然后就没然后了。。==========================先把询问存下来，按照h 排序，在给那一堆数存下来，排序。这样枚举询问，在写个 a数组的指针，只要比当前h小，就往后挪就行，挪的时候，

2017-08-12 20:48:35 526

空空如也

空空如也