C_SUNSHINE's Blog

只想看代码的直接翻到最下面

---

BZOJ4008: [HNOI2015]亚瑟王

• 显然$ans=pr_i*d_i，pr_i是第i张牌使用的概率$
• 于是设$f_{i,j}表示还剩j轮第i个的概率，转移也很简单，直接dp就过了$
• 时间复杂度$O(nr)$

---

BZOJ4009: [HNOI2015]接水果

• 整体二分，问题变成了刚开始给出p条路径，询问p路径有多少条路径是给定路径的子路径。
• 转dfs序，考虑p中的一条路径$u \rightarrow v，设dep_u\leq dep_v$

Read on →

---

BZOJ 4026: dC Loves Number Theory

---

可以先看看wzf的题解学习一下如何做人

Read on →

---

BZOJ 4025: 二分图

Solution

• 离线动态图有个经典做法，对时间轴分治+可持久化并查集，时间复杂度$O(nlog^2n)$，然而本题并不能过。

• 本题可以采用xyz在WC2015讲的维护删除时间最大生成树的方法。

• 由于要判断是否为二分图，我们统计有多少条边满足：在这条边被删除之前图一定不是二分图

Read on →

只想看代码的直接翻到最下面

---

BZOJ4002: [JLOI2015]有意义的字符串

膜PoPoQQQ的题解

---

BZOJ4003: [JLOI2015]城池攻占

注意到任意时刻在一起的每个骑士的攻击力相对大小不发生改变，于是用可并堆维护最小值，每次把儿子并到父亲上就可以了，使用可以打标记的左偏树实现。

Read on →

只想看代码的直接翻到最下面

---

BZOJ3996: [TJOI2015]线性代数

一眼最小割，首先计算出答案

$$ans=\left ( \sum_{i=1}^{n}\sum_{i=1}^{n}A_iA_jB_{j,i}\right )-\sum_{i=1}^{n}A_iC_i$$

然后对于所有i<j，连边$<S,i,B_{i,j}+B_{j,i}>,<S,j,B_{i,j}+B_{j,i}>,<i,j,B_{i,j}+B_{j,i}>,<j,i,B_{i,j}+B_{j,i}>$

对于所有i，连边：$<i,T,C_i*2>$

做最小割得到c，则$ans=\left ( \sum B_{i,j} \right )-\frac{c}{2}$

Read on →

Hi, This a demo post of Logdown.

Logdown use Markdown as main syntax, you can find more example by reading this document on Wikipedia

Logdown also support drag & drop image uploading. The picture syntax is like this:

Read on →