codeforce AIM Tech Round 5几个简单题目

63 阅读 0 评论 42 点赞

我是靠谱客的博主淡淡酸奶，最近开发中收集的这篇文章主要介绍codeforce AIM Tech Round 5几个简单题目，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

1，A，Find Square

这个简单了，题目限制了输入只有一个正方形。找到黑色的部分，然后就开始读一个长。之后算中心就行了。代码都不贴了。

2，B unnatural Conditionals

要求的条件很神奇，要求对于给出的m，n，求两a，b，使得：

s(a) >= m

s(b) >= m

s(a+b) <=n

其中s函数表示针对整数x，求每一位数的和。例如

s(2345) = 2 + 3 + 4 + 5 = 14

其实看起来麻烦，实际上很简单，大于那个好说，关键我们来看小于的那个。两个数相加之后求s，最小是多少呢？最小是1。只要使得两个数相加为一个1开头的整数就行了，例如10000,100000000。只需要构造合适的a，b，使得他们的s大于m就行了。最简单的办法就是构造4444444444444445和55555555555555这种数。由于对于m，只要求大于，不要求上界，可以直接用4除m，得到4的个数，构造一个数组，最后一位修改为5，然后将整个数组全部变成5。分别打印。

3，C Retangles

求一个点，有至少n-1个矩形覆盖了这个点。

本来想着有点复杂的。。。但是瞄了一眼大神解答，嗯。。。我弱爆了。。。

先求两个矩形的共同覆盖区域：


def merge(self, another):
x1 = max(self.x1, another.x1)
y1 = max(self.y1, another.y1)
x2 = min(self.x2, another.x2)
y2 = min(self.y2, another.y2)
return retangle(x1,y1,x2,y2)

嗯，左下角分别求max，右上角分别求min就行。。。。真是简单到怀疑人生。

然后构造一个数组x，x[i]表示从第0个矩形到第i个矩形的共同覆盖范围

def merge_all(inData):
out = [inData[0]]
for i in range(1, len(inData)):
out.append(out[i - 1].merge(inData[i]))
return out

顺着算一次，反着算一次，然后遍历一次两个数组，求去除中间的一个矩阵的合并区域，如果该区域合法，就得到了答案

a = merge_all(retangles)
b = merge_all(retangles[::-1])[::-1]
for i in range(n):
ret=a[i].merge(b[i+2])
if ret.x1<=ret.x2 and ret.y1<=ret.y2:
print(ret.x1,ret.y1);exit()

完整代码如下：

import sys
class retangle():
def __init__(self, x1,y1,x2,y2):
self.x1 = x1
self.y1 = y1
self.x2 = x2
self.y2 = y2
def __str__(self):
return str([self.x1, self.y1, self.x2, self.y2])
def merge(self, another):
x1 = max(self.x1, another.x1)
y1 = max(self.y1, another.y1)
x2 = min(self.x2, another.x2)
y2 = min(self.y2, another.y2)
return retangle(x1,y1,x2,y2)
H=9**15
B=retangle(-H,-H,H,H)
retangles = [B]
n = int(input())
for i in range(n):
x1,y1,x2,y2 = map(int, input().split())
retangles.append(retangle(x1,y1,x2,y2))
retangles.append(B)
def merge_all(inData):
out = [inData[0]]
for i in range(1, len(inData)):
out.append(out[i - 1].merge(inData[i]))
return out
a = merge_all(retangles)
b = merge_all(retangles[::-1])[::-1]
for i in range(n):
ret=a[i].merge(b[i+2])
if ret.x1<=ret.x2 and ret.y1<=ret.y2:
print(ret.x1,ret.y1);exit()