摘要：
AtCoder Grand Contest 005 A STring 翻译 给定一个只包含$ST$的字符串，如果出现了连续的$ST$，就把他删去，然后所有位置前移。问最后剩下的串长。 题解 模拟栈，和维护括号一样的。 cpp include include using namespace std; 阅读全文
posted @ 2018-09-19 17:06
小蒟蒻yyb
阅读(554)
评论(0)
推荐(0)
摘要：
【BZOJ2724】蒲公英（分块） 题面 "洛谷" 谴责权限题的行为 题解 分块什么的都不会，根本就没写过几次。 复杂度根本不会分析，吓得我赶快来练练。 这题要求的是区间众数，显然没有什么很好的主席树之类的方法。 再加之这个数据范围很像$O(n\sqrt n)$，所以我们来分块，假设块大小为$\sq 阅读全文
posted @ 2018-09-18 20:42
小蒟蒻yyb
阅读(512)
评论(1)
推荐(0)
摘要：
题面 "BZOJ" "洛谷" 题解 和 "这题" 区别不是很大吧。 基本上拿过来改一下就做完了。 cpp include include include include include include include include include using namespace std; defi 阅读全文
posted @ 2018-09-18 17:21
小蒟蒻yyb
阅读(345)
评论(0)
推荐(0)
摘要：
【BZOJ4774】修路（动态规划，斯坦纳树） 题面 "BZOJ" 题解 先讲怎么求解最小斯坦纳树。 先明白什么是斯坦纳树。 斯坦纳树可以认为是最小生成树的一般情况。最小生成树是把所有给定点都要加入到联通块中。而斯坦纳树不一样，斯坦纳树只需要把指定点集中的所有点全部加入到联通块中，并且允许使用点集以 阅读全文
posted @ 2018-09-18 17:07
小蒟蒻yyb
阅读(770)
评论(0)
推荐(0)
摘要：
【BZOJ1864】三色二叉树（动态规划） 题面 "BZOJ" 题解 首先把树给构出来。 设$f[i][0/1]$表示当前节点$i$，是否是绿色节点的子树中最大/最小的绿色节点的个数和。 转移很显然。 cpp include include include include include inclu 阅读全文
posted @ 2018-09-18 16:14
小蒟蒻yyb
阅读(238)
评论(0)
推荐(0)
摘要：
【LOJ6089】小Y的背包计数问题（动态规划） 题面 "LOJ" 题解 神仙题啊。 我们分开考虑不同的物品，按照编号与$\sqrt n$的关系分类。 第一类：$i\le \sqrt n$ 即需要考虑所有的情况，那么设$f[i][j]$表示前$i$个物品装了体积$j$的方案数。 显然$f[i][j] 阅读全文
posted @ 2018-09-18 15:55
小蒟蒻yyb
阅读(855)
评论(0)
推荐(2)
摘要：
【BZOJ4247】挂饰（动态规划） 题面 "BZOJ" 题解 设$f[i][j]$表示前$i$个物品中还剩下$j$个挂钩时的最大答案。 转移显然是一个$01$背包，要么不选：$f[i][j]\rightarrow f[i 1][j]$ 要么选，那么首先这个物品至少要占用一个挂钩，然后它会贡献$a[ 阅读全文
posted @ 2018-09-18 15:28
小蒟蒻yyb
阅读(238)
评论(0)
推荐(0)
摘要：
【BZOJ3202】项链（莫比乌斯反演，Burnside引理） 题面 "BZOJ" "洛谷" 题解 首先读完题目，很明显的感觉就是，分成了两个部分计算。 首先计算本质不同的珠子个数，再计算本质不同的项链个数。 前面一个部分和$gcd$相关，一种莫比乌斯反演的感觉。 后面一个部分出现了旋转操作，要求本 阅读全文
posted @ 2018-09-18 15:07
小蒟蒻yyb
阅读(761)
评论(0)
推荐(0)
摘要：
【HDU5469】Antonidas（点分治，字符串哈希） 题面 "HDU" "Vjudge" 题解 啊哈？什么垃圾一眼点分治+Hash判断，哈哈哈哈哈，让我来码码码。 诶，怎么WA了。改改改改改。 诶，怎么很对啊，去网上蒯一个标程来拍拍拍。 诶，怎么拍不WA啊，让我来人工检测一波啊哈哈哈哈。 感觉 阅读全文
posted @ 2018-09-17 22:30
小蒟蒻yyb
阅读(494)
评论(4)
推荐(0)
摘要：
NOIP考完了，这篇博客彻底咕了。 阅读全文
posted @ 2018-09-16 22:25
小蒟蒻yyb
阅读(1393)
评论(10)
推荐(0)
摘要：
AtCoder Grand Contest 004 A Divide a Cuboid 翻译 给定一个$A B C$的立方体，现在要把它分成两个立方体，求出他们的最小体积差。 题解 如果有一条边是偶数显然可以均分，否分沿着最长边隔开。 cpp include using namespace std; 阅读全文
posted @ 2018-09-16 22:08
小蒟蒻yyb
阅读(305)
评论(0)
推荐(0)
摘要：
AtCoder Grand Contest 003 A Wanna go back home 翻译 告诉你一个人每天向哪个方向走，你可以自定义他每天走的距离，问它能否在最后一天结束之后回到起点。 题解 什么逗逼东西。。。 D Anticube 翻译 给定$n$个数，要求选出最多的数，满足任意两个数的 阅读全文
posted @ 2018-09-15 16:51
小蒟蒻yyb
阅读(329)
评论(0)
推荐(0)
摘要：
AtCoder Grand Contest 002 A Range Product 翻译 告诉你$a,b$，求$\prod_{i=a}^b i$是正数还是负数还是零。 题解 什么鬼玩意。 D Stamp Rally 翻译 给定一张图，每次询问从$x y$选择两条路径，要求被经过的点数恰好为$z$，求 阅读全文
posted @ 2018-09-13 15:33
小蒟蒻yyb
阅读(553)
评论(2)
推荐(0)
摘要：
~~先空着，等停课了再开始写。~~ 诸位好，我是yyb。现在显然已经不再是高一的小蒟蒻了，已经升级为了高二的菜鸡了 现在已经不能再每天划划水切切题了，毕竟......已经高二了，所有的机会从高一的两倍全部除了个二。 怎么说呢？一步错，步步错。虽说比起去年这个时候有了很多的进步，然而留给我出错的机会现 阅读全文
posted @ 2018-09-13 15:09
小蒟蒻yyb
阅读(2855)
评论(57)
推荐(0)
摘要：
AtCoder Grand Contest 001 A BBQ Easy 翻译 给你$2n$个数，需要两两配对成$n$对，每对的权值定义为两个数的较小值，求最大权值和。 题解 排序即可。 E BBQ Hard 翻译 "洛谷" 翻译其实有点问题。 应该是 $$\sum_{i=1}^n\sum_{j=i 阅读全文
posted @ 2018-09-11 10:47
小蒟蒻yyb
阅读(451)
评论(0)
推荐(0)
摘要：
【BZOJ1455】罗马游戏（左偏树） 题面 "BZOJ" 然而权限题。 题解 左偏树模板题。 cpp include include include include include include include using namespace std; define ll long long d 阅读全文
posted @ 2018-09-04 19:50
小蒟蒻yyb
阅读(359)
评论(0)
推荐(0)
摘要：
【BZOJ4242】水壶（克鲁斯卡尔重构树，BFS） 题面 "BZOJ" 然而是权限题。 Description JOI君所居住的IOI市以一年四季都十分炎热著称。 IOI市是一个被分成纵H 横W块区域的长方形，每个区域都是建筑物、原野、墙壁之一。建筑物的区域有P个，编号为1...P。 JOI君只能 阅读全文
posted @ 2018-09-01 11:12
小蒟蒻yyb
阅读(513)
评论(0)
推荐(0)
摘要：
【BZOJ3551】Peaks加强版（Kruskal重构树，主席树） 题面 "BZOJ" Description 在Bytemountains有N座山峰，每座山峰有他的高度h_i。有些山峰之间有双向道路相连，共M条路径，每条路径有一个困难值，这个值越大表示越难走，现在有Q组询问，每组询问询问从点v开 阅读全文
posted @ 2018-08-31 22:19
小蒟蒻yyb
阅读(397)
评论(0)
推荐(0)
摘要：
【agc023E】Inversions（线段树，动态规划） 题面 "AT" 给定$a_i$，求所有满足$p_i\le a_i$的排列$p$的逆序对数之和。 题解 首先如何计算排列$p$的个数。 设$cnt[i]$表示$a_k\ge i$的个数，那么满足条件的$p$的总数就是$\prod cnt[i] 阅读全文
posted @ 2018-08-31 19:46
小蒟蒻yyb
阅读(1056)
评论(0)
推荐(0)
摘要：
【CF183D】T shirt（动态规划，贪心） 题面 "洛谷" "CodeForces" 题解 $O(n^2m)$的暴力懒得写了，比较容易，可以自己想想。 做法是这样的，首先我们发现一个结论： 对于某个颜色（我们就把尺寸当成染色问题好了），如果你拿的个数越多，那么它对于答案的贡献就越来越少。这个东 阅读全文
posted @ 2018-08-30 21:16
小蒟蒻yyb
阅读(291)
评论(0)
推荐(0)
摘要：
【BZOJ2423】最长公共子序列（动态规划） 题面 "BZOJ" "洛谷" 题解 今天考试的时候，神仙出题人$fdf$把这道题目作为一个二合一出了出来，我除了orz还是只会orz。 对于如何$O(n^2)$求解最长的长度是很简单的。 设$f[i][j]$表示第一个串匹配到了$i$，第二个串匹配到了 阅读全文
posted @ 2018-08-30 20:25
小蒟蒻yyb
阅读(384)
评论(0)
推荐(0)
摘要：
【BZOJ2118】墨墨的等式（最短路） 题面 "BZOJ" "洛谷" 题解 和跳楼机那题是一样的。 只不过走的方式从$3$种变成了$n$种而已，其他的根本没有区别了。 cpp include include include include using namespace std; define M 阅读全文
posted @ 2018-08-30 08:31
小蒟蒻yyb
阅读(339)
评论(0)
推荐(0)
摘要：
【洛谷3043】跳楼机（最短路） 题面 "洛谷" 题解 思路很妙嗷。 先只考虑只用$y,z$两种移动方式，它们一定能够到达一些楼层， 那么这些楼层再只用$x$拓展就能够计算答案。 那么我们这样子计算答案，设$dis[i]$表示可以到达$mod\ x=i$的楼层的最小值， 显然这个玩意可以最短路求，那 阅读全文
posted @ 2018-08-30 08:16
小蒟蒻yyb
阅读(401)
评论(0)
推荐(0)
摘要：
【BZOJ2463】谁能赢呢？（博弈论） 题面 "BZOJ" "洛谷" 题解 洛谷上对于难度的评级我总觉有些问题。 很多人按照代码难度而并非思维难度在评级，导致很多评级很不合理啊。。。 不说废话了。。 对于一个$n n$的棋盘，我们可以考虑用$1\times 2$的骨牌来进行覆盖。 显然对于$n$为 阅读全文
posted @ 2018-08-29 08:07
小蒟蒻yyb
阅读(272)
评论(0)
推荐(0)
摘要：
【BZOJ3609】人人尽说江南好（博弈论） 题面 "BZOJ" "洛谷" 题解 昨天考试的时候，毒瘤出题人出了一个$noip$博弈十合一~~然后他就被阿鲁巴了，因为画面残忍，就不再展开。~~ 这题是他的十合一中的第四问，然而我并不会做，所以自己就大力YY了一下， 首先一定有$[n/m]$个大小为$ 阅读全文
posted @ 2018-08-29 07:57
小蒟蒻yyb
阅读(323)
评论(0)
推荐(0)
浙公网安备 33010602011771号