2025-11-24 11:01 已编辑 西南交通大学 算法工程师 发布于四川
关注
中国银行编程评测
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).
#中国银行测评#
全部评论
相关推荐
查看20道真题和解析 点赞 评论 收藏
分享
