1003

LYF 签到

1002

题意:

n乘m小于1e5,矩阵,每个位置一个值,从1,1开始。先手希望停止位置的值大,后手希望小。走k步,或在中途轮到走的人选择直接停在该处。在每一步,先手只能在同行走,后手只能在同列走。

LYF解:

考虑k=1的情况,先手可以选择第一行中最大的位置结束游戏。考虑k=2的情况,先手要么选择在起始位置停下,要么选择去最小值最大的列,因为第二步掌握在后手手上,他可以随便选当前列的最小值。考虑k更大的情况,可以发现无非是k=2情况经过先后手交换的情形(后手选择在直接停下必然比继续走相同或更劣,因此不必考虑)。因此知道最后一步是谁走之后判断就十分简单,加上一个起始位置停下的特殊情况即可。

1008

题意:

2e5个数,保证互不重复,范围4e12,问其中最大的好集合有多少数。好集合的定义是所有数模一个相同的大于1的数相等。

WD解:

模一个相同的数相等的含义即为互相的差的gcd非1。那么,对于最小的质数2,显然总集合中的全体奇数和全体偶数可以分别组成一个集合。因此答案必然大于等于n/2。若答案大于n/2,则任取两个数,有四分之一的概率他们即为答案。如何check它们是否答案?check他们的差的所有质因数。显然4e12的范围导致了所有数最多只能有11个质因数。pollard-rho可做。(预处理2e6以内质数也可)随机取几十组做相同操作即可ac

1007

题意:

有一个空的deque,有几种操作。x表示当前是第几次插入

  1. 在右端插入x

  2. 在左端插入x

  3. 询问deque的中间位置( 上取整)是几

  4. 删除deque中的y

保证操作3、4合法。

ZRC解:

用链表维护,保存所有数字对应的链表中的位置,靠奇偶性判断mid应该向左还是向右移动(还需要保存每个数属于左边还是右边来判断删除时mid的移动方向)。但是可能当时状态不太好,写std::list时候先是各种sb问题导致tle,后来又少考虑了一种删除的情况…导致mle。事实上256m内存即使是stl也是够用的。赛场上后来补了一个数组版,还是分类讨论出了很多问题,交了好几发。

题解:

将mid左边和右边分别建立一个deque。显然容易维护,删除时打bool标记即可。

1010

LYF 基本无思维难度,分类讨论细节题

1006

WD 线段树维护好几个值