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 15:14] grapelemonade [Pantw] |
2020-2021:teams:mian:weekly_report:2020_summer_week_6_report [2020/08/21 16:10] (当前版本) withinlover |
||
|---|---|---|---|
| 行 14: | 行 14: | ||
| * 解法：边界只对位于边界 100 格内的格子起作用（因为 100 格以外的不会撞上墙），那么对于较大的 $n$ 我们可以直接按照 $n=300$ 来做，然后直接复制填充计数即可。 | * 解法：边界只对位于边界 100 格内的格子起作用（因为 100 格以外的不会撞上墙），那么对于较大的 $n$ 我们可以直接按照 $n=300$ 来做，然后直接复制填充计数即可。 | ||
| * 评论：状态精简，小心 fst | * 评论：状态精简，小心 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 ===== | ||
| 行 41: | 行 118: | ||
| ==== 专题 ==== | ==== 专题 ==== | ||
| + | 无 | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| + | ABC175，TCO20R3B | ||
| ==== 题目 ==== | ==== 题目 ==== | ||
| + | |||
| + | CF1379D CF1379E CF1380D CF1380E | ||
| + | |||
| + | ABC175 A-E | ||
| ===== Gary ===== | ===== Gary ===== | ||
2020-2021/teams/mian/weekly_report/2020_summer_week_6_report.1597994062.txt.gz · 最后更改: 2020/08/21 15:14 由 grapelemonade
