Codeforces 587C Duff in the Army 题解
题意
给定一棵有$n$个结点的树,某些结点上有一些数,总共有$m$个数,有$q (1\le n,m,k\le 10^5)$次询问。
每次询问给定$u,v,a (1\le u,v\le n,1\le a\le10)$,求出 在$u$到$v$的路径上所有的结点上的数中,前$a$小的数(如果总数小于$a$,则输出所有的数)。
Kaysman Official Website
给定一棵有$n$个结点的树,某些结点上有一些数,总共有$m$个数,有$q (1\le n,m,k\le 10^5)$次询问。
每次询问给定$u,v,a (1\le u,v\le n,1\le a\le10)$,求出 在$u$到$v$的路径上所有的结点上的数中,前$a$小的数(如果总数小于$a$,则输出所有的数)。
有一个高为$h (1\le h\le10^9)$的悬崖,在高度为$x(1\le x\le h)$的位置上,有一个可移动的平台。
每个平台有两种状态:隐藏在悬崖里 或 在悬崖外。一开始,有$n (1\le n\le\min(h,2\cdot10^5))$个在悬崖外的平台,分别为$p_1,p_2,\dots,p_n$,其中$p_1=h$。
你一开始站在$p_1$上,即在悬崖最高点$h$。若你站在高度为$x$的地方(高度为$x$的平台必须在悬崖外),你可以按下一个按钮。如果你按下了按钮,那么高度为$x$和$x-1$的平台的状态会改变,即高度为$x$的平台隐藏到悬崖里,若高度为$x-1$的平台在悬崖里,则它移动到悬崖外;若它在悬崖外,则隐藏到悬崖里。如果按下按钮后,高度为$x-1$的平台在悬崖外,那么你安全地落在高度为$x-1$的平台上(否则你会掉落在下一个在悬崖外的平台上)。这是唯一一种方式从一个平台移动到另外一个平台。
你可以安全地从$x$掉落到$x-2$,但是如果从$x$掉落在$x-3$或更低处,你就死了。
你可以使用魔法。一次魔法只能使在任何高度的平台改变状态(除了高度为$h$的平台)。
求你使用魔法的最小次数,使得你安全地落在地上(即高度为$0$的地方)。
一个字符串$s$如果 它的每一个字符都属于至少一个长度大于$1$的回文子串,那么称$s$是“好的”。如AABBB
,ABAA
,AAAAA
是好的。
给定一个长度为$n (1\le n\le 3\cdot10^5)$的字符串$s$,求出$s$中好的子串的个数。
在一个无限长的线性磁盘上,有$n$个独立的磁头和$m$个需读取的位置$(1\le n,m\le 10^5)$,第$i$个磁头的初始位置为$h_i (1\le h_i\le 10^{10},h_i<h_{i+1})$,第$j$个需读取位置为$p_j (1\le p_j\le 10^{10},p_j<p_{j+1})$,需读取的位置互不相同的。
每一个磁头可以花一个单位时间移动到左边或右边的位置,也可以不动。可以有多个磁头在同一位置。每个磁头可以读取无限多个位置。一个位置被至少一个磁头走过后,它就被读取了。特别,一开始时,$h_i (1\le i\le n)$的位置就被读取过了。
求读取所有需读取位置需要的最少时间。
有两根长度为$n (1\le n\le 10^5)$个单位,两头固定的电线,它们缠绕在一起,给定一个长为$n$,由+
和-
组成的字符串$s$,其中
若$s_i$为+
,则在第$i$个单位长度时,第一根电线在第二根电线上。
若$s_i$为-
,则在第$i$个单位长度时,第二根电线在第一根电线上。
求不拔出电线且不移动装置时,是否能解开它们。若可以,输出Yes
;否则输出No
。
你有很多个电阻器,一个电阻器$R_0$的电阻是$1$。
设一个电阻元件的电阻为$R$,可以由以下三种方式得到一个电阻元件
给定一个最简分数$\frac{a}{b} (1\le a,b\le 10^{18})$,求至少要多少个电阻器 使得 得到的电阻元件的电阻为$\frac{a}{b}$。
给定$n (1\le n\le17)$,定义McDic’s generation为
现在给定一棵树,判断这棵树是否可以经过McDic’s generation一次得到。如果可以,输出被删除的结点的父亲。
有$n (1\le n\le 2\cdot10^5)$个青蛙固定在平面直角坐标系中$Ox$的非负半轴上,对于第$i (1\le i\le n)$个青蛙有两个值,分别是$x_i$和$t_i (0\le x_i,t_i\le 10^9)$($x_i$两两不同),$x_i$代表它的位置,$t_i$代表它的舌头的长度。
有$m (1\le m\le 2\cdot10^5)$只蚊子也固定在$Ox$的非负半轴上,对于第$i (1\le i\le m)$只蚊子有两个值,分别是$p_i$和$b_i (0\le p_i,b_i\le 10^9)$,$p_i$代表它的位置,$b_i$代表它的大小。
如果一个青蛙$i$和一只蚊子$j$,满足 $p_j$在区间$[x_i,x_i+t_i]$内,那么青蛙$i$就可以吃掉蚊子$j$,并且舌头会增长$b_j$。如果有多个青蛙可以吃掉同一个蚊子,那么这个蚊子会被$x_i$最小的那个青蛙吃掉。
蚊子是按照输入的顺序降临的,如果第$i$个蚊子要降临,必须满足 青蛙吃光了可能吃掉的所有蚊子$j (1\le j<i)$。
问第$i$只青蛙吃掉了多少蚊子和最后它的舌头有多长。
给定$n$和$s_1,s_2,\dots,s_n$,由此得到一个$n\times(10^{18}+1)$的矩阵$f$,其中$f_{i,j}=s_i+j (1\le i\le n,0\le j\le 10^{18})$。
在样例$1$中,给定$n=6,s=[3,1,4,1,5,9]$,得到
再给定$q$个查询,每个查询有$L,R$,问第$L$列到第$R$列(以下表达为$[L,R]$)有多少个不同的数。
给定$n,r,c$和一个由$n$个单词组成的句子(两两单词之间有一个空格),在这个句子里选出若干个连续的单词,组成一个“矩阵”,行数不能超过$r$,每行字符数不能超过$c$(包括空格),不能把一个单词拆开。求合法矩阵中,单词数最多的那个矩阵,并输出。