2016.1.23测试总结
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
好像是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中点
这样就可以得到所有答案...
--------------------------------------------------------------------------
2022年9月26日 01:58
Those Class 6th Standard students who have interested in getting the best score in Term-1& Term-2 exams can download the NCERT STD-6 Biology Sample Paper 2023 Pdf with Suggested answers that support Hindi Medium, English Medium, and Urdu Medium Students for SA1, SA2, FA1, FA2, FA3, FA4, NCERT Biology Question Paper Class6 Assignments and other types of exams which are conducted under the board or school level.Those Class 6th Standard students who have interested in getting the best score in Term-1& Term-2 exams can download the NCERT STD-6 Biology Sample Paper 2023 Pdf with Suggested answers that support Hindi Medium.