ww3113306

摘要： 题面： [NOI2017]蔬菜 题解： 首先每天蔬菜会变质这点并不好处理，我们考虑让时间倒流，从后向前处理，这样的话就相当于每天都会得到一定量的蔬菜。 这样做有什么好处呢？ 我们可以发现一个性质：如果从后向前贪心卖菜，那么因为现在可以卖的菜，以后一定还可以卖(因为变成了得到菜)，因此贪心就是对的了。 阅读全文

摘要： 题面：hihoCoder#1698 : 假期计划 组合数 题解： 题目要求是有序的排列，因此我们可以在一开始就乘上A!*B!然后在把这个序列划分成很多段。 这样的话由于乘了阶乘，所以所有排列我们都已经统计到了，因为划分段的时候乘了组合数，所以每段里面的不同排列都已经统计到了，所以就可以解决这道题了。 阅读全文

摘要： ～～～题面～～～ 题解： 考场上只想到了找点双，，，，然后不知道怎么处理奇环的问题。 我们考虑对图取补集，这样两点之间连边就代表它们可以相邻， 那么一个点合法当且仅当有至少一个大小至少为3的奇环经过了它。 观察到只会出现一棵类似树的结构 + t个相对独立的环， 因为环肯定都是独立出来的，所以可以不用 阅读全文

摘要： 在考场上遇到了这个的板子题，，，所以来学习了一下线段树分治 + 带撤销的并查集。 题目大意是这样的：有m个时刻，每个时刻有一个加边or撤销一条边的操作，保证操作合法，没有重边自环，每次操作后输出当前图下所有联通块大小的乘积。 首先观察到如果没有撤销操作，那么直接用并查集就可以维护，每次合并的时候乘上 阅读全文

摘要： 题意： 给定一个序列，你要将其分为k段，总的代价为每段的权值之和，求最小代价。 定义一段序列的权值为$\sum_{i = 1}^{n}{\binom{cnt_{i}}{2}}$,其中$cnt_{i}$表示当前这段序列中数字大小为i的数的个数。 题解： 先考虑暴力DP， f[i][j]表示DP到i位， 阅读全文

摘要： update in 2019.1.21 优化了一下文中年代久远的代码 的格式…… 什么是决策单调性？ 在满足决策单调性的情况下，通常决策点会形如1111112222224444445555588888..... 即不可能会出现后面点的决策点小于前面点的决策点这种情况。 那么这个性质应该如何使用呢？ 阅读全文

摘要： ~~~题面~~~ 题解： 可以发现，每走完一圈付的钱和买的数量是有周期性的，即如果没有因为缺钱而买不起某家店的东西，那么这一圈的所以决策将会和上一圈相同，这个应该是很好理解的，想想就好了。 因为钱数固定时，决策固定，所以每次都O(n)扫一遍看当前情况下走一圈会花多少钱。 然后直接一直取这么多钱，直到 阅读全文

摘要： ～～～题面～～～ 题解： 首先我们要观察到一个性质，因为在固定的起始距离下，经过固定的操作，最后所在的位置是固定的，我们设经过操作1 ~ i之后所在的地方距离终点为d[i]. 那么如果女巫可以修改第i个操作，那么就相当于已经经过了1 ~ i - 1的操作，所以这个时候Alice已经在d[i - 1] 阅读全文

摘要： ~~~题面~~~ 题解： 一开始翻网上题解看了好久都没看懂，感觉很多人都讲得不太详细，所以导致一些细节的地方看不懂，所以这里就写详细一点吧，如果有不对的or不懂的可以发评论在下面。 首先有一个比较明显的50分贪心： 先把d排好序，然后按从小到大的顺序贪心的给每个点选值，同等条件下优先编号大的，于是越 阅读全文

摘要： ~~~题面~~~ 题解： 首先有一个比较明显的策略，肯定先要把能带给自己受益的先选完，然后再以最佳状态去打那些会给自己带来损失的怪。 对于前一部分（可以带来受益的怪），显然我们需要先从代价小的打起，因为这样可以把生命值越积越多，打代价大的怪也更容易成功。 那么对于后一部分怎么办呢？我们需要从受益大的 阅读全文