当前位置：首页 > news >正文

AtCoder abc 144

news 2025/6/30 15:53:24

D - Water Bottle
x先除以a，得到面积。体积和面积是等同考虑的。
分两种情况，一种是水比一半面积少，一种是水比一半面积多。

# -*- coding: utf-8 -*-
# @time     : 2023/6/2 13:30
# @author   : yhdu@tongwoo.cn
# @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$
求数组元素的两两相乘积最大值不能超过L的解法，并求L的最小值。
当你看到求数组某函数最大值的最小值，并且毫无头绪的时候，就应该想到二分。

元素两两相乘的积很明显的应该从a正序，b倒序进行相乘，此时可以保证L最小。如果不满足性质，那么将a扣掉份额。最后累计要扣掉的份额，计算是否满足题目需求。

# -*- coding: utf-8 -*-
# @time     : 2023/6/2 13:30
# @author   : yhdu@tongwoo.cn
# @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.cn
# @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()