偷一张图

定义 $f_u$ 为：$\mathrm{tag}_u = 1$ 的概率。

定义 $g_u$ 为：$u$ 的祖先存在 $\mathrm{tag} = 1$ 的概率。

1. 白色： $g=g/2,f=f/2$
2. 橙色： $f=(g+f)/2$
3. 深灰： $g=(1+g)/2,f=(1+f)/2$
4. 浅灰： $g=(1+g)/2$
5. 黄色：（啥都不用干

¶ 翻译

¶ A. Contest for Robots

给出长度为 $1\le n\le 100$ 的两个序列 $r,b$，且满足 $r_i, b_i\in\{0, 1\}$，你需要确定 $p_i$（$p_i\ge 1$）。

满足 $\sum_{i=1}^n r_ip_i > \sum_{i=1}^n b_ip_i$，并且最小化 $\max_{i=1}^n{p_i}$ 。

如果不可能，输出 $-1$ 。

¶ B. Journey Planning

给出长度为 $1\le n\le 2\cdot 10^5$ 的序列 $b$，$1\le b_i\le 4\cdot 10^5$

称合法序列为，$c_1,\cdots,c_k$，满足 $c_i<c_{i+1}$ 和 $c_{i+1}-c_i = b_{c_{i+1}}-b_{c_i}$（$k=1$ 时也是合法的），定义其美丽值为 $\sum_{i=1}^k b_{c_i}$ 。

求最大美丽值。

¶ 2017

¶ 「雅礼集训 2017 Day1」市场

支持区间减，区间整除，区间最小查询，区间和查询。

线段树，考虑一个区间的最大值 $a$ 和最小值 $b$

若 $k=a-\lfloor a/d \rfloor = b-\lfloor b/d \rfloor$， 则对于 $a<c<b$ 有 $c-\lfloor c/d\rfloor=k$

事实上满足上述的只有 $a=b$ 或 $a=b+1$

证明可令 $a=\alpha k+p_1,b=\beta k+p_2$ 具体略

是道好题

可惜卡常数

感觉题目出得不是很难，部分分给得很足

sto God Song orz

Being teached again

又被 God Song 教育了

体验还是比较好的 230 只有 100 名差评，没有享受到大样例x

¶ 比赛实录

6:30：看 T1，这个博弈我好像推不出来SG，这是 ICG 吗？

滚去看 T2，理解题意 5min ，这个乘积怎么维护啊。。。

DP式子推推搞搞搞

给定一张 $n\le1000$ 个点、$m\le5000$ 条边的有向图

每个点都有一个权值 $f_i$ ，每条边都有一个权值 $t_i$

求图中的一个环，使“环上各点的权值之和”除以“环上各边的权值之和”最大

求多个矩形的面积并

沿 $x$ 轴扫描，用数据结构维护 $y$

这题用到的数据结构很有意思

但是这道题目存在一个特殊的性质：每个数不会减到负，所以问题就简单了

下面是线段树节点合并

1
2
3
4
5

// s 是当前节点
s.sum = s.t
    ? raw[s.r] - raw[s.l-1]
    : (s.l == s.r ? 0 : T[ls].sum + T[rs].sum);