一条长 的数列。记为 ,现在需要在 中删除最多 个数,使得相邻的 的差尽可能大。
「USACO 2018 US Open Contest」Out of Sorts(Gold) - 模拟 + 树状数组
给定下列魔改冒泡排序的伪代码:
1 | sorted = false |
给定数组 A,统计 moo
语句的执行次数。
「2018.09.09 模拟赛」糖果 - 模拟
有两个长度为 n 的序列 A 和 B,需要从这两个序列中各选若干个数,每选一个数的花费为 W,记每个数列被选择的数的和为 sum,选取的总数为 m,使 min{sumA,sumB}−W⋅m 最小。
「USACO 2018 February Contest」Snow Boots(Silver)- 模拟
有一条长度为 n 的路,其中 2⋯n−1 的单位长度有 fi 单位深度积雪。有 B 双靴子,第 i 双靴子可以承受 si 单位深度的积雪,并前进 di 单位长度。
但是靴子都叠在了一起,如果你需要换第 i 双靴子,需要舍弃这双靴子上面的所有靴子,并且当你站在第 j 单位长度上时,只有 fj≤si 才能换上第 i 双靴子。
请求出最少需要丢弃多少双靴子才能走完这条路。
「USACO 2018 February Contest」Rest Stops - 贪心
Farmer John 和 Bessie 正在攀登一条长度为 L 的山,两人的速度分别为 rF 和 rB,保证 rB<rF。
在路上有 n 个休息站供 Bessie 休息,Bessie 在第 i 个休息站休息 t 单位时间可以获得 ci⋅t 的价值。
请在保证 Bessie 不在 Farmer John 身后的情况下使总价值最大。
「USACO 2018 US Open Contest」Lemonade Line - 贪心
给定一个集合 w,你需要在集合中取出若干个数构成一个序列,使得序列中每个 wi 都满足 i−1≤wi,求数列的最小长度。
「USACO 2018 US Open Contest」Out of Sorts(Silver) - 模拟
给定下列冒泡排序的伪代码:
1 | sorted = false |
给定数组 A,统计 moo
语句的执行次数。
「ditoly 暑假模拟赛」减 - 最短路径 + 二分答案
S君是秘密组织「TB」的成员, 现在他要执行一项潜入任务 。潜入地点可以抽象为一张 n 个点 m 条边的无向图,点编号为 1⋯n,每条边上设有警戒设备,第 i 条边上的警戒值为 wi,警戒值越高代表经过这条边时越危险。现在 S 君已经位于 1 号节点,他需要到位于 n 号节点的数据库上窃取数据。
为了 S 君的安全,S 君的搭档小 N 会在后方提供支援,小 N 可以让至多 k 条边上的警戒设备在这次潜入任务中暂时失效。小 N 的目标是让 S 君执行任务时需要经过的最危险的有效警戒设备的警戒值尽可能小,请你求出这个值。