Steve的水池

题目链接

单点时限: 1.0 sec

内存限制: 512 MB

Steve 拥有深棕色头发，晒黑的褐色皮肤，紫色的眼睛，身穿青蓝色的衬衫，一条紫蓝色牛仔裤以及灰黑色的鞋子。他还拥有2px至4px大小的胳膊。Steve 似乎拥有轻微的浅棕色胡子茬，或者拥有一张嘴，这取决于你怎样看他。

Steve 需要种庄稼，圈养动物来获得食物来源，为了抵抗怪物，他需要挖矿获得铁锭，金锭，甚至钻石来制作更高级的武器装备，通常，他还需要对武器装备附魔，来提升效果，为此，他不得不需要经常下矿。

在经历了枯燥又乏味的矿工生活后，Steve 打算建造一个水池来放松放松，他打算把水池建造成一个高度为1，长宽分别为N,M的水池，为此，他需要向水池中倒水，但Steve 只有一个水桶，他不想要浪费更多的铁锭来制作更多的水桶，为此，他需要尽可能少的往水池里倒水以尽快建造好水池，但是Steve 的世界有一个很奇怪的特性，每向一个区域倒水的时候，在这个区域会形成一个水源，当一个区域四个方向中至少有两个方向紧挨着这个区域的地方都为水源的话，这个区域也将会形成水源，Steve 想要知道最少他需要倒多少次水才能使水池每处都形成水源。

输入格式

输入第1行为一个整数T。（1 ≤ T ≤ 1000）
第2行到第T+1行每行为两个整数N,M代表水池的长宽。（1 ≤ N,M ≤ 109）

输出格式

输出为T行，每行输出一个整数，代表Steve 最少需要的倒水次数。

样例

input

1
1 1

output

1

input

2
1 3
3 3

output

2
3

题解：

这是一道很巧妙地考察思维的题，找到规律就很好做。我们转化成给格子染色的模型。

图一

如果水池是上图所示，根据规则其余空白的所有格子都会被染色。

图二 

再来看上图，根据规则，是不是根据规则会变成图一的形式，这就是使所有格子被染色的最少数目。那么问题就变成了，如何给上方第一行和左方第一行染色最少，根据规则能使上方第一行和左方第一行全部变得有颜色，从而使全部格子变得有颜色。

图三

其实你去想如何给上方第一行和左方第一行染色数目是最少也不太好想，那么我们再进行转化，把上方第一行和左方第一行给折一下，想象成一行，那就容易求了，可以很容易知道给上方第一行和左方第一行染色数目最少是(n+m+1)/2。（很容易就能证明，可以自己证一下）

AC代码：

#include <iostream>
#include <algorithm>
#include <vector>
#include <stdio.h>using namespace std;typedef long long ll;int main()
{
//	freopen("input.txt","r",stdin); std::ios::sync_with_stdio(false);int T;cin>>T;int n,m;while(T--){cin>>n>>m;cout<<(n+m+1)/2<<endl;}return 0;
}

尾声：这道题其实很简单，找到规律似乎也很简单。但是当时做的时候看题那么长，和dfs又那么像，就没看了，很可惜。看来，学长并不一定都出难题，也有一些考思维的简单题，就看你能不能抓住了，连看都不看怎么能抓住呢？虽然自己基础比较弱，但是在条件允许的情况下，以后比赛时一定把所有题认真看一下，尽力用自己掌握的知识去解决，一直纠结于自己找bug的题却做不出来，还不如腾出些时间去尝试一下看起来难的题，就算做不出来，也锻炼了自己的胆量，不再惧怕难题了，况且，你找规律很厉害的，不一定做不出来呀。

为将之道，当先治心。泰山崩于前而色不变，麋鹿兴于左而目不瞬，然后可以制利害，可以待敌。—宋·苏洵《心术》

注：麋鹿的麋是鹿下面加个米。