day1 T1

下标 0 - n-1

• 移动到下一个小人： 逆时针 下标+1
• 移动到上一个小人： 顺时针 下标-1

朝向：0 向内 1 向外 指令：0 向左 1 向右

cur 朝向 指令 实际移动方向 下标变化 0 0 顺 cur = (cur-s+n)%n 0 1 逆 cur = (cur+s)%n 1 0 逆 cur = (cur+s)%n 1 1 顺 cur = (cur-s+n)%n

异或： 朝向 ^ 指令方向 = 0 --》顺时针，下标减少s 朝向 ^ 指令方向 = 1 --》逆时针，下标增加s

day2 T1

定义s[i][j]表示 0<=x<=i 0<=y<=min(x,j)的区域内， 满足 k | C(x, y) 的点对(x,y)的数量。

flag[i][j] = 1 (若c[i][j] == 0 则flag[i][j]为0)

s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + flag[i][j]

m = min(n, m)

s[n][m]

day2 T2

假设先切的蚯蚓原来长度为x1,后切的为x2 x1 >= x2

设x1是在t1被切断,切出短的 px1 设x2是在t2被切断,切出短的 p[x2 + (t2-t1)q]

到达t2时,x1较短的那一段变成了: px1 + (t2-t1-1)q

floor(p[x2 + (t2-t1)q]) <= px2 + p(t2-t1)q px1 >= px2, 且 p < 1

先切出来的蚯蚓碎片,增长后一定会大于等于后切出来的对应碎片

基于上述单调性,可以维护三个单调递减队列 q1: 存储原来n个蚯蚓的长度 q2: 存储切出的较短那一段 floor(px) q3: 存储切出的较长那一段 floor(x - px)

delta += q 真实长度 = max(q1.top(),q2.top(),q3.top()) + delta

新切出的蚯蚓没有享受到当前秒的增长q, 放入q2和q3时应该 = 新长度 - (delta + q)