解题报告2

vijos-模拟赛

phoeagon

 本文原创，若有雷同，你抄我的~

怪盗基德-月下の谜 系列

这次比赛的题目迟迟没有出来~ 于是~ 流言风传 题目被基德偷了。。。

1、银翼の舞（の居然用搜狗可以拼zhi）

水题~ 看懂了怎么写都可以~

可以o(nlogn)排序找两头大小，也可以直接线性找大小极端值。

记得基德自己的速度算进去~~~！

否则~

恩恩~ Hang同学。。。

2、扑克の阵

在给定的n<=1000的n*n正方阵中找2个不相重叠的边长为k的子方形使得和最大。

首先，如果求一个最大子方形~

f[i,j]=max(f[i-1,j], f[i,j-1], sum(i,j)-sum(i-k,j)-sum(i,j-k)+sum(i-k,j-k))

第二，两个不相重叠的子正方形，在给定方形中，必定可以用一条纵线或横线分开~

即，相当于原矩形存在一条横或纵分割线，分开的两个矩阵的最大正方形即为解。

则我们预处理以(i,j)为左上角、右下角的边长为k的最大（区域内已知）子矩阵。

之后枚举分割线，分割线两边矩阵的最大子正方形可以分别由左上角和右下角正方形最大值求得。

每一步的复杂度都是O(n^2)，总复杂度也是O(n^2)

3、华丽の旅（其实の也可以在de找到）

你会发现样例其实是usaco原题的Sample。。。。

经典矩形切割，得到最后布上各种颜色的面积。

之后根据给定的颜色关系作最短路（其实是闭包传递~）

注意题目求的是可行的第一种颜色，不要求最省颜料。。。

然后枚举一种颜色使得图上的每一张外露的颜色都可以转化为那种颜色。(floyd记得令f[i,i]=true)

至于范围~ 其实矩形覆盖的最终队列的长度~ 很难估计~

4、最后の战。

在给定上限为x的所有数字中，选出能表示为4的幂和5的幂的乘积的数字。

然后，从这个集合中选择若干个，规定选择x就不能选择x/4, x/5, x*4, x*5

问有多少种选择的方法？

好题来着~

matrix67上有一篇

http://www.matrix67.com/blog/archives/1850（（召集）你能想到的最奇妙的算法题是什么？）

的文章，最后谈到这个题目~

“在1到n中选取若干个数，要求如果选了x就不能选2x和3x，问共有多少种选择方案。例如，n=3时答案为5，这5种选法分别为{}, {1}, {2}, {3}, {2,3}。”

其实容易发现，这两个问题是等价的~

把数字写在一个矩阵里，(x,y)填入(4^x)*(5^y)

用朴素的语言："把数字1放在方阵最左下角，然后不断在一个数的右边填上它的4倍，在其上方填上它的5倍。"

好，这个就是经典的状态压缩动态规划。

用f[i,j]表示第i行的状态是j的方案数。

把每行的选择状态0/1压缩成一个数字~

dp即可。注意f[i,j]=sum(f[i-1,x])中不止要满足（x and j=0）且（x没有相邻的1位，j也没有）

Orz教主 系列　

很抱歉，这次题目不容易~ 到现在只AC两道~ 不过这也是这几次中质量最好的模拟赛~

1、旅行

被骗了~

usaco上有一道~ 那个把路升高或降低的耗费是c*|Ai-Bi|，这个是|Ai-Bi|.

而且这个从i段到i+1段的费用为|Ai-A(i+1)|，而不是usaco的d*|Ai-A(i+1)|。

所以本题可以贪心。

如果第i个同时低于i-1和i+1，把第i个升高到两边较低的。如果i同时高于两边，降低到两个中较高的。

3、超级教主

f[i]=max(f[j]+sum(j+1,i)-100*i) 【f[j]>=100*i】

O(N^2)的动规~

可以用单调队列优化到O(N)

具体做法是，用单调队列维护

f[x]+sum[x+1,n]的高度。

每次从单调队列中取最大值dp~

//注意本题的方程条件【f[j]>=100*i】，

//如果忽视了条件

//题目就只需要记录当前最大值~

答案就是错误的~

比赛当晚我们因为这一点讨论了很久~ 最后大家还是没有丧失理智啊~~哈哈~

要单调队列的~

HOI 系列　

猥题不做~！

2 开心农场~

只有一点提示，就是n块地一定是种一样的东西~

f[i]=max{f[i-time[x]]+benefit[x]}

4、精卫填海

01背包

注意因为取的所有石子体积可以超过v，所以以体力为体积以体积为价值~

NOIP 2009·Dream Team 模拟赛 系列　

不容易的水题。

1、爱在心中

裸的强连通分量~

二次dfs求强连通分量~ 缩点，闭包传递（再次dfs）~我ws~

但是0ms喔~

2、看樱花

稍有水平的dp。

每个数只能取一次，n=1000，是平方级的区间动规。

看到好多人求助说，要用三方的dp~

怎么三方呢~

大概是f[i,j,k]表示从i到j的区间中取，最后停在k~

可是~

明显要tle最后两个点~

其实不需要三次方。。。

注意到题目里向左走向右走需要代价是正的~ 也就是说，除了最后一次，从区间端点走到区间中某一个出“公园”（不是出花园），（为了追求那个点的很小的exit代价），其余都不可能在欣赏过的区间内走来走去走来走去~……

所以只要f[i,j,1/2]表示区间[i,j]上取，最后停在左端还是右端就可以了。

那么怎么处理最后走回到区间的某个点呢？如果枚举端点走到区间内的某个点，复杂度还是三次方。

这个只需要预处理一个数组

cost[i,j]表示从i出发走到j离开公园的最小代价。

f[i,j,1]-cost[j,k]
f[i,j,2]-cost[k,j]

像这样~

这个cost要直接求出最小代价不容易的~ （我一开始很天真的去试）

其实应该求出从i到j离开的代价，之后线性扫一遍得到区间最小值。

所以利用预处理把复杂度降到平方级。

3、情敌

dp~

标程做法是~ 枚举每个超级情敌是否消灭以及在哪个时间消灭(3^m)，对每一种情况再作背包~

复杂度O(3^m*(n-m)*a*b)

我有一种做法，模仿何森在《浅谈数据的合理组织》中解决依赖背包的做法。

不知正确否~ （似乎是正确的~）

不过数据很水，我自己这个算法写错很多次都能AC~

数据的4和7稍微比较强~！ 但我自己搞了个魔鬼数据：

特殊情况的正确性检验。

4、八

容斥原理。

求出1、2、3、4....n个数的公倍数在[a,b]中的数目，作容斥。

//其实不用刻意每次求k个数的公倍数~ 2^n的0/1枚举过去，根据1的数目决定符号就可以了~

飞过海第一次模拟赛&OI总部对抗赛

猥琐没的说~

1、生产武器。

看不懂~ 据说是尼克的任务~ Oliver的烦恼~

2、城市连接

TM的没有范围.

证实n<=1000

当然dijkstra就过~

你想，题目本来就是平方级读入一个邻接矩阵的~

不懂为什么有人tle~

不会是写了王建德吴文虎的《图论算法******》中那个三次方的做法吧~

老书不可信也。

3、抢救文件。

看不懂x和y是干什么用的，两个kelefe~

原题来着，sgu199Beautiful People。

比那道还容易~

这一道根本就没有相同的数~

估计是作者没把握吧~

按A[1..n]排序后作LIS即可。。。

（不要告诉我你的lis是平方级的~）

4、机密文件

思路很好，二分+线性检验~

注意如果用dp不能直接求方案，只能求最少人数，得到后再贪心。

或者dp出可行方案进行调整~

还是不如二分+线性检验的O(log(sumpages)*n).

天啊天啊~ 现在题目怎么看愣是看不懂~

早上看到hh4742在oibh上的新文有关七夕的~

想念她的古韵/秋意清寒模拟赛~

题目至少读得懂~

现在这年头~

唉~

万般无奈时。

phoeagon