这篇文章受密码保护，输入密码才能阅读

这篇文章受密码保护，输入密码才能阅读

题面 这题的关键在求其他所有点到$X$的最短路径. Floyd显然过不了. 冷静分析一波发现无向图中从某个点到$X$的最短路就等于从$X$到那个点的最短路, 有向图中所有边取反后也成立. 所以取反之后在求一次单源最短路就行了. [collapse title="展开代码"] #include<cstdio> #include<cs…

题面 一开始想到一个错误策略: 每次在当前油量能走到的范围内找油最多的加油站...后面发现有可能会要在范围内多次加油才可能走到终点, 需要根据油量从大到小依次选择加油站, 于是容易想到用一个大根堆来维护所有可以走到的油站, 直到不能再走就不断依次选择油站来继续往前走. 如果没有油站可以选就走不到终点. 注意输入的是到终点的距离. [collapse…

题面 首先面值大于$ C$的硬币肯定只能直接计入答案. 剩下的硬币肯定要凑出尽可能接近$ C$的面值, 策略是在面值不超过$ C$的前提下优先使用大面值, 因为这样可以在使现在和将来避免浪费钱的前提下凑近$ C$. 如果不能恰好凑出$ C$而剩余$ x$必须浪费钱时, 就可以优先用小面值补全$ x$, 来使浪费最小化. [collapse titl…

题面 题意: 要用尽量少的6*6的箱子放入一些1*1~6*6的物品, 设他们分别有$ a_i$个. 首先答案至少要$ a_6+a_5+a_4$这么多, 因为他们是不能多个并存的. 然后对于5*5和4*4的物品我们就可以贪心地在空隙中插入物品. 对于放了5*5的箱子每个可以插11个1*1. 对于放了4*4的箱子每个可以放5个3*3和7个1*1, 如果…

题面 感觉这题最水... 显然$ a$越低就越难赢, 而只要每次比赛$ a$之差都在$ k$内就可以赢. 所以每个人都要尽量和第一个$ a$比它大的人比, 如果在n-1场比赛中有一场$ a$的差值大于$ k$就不行, 而且所有比它$ a$小的都不行了(因为都要和它比$ a$还比它小). 于是可以升序排序然后从后往前统计答案. [collapse t…

这篇文章受密码保护，输入密码才能阅读

题面 毒瘤数据结构复习系列. 设0为未安装, 1为已安装, 当安装某个包x时, 统计root~x路径上0的个数, 再把整条路径设为1 卸载包x时, 统计x为根的子树1的个数, 再把整颗子树设为0 线段树的区间覆盖只要把懒标记的+=改为=就行了 看到题解中还有一种更妙的做法: 只进行update操作, 统计线段树根节点sum值变化即可, 理论上常数是…

题面 标题比题面好懂系列. 题目就是要求所有环中边权之和与环长之比的最小值. 令点权为1(方便统计长度. 更一般的0/1分数规划题中点权是可以任意取的, 后续推导一致), 则 $ ans=\sum{e.w}/\sum{v.w}$ $ \sum{e.w}-ans*\sum{v.w}=0$ $ \sum(e.w-ans*v.w)=0$ $ \sum_{…