题意: 给你n个数和一个k. 求这n个数的一个最小子集, 使得元素乘积为k的倍数, 且元素之和最小. 要输出方案. \( n \leq 10^3, k \leq 10^{12} \) 结局: 死在输出方案上了. 思路: 首先发现k的质因数不会很多, 最多有14个. 然后k的因数也不会很多. 所以就dp一下. \(f_i\)表示当前积与k的gcd为i的时候的元素个数. 然后就像个背包一样嘛. 输出方案? 记录从哪里转移来的不就好了. 然后. 考虑这个例子. 3 9 3 24 21 你会先拿24从3更新到9. 然后21就会把3和9的转移都更新. 然后就炸了. 因为3应该是从原来的状态更新的. 但是现在被覆盖了. 然后发现状态是棵树. 可以把状态可持久化记下来. 更新一个状态的时候, 不是直接覆盖, 而是新建一个状态来保证从原来的状态转移出去的情况不会出错. 这样空间复杂度应该和转移次数有关? 然后怎么就糊过去了. 另一个细节是k=1是答案不能是0. woc. 依然感觉很鬼蓄. 代码
还不错的题ovoovo 发现其实要求x的二进制表示中没有相邻的1就行了. 第一问水水的数位dp.从未写得如此愉快. 第二问就是前面的g.然后发现是fib数列.矩阵快速幂搞定.
最近总是被一些水题虐智商啊…怎么回事Ovo 无脑地状压dp一下就好了. 每个物品分开dp,这样可以降到O(2m * n * m)级别. 我还是太弱了.
还比较有意思的一题. 考虑如果Alice选了某一个位置,那么Bob的策略一定是选使得Alice的和最小的一段.也就是对于所有位置,求包含它的所有区间中和最小的一个,再求个max. 这个东西先要展开一倍,然后可以比较方便地用单调队列搞定.
立杰的dp套dp.之前在hwadee培训的时候讲过的题啊. 考虑求lcs时候的f数组的一列,发现相邻两个数要么差1要么不差.于是15就是拿来状压这个东西的. 然后很愉快地写了一个然后很愉快地tle了.妈妈,剧本里没这一节啊. 仔细思考了一下发现每次在计数dp转移的时候去找lcs dp非常慢.而且只要给定状态和转移,目标是确定的.跑1000次浪费了.于是改成预处理转移.就好了.
ioi好神啊,居然写搜索.我显然是不想写高精的啦于是用java于是花费了整整两节课TT 我的想法是dp.设答案为f[m],那么f[m]只与fd有关.设f[i][j]表示i为m的第i小的约数,且已经用了前j个素数的答案.然后就可以转移辣. 然后得二分一下用多大的素数可以卡过.毕竟java自带大常数.而且bzoj坑爹在不管有多少组数据都只多给2秒总时限ovo
看上去apio的成绩都出来了,那我就可以写题解喽. 这题比较水啊,尤其是在考试的时候允许多次提交,服务器还跑得飞快.强行bitset压位就好了. 按位从高向低贪心. 对于l=1的情况直接求最少的覆盖区间就好了. 对于剩下的情况,用f[i][j]表示前i个数能否用j个区间覆盖. 完了辣
题目好长啊,像个阅读题一样.还是比较有意思的一道题.有点像gorgeous和我说的那个原创题的感觉啊. 首先如果没有加边的话那么答案就是∏indegreeu. 如果加了边之后还是dag那么无影响. 如果加了边之后存在一个scc,那么答案就要减去∑(环*∏其它点的indegree).这个东西可以用随随便便的dp来解决.
好玩的数论题。想想发现可以像快速幂一样跑。然后就是思考如何转移优化。 发现模数比较奇怪。居然是fnt的模数ovo那就要用fft喽？可是这里是乘啊。木有关系喽，因为m是素数，所以它一定有原根。于是可以取原根的幂次，就变成加辣。 这种东西我自己当然想不出来ovo 同余系下的东西真有趣ovo
之前听说是异或高消？好神的感觉。 然后可以树形dp嘛！为啥网上题解这么误导ovo 就是f[u][i][j]表示u这个点有没有亮，有没有被按开关。完了嘛。 无语了辣。