CF86D-Powerful Array

简要题面

设一个序列的分值为每个数出现次数的平方乘这个数,给定一个长度为n序列,有m组询问$[l,r]$,求从第l个数到第r个数这个子序列的分值。

题目传送门

无源汇有上下界可行流问题。

设$in_i$表示至少流到i的流量,$out_i$表示至少从i流出的流量。

POJ2449 k短路问题

$A^\star$算法的经典应用—-k短路问题。

$A^\star$算法:设$f(x)=g(x)+h(x)$,其中$g(x)$表示已花费代价,$h(x)$表示预估还需代价($h(x)$要$\le h^\star(x)$)表示每次找到f值最小的拿出来扩展。

给定一个n点m边的有向图,求从s到t的k短路。

首先求出所有点x到t的最短路$dis[x]$,接下来用$dis[x]$作为$h(x)$跑 $A^\star$ ,因为 $h(x)\le h^\star(x)$ ,所以第k次找到t就是k短路。

NOIP2016 愤怒的小鸟

题目传送门

题解

状压DP。
将每一只猪打下来/没打下来用一个二进制位表示。
猪的数量不是很多,每一条抛物线至少要打到一只猪,所以可以枚举出所有可行的抛物线,这条抛物线对每一只猪能/不能打下来用一个二进制为表示。

luogu2396 yyy loves Maths VII

论卡(内存)常卡了一晚上不爽去抗议要求加大内存限制的悲哀2333

题目传送门

POJ1185 炮兵阵地

题目传送门

中文题面还是很清楚的。

不想解释题面了。

NOI原题确实是很难的。

POJ2096 期望DP

题目传送门

简要题面:

一个程序有n个子程序。有s种bug,每天能等概率随机在一个子程序中找到一个bug,如果一个子程序中的一种bug被找到了,再下一次这个子程序的这种bug被找到的概率依然不变。问期望至少需要多少天能在每个子程序中都至少找到一个bug,把每一种bug都最少找到一次。

NOIP2016换教室

题目传送门
md考场上xjb写完了暴力还™写错了,据说暴力分共76分啊,我却只有20分。

辞旧迎新之际,喜羊羊正在打理羊村的绿化带,然后他发现了一棵长着毒瘤的树。

这个长着毒瘤的树可以用 $n$ 个结点 $m$ 条无向边的无向图表示。这个图中有一些结点被称作是毒瘤结点,即删掉这个结点和与之相邻的边之后,这个图会变为一棵树。树也即无简单环的无向连通图。

现在给你这个无向图,喜羊羊请你帮他求出所有毒瘤结点。

C++读入优化的黑科技

输出优化

除了读入的黑科技以外,输出也有黑科技。
和fread对应,输出黑科技叫fwrite,就是把一整个字符串(快速地)写进输出文件。
也就是说在输出的时候,把输出的内容存进字符串,再用fwrite输出会很快(实验结果待填)

Your browser is out-of-date!

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

×