BZOJ学习记录
BZOJ学习记录
关注
浪了好久来刷BZOJ了！
关注数：0 文章数：27 文章阅读量：37571 文章收藏量：13
作者: Rainbow6174
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 · 1686 阅读 · 0 评论 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 · 931 阅读 · 0 评论 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 · 2545 阅读 · 0 评论 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 · 3451 阅读 · 0 评论 BZOJ4034 [HAOI2015]T2 题解&代码 题意： 有一棵有N个节点的树，以节点1为根，且点上有权。 有M个操作，分为三种： 操作 1 把节点x的点权增加 a 操作 2 把以节点x为根的树中所有点的点权都增加a 操作 3 求节点x到根的路径中所有点的点权和分析： 操作1和操作2本质上是没有区别的，区间修改和单点修改显然可以合并，求dfs序后线段树区间维护就可以了 操作3是涉及路径的查询，和树剖很类似，但是比树剖简单很多【比如我求的 原创 2016-06-01 21:32:05 · 1407 阅读 · 0 评论 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 · 3036 阅读 · 0 评论 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 · 2868 阅读 · 0 评论 BZOJ2241 [SDOI2011]打地鼠 题解&代码 题意：给你一个m*n的方格（初始每个位置都大于0），你可以选择一个固定大小不可旋转的方块（例如大小为x*y），使每次这个方块在方格上某个所有位置都非0的区域覆盖一次时区域内每个位置的值减一，问覆盖多少次后这个方格内部的值全部为0（因为有1*1的方块，所以一定有解） 题解：看起来乱七八糟的，但其实就是个暴力搜索，内部测试的时候因为一些问题看错了m和n，不然就1A了…/**************** 原创 2016-04-14 17:07:00 · 3125 阅读 · 0 评论 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 · 830 阅读 · 0 评论 BZOJ 2789 Letters题解&代码 其实是一道贪心= = 对于某个字母一定是要离它最近的字母移过来的 这样就可以对其中一个串标出关于另一个串的唯一的1～n为的重新排列【s1[i]=s2[p[i]]】 对这个排列求它的逆序对数就好啦 【嗯大概和普通的逆序对没什么区别，多了一个间接排序【嗯写了两个sort大约是我比较蠢= =不知道能不能更快一点#include<iostream>#include<algorithm>#incl 原创 2015-07-21 13:08:48 · 755 阅读 · 0 评论 BZOJ 1012 [JSOI2008] 最大数 maxnumber 题解&代码 题目简洁明了= =我就不详细说了，线段树最大值裸题维护一个数列，要求提供以下两种操作： 1、 查询操作。语法：Q L 功能：查询当前数列中末尾L个数中的最大的数，并输出这个数的值。 限制：L不超过当前数列的长度。 2、 插入操作。语法：A n 功能：将n加上t，其中t是最近一次查询操作的答案（如果还未执行过查询操作，则t=0)，并将所得结果对一个固定的常数D取模，将所得答案插入到数列的末尾 原创 2015-12-03 19:18:07 · 679 阅读 · 0 评论 BZOJ 1036 [ZJOI2008]树的统计 Count 题解&代码 题意：一棵树上有n个节点，编号1到n，每个节点i有权值w[i]。 有三种操作： I. CHANGE u t : 把结点u的权值改为t II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值 III. QSUM u v: 询问从点u到点v的路径上的节点的权值和 注意：从点u到点v的路径上的节点包括u和v本身题目非常浅显易懂= =线段树可以用maxv[]和sum[]保存状 原创 2015-12-12 16:54:28 · 600 阅读 · 0 评论 BZOJ 3207 花神的嘲讽计划Ⅰ 题解&代码 题意： 给出n个数，形成一个长度为n的序列（可以看做[1,n]的区间） 有m组询问，对于每组询问给出一个x和一个y，然后给出一个长度为k的序列s。如果在区间[x,y]上，存在至少一个序列和序列s完全匹配，那么输出No，否则输出Yes。 **注意，匹配成功了输出No，失败时才会输出Yes思路：嘛…就是把每k个数字hash一下存进可持久化线段树的对应位置，这样得到了n-k+1个线段树的根节点，分别 原创 2015-12-14 18:22:40 · 805 阅读 · 1 评论 BZOJ 1208 [HNOI2004] 宠物收养所 题解&代码 其实是一道简单的Splay题目【虽然我写了很久 据说【本来就是】用set+二分很容易就过啦，的确一个不需要maintain和pushdown的Splay和咸鱼没什么区别，不过第一次写Splay我觉得自己写得好丑啊= =【还调了一个多小时题意： 给出宠物和人出现的序列，宠物和人都会选择 ①现在存在的 ②和自己特征值之差的绝对值最小的 ③特征值最小的 非同类【即宠物选择人，人选择宠物】，选择 原创 2015-12-25 13:39:28 · 984 阅读 · 0 评论 NOI2005 BZOJ1500 维修队列 题解&代码 题意： 维护一个数列，要求支持六种操作： 1、INSERT posi tot c1 c2 c3 c4… 在队列的第posi位按序插入tot个数字，分别为c1 c2 c3 c4… 2、DELETE posi tot 从队列的第posi位起删除tot个数字，数据保证一定可以删除tot个 3、MAKE-SAME posi tot c 从队列的第posi位起将tot个数字的值改为c，数据保证一定可以 原创 2015-12-28 13:30:15 · 1260 阅读 · 1 评论 BZOJ1503 NOI2004 郁闷的出纳员 题解&代码 题意太傻不多解释= =就是维护一个档案队列，按节点val建树思路： 从query操作（命令F）可以看出，这棵树的顺序核心在于value而不是一般的维护队列，这样的话相同value的节点显而易见地应该放在一起，我们除了s[]记录子树大小之外，额外增加一个z[]记录节点大小（对于x节点来说每有一个与其value重复的z[x]++），注意z[]不需要维护。 然后就是喜闻乐见的标记了，这道题算是比较良心 原创 2015-12-29 18:11:13 · 1560 阅读 · 0 评论 BZOJ3224 CODEVS4543 普通平衡树 题解&代码 醉啦醉啦= =第k大第k小纠结了好久，最后瞎蒙了一个蒙错了然后纠结了好久，后来学长告诉我【你们排名难道是成绩低的排前面么】题意： 维护一个序列，按照val[]排序，支持： 1. 插入x 2. 删除x(若有多个相同的val，因只删除一个) 3. 查询x是第几大(若有多个相同的数，因输出最小的排名) 4. 查询第k大 5. 求x的前驱(前驱定义为小于x，且最大的数，可能树中不存在x) 6. 原创 2015-12-30 20:42:27 · 939 阅读 · 0 评论 BZOJ 1088 [SCOI 2005] 扫雷Mine 题解&代码 我推了好久的dp啊= =一口老血喷出来 这个智商怎么救= =快告诉我怎么救#include<iostream>#include<stdio.h>using namespace std;const int maxn=10005;int n,ans,a[maxn],s[maxn];int cal(void){ for(int i=2;i<=n;i++) { 原创 2016-01-08 13:00:13 · 639 阅读 · 0 评论 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 · 1908 阅读 · 0 评论 BZOJ4199 NOI2015 品酒大会 题解&代码 并查集维护…着急回宿舍（浪）明天再写详细题解/************************************************************** Problem: 4199 User: Rainbow6174 Language: C++ Result: Accepted Time:5992 ms Memory:29628 kb 原创 2016-03-09 22:07:24 · 1167 阅读 · 0 评论 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 · 638 阅读 · 0 评论 BZOJ2938 POI2000 病毒 题解&代码 题意：给出n个病毒代码，判断是否有无限长度的代码满足：不包含任何病毒代码。 题解： 看到多字符串匹配，就想到AC自动机【这语气好奇怪 AC自动机建好fail指针，然后从根向下dfs查找，所有实节点都用flag标记，如果找到了一个不经过病毒路径的环，那么就存在无限长度代码满足不包含任何病毒代码/*************************************************** 原创 2016-03-11 16:45:46 · 1355 阅读 · 0 评论 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 · 854 阅读 · 0 评论 BZOJ2038 2009国家集训队 小Z的袜子(hose) 题解&代码 莫队原例题【有气无力状】…手推那个O(1)的转移计算就行辣… 一眼看过去和上一道题差别不大…懒得写其它解释了 莫队详解参见http://blog.csdn.net/rainbow6174/article/details/50858386/************************************************************** Problem: 2038 原创 2016-03-11 19:47:25 · 763 阅读 · 0 评论 BZOJ3668 NOI2014 起床困难综合症 题解&代码 本题看起来完全不可做…实际上是O(n)的。 冬令营虽然挂了233333但是前一天的练手题倒是秒出…至于题解这么晚…大概是因为我今天比较闲得蛋疼… 最开始虽说选择的范围是m，但是考虑到关于攻击力的所有运算都是位运算，那么大胆猜想按位枚举出m…猜对了 按位非0即1枚举出m的情况，存入ans[] 然后由高位向低位暴力选就行辣…注意即使数字稍小一点了也不要让选出的数大于m，用flag记录当前数是否等 原创 2016-03-11 20:00:31 · 826 阅读 · 0 评论 BZOJ2002 HNOI2010 Bounce 弹飞绵羊 题解&代码 这几天一直在bzoj水不能见人的水题…有时间补补题解吧【说得好像这题不水一样 很简单的分块！ 第一次写到这么简单的分块！ 整个人都舒爽了！ 虽然还是WA了两次…妈的我只是写完一激动忘了输出后加回车…将整个长区间分成近似于sqrt(n)块【分块方法随意，满足可逆性即可 对于每一块，处理出块内每个点弹出这一块所需步数 然后每次查询最多累计sqrt(n)次（块数次） 每次修改最多修改sqrt 原创 2016-03-15 22:07:18 · 832 阅读 · 0 评论 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 · 1128 阅读 · 0 评论
公安备案号11010502030143 京ICP备19004658号 京网文〔2020〕1039-165号 经营性网站备案信息 北京互联网违法和不良信息举报中心 家长监护 网络110报警服务 中国互联网举报中心 Chrome商店下载 账号管理规范 版权与免责声明 版权申诉 出版物许可证 营业执照 ©1999-2024北京创新乐知网络技术有限公司相关知识
BZOJ学习记录
深度学习训练结果记录
《幼儿行为观察与记录》学习心得体会(汇总5篇)
《幼儿行为观察与记录》学习心得体会（通用10篇）
宠物日常记录最新版下载
宠物成长记录手机软件大全
幼儿观察记录范例6篇
宠物日常记录手机软件
幼儿行为习惯观察记录
宠物日常记录软件
网址: BZOJ学习记录 https://m.mcbbbk.com/newsview818978.html
| 上一篇: 山东麒恒宠物有限公司 |
下一篇: 宠物小精灵之日月冠军 |
