2020-team2-031

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

[/wiki/2020-team2 返回]

[[Image(Rank.png,1000px)]]

[[Image(Submissions.png,1000px)]]

= 概述 =

 solved: 9/12

 rank: 4（现场）

= 流水账 =

开场签到'''A1Y16''','''H1Y47''',D被卡了一发后换做法由于没编译wa1，'''D4Y56''',L被卡了一发常数'''L2Y89'''。

G是线段树维护一堆信息，pb上机'''G2Y143''',pb对yyc说了C的结论，yyc对cxt说了J的sg函数，问了cxt线性基有关的部分，yyc嘴了C的做法，cxt上机'''C1Y155'''，yyc上机写J，WA了后下机。

pb开出B，'''B2Y209''',pb和cxt开K，开出后yyc和cxt调了会J，'''J3Y245'''，pb上机，yyc和cxt负责端茶倒水，'''K3Y297'''。

= 总结 =

=== pb： ===
决杀好爽，但是感觉K还是写的有点慢，队友说的做法实现起来整体性确实更好一点，然后就是一些算法的复杂度要多了解一下，比如10次1e18的Pollard-Rho是3s跑不出来的。

今天没有什么特别注意的吧，感觉罚时再少一点，排名是可以再靠前一点的，有些题出的有些慢。

upd 草板子抄错了

=== Creatix： ===
总觉得这场还挺顺的。可能是因为最后有绝杀吧。

而且配合也比较好，没有怎么卡。

upd：我的Pollard-Rho板子是清白的，她只跑了300ms
=== yyc： ===

J调不出来的时候和队友交流了一下，感觉很有效果。另外感觉我手里有一道题之后就不知道干什么了？下次应该减少发呆时间。

= 题解 =

 * A：大概时签到吧

 * B：如果两点之间的矩形中有障碍，那么一定存在一种方案是先走到一个障碍的旁边然后走到终点，从每个障碍四联通的格子BFS

 * C：min{dis(x1,u)+dis(x2,v)+dis(x3,v)}=1/2(dis(x1,x2)+dis(x2,x3)+dis(x3,x1))，枚举边统计

 * D：问题等价于分解质因数之后有没有指数大于1的，对于<=n^1/3的质数p去筛，同时统计有没有p^2，之后剩下的只会是p^2或者p1p2或者p或者1，判断一下即可。

 * E：

 * F：

 * G：hash方法用Σsi*base^i^，注意到65536次操作才会取模一次，总次数不超过nq/65536，直接线段树维护最大值和哈希即可

 * H：差分

 * I：

 * J：推出SG函数然后枚举黑集合中最小的数即可。

 * K：首先对于一个插入序列可以nlogn构建BST，方法是将每个数插入到后继的左儿子一直往右走的最下面一个位置的右儿子，那么用并查集维护右儿子，然后将[1,l-1],[l,r],[r+1,n]分成三类A,B,C，排序之后两个A之间的B带着旁边的C可以做区间dp，转移就是枚举根

 * L：暴力dp，大力卡常，跑了时限的99.7%可还行……

 * M：

[/wiki/2020-team2 返回]

概述

solved: 9/12

rank: 4（现场）

流水账

开场签到A1Y16,H1Y47,D被卡了一发后换做法由于没编译wa1，D4Y56,L被卡了一发常数L2Y89。

G是线段树维护一堆信息，pb上机G2Y143,pb对yyc说了C的结论，yyc对cxt说了J的sg函数，问了cxt线性基有关的部分，yyc嘴了C的做法，cxt上机C1Y155，yyc上机写J，WA了后下机。

pb开出B，B2Y209,pb和cxt开K，开出后yyc和cxt调了会J，J3Y245，pb上机，yyc和cxt负责端茶倒水，K3Y297。

总结

pb：

决杀好爽，但是感觉K还是写的有点慢，队友说的做法实现起来整体性确实更好一点，然后就是一些算法的复杂度要多了解一下，比如10次1e18的Pollard-Rho是3s跑不出来的。

今天没有什么特别注意的吧，感觉罚时再少一点，排名是可以再靠前一点的，有些题出的有些慢。

upd 草板子抄错了

Creatix：

总觉得这场还挺顺的。可能是因为最后有绝杀吧。

而且配合也比较好，没有怎么卡。

upd：我的Pollard-Rho板子是清白的，她只跑了300ms

yyc：

J调不出来的时候和队友交流了一下，感觉很有效果。另外感觉我手里有一道题之后就不知道干什么了？下次应该减少发呆时间。

题解

  • A：大概时签到吧
  • B：如果两点之间的矩形中有障碍，那么一定存在一种方案是先走到一个障碍的旁边然后走到终点，从每个障碍四联通的格子BFS
  • C：min{dis(x1,u)+dis(x2,v)+dis(x3,v)}=1/2(dis(x1,x2)+dis(x2,x3)+dis(x3,x1))，枚举边统计
  • D：问题等价于分解质因数之后有没有指数大于1的，对于<=n1/3的质数p去筛，同时统计有没有p2，之后剩下的只会是p^2或者p1p2或者p或者1，判断一下即可。
  • E：
  • F：
  • G：hash方法用Σsi*basei，注意到65536次操作才会取模一次，总次数不超过nq/65536，直接线段树维护最大值和哈希即可
  • H：差分
  • I：
  • J：推出SG函数然后枚举黑集合中最小的数即可。
  • K：首先对于一个插入序列可以nlogn构建BST，方法是将每个数插入到后继的左儿子一直往右走的最下面一个位置的右儿子，那么用并查集维护右儿子，然后将[1,l-1],[l,r],[r+1,n]分成三类A,B,C，排序之后两个A之间的B带着旁边的C可以做区间dp，转移就是枚举根
  • L：暴力dp，大力卡常，跑了时限的99.7%可还行……
  • M：
附加文件