爱悠闲 > 分类 >

BZOJ 第8页

BZOJ 1002 FJOI2007 轮状病毒 递推+高精度
题目大意:轮状病毒基定义如图,求有多少n轮状病毒 这个递推实在是不会……所以我选择了打表找规律 首先运行以下程序 #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define M 110 using namespace std; struct abcd{ int to,next; bool b
BZOJ 1003 ZJOI2006 物流运输trans 动态规划+SPFA
题目大意:给定一个无向图,运输n天,其中有些天有些点不能走,更换路线代价为k,求代价总和 首先令cost[i][j]为第i天到第j天都走同一路线的最小花销 这个用SPFA处理 然后就是动规的问题了 令f[i]为1~i天的最小花销 则f[i]=min{ f[j]+cost[j+1][i]+k } ( 0<=j<i ) 注意m和n别写反 乘天数之前要特判是不是正无穷 #include<cstdio>
BZOJ 1004 HNOI2008 Cards Burnside引理
题目大意:给定n张卡牌和m个置换,求等价类个数 数据保证这m个置换加上自身置换后构成一个置换群 BZOJ坑爹0.0 这么重要的条件不给出来尼玛怎么做 Burnside引理……昨晚为了做这题硬啃了一晚上白书0.0 都快啃吐了0.0 Burnside引理:一个置换群下的等价类个数等于所有置换的不动点个数的平均值 没有接触过群论的建议去啃白书…… 网上的东西看不懂的 最后那个除法要用乘法逆元 我懒得写E
BZOJ 1005 明明的烦恼 Prufer序列+组合数学+高精度
题目大意:给定一棵n个节点的树的节点的度数,其中一些度数无限制,求可以生成多少种树 Prufer序列 把一棵树进行以下操作: 1.找到编号最小的叶节点,删除这个节点,然后与这个叶节点相连的点计入序列 2.反复进行1,直到这棵树只剩下两个节点时,退出 比如说这个图(来自度受百科) 最小叶节点为2,删除2,将3计入序列 最小叶节点为4,删除4,将5计入序列 最小叶节点为5,删除5,将1计入序列 最小叶
BZOJ 1006 HNOI2008 神奇的国度 弦图最小染色 MCS算法
题目大意:给定一个弦图,求最小染色 弦图相关问题,具体见陈丹琦09年讲稿《弦图与区间图》 PPT里有一个问题没说清楚 就是MCS算法的O(m+n)怎么来的 那个在 http://tieba.baidu.com/p/2891159900 有jcvb神犇详细的解答 至于染色如何标号,时间戳标记暴力硬扫即可 #include<cstdio> #include<cstring> #include<iost
BZOJ 1007 HNOI2008 水平可见直线 半平面交
题目大意:给定n条直线,求从上到下俯瞰能看到哪些直线 半平面交的裸题 首先将所有直线按照斜率排序,依次入栈 如果一条直线和栈顶的交点在栈顶直线和栈顶下面那条直线的交点的左侧,则删除栈顶 若多条直线斜率相同,只插入截距最大的那条直线 最后记录答案输出即可 #include<cmath> #include<cstdio> #include<cstring> #include<iostream> #in
BZOJ 1009 HNOI2008 GT考试 KMP算法+矩阵乘法
题目大意:给定长度为m的数字串s,求不包含子串s的长度为n的数字串的数量 n<=10^9 光看这个O(n)就是挂 我们不考虑这个 令f[i][j]为长度为i的数字串中最后j位与s中的前j位匹配的方案数 比如当s为12312时 f[i][3]表示长度为i,以123结尾且不包含子串”12312“的方案数 a[x][y]为f[i-1][x]转移至f[i][y]的方案数 换句话说(可能描述不清楚) a[x
BZOJ 1011 HNOI2008 遥远的行星 递推
题目大意:给定一条直线上的一些行星,按照题目要求计算,求每个点所受重力 我没有在标题上写”乱搞“的原因是我看了题解一堆说乱搞的0.0 然后我就真乱搞了0.0 每个点只计算临近的1000个,结果狂WA不止。。。 乱搞肯定过不去 不用想了 其实说是递推比较合适 详细题解见http://hi.baidu.com/zeonsgtr/item/789da6f2838a3dc742c36ab7 我不累述了 #
BZOJ 1013 JSOI2008 球形空间产生器sphere 高斯消元
题目大意:给定n维空间下的n+1个点,求这n个点所在的球面的球心 曾经尝试了很久的模拟退火0.0 至今仍未AC 0.0 今天挖粪涂墙怒学了高斯消元…… 我们设球心为X(x1,x2,...,xn) 假设有两点A(a1,a2,...,an)和B(b1,b2,...,bn) 那么我们可以得到两个方程 (x1-a1)^2+(x2-a2)^2+...+(xn-an)^2=r^2 (x1-b1)^2+(x2-
BZOJ 1016 JSOI2008 最小生成树计数 Kruskal
题目大意:给定一个无向图,求最小生成树的方案数 首先对于一个无向图的最小生成树,每种边权的边的数量是一定的 首先我们先跑一遍Kruskal,求出最小生成树上每种边权的出现次数 然后对于每种出现在最小生成树上的边权,我们从小到大处理 对于每种边权,我们枚举这种边权的边有多少种方案可以加进最小生成树上而不形成环 这个用状压处理 ans乘上这个值 然后把这种边权连接的所有联通块缩点 注意最小生成树不存在