8
11
2015
1

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: 1036
Avatar_small
NCERT Mathematics Qu 说:
2022年9月28日 13:14

Mathematics is one of the subjects which plays a key role in everyone’s life and it’s very important to each student. NCERT Mathematics Question Paper Class 2 Mathematics is not a certain time helping subject, it is along with the people for their whole life at any time and at anywhere. It should begin from the foundation of Education to enable 2nd students to understand mathematics easily. Downloading NCERT Mathematics Sample Paper 2023 Class 2 for all formats of exams conducted under Term-1, Term-2 and other types of exams has available for every candidate who wants to get a keen clarity on the question pattern of the exam paper along with revised important questions.


登录 *


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