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$，则输出所有的数)。

Codeforces 1238C Standard Free2play 题解

题意

有一个高为$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$的地方)。

Codeforces 1238D AB-string 题解

题意

一个字符串$s$如果 它的每一个字符都属于至少一个长度大于$1$的回文子串，那么称$s$是“好的”。如AABBB,ABAA,AAAAA是好的。

给定一个长度为$n (1\le n\le 3\cdot10^5)$的字符串$s$，求出$s$中好的子串的个数。

Codeforces 343C Read Time 题解

题意

在一个无限长的线性磁盘上，有$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)$的位置就被读取过了。

求读取所有需读取位置需要的最少时间。

Codeforces 343B Alternating Current 题解

题意

有两根长度为$n (1\le n\le 10^5)$个单位，两头固定的电线，它们缠绕在一起，给定一个长为$n$，由+和-组成的字符串$s$，其中

• 若$s_i$为+，则在第$i$个单位长度时，第一根电线在第二根电线上。

• 若$s_i$为-，则在第$i$个单位长度时，第二根电线在第一根电线上。

求不拔出电线且不移动装置时，是否能解开它们。若可以，输出Yes；否则输出No。

Codeforces 343A Rational Resistance 题解

题意

你有很多个电阻器，一个电阻器$R_0$的电阻是$1$。

设一个电阻元件的电阻为$R$，可以由以下三种方式得到一个电阻元件

• 一个电阻器，则$R=R_0$。
• 一个电阻元件(电阻为$R_e$)串联一个电阻器，则$R=R_e+R_0$。
• 一个电阻元件(电阻为$R_e$)并联一个电阻器，则$R=\frac{1}{\frac{1}{R_e}+\frac{1}{R_0}}$。

给定一个最简分数$\frac{a}{b} (1\le a,b\le 10^{18})$，求至少要多少个电阻器 使得 得到的电阻元件的电阻为$\frac{a}{b}$。

Codeforces 1228F One Node is Gone 题解

题意

给定$n (1\le n\le17)$，定义McDic’s generation为

1. 建一个有$2^n-1$个结点的满二叉树
2. 从这个二叉树中选择一个非根结点$v$
3. 把$v$从树中删除，从$v$的父亲到$v$的儿子连边，如果$v$没有儿子，那么就不连边。

现在给定一棵树，判断这棵树是否可以经过McDic’s generation一次得到。如果可以，输出被删除的结点的父亲。

Codeforces 609F Frogs and mosquitoes 题解

题意

有$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$只青蛙吃掉了多少蚊子和最后它的舌头有多长。

Codeforces 1119D Frets On Fire 题解

题意

给定$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]$，得到

$$\begin{matrix} f & \textbf{0} & \textbf{1} & \textbf{2} & \textbf{3} & \textbf{4} & \textbf{5} & \textbf{6} & \textbf{7} & \ldots \\ s_1: & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & \dots \\ s_2: & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & \dots \\ s_3: & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & \dots \\ s_4: & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & \dots \\ s_5: & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & \dots \\ s_6: & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & \dots \end{matrix}$$

再给定$q$个查询，每个查询有$L,R$，问第$L$列到第$R$列(以下表达为$[L,R]$)有多少个不同的数。

Codeforces 309B Context Advertising 题解

题意

给定$n,r,c$和一个由$n$个单词组成的句子(两两单词之间有一个空格)，在这个句子里选出若干个连续的单词，组成一个“矩阵”，行数不能超过$r$，每行字符数不能超过$c$(包括空格)，不能把一个单词拆开。求合法矩阵中，单词数最多的那个矩阵，并输出。