2020-2021:teams:hotpot:200808-200814
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:hotpot:200808-200814 [2020/08/14 12:25] misakatao 更新 |
2020-2021:teams:hotpot:200808-200814 [2020/08/14 15:01] (当前版本) misakatao 更新 |
||
|---|---|---|---|
| 行 14: | 行 14: | ||
| =====比赛===== | =====比赛===== | ||
| + | |||
| + | 2020.8.9 [[agc047|Atcoder Beginner Contest 047]] ''prob:2/3/6'' ''rank：415'' | ||
| =====题目===== | =====题目===== | ||
| 行 26: | 行 28: | ||
| =====比赛===== | =====比赛===== | ||
| + | |||
| + | 本周无 | ||
| =====题目===== | =====题目===== | ||
| - | 本周无 | + | *Codeforces Round 662 C - Pinkie Pie Eats Patty-cakes |
| + | *分类：二分答案 | ||
| + | *题目大意：有$n$个数，每个数在$[1,n]$之间，可以任意改变排列，问两个相同的数之间的距离最小值最大是多少 | ||
| + | *数据范围：多组数据，$T \le 100$，$2 \le n \le 10^5$，$\sum n 10^5$ | ||
| + | *解题思路：看到题目描述的要求就可以直接想二分答案，考虑二分答案以后如何验证，我们可以直接把同一个元素隔一个放看是否能够组成即可，注意一定是先放数量较多的元素 | ||
| + | *Comment：比较明显的二分答案题，写起来有些复杂 | ||
| + | *Codeforces Round 662 D - Rarity and New Dress | ||
| + | *分类：DP | ||
| + | *题目大意：给出一个$n \times m$的字符矩阵，问有多少种方法可以切下来一个斜着的正方形，其中都是同一个字母 | ||
| + | *数据范围：$1 \le n,m \le 2000$ | ||
| + | *解题思路：令$dp_{i,j}$表示位置$(i,j)$向上组成的最大的斜正方形，转移方程为$dp_{i,j}=min\{dp_{i-1,j-1},dp_{i-1,j+1},dp_{i-2,j}+1\}$ | ||
| + | *Comment：常规的DP题，写出方程需要一定的观察能力 | ||
| + | *Codeforces Round 663 C - Cyclic Permutations | ||
| + | *分类：思维，排列组合 | ||
| + | *题目大意：对于一个排列的一个位置$i$，若存在$1 \le j < i$且$p_j > p_i$或$i < j \le n$且$p_j > p_i$，就从$i$向$j$连无向边，问有多少种排列至少会有一个环 | ||
| + | *数据范围：$3 \le n \le 10^6$ | ||
| + | *解题思路：直接算不好考虑，我们想哪种排列不合法。我们发现只要一个数的左右两边都有数大于它那么就一定成环，所以只有单峰的排列不成环。由于是单峰，所以峰一定是$n$，剩下的每个数可以随意放在左边或者右边且顺序固定，所以一共有$2^{n-1}$种排列不合法，计算即可 | ||
| + | *Comment：稍有难度的思维题，需要转换思路 | ||
| ======郭衍培====== | ======郭衍培====== | ||
| 行 38: | 行 59: | ||
| =====比赛===== | =====比赛===== | ||
| + | |||
| + | 2020.8.9 [[agc047|Atcoder Beginner Contest 047]] ''prob:2/3/6'' ''rank：466'' | ||
| =====题目===== | =====题目===== | ||
| 行 45: | 行 68: | ||
| ======本周推荐====== | ======本周推荐====== | ||
| - | 林星涵： | + | 林星涵：Atcoder Grand Contest 047 - B |
| - | 题目大意： | + | 题目大意：给出 $n$ 个字符串 $S_i$，给出一种操作方式，即每次第一个和第二个选一个删除，问有多少串能够转换成另外一个串，统计对数。 |
| 数据范围： | 数据范围： | ||
| - | 解题思路： | + | $ 2 \le n \le 2e5$ |
| - | 推荐理由： | + | $ S_i \ne S_j$ |
| + | |||
| + | $ |S_1+S_2...+S_n| \le 1e6$ | ||
| + | |||
| + | ps: 串全由小写字母组成 | ||
| + | |||
| + | 解题思路：经过分析之后，我们可以发现一些性质，即长串一定由短串组成，且从短串的第二位开始必然是连续的一段，利用这个性质，我们对串从短到长排序之后，每次对字母做一个桶，在trie树上寻找是否有统计过的点并累加答案，之后倒序插入一个trie树中（只插入到第二位，每次对第一位的个数进行统计）。 | ||
| + | |||
| + | 推荐理由：利用操作的性质，借助trie树较为巧妙的解决了问题。 | ||
| 陶吟翔： | 陶吟翔： | ||
| - | 题目大意： | + | 题目大意：给出一棵$n$个点的树，边有边权，每次可以把一条路径上的边权减一，问最少多少次可以把所有边权减成零，另外有$q$个询问，每次修改一条边的边权，对每个询问也要回答 |
| - | 数据范围： | + | 数据范围：$1 \le n,q \le 10^5$，$1 \le w_i \le 10^9$ |
| - | 解题思路： | + | 解题思路：对于每一个点单独考虑连向子树的边，我们假设$a$是连向子树的边中最大的，$t$是这个点连向父亲的边，显然我们可以把$t$个删除和连向父亲的边一起做，剩下的就必须在子树内解决，所以我们根据经典的电池问题，检查$2 \times a$和$t + sum$的大小然后计算这一个点对答案的贡献。对于修改，显然只会影响两个点的答案，我们再单独处理这两个点即可 |
| - | 推荐理由： | + | 推荐理由：从题目本身到答案本质的计算需要一定的模型转化能力，并且处理答案时的细节处理也比较复杂，全面地考察了做题者的能力 |
| 郭衍培： | 郭衍培： | ||
2020-2021/teams/hotpot/200808-200814.1597379134.txt.gz · 最后更改: 2020/08/14 12:25 由 misakatao
