hdoj 4336 http://acm.hdu.edu.cn/showproblem.php?pid=4336 这是一道关于概率与期望的问题,其中   期望 =  1 / 概率 容斥原理  P =  - p1Up2    +     p1Up2Up3     +    p1U....p2*x+1    -   p1U....p2*x   (即  奇加 偶减) 关于二进制枚举:两层 for 循环 , 第一层用来枚举集合(一共 1 << x   (即 2^x)个集合),第二层用来枚举集合内的元素

HDU.1796 How many integers can you find ( 组合数学 容斥原理 二进制枚举) 题意分析 求在[1,n-1]中,m个整数的倍数共有多少个 与 UVA.10325 The Lottery 一模一样. 前置技能和其一样,但是需要注意的有一下几点: 1. m个数字中可能有0 2. 要用long long 代码总览 #include <cstdio> #include <algorithm> #include <cstring> #incl

UVA.11806 Cheerleaders (组合数学 容斥原理 二进制枚举) 题意分析 给出n*m的矩形格子,给出k个点,每个格子里面可以放一个点.现在要求格子的最外围一圈的每行每列,至少要放一个点,并且放在角上的点,同时算那个角所在的行和所在的列.不允许剩下点,求总共的方案数量,结果对1000007取模. 数据范围2 ≤ M,N ≤ 20,K ≤ 500. 考虑到要求组合数目,首先就需要预处理500以内的组合数.正向求解可能有些困难,这样考虑: 不管三七二十一,先求解出所有情况的总和,即C

题意:平面上有n个点(1<=N<=1000),你的任务是让所有n个点连通,为此, 你可以新建一些边,费用等于两个端点的欧几里得距离的平方.另外还有q(0<=q<=8)个套餐(数量小,可枚举),可以购买,如果你购买了第i个套餐,该套餐 中的所有结点将变得相互连通,第i个套餐的花费为ci. 分析:按照刘汝佳的思路做的.首先求一次本身的最小生成树值,然后枚举购买的套餐(二进制枚举),每次购买了之后,将其权值设为0,并且加进最小生成树. #include<cstdio> #in

B. New Year and Old Property time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output The year 2015 is almost over. Limak is a little polar bear. He has recently learnt about the binary system. He

题目链接:http://poj.org/problem?id=2784 Buy or Build Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 1528   Accepted: 592 Description World Wide Networks (WWN) is a leading company that operates large telecommunication networks. WWN would li

题意:给出n头牛的得病的种类情况,一共有m种病,要求找出最多有K种病的牛的数目: 思路:二进制枚举(得病处为1,否则为0,比如得了2 1两种病,代号就是011(十进制就是3)),首先枚举出1的个数等于k的二进制数,然后跟所有的牛的代号一一比较,符合的   +1,找出其中和最大的:就是转换2进制麻烦,用位运算就好实现了,但是位运算不是很明白含义,明白了再补充: 知识点: 3 & 2 = 2,相同为1,不同为0, 011 & 010 = 010:(怎么利用的这个特点不明白),在计算机网络中也学

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3118 思路:题目要求是去掉最少的边使得图中不存在路径长度为奇数的环,这个问题等价于在图中去掉若干条边,使得这个图成为二分图.注意到n不是很大,于是我们可以想到二进制枚举,枚举每条边的两个顶点是否在同一个集合中,若是,则删除这条边. #include<iostream> #include<cstdio> #include<cstring> #include<algori

3A的题目,第一次TLE,是因为一次BFS起点到终点状态太多爆掉了时间. 第二次WA,是因为没有枚举蛇的状态. 解体思路: 因为蛇的数目是小于5只的,那就首先枚举是否杀死每只蛇即可. 然后多次BFS,先从起点到第一把钥匙,不能往回走,要用VIS数组标记. 第二次从第一把钥匙走到第二把钥匙. 最后一次从最后一把钥匙走到终点即可. Tips 1: 在每次BFS过程中使用优先队列保证每次是最小步长的状态. Tips2 :使用二进制枚举蛇的状态 Tips3:首先使用DFS判断是否绝对有解,如果无解输出"

题目链接:http://acm.nyist.edu.cn/JudgeOnline/problem.php?pid=91 题目大意: 给你一个非负数整数n,判断n是不是一些数(这些数不允许重复使用,且为正数)的阶乘之和,如9=1!+2!+3!,如果是,则输出Yes,否则输出No:n<1000000; 思路: 数据量小,直接预处理出所有满足的数,然后直接判断就行了,预处理时用了二进制枚举子集的方式来处理 #include<iostream> #include<cstdio> #i

某君有 n个互不相同的正整数,现在他要从这 n 个正整数之中无重复地选取任意个数,并仅通过加法凑出整数 X.求某君有多少种不同的方案来凑出整数 X. 输入格式 第一行,输入两个整数 n,X(1≤n≤20,1≤X≤2000),X(1≤n≤20,1≤X≤2000). 接下来输入 n 个整数,每个整数不超过 100. 输出格式 输出一个整数,表示能凑出 X 的方案数. 样例输入 6 6 1 2 3 4 5 6 样例输出 4关于二进制枚举的最通俗易懂的讲解:https://www.cnblogs.com

Disease Manangement 疾病管理 Description Alas! A set of D (1 <= D <= 15) diseases (numbered 1..D) is running through the farm. Farmer John would like to milk as many of his N (1 <= N <= 1,000) cows as possible. If the milked cows carry more than K

Problem UVA12113-Overlapping Squares Accept:116  Submit:596 Time Limit: 3000 mSec  Problem Description  Input The input consists of several test cases. Each test case is contained in five lines and each line contains nine characters. If the horizontal

Problem UVA1354-Mobile Computing Accept:267  Submit:2232 Time Limit: 3000 mSec  Problem Description  Input  Output  Sample Input 5 1.3 3 1 2 1 1.4 3 1 2 1 2.0 3 1 2 1 1.59 4 2 1 1 3 1.7143 4 1 2 3 5    Sample Ouput -1 1.3333333333333335 1.66666666666

题目链接:http://poj.org/problem?id=3279 题目大意: 有一个m*n的棋盘(1 ≤ M ≤ 15; 1 ≤ N ≤ 15),每个格子有两面分别是0或1,每次可以对一个格子做一次翻转操作,将被操作的格子和与其相邻的周围4个格子都会进行翻转.问做少做多少次翻转可以将所有格子翻转成0,输出翻转方案(每个棋子的翻转次数).没有方案时输出“IMPOSSIBLE”. Sample Input 4 4 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 Sample O

<题目链接> <转载于 >>> > 题目大意: 给定一个M*N矩阵,有些是黑色(1表示)否则白色(0表示),每翻转一个(i,j),会使得它和它周围4个格变为另一个颜色,要求翻转最少的点,使得变为全白色的矩阵,输出这个标记了翻转点的矩阵,如果有多个最优解,输出字典序最小的那个矩阵,若没有解,输出IMPOSSIBLE. 解题分析: 由于一个点翻转两次则返回原来的状态,所以最优解每个点最多翻转一次,但是2^(M*N)过大,所以2^N枚举第一行的所有翻转方式(逆字典序枚举

http://acm.hdu.edu.cn/showproblem.php?pid=4309 题意: 有n个城市,每个城市有num[i]个居民,有敌人要进行地毯式轰击,居民们要逃到隧道去.现在有隧道,隧道允许无限个人通过,并且可以容纳w个人:有桥,可以允许无限个人通过,但是不能容纳人:还有一些破桥,修复这些破桥需要w花费,如果不修复,那么最多只能通过一人,如果修复了,那么可以通过无限个人.求出在能安全到达隧道的最大人数时的最小代价.(上述都是单向边) 思路:出题人也是有心了..在题目中有说破桥的

时间限制:1000ms 单点时限:1000ms 内存限制:256MB 描述 Lara Croft, the fiercely independent daughter of a missing adventurer, must push herself beyond her limits when she discovers the island where her father disappeared. In this mysterious island, Lara finds a tomb

时间限制1 Second 内存限制 512 Mb 题目描述 你有n个问题,你已经估计了第i个问题的难度为Ci,现在你想使用这些问题去构造一个问题集.比赛的问题集必须包含至少两个问题,而且比赛的总难度必须至少为l至多为r,此外最简单的问题和最难的问题之间的差异至少为x请您找出能够选择的问题集的数量. 输入 第一行有T组输入(1 ≤ T ≤ 10接下来一行输入n, l, r, x (1 ≤ n ≤ 10, 1 ≤ l ≤ r ≤ 1e9, 1 ≤ x ≤ 1e6)然后输入n个正整数 c1, c2,

https://vjudge.net/problem/UVA-818 题意:有n个圆环,其中有一些已经扣在了一起.现在需要打开尽量少的圆环,使得所有圆环可以组成一条链,例如,有5个圆环,1-2,2-3,4-5,则需要打开一个圆环,如圆环4,然   后用它穿过圆环3和圆环5后再次闭合4,就可以形成一条链:1-2-3-4-5. 思路:从n个圆环中任意选择圆环,这就是枚举子集.所以这道题目可以用二进制枚举来做. 那么如何判断当前打开圆环是可行的呢?在去除打开的圆环后需要判断: ①:每个圆环的分支数都必