首页 > [JLOI2015]装备购买
开通博客写题解
头像 louhc
发表于 2019-08-28 11:58:18
思路 可以像线性基那样做(只不过把二进制换成1000进制而已).因为要求代价最小,我们需要对所有装备按照代价从小到大排序,某件装备尽量被已选装备消去靠前的属性,然后如果遇到某一位不能被消为零,就选该装备并且记录答案.过程基本上和线性基差不多,具体过程参考代码.复杂度为,虽然过亿,但是跑不满,还是可以 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 henry_y
发表于 2019-09-02 21:36:02
真正意义上的线性基...在关于向量加法和标量乘法的线性空间中的线性基。题目的意思就是要构造一个价格最低的基底。对于同个线性空间它的基底的位数不会变，那么要费用最低，可以按费用排序然后依次加入线性基判定是否可行。关于证明，设该线性空间中的向量为，线性基中的向量为，若存在满足，，而A_k是费用最低的一个 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 -符拉迪沃斯托克-
发表于 2021-08-20 22:09:21
真真正正的线性基。。。 上过大一线代的都应该知道，没上过的学过高斯消元或者异或线性基也应该知道。。。 第一反应高斯消元，消到最后就是秩。 但是那个最优解有点难搞。 于是从小到大排个序，依次加入线性基中，还没插满并且插不进去的就是选中的答案。 所以为什么我的代码要开才能过啊。。。 算了，过了就行 附代 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”