2020-2021:teams:hotpot:200822-200828
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:hotpot:200822-200828 [2020/08/28 13:29] 喝西北风 |
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：非常显然的贪心题 | ||
| ======郭衍培====== | ======郭衍培====== | ||
| =====专题===== | =====专题===== | ||
| + | |||
| + | 本周无 | ||
| =====比赛===== | =====比赛===== | ||
| 行 48: | 行 63: | ||
| =====题目===== | =====题目===== | ||
| + | |||
| + | 本周无 | ||
| ======本周推荐====== | ======本周推荐====== | ||
| 行 61: | 行 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$就把数加进答案 |
| - | 推荐理由： | + | 推荐理由：题目本身简洁明了，有多种解法，考察了做题者优化算法的能力以及通过合适的方式处理数据的能力 |
| 郭衍培： | 郭衍培： | ||
| - | 题目大意：给定长度为$2^n$的序列。q次操作，一共四种。一是单点修改，二是给定k，对任意i翻转$[(i-1)\cdot 2^k+1,i\cdot 2^k]$，三是给定k，对任意i交换$[(2i-2)\cdot 2^k+1,(2i-1)\cdot 2^k],[(2i-1)\cdot 2^k+1,2i\cdot 2^k]$，四是区间求和。 | + | 题目大意：给定长度为$2^n$的序列。q次操作，一共四种。一是单点修改，二是给定$k$，对任意$i$翻转$[(i-1)\cdot 2^k+1,i\cdot 2^k]$，三是给定$k$，对任意$i$交换$[(2i-2)\cdot 2^k+1,(2i-1)\cdot 2^k],[(2i-1)\cdot 2^k+1,2i\cdot 2^k]$，四是区间求和。 |
| 数据范围：$n\le 18,q\le 10^5$ | 数据范围：$n\le 18,q\le 10^5$ | ||
| 行 77: | 行 94: | ||
| 解题思路：第二种操作，相当于$a_i$变为$a_{i\wedge (2^k-1)}$，第三种操作相当于$a_i$变为$a_{i\wedge (2^k)}$。因此可以用x表示，当前$a_i$变为$a_{i\wedge x}$。对于区间求和，相当于求$\sum_{i=l}^r a_{i\wedge x}$。不难发现，对[l,r]，若l和r的二进制正好从某一位开始,l都是0，r都是1，这一位前都相等，则[l,r]异或x后仍在连续的一段区间。而任意一段区间，都可以拆成log个满足上述要求的区间。因此可以用一棵支持单点修改，区间求和的线段树来完成这道题。时间复杂度$O(qn^2)$ | 解题思路：第二种操作，相当于$a_i$变为$a_{i\wedge (2^k-1)}$，第三种操作相当于$a_i$变为$a_{i\wedge (2^k)}$。因此可以用x表示，当前$a_i$变为$a_{i\wedge x}$。对于区间求和，相当于求$\sum_{i=l}^r a_{i\wedge x}$。不难发现，对[l,r]，若l和r的二进制正好从某一位开始,l都是0，r都是1，这一位前都相等，则[l,r]异或x后仍在连续的一段区间。而任意一段区间，都可以拆成log个满足上述要求的区间。因此可以用一棵支持单点修改，区间求和的线段树来完成这道题。时间复杂度$O(qn^2)$ | ||
| - | 推荐理由： | + | 推荐理由：不是数据结构的数据结构（虽然也用到了数据结构） |
2020-2021/teams/hotpot/200822-200828.1598592559.txt.gz · 最后更改: 2020/08/28 13:29 由 喝西北风
