====== 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 写起来比较舒适

<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 =====

[[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