8/8-8/9模拟赛解题报告

phoeagon

8月8日和8月9日分别举行了共三场模拟赛。

以下解题报告纯属个人原创，与出题人无关，如有雷同，你抄我的。

8/8下午： Vijos “笨笨工作室” 普及组模拟赛

L阵游戏：

很简单，找规律。刚好几天前在老郭的书上看过。可以证明 a*b%8=0是填满的充要条件。

就好像：

if (a=1)or(b=1)then exit(false)

else if (a*b mod 8=0)then exit(true)

else exit(false);

充分性：首先，容易枚举出，2*4, 3*4的矩形都可以填满。若a*b%8=0，则

（不妨设a<=b）

1.a%2=0 && b%4=0

则可以用2*4的矩形填满。

2.b%4=8 && a>2

则根据组合法则，易得大于1的整数都可以分解成若干个2、3的和。所以矩形可以被2*4, 3*4的覆盖。

所以满足a*b%8=0的矩形可以被L形覆盖。

必要性：

易证a*b%8=0则a、b中必然有一个是偶数，设b%2=0。a可能是奇数或偶数。

则把矩形划分成b行，每行a个小方格。

相邻的行染上不同的颜色。（Red/White）

易得任意L形只可能：

3R1W或1R3W

且sum R = sum W

所以(4R4W)x=ab

所以，左边的x乘上了因数8.

所以只有满足模八得0，才能~~~

其实这道题有缺陷的，就说，这样算起来不能赢的人，可以故意使得棋盘不能被填满，则没有人能赢。（在大多数足够大的棋盘上，做法是显然的）

炸弹安置

一看就是搜索。

但是基本来说有两种裸搜，一种是以爆炸点为基础搜，第二是根据空白点归属搜索。

分别发展出边界比较和格点染色比较。

实验证明，第二种方法快得多~

车厢连接

明显的动态规划。

用的是一种我总是很难想到的思想。

即，计算n个数组成m个排列/选择/组合时，考虑n-1个数组成m个排列/选择/组合，以及n-1个数组成m-1个排列/选择/组合并考虑把最后一个新近加入的元素N“融入”到前面n-1个中。

f[i,j]=f[i-1,j]*(j+1)+f[i-1,j-1](i-j)

不过我搞不懂为什么作者说这道题难以琢磨。

不用高精度，取模。

手镯序号

最小表示法。

首先，很囧的，题目不说清楚是可以选定顺时针、逆时针之一来阅读。你看一下题就知道OX啦~

选定了方向后，就是经典的最小表示法。

不会，但usaco做过，5.*的hidden password.

拷贝上去，0分。

全部人就没拿分的，除了作者。

怀疑数据有错，翌日题目被管理员撤下~

8/9下午： Vijos “笨笨工作室” 提高组模拟赛

黑色日期

vj上两场比赛中唯一到现在我都没做的题目。

据说是简单的统计问题。

显然题意来自usaco 的 friday the thirteen.

我的usaco那道题是一天一天枚举的，在这道题上似乎会超时。

没机会留名字了，跳过。

瓮中捉鳖

很有趣的动规。

二维，可是我这次很难想到那个做法。

很简单的就是了，想通了以后。

f[i,j]=f[i-1,j]*j+f[i-1,j-1]

就想起gXX当年很热心地提醒我说，hanoi要高精喔~！

不过主要被卡在这道题的WS设计上~ 它的瓮不区分而鳖相互区分~

西瓜种植

看起来好像贪心~ 或者动规~ 还是高级数据结构？

是贪心。

满足区间计数条件的贪心。

就是每次按照区间的末位置增序排列一下然后从后到前扫一次区间内的数目是否满足，如果不满足就从后到前的空位置“种瓜”。

题目居然没有说清楚每个位置只能有一个瓜~

而我的网络卡到看不到答疑帖。

比赛完，我和stzgd空虚地讨论优化问题。

显然种瓜数和统计数可以用线段树来维护，这样就不用每次扫描b[i]~e[i]的区间了。

然后zgd还说，这种模拟赛难道用到堆+线段树？

不过我看不出为什么用堆~？ 难道用来维护线段？省得排序一次~？

洪水堵截

这是我看了最有把握的题目。

经典的最小割。

拆点，点间连弧。

MD啊vj的io好像与众不同~ 我的eof多组数据总是出问题~

还有那个数据啊~ 那些点封锁的代价多大都没有的~

我程序一开始inf置为1e7就WA掉。

后来改成int64, inf=trunc(1e18)就AC了。

Mickey很囧的问我不会是网络流吧，我说让我做一定是网络流，时间界很有保证。于是mickey去搜了~ 也不是tle，很奇怪的错误。

所以说，题目还是不清楚。

8/9晚 RQnoj比赛（二十五中***）

第一题（因为这次比赛的题目标题全是我不认识的鸟文~）

输入形如“S=t^3-2t+1 (t=12)”的最高五次多项式，及自变量的取值，求函数值。

经典的水题，WS字串处理而已。

好像当年noip的计算器改良，有空再做这道题。

第二题

给定如“naga de pig as ddog as ffool de ffool oh”的文本，其中单词个数≤100000，不同的单词最多有10000个，单词长度≤25，求每个单词出现的频率并按字典序排列资料。

因为要动态加入词语到字典里面，所以不能用顺序表+二分查找。

（关于这一点，狗牛等认为使用move等还是可以的~但这道题用字符串来move应该不能过~ 如果我出数据， 应该卡到move过不了~）

当然最好的实现时字典树，不过由于字元集很大且长度很大，不能预建树，必须动态建树。复杂度较高。

于是我偷懒的用Hash表。

好像这道题数据也有问题，除了作者外都没有拿分~

我相信我的hash没什么问题~

不过那题的格式也规定得不清楚。

我跟你打赌，这种做法，在比赛中，是可以AC的。

第三题

题意不清。

我研究了很久。

发现我一开始code的做法跟这种理解相差甚远。

于是猥琐地稍微改了代码，于是最后的code很ws。

其实就是求Big Barn一样的那种最大空白正方形。

平方阶预处理，对于每个p做平方阶枚举。

复杂度O(pnm)，0<n,m,p<=200

第四题

搜索。

没写~

貌似近似搜的样子。

道题有部分分。

就是考你怎么剪枝啦。

没研究~ 搜索弱~