lzh的传送带(eszy vreosn)

题意

现有一个$\mathrm{\infty }\ast \mathrm{\infty }\infty *\infty$的方格，每个方格有两个方向,分别是向右和向下，起始是方向都是向右。起始时$(1,1)(1,1)$被标记，接下来进行t步操作，每一步对于每一个被标记的方格，将它身上的标记传给它的方向的那一个，且自身转换成另一种方向，$(1,1)(1,1)$重新被标记。最后询问$(n,m)(n,m)$是否被标记。

做法

$n,m,tn,m,t$数据范围都在$100100$之内，放心的暴力跑每一步，对于每一步，对$(n,m)(n,m)$内所有方块进行操作，可以写一个结构体的二维数组，分别存放当前位置的方向和当前位置是否被标记。时间复杂度为$O(n\ast m\ast t)O(n*m*t)$。

lzh的传送带(herd vreosn)

题意

现有一个$\mathrm{\infty }\ast \mathrm{\infty }\infty *\infty$的方格，每个方格有两个方向,分别是向右和向下，起始是方向都是向右。起始时$(1,1)(1,1)$被标记，接下来进行t步操作，每一步对于每一个被标记的方格，将它身上的标记传给它的方向的那一个，且自身转换成另一种方向。最后询问$(n,m)(n,m)$是否被标记。

做法

我们发现t的数据范围到达了$1e181e18$，我们没有办法直接枚举步数，但是$nn$和$mm$都是$10001000$以内。

考虑第$(x,y)(x,y)$的格子如果经过了$kk$次标记，那么第$(x,y+1)(x,y+1)$经过了$\lceil k\mathrm{/}2\rceil \backslash lceil\; k/2\; \backslash rceil$次标记，第$(x+1,y)(x+1,y)$经过了$\lfloor k\mathrm{/}2\rfloor \backslash lfloor\; k/2\; \backslash rfloor$次标记。

那么我们只需要知道$(1,1)(1,1)$总共经过几次，通过递推就可以知道$(n,m)(n,m)$总共经过几次。递推需要的时间复杂度为$O(n\ast m)O(n*m)$。

我们需要注意，不是第$tt$秒时$(1,1)(1,1)$经过$t+1t+1$次标记，在实际过程中可能有一部分还未能到达$(n,m)(n,m)$，因为一部分格子标记在转移过程中的步数不足$(n+m)-(1+1)(n+m)-(1+1)$（曼哈顿距离）。所以我们可以理解为在某一步之后，$(1,1)(1,1)$不再被重新标记能够正好保证正确性。这一步刚好是$t-n-m+3t-n-m+3$。

我们现在知道了第$tt$步之后$(n,m)(n,m)$经过多少次标记和如何计算，我们同样也可以算出第$t-1t-1$步之后$(n,m)(n,m)$经过多少次标记。如果第$tt$步之后$(n,m)(n,m)$经过多少次标记和第$t-1t-1$步之后$(n,m)(n,m)$经过多少次标记不相等(刚好差$11$)。那就说明$tt$步之后$(n,m)(n,m)$上刚好被标记。

我们设函数f(int t,int n,int m)的返回值为第$tt$步之后$(n,m)(n,m)$经过多少次标记，我们只需要判断f(t,n,m)-f(t-1,n,m)得到的是否为$11$，设置此函数，巧妙的避免了重复运算。总时间复杂度为$O(n\ast m)O(n*m)$。

lzh摆椅子

题意

构造一个$0101$矩阵，使得每行每列的椅子的数量的的奇偶符合要求，且椅子个数尽量最多。

做法

定位是简单思维题，为什么没人做。

考虑全是$11$的矩阵，这样每行每列的奇偶和$nn$的奇偶一致，我们需要最少次数的修改使得奇偶符合要求。

我们每修改一个点，就会改变当前位置的行和列的奇偶，如果行和列的要求刚好有相等的和$nn$的奇偶不一致的数量，那么我们只需要记录下来这些坐标，然后修改这部分的点即可。

如果行和列的要求和$nn$的奇偶不一致的数量不相等，考虑到每修改一个点就能改变当前行列的奇偶，如果行或列里修改过两次，那么行或列的奇偶相当于没变，而列或行有两个地方的奇偶被修改。

可证，行和列的要求和$nn$的奇偶不一致的数量的差刚好为偶数时，可以按要求修改，否则不能。

如果不能，直接输出NO。

如果能，对于多余的行或者列，随便找一个列或行，对其中对应的地方修改。

时间复杂度$O(n\mathrm{²})O(n²)$