2020牛客暑期多校第三场

2020牛客暑期多校第四场

7.23训练

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

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

Prefix Flip

Create The Teams

无

无

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

见下方本周推荐

Prefix Flip

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

tag:线段树

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

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

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

tag:BFS（扩欧?(雾）

题意

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

题解

BFS搜解，然后输出。

comment

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

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