杂题乱做 - 2023.10-526互联

写在前面
CF1872G
The 2021 ICPC Asia Jinan Regional Contest - J Determinant
写在最后

写在前面

如题，杂题乱做。

有的时候闲得无聊就写上几题。

唉，菜。

加训！

CF1872G

2000

https://codeforces.com/contest/1872/problem/G

记非 1 位置坐标依次为：\(p_1, p_2, \dots, p_k\)，显然答案只能是非 1 的位置，另外显然当非 1 位置较多时，答案为 \([p_1, p_k]\) 肯定是最优的。

于是考虑定一个非 1 元素乘积的上界，当乘积大于该上界时就直接输出 \([p_1, p_k]\)，否则 \(k\) 较小，直接暴力枚举答案区间即可。

上界定为 \(2^{60}\) 就差不多了，此时 \(k\le 60\)，总复杂度 \(O(\left\lfloor\frac{n}{60}\right\rfloor\times 60^2) = O(60\times n)\)。

为了方便写了 py，其实用 int128 也行。

T = int(input())
lim = 2 ** 60

while T > 0:
  T = T - 1
  n = int(input())
  a = [0]
  p = [0]
  sum1 = [0]
  sum = [1]
  prod = 1

  s = input().split(' ')
  for i in range(1, n + 1):
    a.append(int(s[i - 1]))
    sum1.append(sum1[i - 1] + a[i])
    if a[i] > 1:
      p.append(i)
      if prod < lim:
        prod = prod * a[i]

  if prod >= lim:
    print(p[1], p[-1])
    continue
  
  for i in range(1, len(p)):
    sum.append(a[p[i]])
    sum[i] = sum[i] * sum[i - 1]

  delta = 0
  ansl, ansr = (1, 1)
  for i in range(1, len(p)):
    for j in range(i + 1, len(p)):
      l, r = p[i], p[j]
      if ((sum[j] / sum[i - 1] - sum1[r] + sum1[l - 1]) > delta):
        ansl, ansr = (l, r)
        delta = sum[j] / sum[i - 1] - sum1[r] + sum1[l - 1]
  print(ansl, ansr)
'''
1
4
2 1 1 3
'''

学到了典中典之小范围暴力大范围特判。