签到题
Python大法好
求$\Pi_{i=a}^{b}\Pi_{j=c}^{d}Gcd(x^{i},y^{j})$
先分解质因子,然后计算每个质因子的贡献.如果某个质因子是两个数共有的,就计算一下其指数在哪个范围的时候,gcd的结果取第一个数的因子,以及在哪个范围内取第二个数的因子,累计起来即可.需要卡一下常数.
有$n$个集合,每个集合中有一些数.现在要从每个集合中取出一个数,然后再从这些数中取出$m$个,使得这些数的极值差最小.求这个最小值.
二分答案.
把所有数从小到大排序,二分极值差,然后用一个滑动窗口一样的东西遍历排好序的序列,如果在某个时刻窗口中的数来自不同的至少$m$个集合,就认为该答案合法.
给出$n$个数,要求把它们拼成两个数,使得这两个数的积最小.
贪心.第一个数是一个一位数,为给出的数中最小的数.剩下的数按照从小到大的次序排成第二个数.注意不要带前导零.
有两个人在一棵树上玩追逐战,追人的那个速度是2个节点每秒,被追的那个是1个节点每秒.假如两个人都采用最优策略,求被追的人最晚会在什么时候被抓住.
以追人的位置为根建树.显然,被追的人的逃跑路线一定是先从当前位置沿父节点走到某个节点上,然后一直走到该节点最深的儿子的位置.所以预处理下每个节点最深的儿子有多深,然后从被追的人的位置往上枚举即可.
解题的技巧性还是有待提升,比如B题的策略和国王游戏就比较像,J题0转-1想到了,离化成前缀和模型差了一点点.接下来应该多刷点Atcoder?