这两天,在vjudge上找了一套曼谷的区域赛来做,大部分的题目都是很水的,有两道题完全没思路,剩余的几道都是稍微想一想就能出解的.
对给出的n,求出所有不同的i×j,(0<=ij<=n)
这题最初并没有什么思路,n的范围是30000,时限是7s,所以我想有没有什么稍微暴力一点的方法.
首先想有没有可能从ans[i-1]推出ans[i].
其实每多一个数i,增加数字一定都在i×j (j<=i)集合里.
那么这个集合里有多少是和之前重复的呢?
如果i×j和之前的重复了,那么必有i × j == s × t,其中s t < i.
因此,把所有满足j == p × q的j去掉,那么剩余的就是增加i后增加的个数.
通过枚举i的约数a,之后枚举p,q,即可得出所有的j.
注意在枚举a的时候,a是逐渐变大的,所以p的范围越来越大,q的范围越来越小.而且在枚举p,q的时候会有一些重复.
因此我们可以直接另p递增,而不是每次枚举约数a的时候都需要重新枚举.
给出l,r,求C(ij)(l<=i<=r 0<=j<=i)中奇数的个数.
首先可以感觉到对每一个i,从C(i0)到C(ii)都要算,所以先对每一个i打一个sum(C(ij))的表.
打表会发现从2^i开始就会重复出现之前的,而且从2^i到2^(i+1)的和是从2^(i-1)到2^i的和的三倍.
因此对整段的2^i到2^(i+1)直接累加,对两端的通过递归求解.
E.Zeroes
给出l到r求出对所有的l <= i <= r,i!的末尾的0的个数有几种不同的情况.
可以发现,从l到r中有几个5的倍数就会有几个不同的0的个数.于是求出l和r-1中5的倍数的个数即可.
R × C (1 <= R C <= 100)的矩阵,上面有个数,代表打鱼的收益,也代表放鱼失去的收益,然后现在规定:放两次鱼,打一次鱼,每次放鱼,都要求本次放鱼的ij均大于上次放鱼的ij,捕鱼也是这样,但是捕鱼和放鱼之间没有限制的联系.求这样的最大收益.不限制打渔次数.
设f[i][j][k]是捕k次鱼,最后捕鱼的位置<=i,j的最大值,而g[i][j][k]是放k次放鱼,最后放鱼的位置<=i,j的最小值.两个状态转移方程相似,只不过一个是min一个是max.
最后求捕i次鱼同时放2×i次鱼的最大值即可.
1000×1000的方块,每块有可能有一个'L'标记,并且每一块可以算出来一个值:由它周围有效的9(包括自己)块推出来,如果它有就额外+3,然后9个中有几个L就+几,最大12.现在,给出一个有效状态的转化之后的方块,求出初始状态.
然后想(13),虽然(13)还是能够定出来,但是(14)就不好弄了,关键是(2,x)的都不知道,重点来了:我们不妨把(2,x)同时确定下来,这样两行一块推.
(21)好定,(22)由于4个定了3个,这个发现也很重要,可以定(22),之后发现已经行了,因为之后的(13)可以定了,那么(23)呢?因为(12)周围定了5个,所以减一下就好了.
之后一直推完第一行,然后第三行,先把第二行信息弄掉就和刚才的一样了.
30×30的方格,在一些方格中填1可以构成一个'+'号,它的长度只有可能是3,5,7,9,11,而且长宽相等,这些加号可以重叠,如果某一个格子有i个'+'号覆盖,那么这个格子的数字为i.不过每个加号的中心不能再其他加号上.求对于给出的矩阵,里面有多少个加号.最多不超过9个.
由于加号数目较少,则可以通过枚举加号的中心来进行搜索.一个格子如果是加号的中心,那么他必须是'1',而且他四周的数字必须都大于1.
有p个人,s个参赛地点,每个参赛地点的容量为C,每个人只会去某几个地点参赛,问最多有几个人可以参赛.
可以发现这是一个二分图,从源点向每个人连一条容量为1的边,从每个人向他想去的参赛地点连一条容量为1的边,从每个地点向汇点连一条容量为C的边,之后跑最大流即可.数据比较水,很快就能过.
给出n个毯子,每个毯子长度无限,但是每a段是厚的,b-a段是薄的.有M个人坐标在0~M-1,问对每个人有几个毯子的厚的部分覆盖到了他.
由于a,b很小(<=16),所以直接暴力求出前16个的结果,后面的可以映射到前面.
也是简单的dp.题目大概说的是有i个城市,每两个城市之间可以直接联通,花费给出,第i个月在地j个城市的收益也给出,求最大收益.
有n×m块格子,每个格子可能与他上下左右四个格子连任意条边,现在给出每个格子的度,但是有一个格子未给出,求这个格子的度.
这明显是一个二分图.二分染色后把两个集合的度之和相减即可得出.