AtCoder abc 144"/>
AtCoder abc 144
D - Water Bottle
x先除以a,得到面积。体积和面积是等同考虑的。
分两种情况,一种是水比一半面积少,一种是水比一半面积多。
# -*- coding: utf-8 -*-
# @time : 2023/6/2 13:30
# @author : yhdu@tongwoo
# @desc :
# @file : atcoder.py
# @software : PyCharmimport bisect
import copy
import sys
from sortedcontainers import SortedList
from collections import defaultdict, Counter, deque
from functools import lru_cache, cmp_to_key
import heapq
import math
sys.setrecursionlimit(50050)def main():items = sys.version.split()if items[0] == '3.10.6':fp = open("in.txt")else:fp = sys.stdina, b, x = map(int, fp.readline().split())x /= aif x >= 0.5 * a * b:y = 2 * (a * b - x) / at = (math.atan2(y, a) / math.pi) * 180print(t)else:y = 2 * x / bt = (math.atan2(y, b) / math.pi) * 180print(90 - t)if __name__ == "__main__":main()
E - Gluttony
等价于求两个数组
a 1 , a 2 . . . a n b 1 , b 2 . . . b n a_1,a_2...a_n \\ b_1,b_2...b_n a1,a2...anb1,b2...bn
求数组元素的两两相乘积最大值不能超过L的解法,并求L的最小值。
当你看到求数组某函数最大值的最小值,并且毫无头绪的时候,就应该想到二分。
元素两两相乘的积很明显的应该从a正序,b倒序进行相乘,此时可以保证L最小。如果不满足性质,那么将a扣掉份额。最后累计要扣掉的份额,计算是否满足题目需求。
# -*- coding: utf-8 -*-
# @time : 2023/6/2 13:30
# @author : yhdu@tongwoo
# @desc :
# @file : atcoder.py
# @software : PyCharmimport bisect
import copy
import sys
from sortedcontainers import SortedList
from collections import defaultdict, Counter, deque
from functools import lru_cache, cmp_to_key
import heapq
import math
sys.setrecursionlimit(50050)def main():items = sys.version.split()if items[0] == '3.10.6':fp = open("in.txt")else:fp = sys.stdinn, k = map(int, fp.readline().split())a = list(map(int, fp.readline().split()))b = list(map(int, fp.readline().split()))a.sort()b.sort(reverse=True)def check(x):ret = 0for i in range(n):if a[i] * b[i] <= x:continueret += a[i] - x // b[i]return ret <= klo, hi = 0, 10 ** 13while lo < hi:mi = (lo + hi) // 2if check(mi):hi = mielse:lo = mi + 1print(lo)if __name__ == "__main__":main()
F - Fork in the Road
普通不删点的dp不难想到。
N=600下,枚举每条可能删的边会超时。但是由于只需要删一条边,因此针对每个点,只可能是它期望值最大的子节点和它之间的那条边被删掉。
因此暴力求解即可。
# -*- coding: utf-8 -*-
# @time : 2023/6/2 13:30
# @author : yhdu@tongwoo
# @desc :
# @file : atcoder.py
# @software : PyCharmimport bisect
import copy
import sys
from sortedcontainers import SortedList
from collections import defaultdict, Counter, deque
from functools import lru_cache, cmp_to_key
import heapq
import math
sys.setrecursionlimit(50050)def main():items = sys.version.split()if items[0] == '3.10.6':fp = open("in.txt")else:fp = sys.stdinn, m = map(int, fp.readline().split())g = [[] for _ in range(n)]f = [0] * na = [0] * ndef calc(pt: int):mx, sel = -1, -1if len(g[pt]) == 1:return 1e18for i in g[pt]:if a[i] > mx:mx, sel = a[i], ifor i in range(n - 2, -1, -1):f[i] = 0c = 0for j in g[i]:if i == pt and j == sel:continuef[i] += f[j]c += 1f[i] = f[i] / c + 1return f[0]for i in range(m):u, v = map(int, fp.readline().split())u, v = u - 1, v - 1g[u].append(v)for i in range(n - 2, -1, -1):a[i] = 0for j in g[i]:a[i] += a[j]a[i] = a[i] / len(g[i]) + 1ans = a[0]for i in range(n - 1):ans = min(ans, calc(i))print(ans)if __name__ == "__main__":main()
更多推荐
AtCoder abc 144
发布评论