8
11
2015
0

UOJ Round #9 A

在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 输入输出。

样例一

input

2 2 0

output

2

explanation

不能加导线。所以只能选择两个相邻的节点,复杂程度为 2 

样例二

input

2 3 3

output

4
 

限制与约定

测试点
编号

n,m规模

r的规模
1
n,m≤4
r≤13
2
3
4
n=1,m≤109
r≤1018
5
6
n,m≤1000
7
8
n,m≤109
9
10

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

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

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

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

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

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

 

#24891 #133. 【UR #9】电路手动分析 Mars_cat 70 0ms 1196kb C++ 725b 2015-08-11 08:42:50

 

#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=1018时可以达到的最大点数为20.5*109个点。于是二分的上界得到了缩小。。于是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;
}

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Category: 程序 | Tags: | Read Count: 318

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com