中国银行编程评测
11.17
第二批中国银行编程评测,一共5道编程题,2小时时间。前3道比较简单,后面两道有点绕,不过我全ac了。
我有印象的几道题:
😺给定n(1<=n<=1e9),问是否存在一对(x,y),满足(x^y)*y + (y^x)*x=n,1<=x,y<=1e9。
解答:让x=1,那么(x^y)*y + (y^x)*x=2y,即n为偶数时有解(1,n/2);而x和y取任意数,这个式子都是偶数,所以直接判断n是否为偶数就行了。
return (n&1) ? "No" : "Yes";
😺给定一个数组a, 长度为n,数组中每个元素范围是[0,n]。定义“好数对(i,j)”为:i*2<=j 且 i!=j 且 a[i] xor a[j]==0。求好数对的数量:
解答:a[i] xor a[j]==0 等价于a[i]==a[j]。从头往后枚举j,维护前j/2个元素各出现了几次即可,复杂度O(n)
😺给定两个排列a和b,长度为n(1<=n<=1e5)。可以交换a中相邻的两个元素。交换后,要让 sum abs(a[i]-b[i])最大,问最少交换几次。
解答:当n为偶数时,sum abs(a[i]-b[i])最大的情况,就是a里面1~n/2的所有元素都对应着b里面n/2+1~n的所有元素。所以让a数组里面<=n/2的给个0标签,>n/2的给个1标签,b数组同理,只需要让a交换后和b的标签对应就好了。计算要交换多少次,只需要计算a中0标签与b中0标签的各个距离之和即可,可以O(n)实现。
当n为奇数时,有个复杂的地方是,元素(n+1)/2既可以给0标签,也可以给1标签。因此就这两种情况都计算一下,取一个交换次数最小值即可。复杂度O(n).
#中国银行测评#
第二批中国银行编程评测,一共5道编程题,2小时时间。前3道比较简单,后面两道有点绕,不过我全ac了。
我有印象的几道题:
😺给定n(1<=n<=1e9),问是否存在一对(x,y),满足(x^y)*y + (y^x)*x=n,1<=x,y<=1e9。
解答:让x=1,那么(x^y)*y + (y^x)*x=2y,即n为偶数时有解(1,n/2);而x和y取任意数,这个式子都是偶数,所以直接判断n是否为偶数就行了。
return (n&1) ? "No" : "Yes";
😺给定一个数组a, 长度为n,数组中每个元素范围是[0,n]。定义“好数对(i,j)”为:i*2<=j 且 i!=j 且 a[i] xor a[j]==0。求好数对的数量:
解答:a[i] xor a[j]==0 等价于a[i]==a[j]。从头往后枚举j,维护前j/2个元素各出现了几次即可,复杂度O(n)
😺给定两个排列a和b,长度为n(1<=n<=1e5)。可以交换a中相邻的两个元素。交换后,要让 sum abs(a[i]-b[i])最大,问最少交换几次。
解答:当n为偶数时,sum abs(a[i]-b[i])最大的情况,就是a里面1~n/2的所有元素都对应着b里面n/2+1~n的所有元素。所以让a数组里面<=n/2的给个0标签,>n/2的给个1标签,b数组同理,只需要让a交换后和b的标签对应就好了。计算要交换多少次,只需要计算a中0标签与b中0标签的各个距离之和即可,可以O(n)实现。
当n为奇数时,有个复杂的地方是,元素(n+1)/2既可以给0标签,也可以给1标签。因此就这两种情况都计算一下,取一个交换次数最小值即可。复杂度O(n).
#中国银行测评#
全部评论
相关推荐
蛋炒饭i:我211目前投了300+还没找到 加油吧
点赞 评论 收藏
分享