HNOI

由题面可得： $$ E_j = \sum_{i = 1}^{j - 1} \frac{q_i}{(i - j)^2} - \sum_{i = j + 1}^{n} \frac{q_i}{(i - j)^2} $$ 令 $q_0 = 0$，并将没有意义的分式的值视为 $0$，则有： $$ E_j = ......

解析 传送门 一道简单的tarjan题 题意：在无向图中找一些点，这些点组成的的点集记为$V$ ，使得去掉任意一个点，剩下的每一个点都可以到达$V$中任意一个点，求点集$V$的大小的最小值及其方案数。 去掉一个点，很自然的联想到割点，那么考虑一下割点在不在备选集合中。 如图，显然可以看出，在割点上设 ......

[HNOI2008]玩具装箱 斜率优化入门题 显然有 $f[i]=\min{f[j]+(s[i]-s[j]+i-j-1-l)^2}$ 拆开可得 $f[j]+(s[j]+j)^2=f[i]+2(s[i]+i-1-l)(s[j]+j)$ 那么我们可以将决策看作是（$s[j]+j$，$f[j]+(s[j] ......

P3185 [HNOI2007]分裂游戏 题目描述 聪聪和睿睿最近迷上了一款叫做分裂的游戏。 该游戏的规则是： 共有 $n$ 个瓶子， 标号为 $0, 1, \ldots, n-1$，第 $i$ 个瓶子中装有 $p_i$ 颗巧克力豆，两个人轮流取豆子，每一轮每人选择 $3$ 个瓶子，标号为 $i,j ......

P3205 [HNOI2010]合唱队 区间DP——取一端 思: 根据题意我们发现，每次排队的时候，会出现两种情况 当前排入的人(即初始队列最后一人)比初始队列中前一个人矮，排到最左边 当前排入的人(同上)比初始队列中前一个人高，排到最右边 可从初始队列最后一人切入。 设置状态:$f[l][r][0 ......

CTT 2023 好吧，事实是时隔四个月我也不记得发生了啥。省流一下大概就是团建很有趣，yzc 长生不老。考试情况的话，D1 是历史最高排名！总榜排名寄得不成样子，为什么你们都那么猛啊？ WC 2023 听课随缘摆烂。 考试的话，拿到题都不会。结合之前的情况，感觉要 200+ 才够看。然后确定还是 ......

Day ??? 去中山集训回来了。 Day 0 没啥心情做题，上午随便写了点板子，然后扫描线写了一个小时调不出来，感觉不是很好。 下午听了下动员，听完之后心态确实好些了，虽然很久没做什么题，但是在考场上写满暴力不挂分似乎并不是很难达到的目标。 晚上到考场旁边订了个酒店，稍微思考了一下明天的策略，然后 ......

P3190 [HNOI2007]神奇游乐园 用$unordered_map$有个坑，写在了下面这个博客 https://www.luogu.com.cn/blog/zhouzhuo/gei-yong-unorderedmap-di-hou-ren-ti-gong-dai-ma 再贴一下代码吧 点击查 ......

题目分析： 对于这种某一个值很大另一个值很小的背包题，就是要求找特殊性质。 既然每一个 $w$ 都可以写成 $a \times 2^b$ 的性质，就可以对于每一个 $b$ 单独做背包，这样的复杂度并不高，这样就可以得到 $f_{i,j}$ 表示第 $i$ 位选择 $j$ 个的最大价值。 对于背包合并 ......