2020-2021:teams:mian:weekly_report:2020_summer_week_6_report
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:mian:weekly_report:2020_summer_week_6_report [2020/08/21 13:10] grapelemonade [专题] |
2020-2021:teams:mian:weekly_report:2020_summer_week_6_report [2020/08/21 16:10] (当前版本) withinlover |
||
|---|---|---|---|
| 行 8: | 行 8: | ||
| ===== Pantw ===== | ===== Pantw ===== | ||
| + | [[https://www.topcoder.com/stat?c=problem_statement&pm=16348|TCO20 Parallel 3B: ShortBugPaths]] | ||
| + | |||
| + | * 分类：DP，计数 | ||
| + | * 题意：一个 $n\times n$ 的方格，跳 $j$ 次，每次可以跳 $d_1$ 步或 $d_2$，... 或 $d_m$ 步，问可能的路径条数。$n\leqslant 10^9, 0\leqslant j \leqslant 10, 0\leqslant d_i\leqslant 10$ | ||
| + | * 解法：边界只对位于边界 100 格内的格子起作用（因为 100 格以外的不会撞上墙），那么对于较大的 $n$ 我们可以直接按照 $n=300$ 来做，然后直接复制填充计数即可。 | ||
| + | * 评论：状态精简，小心 fst | ||
| + | |||
| + | [[https://www.topcoder.com/stat?c=problem_statement&pm=16345|TCO20 Parallel 3B: HorseTicket]] | ||
| + | |||
| + | * 分类：计数，DP | ||
| + | * 题意：给 n 个串，所有字符互不相同，每个串至多选一个字符，按任意顺序组成新串，问所有可能结果串中字典序第 i 个串的内容。 | ||
| + | * 解法：枚举确定每一位，对给定前缀按照后半部分长度计数统计可能串数。 | ||
| + | * 评论：python 写起来比较舒适 | ||
| + | |||
| + | <hidden><code python> | ||
| + | import math | ||
| + | |||
| + | |||
| + | class HorseTicket: | ||
| + | |||
| + | def prefixSum(self, races, curpre): | ||
| + | ret = 0 | ||
| + | race = [] | ||
| + | invalid = False | ||
| + | for i in curpre: | ||
| + | for j in curpre: | ||
| + | if i != j: | ||
| + | for k in races: | ||
| + | if i in k and j in k: | ||
| + | invalid = True | ||
| + | if invalid: | ||
| + | return 0 | ||
| + | for u in races: | ||
| + | valid = True | ||
| + | for i in u: | ||
| + | if i in curpre: | ||
| + | valid = False | ||
| + | if valid: | ||
| + | race.append(u) | ||
| + | races = race | ||
| + | nn = len(races) | ||
| + | c = [0 for i in range(nn + 1)] | ||
| + | c[0] = 1 | ||
| + | for i in range(nn): | ||
| + | for j in range(nn, 0, -1): | ||
| + | c[j] += c[j - 1] * len(race[i]) | ||
| + | for i in range(nn + 1): | ||
| + | ret += math.factorial(i) * c[i] | ||
| + | return ret | ||
| + | |||
| + | def getTicket(self, races, index): | ||
| + | total = self.prefixSum(races, '') | ||
| + | if index >= total: | ||
| + | return '!' | ||
| + | |||
| + | chars = [] | ||
| + | for u in races: | ||
| + | chars.extend([i for i in u]) | ||
| + | chars = sorted(list(set(chars))) | ||
| + | |||
| + | ans = '' | ||
| + | while index > 0: | ||
| + | index -= 1 | ||
| + | for i in chars: | ||
| + | if i in ans: | ||
| + | continue | ||
| + | prefix = ans + i | ||
| + | tot = self.prefixSum(races, prefix) | ||
| + | if tot > index: | ||
| + | ans = prefix | ||
| + | break | ||
| + | else: | ||
| + | index -= tot | ||
| + | return ans | ||
| + | |||
| + | </code></hidden> | ||
| ===== Withinlover ===== | ===== Withinlover ===== | ||
| + | |||
| + | [[http://acm.hdu.edu.cn/showproblem.php?pid=6598|HDU6598]] | ||
| + | |||
| + | * 分类：网络流 | ||
| + | * 题意：给定n个点m组关系(u, v, a, b, c)，对点黑白染色，若u, v均为黑色答案加a，均为白色答案加c，一黑一白答案加b。求最大值。 | ||
| + | * 解法：玄学建图，把一条边拆成6条做。转换成最小割问题 | ||
| + | * 评论：建图思路很妙，知道了怎么建图就是板子题了。 | ||
| ===== Gary ===== | ===== Gary ===== | ||
| + | [[http://acm.hdu.edu.cn/showproblem.php?pid=6599|HDU6599]] | ||
| + | |||
| + | * 分类：PAM,manacher/hash | ||
| + | * 题意：给定字符串，一个字符串满足条件当且仅当本身是回文串且前一半也是回文串，求每个长度满足条件的串个数 | ||
| + | * 解法：直接manacher求出每个点最长的回文串，建立pam时对pam上每个点存下他的长度lenth以及在原串中的位置pos，pam上每个新点，通过lenth和pos和manacher求出的回文串长度来判断该点的回文串是否满足条件，最后遍历parent树，统计所有满足条件的节点 | ||
| + | * 评论：不熟PAM，开始还以为不能这么做 | ||
| ====== 个人训练 ====== | ====== 个人训练 ====== | ||
| 行 21: | 行 110: | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| + | ABC175，TCO20R3B | ||
| ==== 题目 ==== | ==== 题目 ==== | ||
| + | AGC047E, ABC175D, ABC175E, TCO20R3B[300 / 500 / 1000] | ||
| ===== Withinlover ===== | ===== Withinlover ===== | ||
| ==== 专题 ==== | ==== 专题 ==== | ||
| + | 无 | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| + | ABC175，TCO20R3B | ||
| ==== 题目 ==== | ==== 题目 ==== | ||
| + | |||
| + | CF1379D CF1379E CF1380D CF1380E | ||
| + | |||
| + | ABC175 A-E | ||
| ===== Gary ===== | ===== Gary ===== | ||
| 行 35: | 行 132: | ||
| ==== 专题 ==== | ==== 专题 ==== | ||
| + | 无 | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| + | |||
| + | |||
| + | ABC175，TCO20R3B | ||
| ==== 题目 ==== | ==== 题目 ==== | ||
| + | |||
| + | Educational Codeforces Round 93 C,D,E,F,G | ||
| + | |||
| + | ABC175 A,B,C,D,E | ||
| + | |||
2020-2021/teams/mian/weekly_report/2020_summer_week_6_report.1597986603.txt.gz · 最后更改: 2020/08/21 13:10 由 grapelemonade
