数据结构 [BZOJ1503]郁闷的出纳员 动态开点权值线段树模板
12 02 20
自己摸索着写的指针版动态开点权值线段树,也没有那么毒瘤。。对于提高或者降低工资,我们可以移动最低工资线,同时记录工资变化多少用于对新人的处理,那么就不用对每个人的工资进行操作了。特别的,对于减工资的操作,我们可以写一...
数据结构 [CF600E] Lomsat gelral 树上启发式合并
12 02 20
树上启发式合并qwq,一听就是很高级的算法,其实也不难。这个算法主要也只能应用于:子树统计无修改操作算法实现过程首先进行轻重链剖分,和树剖不同的是,我们每次先dfs轻儿子,暴力统计答案大小,并且暴力删除轻儿子产生的影...
动态规划 [NOIP2017] Treasure 状压dp+枚举子集
12 02 20
没想到联赛居然考这样的题目了。。trick:枚举子集:for(int i=S;i;i=(i-1)&S)我们发现设$dp[i][S]$表示第i层,状态为S时的最小花费。状态转移方程显然:$dp[i+1][S|s...
数据结构,动态规划 [JXOI2018模拟] way 树形dp+启发式合并
12 02 20
题目大意:给n个点的有根树,每个点有个权值和大小,q个询问,每个询问为x,s,意为在x子树中,选出大小之和不超过s的点,其中最大权值和是多少。考场上写个暴力,考后顺便就学了启发式合并。启发式合并也就是一种思想,即把小...
图论 [JXOI2018模拟]攻略世界树 网络流+建图
12 02 20
Background T3 Description 这是在ALO世界线上。为了帮助桐子救出本子娜,ALfheim Online的多个工会展开了针对世界树的...