首先题目给出结论,对于任意 \(n,m\) 均有解。
所以如果 \(A\) 中后 \(x\) 个数和 \(B\) 中前 \(x\) 个数两两配对,就可以转化为 \(n-x,m+x\) 的子问题。
所以对于 \(A\) 中最后一个数 \(n-1\),在 \(B\) 中至少存在一个数 \(x\) 使得 \(x\ \&\ (n-1) = n-1\)。我们只记录 \(B\) 中最小的 \(x\)。
关键结论:\(\forall k\in[0,x-m]\ ,\ (x-k)\ \&\ (n-1-k)=(n-1-k)\)。
说人话,就是将 \(A\) 后面这一段和 \(B\) 前面这一段按顺序两两配对一定是合法解。
理性分析如下,我们令 \(n-1\) 中为 \(1\) ,而 \(m\) 中为 \(0\) 的最高位为第 \(i\) 位,那么枚举 \(x\) 的过程就是将最低的 \(i\) 位一直加到后 \(i\) 位和 \(n-1\) 完全相同。那么再减回去也一定完全相同。
Code:
#include <bits/stdc++.h>
using namespace std;
int n, m;
int main() {
scanf("%d%d", &n, &m);
for (int i = n - 1, j = m; ~i; ) {
int k = j;
while ((k & i) != i) ++k;
for (int _ = 0; _ <= k - j; ++_) printf("%d %d\n", i--, k - _);
j = k + 1;
}
return 0;
}
原文地址:http://www.cnblogs.com/Kobe303/p/16849322.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性