5 Rainbow6174

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 6w+

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

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

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

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

BZOJ4034 [HAOI2015]T2 题解&代码

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

2016-06-01 21:32:05

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

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

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

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

2016-04-14 17:07:00

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

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

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

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

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

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

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

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

2016-03-15 22:07:18

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

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

2016-03-11 20:00:31

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

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

2016-03-11 19:47:25

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

BZOJ2938 POI2000 病毒 题解&代码

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

2016-03-11 16:45:46

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

查看更多

勋章 我的勋章
  • 专栏达人
    专栏达人
    授予成功创建个人博客专栏的用户。专栏中添加五篇以上博文即可点亮!撰写博客专栏浓缩技术精华,专栏达人就是你!
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!