Warning: session_start(): open(/tmp/sess_113f22fec2e381c7cb4fa51236c7a06a, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Writing /data/wiki/data/cache/d/de2edb2fcb553ea79b79c722a4e13dbc.captchaip failed
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
====== 2020 Summer Week 6 Report ======
====== 团队训练 ======
[[2020-2021:teams:mian:hdu_training:2019_multi-university_training_contest_2|2019 Multi-University Training Contest 2]] ''%%task:8/8/12%%''
====== 本周推荐 ======
===== 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 写起来比较舒适
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
===== 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 =====
[[http://acm.hdu.edu.cn/showproblem.php?pid=6599|HDU6599]]
* 分类:PAM,manacher/hash
* 题意:给定字符串,一个字符串满足条件当且仅当本身是回文串且前一半也是回文串,求每个长度满足条件的串个数
* 解法:直接manacher求出每个点最长的回文串,建立pam时对pam上每个点存下他的长度lenth以及在原串中的位置pos,pam上每个新点,通过lenth和pos和manacher求出的回文串长度来判断该点的回文串是否满足条件,最后遍历parent树,统计所有满足条件的节点
* 评论:不熟PAM,开始还以为不能这么做
====== 个人训练 ======
===== Pantw =====
==== 专题 ====
无
==== 比赛 ====
ABC175,TCO20R3B
==== 题目 ====
AGC047E, ABC175D, ABC175E, TCO20R3B[300 / 500 / 1000]
===== Withinlover =====
==== 专题 ====
无
==== 比赛 ====
ABC175,TCO20R3B
==== 题目 ====
CF1379D CF1379E CF1380D CF1380E
ABC175 A-E
===== Gary =====
==== 专题 ====
无
==== 比赛 ====
ABC175,TCO20R3B
==== 题目 ====
Educational Codeforces Round 93 C,D,E,F,G
ABC175 A,B,C,D,E