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 线段树维护好几个值