第四场膜你赛总结

前言

这场比之前的能做多了QwQ

题目+题解

T1 原题：NKOI 3539 移棋子游戏[6月月赛题A]

【题意】

明明和亮亮在玩一个游戏。桌面上一行有n个格子，一些格子中放着棋子。明明和亮亮轮流选择如下方式中的一种移动棋子（图示中o表示棋子，*表示空着的格子）:
1）当一枚棋子的右边是空格子的话，可以将这枚棋子像右移动一格。
**o*** -> ***o**
2）当一枚棋子的右边连续两个都有棋子，并且这个棋子往右边数第3格没有棋子，那么可以将这个棋子可以跳过去那两个棋子
**ooo* -> ***oo*
当任何一枚棋子到达最右边的格子时，这枚棋子自动消失。当一方不能移动时，这方输。假设明明和亮亮都采取最优策略，明明先走，谁将取胜？

50%的点n是小于20的，但是我可能先做了第二题，记错了范围啊，以为是100，暴力也没打。就YY了一种方法，其实跟正解有点类似：我的想法就是按棋堆(就是一段连续的棋子)来看，不是看每个棋子。算到每个棋堆到最右边的步数和，再判奇偶。

正解就直接贴了..

考虑每个棋子到最右边格子的距离。把所有棋子这样的距离的总和计为s。我们发现不管选择两种操作中的一种操作，每走一步，s的奇偶性都会发生一次变化。所以说，如果第一次轮到明明时，s是奇数，那么每次轮到明明时s都是奇数。而当s是奇数时，s肯定>0，这时明明总可以走最右边的棋子。也就是说当s为奇数时，总有棋子可以走。所以说，一开始若s为奇数，则明明必胜。同理，若一开始s为偶数，则当亮亮走的时候s总是奇数，所以明明必败。

T2

【题意】

有一块n *n 的土地上，明明和亮亮站在(1,1)处。每块地上写有一个数字a(i, j)。现在他们决定玩一个游戏，每一秒钟，他们俩走向相邻且坐标变大的格子（从(x,y)到(x+1,y)或者从(x,y)到(x,y+1)），他们俩可以按照不同方式来走，最后经过2n-1步到达(n,n)处。明明和亮亮每一秒钟计算他们站的两个位置上数字的差的绝对值，他们希望这些差值的和最大，请问这个最大的和是多少？

这个刚看完题目和范围，写了写就马上决定先跳过第一题打第二题先了。经典的DP。设f[k][i][j]表示已经走了k步，明明走到的横坐标为i,亮亮走到的横坐标为j.当然还有其他的状态表示我就不说了。这样我们就可以通过这个表示出两人走了k步后分别所在的坐标：(i,k+1-i);(j,k+1-j) -> 设为(x1,y1);(x2,y2)。

那么状态转移的方程就是f[k][i][j]=max(f[k-1][i-1][j-1],f[k-1][i][j-1],f[k-1][i-1][j],f[k-1][i][j])+abs(a[x1][y1]-a[x2][y2]).

时间复杂度是O(n^3).

T3

【题意】

有一块N*M的草地组成。显然有的地方草长的好，有的地方长的不好，于是每一块草都有一个舒服度 F。
现在明明和亮亮要选定一个a*b的草场作为晚会的地点，小朋友们就坐在上面，显然他希望小朋友们坐的最舒服！
不过别急，篝火晚会怎么能少了篝火呢，篝火需要占用c*d的草地，当然，篝火必须严格放置在选定的草地的内部，也就是说，篝火的边界不能和选定操场的边界有公共部分。
给定 N*M 大草地每一块的舒服度，寻找一个 a*b 的草地，除去一个严格内部的 c*d 的子草地，使得总的舒服度最大。

这道题比赛花的时间最多了。前后打了大概四五个版本(因为怕错，所以我的代码是一步一步越改越快的..)，互相对拍= =也是醉。

在打暴力的时候我们会发现，如果能预处理出当我选择某处的草地时严格内部最小的子草地的值的话，我的时间复杂度就能从O(n^4)降到O(n^2)--一个能接受的时间复杂度。

而由子草地的大小是固定的，就很容易想到滑动的窗口啊，学单调队列的第一道题！然后直接用啊就好了..

一开始像GDXB那样想过二维树状数组，也像hyc那样想过用RMQ来维护，但是我都没有打(因为想到用单调队列了，感觉这个好打很多啊。

T4 原题-hdu4812

【题意】

嗯点分治啊，我不会啊。。所以要学啊。。

设d[x]为x到重心root的路径上点权的乘积，那么满足条件的点对(x,y)就满足d[x]*d[y]/d[root]≡k(mod 10^6+3)。也就是d[x]≡k*d[root]*d[y]^(-1) (mod 10^6+3)。因为模数比较小，就可以直接开个数组存这些k*d[root]*d[y]^(-1)值，于是找其他子树的时候只需要看看那个数组里有没有和v[x]一样的值就好了。

然后去做点分治的题了