近期习题集

题目都比较简单。。
都是基础题。

所以说都是自己基础差。

Spoj FLOWERS

给你一个m行n列的矩阵,把他补全成n*n的方阵。
要求每行的n个数都是1-n的全排列,每列的n个数都是全排列。
求字典序最小的解。(讲方阵一行一行地拿出来串成字符串后比较字典序)
或者输出无解。

Spoj SDGAME2

n个数的数列。现在定义一个位置合法当且仅当这个位置上的数字大于0且小于等于10^9。
有一个常数m。
支持一下操作:
所有数乘以一个数。
改一个位置的数。
询问区间[l,r]里面所有合法的位置的数字的乘积模m。

Sgu 413

给一个点数是偶数的无向连通简单图(V,E)。。要求将V划分为若干子集,要求每个子集的导出子图是点数>1的树。
输出任意一组解。

bzoj2412

有一条电线。上面有n个关键节点。。
现在有一个关键节点出了问题。
我们要把找出出问题的关键节点是哪一个。
每次可以指定一个关键节点i询问,可以得知[1,i]这段电线有没有关键节点出问题。

指定的点不同时,询问的代价也不同,指定i节点询问,付出的代价是Ci

现在给定n<=2000,以及数组C[]。
要求指定一种询问策略,使得最坏情况下付出代价最小。


未完待续



























sol

flowers
如果我们只需要填上m+1行,不用管填完之后能不能再填上m+2行,该怎么做呢?
显然建立二分图,求一个最小字典序的完备匹配就好了。
注意到这个二分图,左边每个点的度数都是n-m,右边每个点的度数也都是n-m。
根据hall定理,这样的二分图肯定是有完备匹配的
所以只要前m*n的矩阵是合法的,肯定有解
一行一行填,这样就可以了
注意我们需要实现最小字典序的匹配,只要先求一个完备匹配,然后调整就可以了。求最小字典序匹配,复杂度是可以做到O(nm)的。
所以总复杂度是O((n-m)*n^3)

SDGAME
注意到一个数被乘以至多三十来次大于1的数字之后,就会大于10^9,全局乘以仍然是非法的。
注意到一个数被乘以0之后。。就可以不管它了,因为全局乘以之后它还是非法的。
所以用类似gss4的方法,暴力对合法的数字执行乘法操作就行了。。

sgu 413
手玩一下就会发现这个基本构造不出无解情况。
实际上只要点数是偶数就肯定有解。
lordxfastx给了一个奇怪的思路。。反正我是没看懂。。
他的想法大概就是随便搞一个生成树,然后选一个包含根节点的合法点集(导出子图是树),并且删掉这个点集之后,得到的生成森林的每个树的点数都是偶数。。
但是我不知道怎么找这个点集。。。

看了vjudge的代码之后。
http://vjudge.net/problem/viewSource.action?id=655979
发现这样的做法也可以。。
看代码。。正确性挺显然的。

bzoj 2412
每次询问后,可能的答案集合一定是一段连续区间。
显然可以有区间dp模型。
定义f[l][r]为答案区间在[l,r]时候的最小代价
显然f[l][r]=min{max(f[l][k],f[k+1][r])+Ck},l<=k<r
这样直接dp是O(n^3)的,会tle。
然后我们发现。。固定了l,r之后。。
函数g(x)=max(f[l][x],f[x+1][r])。。
这个函数明显是单谷的。
(因为随着x增加,f[l][x]单调增,f[x+1][r]单调减)

而且很明显,谷的位置也是单调的。。[l,r]区间的谷的位置一定小于等于[l,r+1]的。
所以我们递推谷的位置。。用单调队列随便搞搞就成O(n^2)了。。

但是

lordxfastx:这样做的常数太大,还是会tle。

上面的做法我没有写。。就没有验证了。。
我也不知道bzoj这题有没有人是用上面的方法碾压过去的。。
lordxfastx说只要用记忆化搜索。。求谷的时候直接二分,然后通过一些显然的剪枝来避免求一些无用的状态,就可以快很多。
我试了一下发现确实跑得挺快。。而且代码长度是bzoj ac代码中最短的。。
(虽然最坏还是O(n^3)的)


未完待续

Comments

comments powered by Disqus