首页 > 代码库 > 九度oj 题目1380:lucky number
九度oj 题目1380:lucky number
- 题目描述:
- 每个人有自己的lucky number,小A也一样。不过他的lucky number定义不一样。他认为一个序列中某些数出现的次数为n的话,都是他的lucky number。但是,现在这个序列很大,他无法快速找到所有lucky number。既然这样,他就想找到那些不是lucky number。
- 输入:
- 输入有两行.第一行有n和m。n表示出现次数为n的是lucky number,m表示序列的长度。2<=n<=10,m<=10^6,m%n!=0。第二行为序列元素,每个元素都是正整数。
- 输出:
- 输出那个不是lucky number的数。题目保证非lucky number只有一个。
- 样例输入:
2 51 1 2 2 3
- 样例输出:
3
发现许多重复几次的问题用位运算都是很好的办法,本题把每一个数转化为32位的二进制数
代码如下1 #include <cstdio> 2 #include <cstring> 3 4 int n, m; 5 int num; 6 int wnum[33]; 7 8 int main(int argc, char const *argv[]) 9 {10 while(scanf("%d %d",&n,&m) != EOF) {11 12 memset(wnum, 0, sizeof(wnum));13 int t = m % n;14 while(m--){15 scanf("%d",&num);16 for(int j = 0; j < 32; j++) {17 int p = num&1;18 wnum[j] = wnum[j] + p;19 num = num >> 1;20 }21 }22 for(int j = 0; j < 32; j++) {23 wnum[j] = wnum[j] % n;24 }25 26 int ans = 0;27 28 for(int j = 31; j >= 0; j--) {29 ans = ans * 2 + wnum[j]/t;30 }31 printf("%d\n",ans);32 }33 return 0;34 }
比如
2 5
1 1 2 2 3
结果是3
编码得到
00000001
00000001
00000010
00000010
00000011(因为数字比较小,省略了前面3位即24个0)
求和 00000033
取余 00000011
出现了m%n = 1次
结果为3
另外,设那个不为lucky_number的数为x,有
x % n = sum%n = y
m%n *x +sum(others) = sum不知道由这两点能不能启发出更好的办法
九度oj 题目1380:lucky number
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。