TLE_Automatの小窝

求知若饥，虚心若愚

0%

发表于 更新于 分类于
本文字数： 1.4k 阅读时长 ≈ 1 分钟

题目链接

https://codeforces.com/gym/104076/problem/A

题目大意

给定长度为 \(n\) 的序列 \(\{ a_n\}\) ，移去其中长度为 \(m\) 的子序列，对于剩下的元素能进行如下三种操作（无顺序和次数限制）：

  • 加 \(1\)
  • 减 \(1\)
  • 除以 \(2\) 并向下取整

问最少进行多少次操作能把这些数变相同。

数据范围

  • \(1\le n \le 500 , 0 \le m < n, 1\le a_i \le 10^{9}\)
阅读全文 »

发表于 更新于 分类于
本文字数： 2.4k 阅读时长 ≈ 2 分钟

图论相关

题目来源

ABC308Ex

题意

给定一张 \(n\) 个点 \(m\) 条边的无向带权图，找到图中一个权值最小的 \(\text{Q}\) 。

\(\text{Q}\) 定义为一个环带上一条与这个环相连且不在环上的边。

\(4\le n \le 300 , 4\le m \le \frac{n(n-1)}{2}\) 。

思路

考虑枚举每一条边作为 \(\text{Q}\) 的尾巴，然后把这条边删去，从这条边的一个端点跑一个单源最短路。然后再枚举两个点，能够轻松找到不经过这条边的一个最小环。

这样枚举尾巴的时间复杂度为 \(O(n^2)\) ，找最小环的时间复杂度为 \(O(n^2)\) ，总时间复杂度为 \(O(n^4)\) ，这是难以接受的。

考虑到一个环会占用一个点相连的两条边，最劣情况下尾巴也是第三小的边，所以我们第一步不需要枚举所有的边作为尾巴，只需要枚举每个点相连的前三小的边做尾巴即可。这样枚举尾巴的时间复杂度降为 \(O(n)\) ，总时间复杂度降为 \(O(n^3)\) 。

阅读全文 »