bzoj4071 [Apio2015]巴邻旁之桥
这是apio里我最自豪的一道题了.让三分党去…吧. k=1直接在所有坐标的中位数处建桥就行了不要问我为什么. 首先感受一下发现可以按(a+b)把序列分成两半,然后两半就是k=1的情况嘛.那直接处理一下每个前缀和后缀的答案就完了辣.
这是apio里我最自豪的一道题了.让三分党去…吧. k=1直接在所有坐标的中位数处建桥就行了不要问我为什么. 首先感受一下发现可以按(a+b)把序列分成两半,然后两半就是k=1的情况嘛.那直接处理一下每个前缀和后缀的答案就完了辣.
apio的第二题.其实是我做题顺序里的最后一道. 我的方法比较奇怪.对于p分开讨论.如果p>c那么直接建边,否则在图的旁边再建若干条链,把这个点连到链上去.然后再跑一下最短路. 卡一卡常数就过去啦.
看上去apio的成绩都出来了,那我就可以写题解喽. 这题比较水啊,尤其是在考试的时候允许多次提交,服务器还跑得飞快.强行bitset压位就好了. 按位从高向低贪心. 对于l=1的情况直接求最少的覆盖区间就好了. 对于剩下的情况,用f[i][j]表示前i个数能否用j个区间覆盖. 完了辣