POJ2096 期望DP

题目传送门

简要题面:

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

NOIP2016换教室

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

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

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

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

C++读入优化的黑科技

输出优化

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

模板-缩点

传送门
把强连通分量缩成一个点,然后对DAG跑拓扑排序,处理出最大值。
其实是【模板】缩点+【模板】拓扑排序

模板--高斯消元

原题传送门
$A×X=B$,已知矩阵$A$,$B$,求矩阵$X$。
算法流程:

  1. 把A消成上三角矩阵
  2. 依次反代得到结果

luogu1262间谍网络

原题传送门

题目描述

由于外国间谍的大量渗入,国家安全正处于高度的危机之中。如果A间谍手中掌握着关于B间谍的犯罪证据,则称A可以揭发B。有些间谍收受贿赂,只要给他们一定数量的美元,他们就愿意交出手中掌握的全部情报。所以,如果我们能够收买一些间谍的话,我们就可能控制间谍网中的每一分子。因为一旦我们逮捕了一个间谍,他手中掌握的情报都将归我们所有,这样就有可能逮捕新的间谍,掌握新的情报。

模板---SPFA负环判定

原题传送门
题意:给定t个n点m边的图,分别判断图中有没有负环。
数据范围: N,M<=200000 ,t<=10

原题见UOJ78
有n位男生,m位女生,其中有一些男生和女生愿意结成配偶。
请问这个班级里最多产生多少对配偶?

匈牙利算法是一种用增广路求二分图最大匹配的算法。

Your browser is out-of-date!

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

×