2016.1.23测试总结

好像是JSOI2009..
 
前三题一股联赛题的感觉
前两道题简单得BZOJ都不忍心加了...
--------------------------------------------------------------------------
 
说下题:
T1:n个人在食堂打饭,有m种饭菜,每个同学对于每种饭菜都有一定需求量,并且每个人都会尽量把自己需求的打够,现在你也有一个对每种饭菜的需求量,问你最靠后要插队在哪个同学后面才能满足你的需求?m<=10,n<=100
T2:给你一个2×n的矩阵,要求从中选出一个凸字型,可正可倒,使凸字形框出的数字和最大,问这个和的最大值,n<=10^6
T3:有n个瓶子,每个有一个容量vi,要求从中选k个交给外星人,外星人会执行这三种操作:
    1.装满一个瓶子
    2.倒空一个瓶子
    3.把一个瓶子里的水往另一个瓶子里倒,直到一个满或者一个空为止
外星人很抠门,总是会给你做以上操作能得到的水的多少的最小正值,现在问你怎么选瓶子,才能让外星人给你的水最多,输出这个最大值。k<=n<=1000
T4:俩人为了争夺一张吸氧羊的电影票玩起了游戏,规则是在有障碍的格子里摆棋子,每次每个人在上次放的人的周围四格放,不能放障碍上,且每个格子只能放一个棋子,先手第一步任意放,问先手第一步放哪些格子有必胜策略。棋盘大小n*m, n,m<=100
 --------------------------------------------------------------------------
T1:这数据范围n^2大暴力都能过...这分送得简直比noip都干脆
--------------------------------------------------------------------------
T2:傻逼DP
f[i][j]表示第i列,目前是第j种状态,最大和
第0种状态是凸型左边的空白,值永远为0
第1种状态是凸型中凸出来的一坨左边区域,可以从0或1转移过来
第2种状态是凸型中间凸出来的部分,可以从1或2转移过来
第3种状态是凸型中凸出来的一坨右边区域,可以从2或3转移过来
第4种状态是凸型右边的空白,可以从3或4转移得到
最后答案就是max{f[n][3],f[n][4]}
因为凸型可以倒过来,所以交换两行再做一次即可
--------------------------------------------------------------------------
T3:
YY一下发现两个瓶子可以得到的最小正值就是他们容量的gcd,(因为实际上是在做更相减损,用更相减损术的正确性定理可以证明)
有gcd(a,b,c) = gcd(gcd(a,b),c)
因此要选k个数,使gcd最大
把每个数分解约数丢到表里面,最后出现了超过k次的最大约数就是答案
--------------------------------------------------------------------------
T4:
习惯了前面sb题的节奏做这个题直接懵逼了...
我花了4个小时去找规律和优化搜索...
然而并没有什么卵用..还是只有暴力的三十分..
标准解法:考虑二分图匹配
相邻的格子连边,显然是个二分图
求一个最大匹配,如果先手在某个有匹配的点上的话,那显然就挂了,因为不论怎么走对方可以走和你匹配的格子,然后下一个你的先手又必须走在一个已匹配的格子...因此没有匹配的点就是答案,因为先手走在这些格子,下一步轮到对方先手时他就不得不走某个已匹配的点
但是最大匹配有很多种,我们需要把每一种最大匹配的孤立点都选出来
建立网络,源点连向一个点集(设为V1),另一个点集连向汇点(设为V2),跑最大流
从源点开始搜索,并且只走流量为1的边,如果一种走法能够到达t,说明这个走法上的边可以经过调整匹配,使得经过的V1中点被空出来,因此把路径上所有经过的V1中点加入答案
同样还要从汇点开始来一发,不过这次只走流量为0的边,并且只添加经过的V2中点
这样就可以得到所有答案...
--------------------------------------------------------------------------