UOJ Logo snakes的博客

博客

Codeforces Round #368 (Div.2) 官方题解

2016-08-21 08:33:23 By snakes

Codeforces Round #368 (Div.2) 官方题解

题解 By zloyplace35
翻译 By Snakes

谢谢大家,希望你们能喜欢这些题目。

A — Brain的照片

对于所有的字符,如果有任意字符在集合$\{C,M,Y\}$里,那么答案就是“#Color”,否则答案是“#Black&White”。

B — 面包店

我们可以发现,如果选择一个城市开面包店,若它和最近的仓库最短路上有其他城市,那么我们必定不会选择这个城市,因为道路距离增大,答案也会增大。

因此,我们只要选择两个相邻的城市,一个是仓库,另一个是选择开面包店的城市。我们只用查找每个仓库相邻的非仓库的城市的最短距离即可。如果没有这样的一对城市则输出$-1$。

C — 勾股数

或许这一轮比赛中最有趣的就是这道题了吧。

题目大意:

给出一个数$a$,找到两个数$b$和$c$完成以下两个等式:

$$a^2=b^2+c^2$$

$$a^2=abs(b^2-c^2)$$

先考虑无解的情况:

若$а=1$,则:

$1=b^2+c^2$ — 不成立。

$1=abs(b^2-c^2)$ — 不成立,并不存在两个平方数使得差为$1$。

若$a=2$,则:

$4=b^2+c^2$ — 不成立。

$4=abs(b^2-c^2)$ — 不成立,比$4$大且最小的两个平方数之差为$5$。

再来考虑有解的情况:

若$a$为奇数:

令$b=\lfloor\frac{a^2}2\rfloor$,$c=\lfloor\frac{a^2}2\rfloor+1$。

则$c^2-b^2=(c-b)*(c+b)=(1)*(a^2)=a^2$。

若$a$为偶数:

若$\frac a2$为奇数,那么我们可以用上文奇数的方法求出$b$和$c$:

$b=\lfloor\frac{a^2}4\rfloor*2$,$c=\lfloor\frac{a^2}4\rfloor+1*2$。

若$\frac a2$为偶数,我们可以用已知的三元组$\{3,4,5\}$得到答案:

$b=3*\frac a4$

$c=5*\frac a4$

D — 可持久化书柜

方法一:

我们可以注意到数据可以离线处理。我们可以先建树,然后DFS从询问的版本中处理每个询问。

方法二:

注意到每次并不会操作整列,那么我们可以用数组记录每行的版本。对于某个操作,我们只需在该行创建新版本修改书柜或者查询。这个方法可以避免存储冗余信息。

E — 花圈(有谁能帮忙QAQ)

Let us handle each request as follows:

Let's go for a "frame" request and remember lamp garlands, which lies on the boundary. Then, in order to find concrete garland, what part of it lies within the query, sum all of its segments, the ends of which are lamps that lie on the "frame".

Also, do not forget the garlands that lie entirely within the request. Each garland at the beginning we find the extreme points, and to check whether it lies entirely within the query, check whether the lie inside its extreme points.

如果有错漏请在评论区留言,谢谢!

UPD:官方英文版已放出。

评论

lkmcfj
看不懂E题题解QAQ

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。