CF605E Intergalaxy Trips

题目大意

有一个有$n$个点的有向完全图,每条边每天有一个开放几率$p[i][j]$,给定$p$,你需要求出从$1$到$n$的期望天数

$n \leq 10^3$

AGC035D Add and Remove

题目大意

有一个长度为$n$的序列${a_i}$,每次可以选择连续的$3$个数,把中间那个数加到左右两个数上后删除中间那个数。

求最后剩下的两个数的最小值。 $n \leq 18$

CF504E Misha and LCP on Tree

题目大意

给你一棵有$n$个节点的树,每个节点上有一个字符$c$。

有$m$次询问,每次询问$a\sim b$路径上的字符串和$c \sim d$路径上的字符串的最长公共前缀$\texttt{(LCP)}$

$n \leq 3 \times 10^5,m \leq 10^6$

AGC022E Median Replace

题目大意

你有一个长度为$n$的串$\texttt{S}$,其中有一些位置上的字符是?,其他的字符则是$0/1$之间的一种

每次可以进行一步操作:选择$3$个连续的字符,并把它们用它们的中位数替换

求有多少种把?替换成$0/1$的方案使得在进行$\frac{n-1}{2}$次操作后剩下的字符为$1$?

AGC034E Complete Compress

题目大意

有一棵有$n$个节点的树,每个节点上有$0/1$枚棋子,每次可以选择两个棋子并移动到它们的路径上的相邻节点(满足路径长度至少为$2$),求把所有棋子移到同一个节点的最小花费(无解输出$-1$)。

$n \leq 2 \times 10 ^ 3$

题目大意

你有一个序列${a_i}$,你要找出$k$个不相同的区间$[l_i,r_i]$,满足$\forall \; i, (r_i-l_i+1) \in [L, R]$,使得这些区间的和最大。

求这个最大值

CF1316D Nash Matrix

题目大意

有一个$n \times n$大小的棋盘,棋盘的每个格子上有一个字母(是U,L,R,D,X中之一),其中U表示向上走,D表示向下走,L表示向左走,R表示向右走,X表示走到这个格子就停止。

现在给你$n ^ 2$个坐标$(x_{i,j}, y_{i, j})$表示从$(i, j)$出发能走到的位置(如果无限循环则为$-1$),你需要构造出这个棋盘,或者输出INVALID,$n \leq 10^3$

CodeChef TANDEM

题目大意

我们定义一个字符串$s$为$\texttt{tandem}$当且仅当这个字符串能被表示三个相同的字符串$A$首尾相连的结果

对于一个字符串$s$的所有子串$s_{l \cdots r}$,如果它是一个$\texttt{tandem}$,则它是一个有趣的$\texttt{tandem}$当且仅当$s_l \not= s_{r+1}$,否则这就是一个无聊的$\texttt{tandem}$

现在,你需要统计有趣的和无聊的$\texttt{tandem}$的数量

洛谷4768 [NOI2018] 归程

题目大意

有一个$n$个点$m$条边的无向联通图, 每条边有两个属性:长度$d$,海拔$h$

有$q$个询问,每个询问给定两个数$v$, $p$,你要找到一个节点$u$,其中$u$要满足$v$到$u$存在一条路径使得这条路径上的边海拔全部大于$p$,求所有可能的$u$到$1$的最短路长度的最小值

CF1299C Water Balance

简要题意

你有一个序列${a}$,你的每次操作可以把一段区间里的数全部变成这个区间的平均数,求能得到的字典序最小的序列

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×