程序员进阶之算法练习（十三）
前言
比赛就在这周末，这篇是比赛前最后一篇训练总结。
正文
hdu 5980（简单题）
题目大意
一个32位的数字，每个bytes包括8bit，所以一个整数是由4bytes组成；
现给出n个数字，问组成数字的bytes中，有多少个'a'。
Sample Input
3
97 24929 100
Sample Output
3
题目解析
对于每个数字，用0x000000ff进行与操作，取出最后8位，然后与'a'判断，然后右移8位，知道数字为0即可；
hdu 5978（简单题）
题目大意
一个盒子里有k个红球，1个黑球，两个人轮流从盒子取球（不放回），取出红球者胜出；
现在给出k，要求：
输出0表示，先后手一样的胜率；
1表示，先手有优势；
2表示，后手有优势；
k = 10^5
Sample Input
1
2
Sample Output
0
1
题目解析
容易知道，
k=1的时候，先手优势；
k=2的时候，均势；
k=3的时候，先手优势；
k=4的时候，均势；
接着推导，
k=5的时候，又是先手优势；k=6的时候，还是均势；
猜想，根据奇偶性即可判断结果。
验证：
用sg函数来表示，sg[i]=0表示均势，sg[i]=1表示先手优势，sg[i]=2表示后手优势；
如果sg[i]=0，那么有sg[i+1]=1，因为k=i+1的时候，多了1/(i+1)的直接获胜概率；
如果sg[i]=1, 那么有sg[i+1]=0，因为k=i+1的时候，先手有1/k的概率直接获胜，后手有(k-1)/k * (1 / (k-1))=1/k的概率直接获胜，剩下的是均势；
hdu 5934
题目大意
有n个炸弹，给出炸弹的坐标(x[i], y[i]), 爆炸的范围r[i], 引爆的代价c[i];
（如果爆炸的范围内有炸弹，也会被引爆）
求n个炸弹引爆的最小代价；
n=1000
Sample Input
1
5
0 0 1 5
1 1 1 6
0 1 1 7
3 0 2 10
5 0 1 4
Sample Output
Case #1: 15
样例数据解释：
1 样例数量
5 n个炸弹
0 0 1 5 x[i], y[i], r[i], c[i]
题目解析
（你可能只需引爆部分炸弹，如果某些炸弹考得比较接近）
一开始用贪心，策略如下：
记录前i个引爆的最小代价，ans[k] = 1，表示第k个炸弹是主动引爆；
对于第i个炸弹，有两种可能：主动引爆和被动引爆；
- 主动引爆的最小代价：对于前面i-1个炸弹中ans[k]=1,且在i的爆炸范围内的炸弹，可以不引爆，算出i个炸弹的引爆最小代价sum1;
- 再看被动引爆的最小代价：从前面i-1个炸弹中，选择能引爆i，且代价最小的一个点，作为引爆i的点；然后把i能引爆的点优化掉，算出sum2；
比较sum1和sum2，得出当前最优解。
但是，
中间WA了几次，发现这种策略无法保证正确性，于是换一种思路：
对于炸弹，我们分成几类：
- 1、两两能相互引爆；
- 2、A能引爆B，B不能引爆A；
- 3、A和B是独立的；
容易知道，对于类型1，只需选择一个最小的引爆；类型2要选择引爆链的最前端（A->B->C）；对于类型3，两个都要引爆；
最终做法：
按照炸弹的引爆范围建图，如果A能引爆B，那么连A到B的边；
遍历有向图，把强连通分量缩点；
最后把所有入度为0的点的cost相加即可得到答案；
hdu 5937
题目大意
给出1~9，9个数字的数量；
从数字中，每次选3个数字组成a+b=c，只要有一个数字不同，视为不同的等式，每个数字只能用一次；
问最多组成多少个等式；
每个数字不超过100个。
input
1 1 1 1 1 1 1 1 1
output
2
解释：最多有 1+2=3， 和 4+5=9两种。
题目解析
总共有:
8种：1+1/2/3/4/5/6/7/8=2/3/4/5/6/7/8/9..
7种：2+1/2/..../7
..
到最后的
1种：8+1=9
总共有36种，其中1+2=3 和 2+1=3 是相同的；
于是有(36 - 4) / 2 + 4 = 20种； （4种是1+1, 2+2, 3+3, 4+4)
给20个等式编号；
dp[[i] 表示状态i，其中二进制位为1表示取该位数对应的等式；总共有2^20个状态；
状态转移:
如果i+(1<<k)合法，则有 dp[i+(1<<k)]=dp[i]+1;
ans = max(dp[i]);
复杂度:
O(2^20 * 20);
但是无法解决1+2=3 和 2+1=3的问题；
在上面的基础上，改用搜索，直接枚举所有的可能。
添加一个剪枝：当目前搜的解无法比之前更优时返回；
hdu 5943
题目大意
(s+1,s+2,⋯,s+n) n个数，放在1~n的位置上，第i个数字必须满足x[i] % i == 0.问能不能放。
例如：s=3, n=8
4 ~ 11 总共8个数，可以这么放：
1 2 3 4 5 6 7 8
11 10 9 4 5 6 7 8
s 和 n的范围是1e9。
题目解析
题目的数据很大，但是容易知道，对于区间[l, r]内地的素数，只能放在1上面，那么如果区间内存在两个素数，即无解，于是可以这么做：
重叠的部分可以对齐放；
不重叠的部分，如果存在2个质数，无解；
小于1000的部分，用匈牙利算法；
这部分是队友推出的结论，我就直接认为大于1000个就无解。
hdu 5971
题目大意
n个人，m个1对1的比赛，每次比赛都是goodPlayer vs badPlayer；
给出x个goodPlayer 和 y个badPlayer；
询问：
是否每个人在比赛中或者在给出的x、y内；
是，输出Yes；
否，输出No；
N (1 ≤ N≤ 1000)、M(1 ≤M ≤ 10000)、X,Y(X+Y≤N )
Sample Input
5 4 0 0
1 3
1 4
3 5
4 5
5 4 1 0
1 3
1 4
3 5
4 5
2
Sample Output
NO
YES
题目解析
题目意思不清楚，根据样例猜测：
首先希望每个人在比赛中合法，同时与给定的good、bad不冲突，最后每个人都在比赛中 或者 在制定的good、bad中；
于是可以这么做：
用vis[i] 来表示第i个人的状态：
vis[i] = 0 表示未知数；
vis[i] = 1 表示good；
vis[i] = -1 表示bad；
按照题目给出的x、y个人标志1和-1；然后按照这些人的比赛进行dfs；
然后再遍历n个人，如果这个人在比赛中，并且目前还未标志，给他随意标记为good，然后dfs；
最后看n个人是否全部vis[i] != 0即可；
hdu 5975
题目大意
n个数，q个操作。
给出一个通项公式：f(x) = lowbit(x)，然后给出操作：
1 l r ， 询问区间[l,r] 的区间和；（f[i]的和, i = l ~ r)
2 x, 询问树状数组中，修改x的需要修改几次值；
n≤1018,q≤105
题目解析
暴力推出解：
x 1 2 3 4 5 6 7 8 9 10 11 12
1 2 1 4 1 2 1 8 1 2 1 4
容易推出：
前n项和由1、2、4、8等组成，其中1的间隔是2，2的间隔4，4的间隔8，这样暴力算一遍即可；
总结
喜欢简单点的生活，怕麻烦，懒；
也是怕失败，不太愿意坚持，不太愿意尝试。
总觉得自己年轻，实际上不久就到而立之年；
总是计较自己做的事情，是不是对以后有帮助，是好还是坏呢？
修养了半年多，明年可以一拼。
