2020-2021:teams:hotpot:200822-200828
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:hotpot:200822-200828 [2020/08/28 13:33] 喝西北风 |
2020-2021:teams:hotpot:200822-200828 [2020/08/28 17:21] (当前版本) misakatao |
||
|---|---|---|---|
| 行 9: | 行 9: | ||
| =====专题===== | =====专题===== | ||
| - | 无 | + | 本周无 |
| =====比赛===== | =====比赛===== | ||
| 行 36: | 行 36: | ||
| =====题目===== | =====题目===== | ||
| + | |||
| + | *Codeforces Round 665 C - Mere Array | ||
| + | *分类：思维 | ||
| + | *题目大意：有$n$个数，问能否从小到大排序，两个数能进行交换的条件是:这两个数的最大公约数是这个数组中最小纸 | ||
| + | *数据范围：多组数据，$T \le 10^4$，$1 \le n \le 10^5$，$\sum n 10^5$ | ||
| + | *解题思路：如果两个数能换那么它们都能和最小值换，所以只要所有位置不对的数都能和最小值换即可 | ||
| + | *Comment：较为简单的思维题 | ||
| + | *Codeforces Round 665 D - Maximum Distributed Tree | ||
| + | *分类：dfs，贪心 | ||
| + | *题目大意：有一棵树$n$个点，给定一个$k$，要求给每个边赋值，使得所有边的乘积是$k$且任意两点间距离和最大 | ||
| + | *数据范围：多组数据，$T \le 100$，$2 \le n \le 10^5$，$\sum n 10^5$ | ||
| + | *解题思路：由于题目给出的$k$是按照质因子给出，我们直接把质因子排序，然后对答案贡献大的边放大的质因子贪心即可 | ||
| + | *Comment：非常显然的贪心题 | ||
| ======郭衍培====== | ======郭衍培====== | ||
| =====专题===== | =====专题===== | ||
| + | |||
| + | 本周无 | ||
| =====比赛===== | =====比赛===== | ||
| 行 63: | 行 78: | ||
| 陶吟翔： | 陶吟翔： | ||
| - | 题目大意： | + | 题目大意：给定$n$个数$a_1,a_2 ... a_n$，问有几个四元组$(i,j,k,l)$满足$i < j < k < l$且$a_i = a_k,a_j = a_l$ |
| - | 数据范围： | + | 数据范围：多组数据，$1 \le T \le 100$，$4 \le a_i,n \le 3000$ |
| - | 解题思路： | + | 解题思路：先$O(n^2)$预处理出每个位置往后某个数有多少，然后枚举$i$和$k$，每次$k$移动的时候会变两个数，直接计算合法的对数，如果此时$a_i=a_k$就把数加进答案 |
| - | 推荐理由： | + | 推荐理由：题目本身简洁明了，有多种解法，考察了做题者优化算法的能力以及通过合适的方式处理数据的能力 |
| 郭衍培： | 郭衍培： | ||
2020-2021/teams/hotpot/200822-200828.1598592781.txt.gz · 最后更改: 2020/08/28 13:33 由 喝西北风
