比赛就在这周末,这篇是比赛前最后一篇训练总结。
一个32位的数字,每个bytes包括8bit,所以一个整数是由4bytes组成; 现给出n个数字,问组成数字的bytes中,有多少个'a'。
Sample Input
3
97 24929 100
Sample Output
3
对于每个数字,用0x000000ff进行与操作,取出最后8位,然后与'a'判断,然后右移8位,知道数字为0即可;
一个盒子里有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的概率直接获胜,剩下的是均势;
有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个炸弹,有两种可能:主动引爆和被动引爆;
比较sum1和sum2,得出当前最优解。 但是, 中间WA了几次,发现这种策略无法保证正确性,于是换一种思路: 对于炸弹,我们分成几类:
容易知道,对于类型1,只需选择一个最小的引爆;类型2要选择引爆链的最前端(A->B->C);对于类型3,两个都要引爆; 最终做法: 按照炸弹的引爆范围建图,如果A能引爆B,那么连A到B的边; 遍历有向图,把强连通分量缩点; 最后把所有入度为0的点的cost相加即可得到答案;
给出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的问题;
在上面的基础上,改用搜索,直接枚举所有的可能。 添加一个剪枝:当目前搜的解无法比之前更优时返回;
(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个就无解。
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即可;
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,这样暴力算一遍即可;
喜欢简单点的生活,怕麻烦,懒; 也是怕失败,不太愿意坚持,不太愿意尝试。 总觉得自己年轻,实际上不久就到而立之年; 总是计较自己做的事情,是不是对以后有帮助,是好还是坏呢? 修养了半年多,明年可以一拼。