Codeforces Round #620 (Div. 2) 题解

Before Read

Solve 4 of 7
Rank:1120
Rating Change:+29 1735 → 1764
Contest Link

A. Two Rabbits

Describe


两只可爱的兔子分别从$x,y$出发,相向而行,其中,左边的兔子一次跳$a$个单位,右边的兔子一次跳$b$个单位,数据保证$x<y$。
现有$t(0 \leq t\leq 1000)$组,保证$(0\leq x< y \leq {10}^9 ,1\leq a ,b\leq {10}^9)$。
问每组兔子是否能相遇(都跳$ans$次使其在同一点),若可以输出$ans$否则输出$-1$。

Solution

Codeforces的A题一般都是比较简单的qwq
这就是大名鼎鼎的小学相遇问题。
那么直接路程差除以速度和是否是整数即可。

Code

(请忽略窝比赛时随手定义的变量名qwq)

B. Longest Palindrome

Describe

有$n(1\leq n\leq 100)$个字符串,每个字符串长度均为$m(1\leq m \leq 50)$,你可以选取其中的几个字符串,任意顺序组合,使其为一个回文字符串,输出最长的字符串长度与这个字符串。

Solution

由于所有字符串的长度均为$m$,所以要将两两互相回文的字符串组合即可,比如说样例1(这个bat蝙蝠是不是预示着什么…)

我们可以$O(N^2 \times M)$的求出两个字符串是否互相回文,比如说$\texttt{tab}$与$\texttt{bat}$互相回文。
那么我们可以将其组合起来。
设我们已经组合出来了$s_i,t_i$是互相回文的,那么答案就是$s_1,s_2,s_3…s_k,t_k,t_{k-1},t_{k-2}…t_1$。
当然这种方法是不完美的。
比如说这个数据:

那么显然$xxx$可以放在中间。
所以我们在最后特判一下即可。

C. Air Conditioner

Describe

餐厅里有个空调,在任意一个时刻,空调可以关(温度不变),加热(温度$+1$),降温(温度$-1$)。
给出$n(1\leq n\leq 100)$个限制,在$t(1\leq t\leq {10}^9)$时,温度要在$[l,r](-{10}^9 \leq l \leq r \leq {10}^9)$区间之内。
一开始时间为$0$,温度为$m(-{10}^9\leq m \leq {10}^9)$,问能否满足全部限制。
总共$q(1\leq q\leq 500)$组数据。

Solution

显然可以用区间乱搞。
设$L,R$表示当前可以到达的温度区间。
一开始$L=R=m$。
那么在接下来的时间可以到达$[L-(t_i-t_{i-1}),R-(t_i-t_{i-1})]$内任意一个温度,只要判断是否与$[l_i,r_i]$有相交即可。别忘记最后要更新区间呦~

Code

D. Shortest and Longest LIS

Describe

给出一个由$<$和$>$组成的序列,第$i$个表示$a_i$和$a_{i+1}$的大小关系,求出两个满足这个条件的序列,其中一个$LIS$最长,一个$LIS$最短,多组询问,询问的序列长度和不超过$2\times {10}^5$。
P.S:LIS是最长不下降子序列长度

Solution

构造题。
最长构造:


最短构造:

那么构造就好了

Code

E. 1-Trees and Queries

Describe

给定树,$q$此询问如果加入边$(a,b)$,$x$到$y$是否有长度为$k$的路径(不一定是简单路径)。

Solution

先$LCA$预处理,$logN$求任意两点间距离。
那么加入$(a,b)$边,$x$到$y$的路径只有$3$种情况:
– x–> y
– x–>a–>b–>y
– x–>b–>a–>y
所以乱搞就好了(注意可以走重复点所以直接%2即可)。

Code

F. Animal Observation

太难了不会qwq
挂个题解链接:戳这里

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇