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}$,你的每次操作可以把一段区间里的数全部变成这个区间的平均数,求能得到的字典序最小的序列

CF1285D Dr. Evil Underscores

题目大意

你有一个数组${a_n}$,求一个数$x$ ,满足$\max{a_i \oplus x}$最小,输出这个最小值

CF1285E Delete a Segment

题目大意

你有$n$个区间$[l_i, r_i]$, 你要恰好删掉一个区间,使得剩下的$n-1$个区间的并的总和最多

eg. [1,2], [3,5], [3,7]的并是[1,2], [3,7]

斜率优化的练手题

通读题目可以发现
$$
f_i=\max (f_j+g(s[i]-s[j]))
$$

$$
其中f_i表示在i处强制结束一段的最大代价,s_i表示a_i的前缀和,g(x)表示(ax^2+bx+c)
$$

洛谷3959 [NOIP2017]宝藏

题目大意

给你$n$个点,$m$条边,要你选一个点作为根建一棵生成树满足代价最小

一棵生成树的代价是$\Sigma \; dep[i] * dis[fa_i][i]$, 其中$dep_i$表示$i$节点在这棵生成树中的深度(根节点深度为$0$,$dis[fa_i][i]$表示$i$节点到他父亲节点的距离

题目大意

给你$n,f_1,f_2,f_3,c$,让你求$f_n=c^{2n-6} \times f_{n-1} \times f_{n-2} \times f_{n-3}$

设$f_u$表示$u$不被以$u$为根的子树内点(包括$u$)通上电的概率,则有:

$$f_u=(1-p_u) \times \prod_{v \in subtree \; u}e(u, v) \times f_v$$

Your browser is out-of-date!

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

×