枚举最大值的那一行,显然是个\(Catlan\)数,然后一个数能成为行最大值,那么他前面的数都要是他们列的最大值.
 然后枚举两行最大值,\(O(1)\)算算即可.
 有个数对,每次可以取出两个删除他们,并添加一个数对或,问最后能否搞出来给定的一个数对,.
 合并的过程类似一个树形结构,我们发现最后面的数对中肯定来源于原有数对中的数,枚举来源的数对.然后几种情况分别简单讨论即可.
 日竟然想了很久,讨论大法好,不要总想一步解决.
 给定一个个点的带边权图,从中选取出一个团,定义这个方案的权值是团中边权值和减去两端点都不在团中的边权值和.求所有方案的权值和,.
 看到数据范围,显然可以想到将点集分成两半然后分别计算再合并啥的.
 方案的权值跟都不在点集中的边有关,好像不太好算.我们发现一个方案的权值可以用只跟团中点有关值求得.
 设一个点相邻的边权和,一个方案的权值即为.
 有了这个转换,再回到问题,我们分成两个集合.枚举一个集合中选取的点集,然后另一个集合中可选的子集就可以处理出来,然后用子集莫比乌斯变换预处理即可.
 这样复杂度是.
 TCO2016 2A 1000
 时间:
 5.29 22:07(玛雅还没写)
 题意:
 有个机器,每个机器有两个属性,你有张票,每次可以往一个机器里投票.每投一次票,有的概率获得奖励,在没有获得奖励之前不能换机器,并且在获得奖励后下一次投票必须换一个机器.
 问期望最大奖励是多少,.
 题解:
 其实是裸的FFT啊,然而我以为要随时取max,傻逼了.
 表示刚开始往投票,还剩下张票的期望值.然后转移里面只有加法没有max,是一个卷积形式,分治+FFT即可.
 可以过.
 BZOJ4621 TC605hard
 时间:
 6.14 22:37
 题意:
 最初你有一个长度为的数字序列.为了方便起见,序列是一个排列.
 你可以操作最多次.每一次操作你可以先选定一个的一个子串,然后将这个子串的数字全部变成原来这个子串的最大值.问最终有几种可能的数字序列.答案对取模.
 题解:
 ...
 THOI2013 魔塔
 时间:
 5.31 上午考试
 题意:
 你是一个英雄,有个怪物,每个怪物属性为:表示血量,攻击,防御,你也有这三个属性.你和怪物们依次决斗,每回合同时互相攻击,直到一方血量非正,攻击伤害为攻击者的攻击防御者的防御.为了使你最终战胜所有怪物,你可以购买属性,假设属性为,那么所需金币数为,问你最小花金币数.
 .
 题解:
 花费金币数为.
 第一看上去,直接三分套三分啊,然而发现不对劲.
 考虑枚举,因为关于的式子很诡异,然后我们发现有效的对于每个怪物只有个.
 然后确定后这个式子关于导数不增,是个单峰函数,这个就可以求出来,然后发现在递增的时候这个函数的极值点也递减,用单调指针扫就可以了,扫的过程中维护后缀和,由于指针单调修改,查询是可以的.
 总复杂度为.
 THOI2013 星际飞船
 时间:
 5.31 上午考试
 题意:
 有个向量,你需要求出:1.从中选出一些,使得其向量和在上投影最大.2.从中选出一些使得其向量和模长最长.3.从中选出个向量使得其向量和模长最长,求出所有答案.
 题解
 (哼,明明考场上想cai出正解了,结果没时间了)
 一开始没看到有部分分,于是就想第一,二问是在逗比吧,不是只要求出第三问就可以了?于是想起来了数学题里第一问证明的结论是为第二问服务的.于是恍然大悟.
 如果知道最终向量方向,就可以和第一问一样地做,都可以求出来,那就随机或直接暴力精度枚举最终向量,就可以了.
 BZOJ4605 崂山白花蛇草水
 时间:
 6.14
 题意:
 每次在平面一个位置加入一个数,询问矩阵第k大,强制在线.
 题解:
 替罪羊思想+KD-Tree模板题,这两样都没写过= =.
 值域线段树套KD-Tree,因为KD-Tree需要重构,放入内层.
 应用替罪羊思想,当不满足深度平衡时,找祖先中最深的不满足重量平衡的,进行重构.
 然而每次插入后,找到一个最深的不满足重量平衡的会更快= =.
 BZOJ 两个串
 时间:
 6.18
 题意:
 给定两个只含小写字母和通配符'?'(即可以匹配任意一个字符)的串,问在中出现次数.
 题解:
 经典FFT字符串匹配题.
 暴力:
 CF Fuzzy Search算法,对于每一种字母,表示在位置时的该字母匹配数.
 那么对于每个字母,,我们发现这是一个类似卷积的东西,,对于每个字母做FFT即可.
 把式子划开可以得到一个卷积,那么做一遍FFT即可.
 然而我们忘记考虑通配符了,那么重新定义匹配值,只有这一位为'?'时,该位为0.