bzoj水题大乱斗(一)

作者: 99hgz 分类: noip 发布时间: 2099-12-31 15:48

水题warning

请大佬在菜鸡的陪同下观看

 

bzoj100题题解

首先说一下,这里有那么几个题解还是从网上抄的,如果你发现了差不多的题解,不要怀疑,他就是抄我的

id 题目名 算法 实现细节
1000 A+B Problem 模拟 世纪难题
1001 [BeiJing2006]狼抓兔子 最短路 平面图最小割,推荐论文https://wenku.baidu.com/view/a10e0529bd64783e09122ba9.html?re=view
1002 [FJOI2007]轮状病毒 基尔霍夫矩阵 果断是抄的,还偷懒写了python,生成树的计数,论文https://wenku.baidu.com/view/782ab9eb19e8b8f67c1cb9a9.html
1003 [ZJOI2006]物流运输 最短路,DP 预处理第i天到第j天每天都能走的最短路,dp推一发,注意初始值
1008 [HNOI2008]越狱 组合数学 拿总的减去不合法的,即不会越狱的情况,那么第一个有m种可以选,后面每个都有m-1种可以选
1010 [HNOI2008]玩具装箱toy 斜率优化,DP 斜率优化嘛,不会的话为什么不问问隔壁hk呢
1012 [JSOI2008]最大数maxnumber 单调栈 如果对于i<j有a[i]<a[j]那么a[i]死都用不上。栈里要存位置,查询的时候二分下
1029 [JSOI2007]建筑抢修 贪心 贪心,先以T2排序,建一个大根堆。枚举所有建筑,如果当前建筑能修就修,不能修就在堆里找一个T1最大的,判断去掉它后1能不能修2时间是不是更少即是不是更优
1036 [ZJOI2008]树的统计Count 树链剖分 裸题
1040 [ZJOI2008]骑士 基环外向树+树形DP 把恨的人转化为它在树上的父亲,先想到二分图的最大权值独立集,转化为网络流在这么大的数据范围下显然不行。(然后偷瞄了几眼题解)那么对于一棵树,做法就同 没有上司的舞会一样。那么现在n个点,n条边,可能是基环外向树森林。对于一个环,先dfs找到一个环边,断开这条边(记录一下不要通过这条边转移),转化为树。对于这条边连接的点u,v,因为不能同时选u,v,那么有两种情况,不选u,v随意,不选v,u随意,对应dp时的f[u][0]和f[v][0],这个联通块的最大值就是取个max。因为是森林,所以,把所有联通块的最大值都加起来就好了。
1050 [HAOI2006]旅行comf 并查集 (又看了一眼题解)既然是个分数,要求值最小,那么和 秦始皇的国家道路系统 有些雷同,枚举最小边的值,找一个合法的最小的边来做分子。然后就没想出来(划掉)。先按边的权值从小到大排序,枚举第i条边做最小边,那么从再按顺序枚举剩下的边做分子,这里用并查集来维护S和T的连通性,当联通的时候就可以统计答案了。
1051 [HAOI2006]受欢迎的牛 强连通缩点 对于一个联通块里的牛,获得了这个块内所有牛的欣赏,如果缩点后处在拓扑图尾端(即出度为0)的块有且仅有一个,那么这个块内的所有牛都符合条件
1053 [HAOI2007]反素数ant 数学+搜索 “应该算反素数里比较水的吧,主要满足两个性质(1)一个反素数的所有质因子必然是从2开始的连续若干个质数,因为反素数是保证约数个数为的这个数尽量小(2)同样的道理,如果n=2^t1*3^t2*5^t3*…,那么必有t1>=t2>=t3>=…,然后就可以dfs大暴力啦,推荐http://blog.csdn.net/ACdreamers/article/details/25049767
1064 [Noi2008]假面舞会 图论+dfs找环找链 非常电压的题目,题解http://blog.sina.com.cn/s/blog_86942b1401015r81.html,反正菜鸡是想不出来的。主要思路就是a能看到b,那么就建一条边a->b。然后分两种情况:有环,只有树。对于第一种情况,找出这些环,k的最大值就是这些环的大小的最大公约数。k的最小值就是k的最大值中第一个大于等于3的约数。因为题目中说“由于并不是每个人都能记住自己所看到的全部编号”,那么只要环满足,树一定能满足。第二种情况k的最大值就是所有链的链长之和。最小值显然是3。关于找环:双向建边,对每个点进行标号,遇到正向边标号+1,反向边标号-1,然后当遇到已经被标号了的点,就说明找到了一个环,其点的个数为|已标号-当前标号|,然后标号不变继续查找。
1083 [SCOI2005]繁忙的都市 最小生成树 裸题,写的prim也过了
1089 [SCOI2003]严格n元树 DP 抄题解啦啦啦。假设我们已知dp[i-1],那么深度不大于i的树就相当于多出了一个根节点,其每一个儿子(共n个儿子)都是一颗深度不大于i-1的树。那么dp[i]=dp[i-1]^n+1(还有没有儿子的情况),直接线性递推就可以得到答案了。(长一个根挺巧妙的)
1143 [CTSC2008]祭祀river 最大独立集 定义:选出一些顶点使得这些顶点两两不相邻,则这些点构成的集合称为独立集。找出一个包含顶点数最多的独立集称为最大独立集。方法:最大独立集=所有顶点数-最小顶点覆盖。证明:若2,4,7构成最小顶点覆盖,那么其他点6个构成最大独立集。且其他点不可能相连。假设其他点相连则这条边必定没有被2,4,7 覆盖,与2,4,7是最小顶点覆盖矛盾。因此其他点之间必定没有边。而2,4,7是最小顶点覆盖,所谓最小就是不能再小了,因此我们的独立集就是最大了。
1179 [Apio2009]Atm 最短路+缩点 强连通缩点,记录这个强连通内所有ATM 的钱的总和,构建新图,从S到T跑最短路即可
1208 [HNOI2004]宠物收养所 Splay 最讨厌splay了,还得维护两个splay,hzw那里有用set水过的代码
1212 [HNOI2004]L语言 trie+DP “首先令f[i]表示到i的前缀能否被理解,那么答案就是f[i]==1时最大的i转移也很简单,如果f[i]==1,这个串就可以从i+1开始匹配一个新单词,因为单词长度<=10,暴力在trie上走就是了
1214 [HNOI2004]FTP服务器 模拟? 看到题的第一眼慌掉了,这么复杂的模拟题?当看到Python 2B的时候就懂了
1237 [SCOI2008]配对 DP 可以证明配对的两个数的位置最多差两格远,不然会有更优方案
1305 [CQOI2009]dance跳舞 网络流+二分 裂点,仔细想想还算简单的,当时智障连错边WA了一天
1412 [ZJOI2009]狼和羊的故事 最小割 建图:狼连原点,边权inf,羊连汇点,边权inf。狼到空地,狼到羊,空地到羊,连边,边权为1。最大流最小割定理完事。基本套路?
1433 [ZJOI2009]假期的宿舍 二分图最大匹配 裸题
1477 青蛙的约会 扩展欧几里得 裸题
1486 [HNOI2009]最小圈 二分+spfa 二分最小值,每条边都减去mid,如果存在负权圈,说明有一个平均权值<mid的圈
1500 [NOI2005]维修数列 splay 贴的代码,不想说话,听说可以rope水过
1588 [HNOI2002]营业额统计 splay 娘的又是splay,也有set水过的方法
1597 [Usaco2008 Mar]土地购买 斜率优化,DP 不是很懂,再去看看题解
1607 [Usaco2008 Dec]Patting Heads 轻拍牛头 暴力 for循环专练
1798 [Ahoi2009]Seq 维护序列seq 线段树 线段树+lazytag模板题
1800 [Ahoi2009]fly 飞行棋 暴力 就是暴力嘛
1823 [JSOI2010]满汉全席 2-SAT 模板题
1857 [Scoi2010]传送带 三分套三分 貌似是我在bzoj上交的第一题,三分AB上的点再三分CD上的点,没证过
1876 [SDOI2009]SuperGCD 高精度 Python水过
1968 [Ahoi2005]COMMON 约数研究 暴力 又刷了一道水题
1975 [Sdoi2010]魔法猪学院 k短路 A*+spfa,一直找接下来的一条路,直到能量不够,用STL的优先队列也过了
2002 [Hnoi2010]Bounce 弹飞绵羊 分块 分块,每个元素计算几次弹出所在块和弹出后落到的位置
2038 [2009国家集训队]小Z的袜子(hose) 莫队 莫队模板题
2111 [ZJOI2010]Perm 排列计数 组合数学 完全忘光了,设f[i]表示以i为根的子树形成小根堆的方案数,f[i]=C(si[i<<1],si[i]?1)?f[i<<1]?f[i<<1|1]
2115 [Wc2011] Xor dfs找环+线性基 任意地先找出一条从1到n的路径,把这条路径上的xor和作为ans初值,然后求若干个环与这个ans初值所能组合成的xor最大值。
2118 墨墨的等式 最短路+数论 “若x能被表示出来,那么x+a[1]*k也能被表示出来,那么就要求最小的x[i]满足x[i]%a[1]==i,最小值转化为最短路就是i向i+a[j]%a[1]建一条长度为a[j]的边,最后所有小于等于x的能被构造出来的数总共ans[x]=∑((x – d[i]) / a[1]) + 1(0<=i<a[1])个,答案即为ans[bmax]-ans[bmin-1]
2120 数颜色 莫队 带修改的莫队,多一维记录时间,作为第三级关键字,暴力修改就行了,感觉没多大用
2140 稳定婚姻 强连通分量 结论:在同一个强连通分量里的夫妻是危险的
2152 聪聪可可 树形DP 求出每个节点i长度对3取模为j的点数f[i][j],直接统计
2227 [Zjoi2011]看电影(movie) DP 抄题解:概率等于合法的方案数除以总方案数。总方案数=K^N,合法方案数的计算:在最后面加一个座位,然后所有的座位连成一个环。现在那么总方案数等于(K+1)N,每种环都算了(K+1)次,所以除以(K+1),最后抽调一个空白的座位来构造一个合法的方案,所以要乘(N?K+1)。ans=(K+1)^(N-1)*(K-N+1)/K^N
2242 [SDOI2011]计算器 数论 第二个扩欧,后一个BSGS,模板题
2257 [Jsoi2009]瓶子和燃料 裴蜀定理 两个容量为a和b的瓶子,它们倒来倒去最后可以得到的体积一定是ax+by (x和y为可为负的整数)。裴蜀定理:若a和b是整数,且Gcd(a, b)==d,那么ax+by(x和y为整数)一定是d的倍数
2330 [SCOI2011]糖果 差分约束 这题神坑,如果按普通方法建边的话会有负边,就会出现负权,那么最后统一加一个值是错的,因为不一定联通。所以要转化,这题要倒着建边的玄学优化?
2333 [SCOI2011]棘手的操作 左偏树 左偏树模板题,带标记,这题靠着hzw大神的对拍,总共还写了4个小时,交了4发才过,感觉写了几百个BUG
2435 [Noi2011]道路修建 DFS 看起来像水题,就是水题,直接DFS,也算是Noi题??
2460 [BeiJing2011]元素 线性基 “线性基模板题,能插入到线性基里就把膜力加起来。线性基的性质:1.线性基的异或集合中不存在0。2.线性基的异或集合中每个元素的异或方案唯一,其实这个跟性质1是等价的。3.线性基二进制最高位互不相同。4.如果线性基是满的,它的异或集合为[1~2^n-1]。证明左转拟阵。
2462 [BeiJing2011]矩阵模板 HASH 一开始以为是KMP,GTMD我又不会写,查了下题解是矩阵hash,跟一维差不多,自己想吧
2463 [中山市选2009]谁能赢呢? 博弈论 直觉告诉我跟面积奇偶有关,证明:首先对于n是偶数,一定能被1*2的骨牌覆盖!所以从起点开始,先手一定走的是骨牌的另一端,后手一定走的是骨牌的前一端,因此无论何时,先手总是可以走。因此先手必胜。
2656 [Zjoi2012]数列(sequence) 高精度 展开可得k1*A[2i]+k2*A[2i+1]=(k1+k2)*A[i]+k2*A[i+1],+Python没了
2705 [SDOI2012]Longge的问题 欧拉函数 枚举n的约束k,令f(k)为gcd(i,n)=k的i个数(i<=n),答案为∑(k*f(k))。∵gcd(i,n)=k ∴gcd(i/k,n/k)=1=euler(n/k)
2730 [HNOI2012]矿场搭建 tarjan+DFS 求割点,分三种情况:1.联通块内没有割点,建两个出口,方案数*=size*(size-1) 2.联通块内有一个割点,建一个出口,方案数*=size 3.联通块内有三个以上个点,不用建
2754 [SCOI2012]喵星球上的点名 后缀数组 后缀数组模板题,最水的一道?感觉我就能理解这道的解法,果然我太渣了,什么 弦论 根本搞不懂。做法就是把所有字符串连起来,中间接个分割字符,然后对每个点名,找到,排名rank,再向左右找,直到公共前缀长度小于点名的长度,再在这个区间里统计有哪些喵即可。(其实是对暴力的优化)
2761 [JLOI2011]不重复数字 STL SET,MAP随便搞
2809 [Apio2012]dispatching 左偏树+DFS 左偏树。对每个节点维护一个堆,堆的大小,总的薪水三个值。从根DFS,先递归儿子,再把信息都合并,如果总的薪水>预算,那么就弹出最大值,直到薪水<预算,更新答案
3155 Preprefix sum 树状数组 差分一下,同理可以得到树状数组区间修改的方法,不会的自行百度
3207 花神的嘲讽计划Ⅰ HASH+STL 正解应该是主席树来存HASH的值吧,这里又用vector水过了,存一个hash的值和出现位置,找的时候挨个找再判断就行了
3224 Tyvj 1728 普通平衡树 Splay 用pb_ds里的splay水过了,洛谷上有vector的写法
3289 Mato的文件管理 莫队+树状数组 每次需要交换的次数就是区间内的逆序对数,先用莫队,修改答案的时候用树状数组就好了
3295 [Cqoi2011]动态逆序对 CDQ分治 三维CDQ分治模板题,一维来记录插入时间(倒着做),一直都在的为0,注意统计对答案的影响的时候有两种情况,如果你是像我一样最后一位是插入时间,还要判断时间相同的情况
3439 Kpm的MC密码 DFS序+主席树+Trie DFS序和主席树简直绝配,先对所有字符串倒着建trie树,那么一个串的kpm串就在它的子节点上。插完后对trie树进行DFS编号,那么每个点都有进入时间in和退出时间out,,如果这个点对应了一个存在的字符串,就把编号插到主席树上in这个位置上。对于每个查询,就是找 字符串对应的trie树节点的in到out区间内的第k小的数。
3555 [Ctsc2014]企鹅QQ HASH 枚举去掉哪一位,HASH即可
3624 [Apio2008]免费道路 并查集 用并查集维护连通性,1.先加入所有水泥路,判断是联通块数是否小于等于k + 1,否则输出无解。2.加入鹅卵石路,要求每条路连通两个不连通的集合,并标记为选中,判断联通块是不是只有一个,否则输出无解。3.删除所有边。4.插入第二步所选的边,共addedges条,再插入k-addedges条鹅卵石路,加不到输出无解。5.最后补上能连的水泥路即可
3626 [LNOI2014]LCA 树链剖分 x和y的lca的深度,可以把x到根的所有结点加1,求y到根的路径上的权值和即可,那么可以用树链剖分维护,同时用支持区间操作带懒惰标记的线段树。最后用ans(r)-ans(l)即可。
3680 吊打XXX 爬山算法 物理题?反正我不会,左转hzwer.com
3714 [PA2014]Kuglarz 最小生成树 要知道每一个位子有球,就得知道sum(i)-sum(i-1)。花费a[i][j]即可把i-1,j放到同一个集合里,最后要所有i在同一个集合,那么对每一个a[i][j],建一条i-1到j权值为a[i][j]的边,跑最小生成树即可。
3767 A+B Problem加强版 模拟 python
4003 [JLOI2015]城池攻占 左偏树 代标记的左偏树模板题,参考2809,战胜之后打标记即可。这里维护了三个标记,统一加了多少,称了多少,攻下几个城池。
4033 [HAOI2015]树上染色 树形DP f[i][j]表示i结点及其子树总共染黑j个点所获得的最大收益。对于每一条边,贡献为左边白点数*右边白点数+黑点*黑点。
4195 [Noi2015]程序自动分析 并查集 先把所有相等的并起来,在判断不等的满不满足即可
4198 [Noi2015]荷马史诗 哈夫曼编码 插入一些长度为0,深度为1的树,把字符串总数凑到k-1的倍数,然后每次以k个最短的字符串做哈夫曼编码。
4236 JOIOJI map+hash 维护前缀和,插到map里
4326 NOIP2015 运输计划 二分+LCA+树上差分 树上差分:找出被所有路径都覆盖的边,在树中将所有路径起、始权值加1,起、始点的lca权值减2,从所有叶节点开始把权值往上累加。二分最短时间x,那么所有大于x的路径都要改造。找到这些路径,判断这些路径是否有共同覆盖的边,即为要改造的边,乱搞判断即可。
4415 [Shoi2013]发牌 线段树 转化为每次查询第k大的问题
4443 [Scoi2015]小凸玩矩阵 二分+二分图匹配 二分答案x,那么就要找到n-k+1个小于x的数。遍历a[i][j],若a[i][j]<x则i像j连一条边,跑二分图匹配即可。
4523 [Cqoi2016]路由表 trie树+单调栈 建一棵trie树,点内存插入时间的编号。每次查找的时候维护一个单调上升的序列,最后统计序列内有多少点在l~r区间内
4551 [Tjoi2016&Heoi2016]树 dfs+并查集 先dfs把最后的并查集求出来,让每个代表及的点成为并查集的根,到这处理询问,询问的就是这个点的集合的根,去掉标记就是把x和x的父亲连起来
4604 kth maximum number 模拟 照题意暴力即可,升级版4605
4719 [Noip2016]天天爱跑步 线段树+DFS序 推荐题解http://www.cnblogs.com/TheRoadToTheGold/p/6677435.html,把一条路径分成向上的和向下的,可以计算得可以统计答案的深度,用dfs序来限制答案在子树内
4802 欧拉函数 素数测试+质因数分解 MillerRabin+PollardRho模板题
4950 [Wf2017]Mission Improbable 二分图匹配 求每一行和每一列的最大值,遍历,若i行的最大值=j列的最大值,从i向j建边。最后跑二分图匹配,注意0的情况
4952 [Wf2017]Need for Speed 二分 数学题+二分
4953 [Wf2017]Posterize DP 貌似是贴的,自己写的超时了…,题解http://www.lydsy.com/JudgeOnline/upload/7sol.pdf
4956 [Wf2017]Secret Chamber at Mount Rushmore 传递闭包 求每两个字符间能否转移,然后暴力判断即可
4972 小Q的方格纸 前缀和 构造一个梯形的前缀和和一个矩形的前缀和,乱搞即可
4975 区间翻转 正序对 可证一次操作都会使正序对数和逆序对数互换且顺序对奇偶性发生变化,最后正序对数为0,所以若顺序对数为偶数,先手必败否则必胜
4976 宝石镶嵌 DP 若n – k > (log(最大值) / log(2),答案即为所有数or的结果,否则dp直接转移。
4989 [Usaco2017 Feb]Why Did the Cow Cross the Road 树状数组 先统计总的逆序对数,每次暴力用树状数组旋转即可
4990 [Usaco2017 Feb]Why Did the Cow Cross the Road II LCM 转化为最长公共前缀
4991 [Usaco2017 Feb]Why Did the Cow Cross the Road III CDQ分治 三位偏序裸题
4992 [Usaco2017 Feb]Why Did the Cow Cross the Road spfa “一个点拆成走了3k,3k+1,3k+2步3个点,建边,最短路
4993 [Usaco2017 Feb]Why Did the Cow Cross the Road II LCM 转化为最长公共前缀
4994 [Usaco2017 Feb]Why Did the Cow Cross the Road III 树状数组 二位偏序稍加改动,a先从小到大排序,统计a[j]<b<b[j]的个数
5039 [Jsoi2014]序列维护 线段树 同1798

发表评论

电子邮件地址不会被公开。 必填项已用*标注