2020牛客暑期多校第三场

2020牛客暑期多校第四场

7.23训练

Min_25筛(式子有点多,正在研究)

这周训练比较密集,比赛摸了

CF的几道题:

Prefix Flip

Create The Teams

Omkar and Baseball

图论

无

LeetCode 212.

见下方本周推荐

无

无

Empty Vesselshttps://codeforces.com/group/azDPdoF24f/contest/288496/problem/F

见下方本周推荐

Prefix Flip

题意:给一个01串,每次可以选择一个前缀,先进行01反转,再整体翻转一次.问怎样操作可以在$2n$次操作内,将一个串变成目标串.

tag:线段树

题解:从后往前处理,用两个变量维护当前前缀实际上对应的是哪一段区间,线段树区间+1表示01反转操作.之后单点查询,根据奇偶性判断翻转哪个前缀就行了.

comment:乍一看像是bitset乱搞题,后来想想区间翻转没法实现,遂放弃.还是线段树大法好.

LeetCode 212.

题意：给一个单词集合和一个字符矩阵。一个单词是字符矩阵可导出的当且仅当从字符矩阵某个位置开始上下左右连续地走可以组成这个单词。求所有字符矩阵可导出的单词和所给单词集合的交集。

tag：基础搜索，trie，stl

题解：直接dfs字符矩阵，复杂度太高。实际上在dfs的时候有些前缀是没必要看的，因此对给定的单词集合建trie，按照trie上存在的结构在字符矩阵里面搜就行。复杂度低了很多但还会T，进一步剪枝，对于某个trie叶节点，如果曾经走到那么下次可以直接略过，剪掉这个枝也可以加速。判交集（判存在）的时候也可以用哈希/unordered stl/pb_hash_table来加速。

Empty Vesselshttps://codeforces.com/group/azDPdoF24f/contest/288496/problem/F

tag:BFS（扩欧?(雾）

题意

给最多十个水桶，反复倒量出A升水，桶容量⇐2e4，倒的次数不超过1e6。

题解

BFS搜解，然后输出。

comment

两个水桶的时候能量出来的水显然是gcd(a,b)的整数倍，所以一开始想歪了，以为这个1e6的操作限制的是扩欧的解范围。再加上一共十个数就感觉连续扩欧的话分分钟就超过1e6了。

后来才发现这个题考的好像是如何把用桶们的系数表示A转化为桶的操作。。。我是nt。。。