By MonkeyKing from Hexo

所谓algorithms unweekly， 就是开心的时候就写点的有关的algorithms的blog, 如果你喜欢weekly的algorithms, 请移步这里Algorithms weekly by Petr。

那么你现在看到的就是第一篇algorithms unweekly，这篇文章讲的是笔者2020年第四季度喜欢的两道题目。 由于原稿是用excel表格整理的，没有高端大气上档次的各种markdown特效，而我也懒得去加，所以比较丑，希望以后的algorithms unweekly不会这么草率。
言归正传，下面掌声有请两位嘉宾闪亮登场！

题目名称 Pocky Game

题意：有N(n<=100)堆石头，每堆有ai(<=1e9)个石头，先手从最左边拿石头，每次拿走最左边一堆中任意个数的石头，后手从最右边堆中拿走任意个数的石头，拿最右边一堆或者是最右边1个。没有办法拿石头的人输。

首先这个题目名字就出的很有意思，和题意有着一脉相连的感觉。是少数能让人做过很久还记得名字的题。 那么正常人一开始看到这题都会想着从n比较小的时候开始递推，但是推到3左右却发现什么结论也得不到，好像只能通过一些复杂的不等关系来判断先后手孰胜孰负。

things you can choose when playing pocky game

这个时候我们可以借助一种游戏（正如题目名字那样！）的思想来考虑这个问题，那到我的回合的时候，我究竟该拿走多少石头，要是我这边石头很多，我可以不停的一个一个拿，把对手耗死，但要是前面有一堆很好的石头，我可能就需要快速渡过前面的几堆石头，然后占据（这里用“占据”这个词是因为，如果场面上只剩下了这一堆石头，那肯定是先到的人赢）那一堆石头，再把对手耗死。

那么我们把这个博弈的游戏真正当成一个游戏来玩，就会发现一些奇妙的策略：每次要么取走一堆，要么取走一个。 而当前决定胜负的就是现在是哪一片区间，然后左边右边分别有多少石头。

这样子我们就有了做出这个题目的基础，但是石头太多，直接dp显然不是一个好办法，结合之前说的游戏思想，发现既然我们是“占据”了这堆石头，那显然这堆石头是韩信点兵，多多益善。这里就存在了单调性，就以左边的人为例，肯定是最左边那堆石头越多越好。那剩下的区间dp就呼之欲出了，那我们要不要记录最右边的石头个数呢？（”不需要！“）这凭借的大概就是对于dp这种方法的熟练度了吧。也就是我们记dp1[l][r]表示l+1,r都是满的石头堆，那么第l堆石头至少要有多少个我们的左边这位玩家才能获胜。剩下的就是一些正常的数学分析（分来讨论）了，这里就不展开叙述。那这个题目有意思的地方就在于，如果你就只用看待题目的眼光来看待他，恐怕没办法想明白他的单调性，我们得设身处地的把自己当做其中的一名玩家，才可以意识到这一步的move究竟意义何在，每一步的move究竟意义何在，才能意识到问题的部分的单调性，从而设计出合理的状态。

题目名称 Latin Square

题目的要求是给了一个二维的矩阵，每一行和每一列都是一个排列，有如下的操作：

①：让某一行/某一列上的排列变换成它的逆排列

②：把某一行/某一列上的数往左/右置换一格

这道题目看上去和排列有关系，似乎应该有什么高级数据结构或者排列的性质来维护这些操作，但是谁能想到我们可以把排列当成一个离散函数！

我也做过一些有关排列的题目，大多数运用了排列的性质，或者是环的性质，但是却没有这样的题目，排列和逆排列这种关系与函数和反函数的关系竟然是一样的，题目作者挖掘到了排列和函数之间的潜在关系，而不是传统的排列和环的关系，让人耳目一新。并且也不是想到这一点，把排列当成函数就解决了所有问题的。

想到这一点后，上面的操作变成了让所有点平移一个，或者是沿着x=z或y=z翻折。那么直接运用数据结构来维护仍然是一个很困难的事情，这个时候又出现了一个巧妙的做法，利用线性代数的知识来直接对坐标进行变换！平移可以想成坐标的对坐标进行置换，而沿着x=z或y=z反着可以想象成是对(x,z) (y,z)进行置换。

这样一个排列的题目先转换成了一个和排列无关的题目，继而又转换成了一个排列的题目，做完这道题目确实令人若有所思，一些毫无关联的事物实际上存在着巧妙的联系。