BJOI2019 游记

提前占坑。记录第一次省(bao)选(ling)

一些 dp 的优化方式

简单总结了一下

Description

给定字符串 $s$ ,和每个位置上的权值 $a_i$。对于每一个 $i \in [0, n)$ 求出有多少对 $(i, j)$ 满足 $LCP(sa_i, sa_j) \ge i$ 以及在这些 $(i, j)$ 中 $a_i \times a_j$ 最大是多少。$sa_i$ 表示从 $i$ 开始的后缀。

Do geese see god?

Description

给一个字符串 $s$ 和一个整数 $k$ 。求所有最短的满足 $s$ 是他的一个子序列并且是一个回文串的字符串中字典序第 $k$ 大的。

CodeChef RIN

Description

你有 $m$ 个学期来完成 $n$ 个课程,每个学期能上任意多课程,每个课程恰好被学一遍。有些课程有前置条件,必须先学 $a$ 课程才能学 $b$ 课程。在第 $i$ 个学期完成第 $j$ 这个课程能够获得 $A[i][j]$ 的分数($A[i][j]=-1$ 说明 $i$ 学期不教授 $j$ 课程)。求最大的平均分数。

Description

给定一棵以 $1$ 为根的 $n$ 个节点的树,每条边有一个边权。有 $m$ 个叶子。将一条边的边权从 $x$ 修改至 $y$ 需要的代价是 $|x-y|$ 。求将所有叶子到根节点的距离修改成相同的最小代价。

HDU6203 ping ping ping

Description

给你一颗以 $0$ 为根的有根树。现在有些节点坏掉了,与周围无法联通。已知 $m$ 对 $(u,v)​$ 无法联通,求最少坏了几个节点。

BZOJ3143 「HNOI2013」游走

Description

$n$ 个点 $m$ 条边的无向连通图,在上面从 $1$ 号点开始随机游走。现在你可以给每条边从 $1$ 到 $m$ 编号作为分数(经过就得分)。求如何编号使得总分的期望最小。输出这个最小值即可。

$n \leq 500$

Description

有 $n$ 张卡牌,$r$ 局游戏,每张卡牌有 $p_i$ 的概率发动技能,如果发动会造成 $d_i​$ 的伤害。每局游戏从第一张卡牌开始开始一个个遍历,如果发动过技能则忽略继续;否则如果这张卡牌现在发动了,则结束回合;没有发动则继续。求造成的总伤害的期望。

BZOJ2134 单选错位

Description

$n$ 道题,第 $i$ 道题有 $a_i$ 个选项。求将正确答案全部右移一位(第 $n$ 题移到第 $1$ 题)之后期望对的题数

Your browser is out-of-date!

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

×