Mars_Cat

在9号晚上做了一下UOJ Round #9 。。发现Rating居然还是上升的。。

倍感惊奇。
那时候只有A题60分。。很可怜的一个分数是吧。。其中20分还是一只Pluto_Rabbit想到的= =|

A. 【UR #9】电路手动分析  时间限制：1s 空间限制：256M

描述

在设计电路的过程中，常常要手动分析电路。
我们故事的主人公——奸笑熊是一个参加了 NOI2015 结果遗憾退役的 OIer。
马上就要回班搞高考了，奸笑熊不免有点伤感。于是奸笑熊开始玩电路散散心。
奸笑熊的电路有 n×m  个节点，排成 n  行 m  列。任意两个相邻节点之间连着一条导线。如果两个节点(x1,y1),(x2,y2)满足|x1 −x2|+|y1−y2|=1则称这两个节点相邻。
奸笑熊定义一个电路的复杂程度为最大的非负整数s满足可以选出s个节点使得任意两个被选中的节点间都有一根导线相连。
奸笑熊手里还有r根导线，可以连在r对节点之间。奸笑熊希望新加上不超过r根导线后，电路的复杂程度最大。
请你帮奸笑熊手动分析他的电路，告诉他复杂程度最大是多少。

输入格式

共一行，包含三个整数 n,m,r。保证n,m≥1，r≥0 。

输出格式

共一行，包含一个整数表示答案。
C/C++ 输入输出 long long 时请用 %lld。C++ 可以直接使用 cin/cout 输入输出。

2 2 0

2

2 3 3

4

限制与约定

上文提到的20分为4,5两个点。。
附：UOJ官方题解

然后你会发现居然没有40分的解决方案= =|
那么窝的60分是怎么是怎么出现的呢？（其实是写炸了。应该是70分。。然而50分的题解也没有出现。。）

50分实际上还是挺简单的。。就是找到第一个点之后用优先队列维护已知图的周边点，每次选取一个点与原图连线最多。。

然后我们就可以来看看100分的了。

可以证明：在形状最接近正方形时，在同数量点的图中，连线最少。
于是就可以二分答案啦！

然后呢。。就捉急啦！70'

#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <algorithm>

using namespace std;

typedef long long LL;
typedef long long ll;
LL n, m, r, ans;

bool check(LL xx)
{
	LL rr = r;
	if (xx > n*m)return 0;
	LL tt = (LL)(sqrt(xx));
	tt = min(tt, n);
	LL l = xx / tt, s = xx%tt;
	rr -= l*tt*(l*tt - 1) / 2 - (l - 1)*tt - (tt - 1)*l;
	if (s)
	{
		rr -= l*tt - 1;
		--s;
	}
	LL n = (l*tt - 2)*s + (1 + s)*s / 2;
	return n <= rr;
}


int main()
{
	scanf("%lld%lld%lld", &n, &m, &r);
	if (n > m)swap(n, m);
	LL L = 1, R = n*m+1, mid;
	while (L < R)
	{
		mid = (L + R) >> 1;
		if (check(mid))L = mid + 1; else R = mid;
	}
	printf("%lld\n", L-1);
	return 0;
}

太差了。

单步调试发现：程序中的q的平方会超过long long 的范围。。

于是我们需要优化。经过计算可以证明r=10¹⁸时可以达到的最大点数为2^0.5*10⁹个点。于是二分的上界得到了缩小。。于是A了。。

#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <algorithm>

using namespace std;

typedef long long LL;
LL n, m, r, ans;

bool check(LL xx)
{
	LL rr = r;
	if (xx > n*m)return 0;
	LL tt = min((LL)(sqrt(xx)), n);
	LL l = xx / tt, s = xx%tt;
	LL q = l*tt;
	if (rr < q*(q - 1) / 2 - q * 2 + tt + l)return 0;
	rr -= q*(q - 1) / 2 - q * 2 + tt + l;
	if (s)
	{
		if (rr < q - 1)return 0;
		rr -= q - 1;
		--s;
	}
	LL n = (l*tt - 2)*s + (1 + s)*s / 2;
	return n <= rr;
}


int main()
{
	scanf("%lld%lld%lld", &n, &m, &r);
	if (n > m)swap(n, m);
	LL L = 1, R = min(n*m + 1, 1500000000ll), mid;
	while (L < R)
	{
		mid = (L + R) >> 1;
		if (check(mid))L = mid + 1; else R = mid;
	}
	printf("%lld\n", L-1);
	return 0;
}