0%

CodeforcesRound#524

过了3题,上了点分,还行。
链接

A. Petya and Origami

题意:Petya想要邀请他的$n$位朋友,而每张邀请函需要2个红色sheets、5个绿色sheets、8个蓝色sheets。然后你要买notebook来获得sheets,每个notebook里有$k$个sheets,但仅含一种颜色,问最少需要买多少notebook。

做法:$ans = \lceil\frac{2n}{k}\rceil + \lceil\frac{5n}{k}\rceil + \lceil\frac{8n}{k}\rceil$。

B. Margarite and the best present

题意:给你一个数组$a_i = i \cdot (-1)^i$,求$\sum\limits_{i = l}^{r} a_i$ 。

做法:令$S(j)=\sum\limits_{i = 1}^{j} a_i$。容易知道当$j$为偶数时$S(j)=\frac{j}{2}$,那么当$j$为奇数时,$S(j)=S(j-1)-j$。那么$ans=S(r)-S(l-1)$就可以快速算出来。

C. Masha and two friends

题意:给你一个像下图一样有些部分为白色有些部分为黑色的棋盘,然后将某个区域涂成白色,再将某个区域涂成黑色,而区域是由两个坐标表达,代表分别代表左下角以及右下角的区域。(看题目Note部分更容易理解)问最后白和黑的格子的数量。

做法:这个图若白块个数为$white$,那么黑块个数即$nm-white$。那么数一种就可以了。因为最后涂的是黑色,那么数黑色会更好数。我们最好把涂的块与没进行过涂的块进行分开处理。
例如输入:

1
2
3
4 4
2 2 3 3
3 3 4 4


令区间$(x1,y1,x2,y2)$原来的黑色块记作$count(x1,y1,x2,y2)$。
那么没涂过的部分由容斥原理就是$count(1,1,4,4)-count(2,2,3,3)-count(3,3,4,4)+count(3,3,3,3)$。(看上图更容易理解,红色框起来的部分是要加,而蓝色框起来的部分是要减。)
然后容易知道$black=(x4-x3+1)(y4-y3+1)+$没有被处理的部分的黑块。
即$black=count(1, 1, n, m) - count(x1, y1, x2, y2) - count(x3, y3, x4, y4) + count(x5, y5, x6, y6) + (y4 - y3 + 1) * (x4 - x3 + 1)$(设相交区间为$(x5,y5,x6,y6)$)。
而相交区间$(x5, y5, x6, y6)$ 即 $(max(x1, x3), max(y1, y3), min(x2, x4), min(y2, y4))$。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def mainA():
n, k = map(int, input().split())
a = (2 * n, 5 * n, 8 * n)
print(sum(map(lambda x: (x + k - 1) // k, a)))

def mainB():
def calc(x):
return -x + x // 2 if x & 1 else x // 2
T = int(input())
for t in range(T):
l, r = map(int, input().split())
print(calc(r) - calc(l - 1))

def mainC():
def count(x1, y1, x2, y2):
if x1 > x2 or y1 > y2:
return 0
ret = (x2 - x1 + 1) * (y2 - y1 + 1) // 2
return ret if (x2 - x1) & 1 or (y2 - y1) & 1 or not (x1 + y1) & 1 else ret + 1
T = int(input())
for t in range(T):
n, m = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
x3, y3, x4, y4 = map(int, input().split())
x5, y5, x6, y6 = max(x1, x3), max(y1, y3), min(x2, x4), min(y2, y4)
black = count(1, 1, n, m) - count(x1, y1, x2, y2) - count(x3, y3, x4, y4) + count(x5, y5, x6, y6) + (y4 - y3 + 1) * (x4 - x3 + 1)
print(n * m - black, black)

回到开头