Rainbow6174-CSDN博客

原创 Directed Graph Model

The Directed Graph ModelA directed graph G consists of a set of vertices V and an edge set E of ordered pairs of vertices. For our purposes, each vertex corresponds to an artist. If (Y,X)∈E(Y,X) \in E(Y,X)∈E then there is an arrow pointing from YYY to XXX

2021-02-27 00:33:02 220

原创 BZOJ1251 序列终结者题解&代码

题意：给出一个初始均为0的序列，两个操作分别是 1、1 l r v区间[l,r]的值增加v 2、2 l r翻转区间[l,r]的值 3、3 l r求区间[l,r]的最大值题解：普通的Splay，标记有翻转标记和增加标记，注意标记和下传时间同步维护val和mx即可嗯…加两个虚节点作为首尾就可以了【刚才忘了说】大家都是用单旋Splay复习的…都是随手写大量标记Splay练手的QAQ只

2016-07-19 23:30:14 1639

原创 BZOJ1711 [Usaco2007 Open]Dining吃饭题解&代码

题意：有N头牛，F种食物和D种饮料，每头牛有多种喜欢的食物和饮料，每头牛只可以吃一种食物和饮料，且每种食物和饮料都只能被一头牛吃掉。一头牛满意当且仅当它吃到满意的食物并且喝到想喝的饮料，问最多可能让多少头牛满意。题解：把每头牛拆成两个点x和x+n，给x和x+n连一条容量为1的边如果一头牛x喜欢一种食物，那么给x和食物编号点连一条容量为1的边如果一头牛x喜欢一种饮料，那么给x+n和

2016-06-13 20:06:54 889

原创 BZOJ3511 土地划分题解&代码

pkusc发现自己不会费用流233333于是两天速成费用流【然而这是一道最小割（最大流QwQ 题意：给出n个点m条边，并设定：点x在被划分至集合A时获得权值A[x]，否则即被划分至集合B并获得权值B[x]；边(x,y)连接的x和y均属于集合A时获得权值ea，均属于集合B时获得权值eb，否则获得权值-ec。题解：这题…反正我是没自己建出图来。对于点x，从S(代表集合A)向x连容量为v

2016-06-09 10:25:55 2495

原创 BZOJ2223 [Coci 2009]PATULJCI 题解&代码

题意：给出一个长度为n的序列a满足1≤a[i]≤n。又有m组询问，每次对于一个区间[l,r]问是否存在一个数在[l,r]中出现的次数大于(r-l+1)/2。如果存在，输出yes，否则输出no。题解：标准主席树…主席树还是这么简单粗暴QwQ但是我MLE了好多次，这空间卡得我怀疑人生…不过最后的错误反而不在空间233333 我把n和m弄错了WA了好几次，总之是简单错误啦和BZOJ3524是

2016-06-01 21:52:45 3405

原创 BZOJ4034 [HAOI2015]T2 题解&代码

题意：有一棵有N个节点的树，以节点1为根，且点上有权。有M个操作，分为三种：操作 1 把节点x的点权增加 a 操作 2 把以节点x为根的树中所有点的点权都增加a 操作 3 求节点x到根的路径中所有点的点权和分析：操作1和操作2本质上是没有区别的，区间修改和单点修改显然可以合并，求dfs序后线段树区间维护就可以了操作3是涉及路径的查询，和树剖很类似，但是比树剖简单很多【比如我求的

2016-06-01 21:32:05 1346

原创 BZOJ2243 [SDOI2011]染色题解&代码

题意：给定一棵有n个节点的树和m个操作，操作有： C a b c 将树上a到b路径上所有点都染成颜色c； Q a b 询问树上a到b路径上的颜色段数量（连续相同颜色是同一段）思路：树上的路径！树链剖分！可惜智障了…没想到怎么维护颜色段【妈的这么简单的维护当时居然不会树剖划分一下树，然后线段树维护每一段的最左lc[]最右rc[]和不同颜色色段数量和sum[]，查询的时候关于判断

2016-04-14 17:26:29 2993

原创 BZOJ2242 [SDOI2011]计算器题解&代码

题意：有三种要求： 1、给定y,z,p,计算Y^Z Mod P 的值； 2、给定y,z,p，计算满足xy≡ Z ( mod P )的最小非负整数； 3、给定y,z,p，计算满足Y^x ≡ Z ( mod P)的最小非负整数。分别处理即可思路： 1显然是快速幂了，纯模板 2是扩展欧几里得（exgcd），求满足xy-pk=z的最小x（k任意） 3利用了费马小定理的性质a^(p-1)≡1(

2016-04-14 17:15:19 2821

原创 BZOJ2241 [SDOI2011]打地鼠题解&代码

题意：给你一个m*n的方格（初始每个位置都大于0），你可以选择一个固定大小不可旋转的方块（例如大小为x*y），使每次这个方块在方格上某个所有位置都非0的区域覆盖一次时区域内每个位置的值减一，问覆盖多少次后这个方格内部的值全部为0（因为有1*1的方块，所以一定有解）题解：看起来乱七八糟的，但其实就是个暴力搜索，内部测试的时候因为一些问题看错了m和n，不然就1A了…/****************

2016-04-14 17:07:00 3073

原创 BZOJ2683 简单题题解&代码

题意：给出n*n的棋盘，初始值为0，维护两种操作： 1 x y a 给(x,y)处加a 2 x1 y1 x2 y2 查询(x1,y1)(x2,y2)的矩形内部的和对每次求和都需要输出答案思路：其实我是直接看题解是cdq分治的【捂脸】不敢随意装逼，只是写了一次cdq分治熟悉了一下插入和查询都是单点操作（查询操作可以修改为4个单点的二维前缀和）不知所云…有点尴尬，我思考一下再说o

2016-04-08 16:24:44 791

原创 BZOJ3524 POI2014 Couriers 题解&代码

题意：给出一个长度为n的序列a满足1≤a[i]≤n。又有m组询问，每次对于一个区间[l,r]问是否存在一个数在[l,r]中出现的次数大于(r-l+1)/2。如果存在，输出这个数，否则输出0。思路：嘛，很纯粹的主席树…只不过空间限定太严格了点，竟然卡空间，我卡了好几次才AC… 不过我现在特别纠结为啥我BZOJ2223过不了#include<iostream>#include<cstd

2016-04-06 13:33:54 1058

原创 POJ3468 A Simple Problem with Integers 题解&代码

题意：给出n个数排成一列，有q个操作，分为Q和C，Q操作[l,r]询问区间[l,r]的区间和，C操作[l,r]对[l,r]区间同时增加x，按题意输出就行了题解：线段树，主要是好久没写又错了好长一段时间…万年LL我就不多说了，看错范围觉得sum[]不需要LL，另外重点是query和insert不可能越界访问，所以就算区间对于这组数据是无效区间，只要访问到对应区间也一定要pushdown…忘了结果纠

2016-04-05 10:48:18 518

原创 POJ1905 Expanding Rods 题解&代码

题意：给出一个长L的木棒，给出温度n和膨胀系数C。已知木棒的长度S遵循公式S=L*(1+n*C) 如图，图源自小優YoU 求当一根木棒如此膨胀时形成的弧形中心位置和原来的中心位置之间的距离h思路：暴力几何题…主要是一些公式推导，如下【依照代码的变量命名，即上文S均w ① L0=(1+n*C)*L ② L=2*sqrt(R*R-(R-h)*(R-h)) ③ S=2*pi*R*(

2016-04-01 11:55:03 519

转载 link-cut tree预习

转自http://www.cnblogs.com/BLADEVIL/p/3510997.html?utm_source=tuicool&utm_medium=referral 动态树是一类要求维护森林的连通性的题的总称，这类问题要求维护某个点到根的某些数据，支持树的切分，合并，以及对子树的某些操作。其中解决这一问题的某些简化版（不包括对子树的操作）的基础数据结构就是LCT(link-cut tre

2016-03-31 20:31:02 422

原创 POJ3126 Prime Path 题解&代码

题意：每次给出两个四位素数a和b，要求每次修改a中的一位【要保证修改后仍然是四位数】，询问最少修改几次后能得到b，不能得到的话输出impossible其实是个bfs水题…结果我判素数浪了一发WA了好久原因是sqrt(i+0.5)我偷了个懒只写了sqrt(i)结果素数判错了最后这种水题硬是写了一发对拍拍出来了#include<iostream>#include<queue>#include

2016-03-22 16:31:44 1242

原创 BZOJ2002 HNOI2010 Bounce 弹飞绵羊题解&代码

这几天一直在bzoj水不能见人的水题…有时间补补题解吧【说得好像这题不水一样很简单的分块！第一次写到这么简单的分块！整个人都舒爽了！虽然还是WA了两次…妈的我只是写完一激动忘了输出后加回车…将整个长区间分成近似于sqrt(n)块【分块方法随意，满足可逆性即可对于每一块，处理出块内每个点弹出这一块所需步数然后每次查询最多累计sqrt(n)次（块数次）每次修改最多修改sqrt

2016-03-15 22:07:18 791

原创 BZOJ3668 NOI2014 起床困难综合症题解&代码

本题看起来完全不可做…实际上是O(n)的。冬令营虽然挂了233333但是前一天的练手题倒是秒出…至于题解这么晚…大概是因为我今天比较闲得蛋疼… 最开始虽说选择的范围是m，但是考虑到关于攻击力的所有运算都是位运算，那么大胆猜想按位枚举出m…猜对了按位非0即1枚举出m的情况，存入ans[] 然后由高位向低位暴力选就行辣…注意即使数字稍小一点了也不要让选出的数大于m，用flag记录当前数是否等

2016-03-11 20:00:31 778

原创 BZOJ2038 2009国家集训队小Z的袜子(hose) 题解&代码

莫队原例题【有气无力状】…手推那个O(1)的转移计算就行辣… 一眼看过去和上一道题差别不大…懒得写其它解释了莫队详解参见http://blog.csdn.net/rainbow6174/article/details/50858386/************************************************************** Problem: 2038

2016-03-11 19:47:25 725

原创 BZOJ3781 小B的询问题解&代码【附莫队总结】

莫队这种低端局折腾了将近两天，自己也是有点浪主要还是分块后的处理…边界算错好多次orz题意：给出一个序列包含n个1~k间的整数。共询问M个区间[L,R]，求Σc(i)²（i∈[1,k]），c(i)表示i在[L,R]中的重复次数。题解：莫队，其实是暴力分块首先我们注意到区间没有被修改过，那么我们可以利用cdq分治的离线思路【为什么扯到了自己还没写过的奇怪东西】…好的我们确认了这道题可以

2016-03-11 19:35:32 768

原创 BZOJ2938 POI2000 病毒题解&代码

题意：给出n个病毒代码，判断是否有无限长度的代码满足：不包含任何病毒代码。题解：看到多字符串匹配，就想到AC自动机【这语气好奇怪 AC自动机建好fail指针，然后从根向下dfs查找，所有实节点都用flag标记，如果找到了一个不经过病毒路径的环，那么就存在无限长度代码满足不包含任何病毒代码/***************************************************

2016-03-11 16:45:46 1239

原创 BZOJ1030 JSOI2007 文本生成器题解&代码

题意：给出n个匹配串，询问：对于长度为m的串，有多少个串至少包含一个匹配串（答案对10007取模）题解： “至少包含一个匹配串的长度为m的串”，那么很容易转化为“所有串除去不包含任何匹配串的长度为m的串” 然后就是喜闻乐见的AC自动机上的dp了，dp方程显然是dp[i][j]表示长度为i的串匹配到j位时有多少不包含任何匹配串有：dp[i][ch[j][k]]+=dp[i-1][j] 即

2016-03-11 16:30:13 596

原创 BZOJ4199 NOI2015 品酒大会题解&代码

并查集维护…着急回宿舍（浪）明天再写详细题解/************************************************************** Problem: 4199 User: Rainbow6174 Language: C++ Result: Accepted Time:5992 ms Memory:29628 kb

2016-03-09 22:07:24 1133

原创 POJ1743 Musical Theme 题解&代码

后缀数组… 对最长不重叠子串长度进行二分判定，判定方式是暴力分组利用height[]的性质：如果height[i]>x,height[i-1]>x，那么存在从sa[i-2]到sa[i]的部分最长公共子串大于x 可以推论：对于height[i]~height[j]均大于x，那么存在sa[i-1]到sa[j]的部分最长公共子串大于x 这样可以得出对于一段连续的满足条件的height[]，有连续

2016-03-09 22:04:32 414

原创 HDU5638 bestcoder#74 Toposort 题解&代码

场上没想出来…搜索直接过了就没算复杂度，愉快FST，第一次以TLE的姿态FST…我只能说pretest简直太丧病了…因为所有步骤可以转换成为1-18位单个位转换和a[]的异或转换所以对这些做个01背包…然后将s^t放进去（相同数的异或值是0，另外整个式子一定满足对于新的a[]存在s^a[i]^…^t=0），O(1)地得到了答案#include<iostream>#include<cstdio>

2016-03-07 21:16:38 498

原创 HDU5637 bestcoder#74 Transform 题解&代码

场上没想出来…搜索直接过了就没算复杂度，愉快FST，第一次以TLE的姿态FST…我只能说pretest简直太丧病了…因为所有步骤可以转换成为1-18位单个位转换和a[]的异或转换所以对这些做个01背包…然后将s^t放进去（相同数的异或值是0，另外整个式子一定满足对于新的a[]存在s^a[i]^…^t=0），O(1)地得到了答案#include<iostream>#include<cstdio>

2016-03-07 19:25:31 468

原创后缀数组suffix模板

25min默完，漏掉了一些p=n时的小优化…还有m=p的常数优化好在主体没什么问题，看来还是不够熟悉#include <iostream>#include <cstdio>#include <cstring>using namespace std;const int maxn = 100005;int sa[maxn], Rank[maxn], height[maxn];int wa

2016-03-02 20:54:15 538

原创 HDU2222 Keywords Search 题解&代码

题意：多组数据，每组数据有n个字符串作为字典，然后给出另外一个字符串，询问这个新的字符串中有几个字典中的单词。多个匹配串对单字符串匹配，AC自动机是标准解法，算是测试模板了【笑然而RE了一发WA了一发…没看清数据范围对于字典中的字符串建立trie树和fail指针，然后对待匹配串匹配即可有一些奇怪的小细节譬如字典中可能有多个相同字符串，以及判重问题…恩还是很好解决的嘛#include <i

2016-03-02 19:40:01 481

原创 AC自动机模板

啦啦啦二十分钟默出来编译通过，一会去试几道题好啦#include <iostream>#include <cstdio>#include <cstring>using namespace std;const int maxn = 10005;const int maxm = 100;int n, tot, temp;int ch[maxn][maxm], fail[maxn], fla

2016-03-02 15:49:45 493

原创 KMP模板

vim用起来略爽233333感觉代码不是同一个人写的了这个版本kmp是说要手动统计length，然后next[]是从1开始…因为比较好用，很多时候不用特判(特判的时候比较方便)#include <iostream>#include <cstdio>#include <cstring>using namespace std;const int maxn = 100005;int next

2016-03-02 15:25:31 329

原创 BZOJ3670 NOI2014 动物园题解&代码

利用了kmp的next数组特性，求出既是i位字符串的前缀又是其后缀的字符串个数num[i]，然后按表达式求出积即可首先进行统计，在求next的时候就可以统计出num[i]了【对于每一个p=next[i],num[i]满足num[i]=num[p]+1（即对于i位字符串，一定有p位字符串满足条件，于是加上p位字符串的num值，和求next[]的思路相似）】。最后再次进行枚举，此时对于每一位ne

2016-03-02 15:14:55 1870

原创 POJ 2778 DNA Sequence 题解&代码

调了三个小时…2333333感觉自己傻逼了是一道很有(ma)趣(fan)的AC自动机+矩阵快速幂我们需要算出的初始矩阵是dp[i][j]是用一步从自动机的第i个位置到第j个位置有几种不产生病毒DNA的方式然后乘n次就得到答案辣【答案当然是从初始位置（0）到最终位置i的方式数之和被vim坑了一发…还是不太习惯，平时写习惯的矩阵快速幂迷之CE… 后来发现初始矩阵算对了但是还是答案太少…感谢样例

2016-03-01 20:32:05 477

原创 POJ3630 Phone List 题解&代码

第一次用vim写代码…感觉爽爽哒，终于明白很多代码为什么会有诡异的空格什么的…习惯 vim的快捷操作几乎全部是和单词相关，也就是说如果一句代码中间没有空格…vim的优势就完全消失了在下的习惯一时半会改不过来…嘛，不过既然看到了其道理自然是要努力改的裸的trie树，最后加上一遍dfs，dfs检验是不是有一条路径上同时有两个单词结尾，如果有输出NO，反之则反#include<iostream>#in

2016-02-29 18:57:51 708

原创 POJ3294 Life Form 题解&代码

报警了…交了11发WA最后发现数组开大RE之后代码一直是对的… 100个字符串长度是1000… 我都用的是100… 为什么不RE…QAQ 觉得从RE变成不RE数组就没问题还是too naive 【说好的后缀数组学习笔记呢【下周吧，先跟标准进度#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>u

2016-02-27 17:44:17 752 2

原创 HDU4416 Good Article Good sentence 题解&代码

啦啦啦，第三道强行算作今天（19号）完成，flag get，开心这道看到它各种RE心都碎了…于是查出了两个错 1、关于字符串rank最后补0，我栽在了多组数据上…平时单组我就强行当做自己补过0了，结果吃了个亏，折腾了半个小时才发现 2、关于分隔字符也是人…23333333我开了2w+的数组RE了，交了好几遍改了好几次都没发现，最后看题解发现人家开了3w最近好像懒了很多，题解越来越短啦…不过今

2016-02-20 00:39:01 730

原创 POJ 2774 Long Long Message 题解&代码

第二道后缀数组…其实感觉比上一道简单【23333 后缀数组的主要用法之一就是height[]…这道题就是把两个字符串用分隔符连接起来，求新字符串的height[]，然后找到有效height的最大值即可【有效height就是该height对应的两个串分别在两个字符串中#include<iostream>#include<algorithm>#include<cstdio>#include<cs

2016-02-19 20:24:04 426

原创真是不把自己逼到再无退路就不学

三天学了三种字符串数据结构【雾第二天还浪了半天多… 然而我一个寒假什么都没做人生真是失败好啦不乱想啦，今天过掉后缀数组，明天复习manacher和AC自动机不管怎么样还是有结果的不是么好弱，感觉自己好弱

2016-02-19 16:38:47 563 1

原创 POJ3261 Milk Patterns 题解&代码

二分后对后缀数组的height分组…解决第一次写(chao)后缀数组，调了两个多小时，代码都不会抄【笑本来该附后缀数组学习记录，感觉快要吃饭了不想写…再说吧（正文在最后）发现了一个很玄妙的地方，二分方法不同的话时间差很大…大概是数据比较玄学？这是63ms版 l=1,r=n,mid; while(l<r) { mid=(l+r)/2; i

2016-02-19 16:22:53 526

原创 URAL1297 Palindrome 题解&代码【附manacher学习记录】

作为一道manacher模板题我不太理解为什么大家都是用后缀数组做的…大概是那时候还没有出现manacher… 所谓前人栽树后人乘凉，作为一个学习者好像也没什么脸面说别人做得麻烦来着不扯了，manacher模板简洁明了，感觉也没什么风格冲突…我就直接用了manacher是在字符串s中用p[i]表示以i为中心的最长回文(子)串长度，求出p数组就达到了目的这种表示法有一个问题，即回文串可能是偶数长

2016-02-18 11:39:05 407

原创 POJ3691 DNA repair 题解&代码

我心好痛啊…f**k -1改成0x3f3f3f3f就过了…这么玄妙的东西我卡了半个月我服等老师再研究一下吧，我现在不想看到这道题 //一道题的代码几乎能背过是什么体验注释不删，等待第二版更新#include <cmath>#include <climits>#include <cstdlib>#include <iostream>#include <queue>#include

2016-02-17 21:01:42 884

原创感觉自己好弱

看到别人的成长之路都是rating1900+对应访问量1w+ 虽然差得很远很远但还是在想自己，不知道什么时候CF1900+什么时候访问量1w+呢按照现在CSDN新模式，一篇blog访问量是30-60…maya 200篇【不对好像不多啊【诶人生有希望了啊【200道题就可以了嘛【活在梦里【不知道为什么突然感觉很有动力呀【不说了我去继续看题【突然满满的正能量

2016-01-23 11:51:50 589

空空如也

空空如也