本题要求两个 集合 中 "对称数" 匹配的最大值 ,有以上信息易知,我们把每个数看成一个点,给"对称数"间连上边,这道题立马就变成了 "二分图匹配" .

注意,由于题目要求 "不足的数高位补0" ,仅靠&的判断是不够的.一种简单的实现方法是把数拆开放进数组中,然后我们可以把数二进制每一位取出来,逐一判断.

#include <map>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <bitset>
#include <cstring>
#include <iostream>
#include <algorithm>

#define LL long long
#define INF (0x3f3f3f3f)
#define LINF (0x3f3f3f3f3f3f3f3fLL)
#define F(x,y,z) for(int x=y;x<=z;x++)
#define D(x,y,z) for(int x=z;x>=y;x--)

using namespace std;

int n, m, g[200+5], h[200+5], used[200+5], from[200+5];
vector<int> e[200+5];

bool Check (int x,int y)
{
    int a[200+5], b[200+5], c=0, d=0;
    memset(a, 0, sizeof(a));
    memset(b, 0, sizeof(b));
    while(x>0) 
    {
        a[++c]=x&1;
        x>>=1;
    }
    while(y>0) 
    {
        b[++d]=y&1;
        y>>=1;
    }   
    for(int i=1; i<=max(c, d); i++)
        if (a[i]==b[i]) return 0;
    return 1;    
} 

bool Hungary (int x) 
{
    int v;
    for(int i=0; i<e[x].size(); i++) 
    {
        v=e[x][i];
        if (!used[v])
        {
            used[v]=1;
            if (!from[v] || Hungary(from[v]))
            {
                from[v]=x;
                return 1;
            }
        }
    }
    return 0;
}

int main () 
{
    int ans=0;
    ios::sync_with_stdio(0);
    cin >> n >> m;
    for(int i=1; i<=n; i++) cin >> g[i];
    for(int i=1; i<=m; i++) cin >> h[i];
    for(int i=1; i<=n; i++) 
        for(int j=1; j<=m; j++) 
            if (Check(g[i], h[j])) e[i].push_back(j);   
    for(int i=1; i<=n; i++)
    {
        memset(used, 0, sizeof(used));
        if (Hungary(i)) ans++;  
    }    
    if (ans) cout << ans;
    else cout << "I want nobody nobody but you";
    return 0;
}

#include<cstdio>
#include<algorithm>
using namespace std;
bool edge[201][201];
bool vis[201];
int n,m; 
int M[201];
bool ok(int a, int b){
    int x = a ^ b;
    int p = 32 - __builtin_clz(x);
    return ((1 << p) == (1 + x));
}
bool dfs(int u){
    for(int j=1;j<=m;j++){
        if(edge[u][j]&&!vis[j]){
            vis[j]=true;
            if(!M[j]||dfs(M[j])){
                M[j]=u;
                return true;
            }
        }
    }
    return false;
}
int main(){
    int ans=0;
    unsigned int A[201],B[201];
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&A[i]);
    for(int i=1;i<=m;i++)scanf("%d",&B[i]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(ok(A[i],B[j])) edge[i][j]=true;
    for(int i=1;i<=n;i++){
        if(dfs(i))ans++;
    }
    if(ans)printf("%d",ans);else puts("I want nobody nobody but you");
}

#include<cstdio>
#include<algorithm>
using namespace std;
bool edge[201][201];
bool vis[201];
int n,m;
int M[201];
bool ok(int a, int b){
int x = a ^ b;
int p = 32 - __builtin_clz(x);
return ((1 << p) == (1 + x));
}
bool dfs(int u){
for(int j=1;j<=m;j++){
if(edge[u][j]&&!vis[j]){
vis[j]=true;
if(!M[j]||dfs(M[j])){
M[j]=u;
return true;
}
}
}
return false;
}
int main(){
int ans=0;
unsigned int A[201],B[201];
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&A[i]);
for(int i=1;i<=m;i++)scanf("%d",&B[i]);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(ok(A[i],B[j])) edge[i][j]=true;
for(int i=1;i<=n;i++){
if(dfs(i))ans++;
}
if(ans)printf("%d",ans);else puts("I want nobody nobody but you");
}

C++代码+题解
http://www.cnblogs.com/937337156Zhang/p/6047235.html

高质量代码

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

int n = 0, m = 0;
int A[201] = { 0 }, B[201] = { 0 };

bool Judge(int A, int B) {
int* pMax = (A > B) ? &A : &B;

while (*pMax > 0) {
int nLast_A = A & 1;
int nLast_B = B & 1;

if (nLast_A == nLast_B) return false;

if (A > 0) A >>= 1;
if (B > 0) B >>= 1;
}

return true;
}

int bLink[201][201] = { false };
int Is[201] = { false };
int nRight[201] = { 0 };
bool Find(int nLeft) {
for (int i = 1; i <= m; i++) {
if (bLink[nLeft][i] && !Is[i]) {
Is[i] = true;
if (nRight[i] == 0 || Find(nRight[i])) {
nRight[i] = nLeft;
return true;
}
}
}
return false;
}

int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &A[i]);
for (int i = 1; i <= m; i++) scanf("%d", &B[i]);

for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (Judge(A[i], B[j])) bLink[i][j] = true;
}
}

int ans = 0;
for (int i = 1; i <= n; i++) {
if (Find(i)) ans++;
memset(Is, false, sizeof(Is));
}

if (ans == 0) {
printf("I want nobody nobody but you\n");
}
else {
printf("%d\n", ans);
}

return 0;
}

#include<cstdio>
#include<cstring>
using namespace std;
int n,m;
int a[510];
int b[510];
bool judge(long long x)
{
x++;
for(long long i=1;i<=x;i=(i<<1))if(i==x)return 1;
return 0;
}
bool c[510][510];
bool used[510];
int l[510];
bool dfs(int x)
{

for(int i=1;i<=m;i++)
if(c[x][i]&&!used[i])
{
used[i]=true;
if(l[i]==-1||dfs(l[i]))
{
l[i]=x;
return true;
}
}
return false;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=m;i++)
scanf("%d",&b[i]);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(judge(a[i]+b[j]))
c[i][j]=true;

memset(l,-1,sizeof(l));
int ans=0;
for(int i=1;i<=n;i++)
{
memset(used,false,sizeof(used));
if(dfs(i))ans++;
}

if(ans)printf("%d\n",ans);
else printf("I want nobody nobody but you");
return 0;
}
我感到这世间深深的恶意

二分图匹配模板题
#include<cstdio>
const int maxv=0x7fffffff,maxn=200;
int n,m,x,ans,mat[maxn+10],A[maxn+10],B[maxn+10];
long long k;
bool p,a[maxn+10][maxn+10],used[maxn+10];
bool find(int x){
for (int i=1;i<=m;i++)
if ((a[x][i])&&(!used[i])){
used[i]=1;
if ((mat[i]==0)||(find(mat[i]))){
mat[i]=x;
return 1;
}
}
return 0;
}
int main(){
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
scanf("%d",&A[i]);
for (int i=1;i<=m;i++)
scanf("%d",&B[i]);
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++){
x=A[i]^B[j];
p=0;
for (k=1;k<=maxv;k=(k<<1)^1)
if ((k==x)&&(x==A[i]+B[j])){// if
p=1;
break;
}
if (p)
a[i][j]=1;
}
for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++)
used[j]=0;
if (find(i))
ans++;
}
if (ans)
printf("%d\n",ans);
else
printf("I want nobody nobody but you\n");
return 0;
}

最近智商捉鸡。。。二进制写错几次然后看了神犇的题解【其实貌似不用这么麻烦我只是顺便练模板
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <cstring>
#include <bitset>
using namespace std;

vector<int> G[1010];

int N, M;
int A[1010], B[1010];
int linker[1010];
bool vis[1010];

inline void in() {
int i;
scanf("%d%d", &N, &M);
for(i = 0;i < N;i ++) {
scanf("%d", &A[i]);
}
for(i = 0;i < M;i ++) {
scanf("%d", &B[i]);
}
}

inline bool ok(int a,int b) {
int x=a^b;
int p=32-__builtin_clz(x);
return ((1<<p)==(1+x));
}

inline void build() {
int i, j, k, l, m;
for(i = 0;i < N;i ++) {
for(j = 0;j < M;j ++) {
if(ok(A[i], B[j])) {
G[i].push_back(j + N + 1);
G[j + N + 1].push_back(i);
}
}
}
}

bool dfs(int x) {
int i;
for(i = 0;i < G[x].size();i ++) {
int v = G[x][i];
if(!vis[v]) {
vis[v] = 1;
if(linker[v] == -1 || dfs(linker[v])) {
linker[v] = x;
return 1;
}
}
}
return 0;
}

inline void solve() {
int ans = 0;
memset(linker, -1, sizeof(linker));
for(int i = 0;i < N;i ++) {
memset(vis, 0, sizeof(vis));
if(dfs(i)) ans ++;
}
cout << ans;
}

int main() {
//freopen("in.txt","r",stdin);
in();
build();
solve();
//while(1);
return 0;
}

P1693Miku_Nobody
Accepted

记录信息

评测状态 Accepted
题目 P1693 Miku_Nobody
递交时间 2015-07-09 00:26:42
代码语言 C++
评测机 VijosEx
消耗时间 45 ms
消耗内存 440 KiB
评测时间 2015-07-09 00:26:52

评测结果

编译成功

foo.cpp: In function 'bool check(int, int)':
foo.cpp:43:40: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
if( ( 1 << ( max( lena , lenb ) ) + 1 ) - 1 == ( a ^ b ) )
^

测试数据 #0: Accepted, time = 15 ms, mem = 436 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 440 KiB, score = 10

测试数据 #2: Accepted, time = 0 ms, mem = 436 KiB, score = 10

测试数据 #3: Accepted, time = 0 ms, mem = 436 KiB, score = 10

测试数据 #4: Accepted, time = 0 ms, mem = 440 KiB, score = 10

测试数据 #5: Accepted, time = 0 ms, mem = 440 KiB, score = 10

测试数据 #6: Accepted, time = 0 ms, mem = 440 KiB, score = 10

测试数据 #7: Accepted, time = 15 ms, mem = 440 KiB, score = 10

测试数据 #8: Accepted, time = 15 ms, mem = 440 KiB, score = 10

测试数据 #9: Accepted, time = 0 ms, mem = 440 KiB, score = 10

Accepted, time = 45 ms, mem = 440 KiB, score = 100

代码

#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

int n , m;
int a[200 + 2] , b[200 + 2];
int use[200 + 2];
int graph[200 + 2][200 + 2];
int match[200 + 2];
int i , j;
int ans;
int x , y;
int lena , lenb;

bool hungary( int x )
{
int i;
for( i = 1 ; i <= m ; i++ )
if( !use[i] && graph[x][i] )
{
use[i] = 1;
if( !match[i] || hungary( i ) )
{
match[i] = x;
return 1;
}
}
return 0;
}

bool check( int a , int b )
{
x = a;
y = b;
lena = 0;
lenb = 0;
while( ( x >>= 1 ) )
lena++;
while( ( y >>= 1 ) )
lenb++;
if( ( 1 << ( max( lena , lenb ) ) + 1 ) - 1 == ( a ^ b ) )
return 1;
return 0;
}

int main()
{
scanf( "%d %d" , &n , &m );
for( i = 1 ; i <= n ; i++ )
scanf( "%d" , &a[i] );
for( i = 1 ; i <= m ; i++ )
scanf( "%d" , &b[i] );
for( i = 1 ; i <= n ; i++ )
for( j = 1 ; j <= m ; j++ )
if( check( a[i] , b[j] ) )
graph[i][j] = 1;
for( i = 1 ; i <= n ; i++ )
{
memset( use , 0 , sizeof( use ) );
if( hungary( i ) )
ans++;
}
if( ans == 0 )
cout << "I want nobody nobody but you" << endl;
else
cout << ans << endl;
return 0;
}

xor

借用了986504542的判断方法， 但builtin_clz函数前有两个下划线啊 - -， 我还以为有什么头文件的... 二分图最大匹配， 不多说， 秒杀AK...

#include <iostream>

using namespace std;

int n, m;
int a[201], b[201], f[402][402];
int flag[402], match[402];

int dfs(int cur)
{
for (int i = 1; i <= m + n; i++)
{
if (f[cur][i] == 1 && flag[i] == 0)
{
flag[i] = 1;
if (match[i] == 0 || dfs(i))
{
match[i] = cur;
match[cur] = i;
return 1;
}
}
}

return 0;
}

bool ok(int a, int b)
{
int x = a ^ b;
int p = 32 - __builtin_clz(x);
return ((1 << p) == (1 + x));
}

int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int j = 1; j <= m; j++)
cin >> b[j];

for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (ok(a[i], b[j]))
f[i][j + n] = f[j + n][i] = 1;

int ans = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n + m; j++)
flag[j] = 0;

if (dfs(i))
ans++;
}

ans != 0 ? cout << ans << endl : cout << "I want nobody nobody but you" << endl;

return 0;
}

其实就是一道模拟题嘛。。
a[i]顶多对应一个b[j]，算是个特殊情况的二分图，但是完全没必要用最大匹配算法写。。
var
a,b:array[0..300]of int64;
i,j,m,n,ans:Longint;
k:int64;
begin
ans:=0;
read(n,m);
for i:=1 to n do read(a[i]);
for i:=1 to m do read(b[i]);
for i:=1 to n do
for j:=1 to m do
if (b[j]>0)then
begin
k:=a[i]xor b[j]+1;
if k=(k and (-k)) then
begin
inc(ans);
b[j]:=0;
break;
end;
end;
writeln(ans);
end.

匈牙利算法。
我是这样判对称音的。。C++里有__builtin_clz(x)表示x的二进制开头有多少个0：
bool ok(int a,int b)
{
int x=a^b;
int p=32-__builtin_clz(x);
return ((1<<p)==(1+x));
}

之前一直超时 交了10此后把二分判对称音改成对数就A了，（查了半天网络流 AC率啊！）
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 1188 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 1188 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 1188 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 1188 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 1188 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 1188 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 1188 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 1188 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 1188 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 1188 KiB, score = 10
Accepted, time = 15 ms, mem = 1188 KiB, score = 100
#include <stdio.h>
#include <math.h>
#include <algorithm>

using namespace std;

#define MAXN 500

int num[33];
int n,m;
int map[MAXN][MAXN];
int a[MAXN],b[MAXN];
int h[MAXN],gap[MAXN];

int Find(int x){
/* int l=0,r=32;
while (1){
int mid=(l+r)/2;
if (num[mid]==x) return num[mid+1]-1;
if (num[mid]>x) {
r=mid;
}
else {
l=mid;
}
if (l==r) return num[l+1]-1;
if (l==r-1&&num[l]<x&&num[r]>x) return num[r+1]-1;
}*/
return num[int(log10(x)/log10(2))+1]-1;
}

bool f;

int sap(int v,int flow){
if (h[n+m+1]>=n+m+2) return 0;
int rec=0,minh=n+m+1;
if (v==n+m+2){
f=true;
// system("pause");
return flow;
}
for (int i=0;i++<n+m+2;){
if (map[v][i]){
if (h[v]==h[i]+1){
int ret=sap(i,min(flow-rec,map[v][i]));
map[v][i]-=ret;
map[i][v]+=ret;
rec+=ret;
if (h[n+m+1]>=n+m+2) return rec;
if (rec==flow) return flow;
}
minh=min(minh,h[i]);
}
}
if (!(--gap[h[v]])){
h[n+m+1]=n+m+2;
return rec;
}
if (!f){
h[v]=minh+1;
}
gap[h[v]]++;
return rec;
}

int maxflow(){
int ans=0;
gap[0]=n+m+2;
while (h[n+m+1]<n+m+2){
f=false;
ans+=sap(n+m+1,0x7fffffff);
}
return ans;
}

int main(){
for (int i=0;i<MAXN;i++){
for (int j=0;j<MAXN;j++){
map[i][j]=0;
}
h[i]=gap[i]=0;
}
num[0]=1;
for (int i=1;i<33;i++) num[i]=num[i-1]*2;
scanf("%d%d",&n,&m);
for (int i=0;i++<n;){
scanf("%d",&a[i]);
map[n+m+1][i]=1;
}
for (int i=0;i++<m;){
scanf("%d",&b[i]);
map[n+i][n+m+2]=1;
}
for (int i=0;i++<n;){
for (int j=0;j++<m;){
if ((a[i]^b[j])==Find(max(a[i],b[j]))){
// printf("%d %d %d %d\n",i,j,a[i]^b[j],Find(max(a[i],b[j])));
map[i][n+j]=1;
}
}
}
printf("%d\n",maxflow());
// system("pause");
return 0;
}

这题出的...

原来中间变量超出了longint~

难怪TLE了一次~

位运算判断对音：

某牛给出了判断的必要不充分条件：

if x xor y=x+y then 是 else 不是；

给出反例:

4=100; 2=10;

4 xor 2=4+2 显然4 和2不是对音；

个人的方法：

if (x and y=0) and ((x xor y+1) and x=0) then 是 else 不是；

接下来就是 经典的Hungary 算法

当二分图匹配穿上位运算的外衣……

无语了

位运算求配位音：

function able(x,y:longint):boolean;

var

i,lx,ly,tx,ty:longint;

flag:boolean;

begin

lx:=trunc(ln((x+1))/ln(2));

ly:=trunc(ln((y+1))/ln(2));

if ly>lx then lx:=ly;

tx:=not x;

flag:=true;

for i:=1 to lx do

begin

if (y and 1)(tx and 1) then begin flag:=false; break; end;

y:=y shr 1;

tx:=tx shr 1;

end;

exit(flag);

end;

写的是挺丑 莫见怪……

二分图匹配~

http://hi.baidu.com/木子日匀/blog/item/3988d92f6ec72a5a4ec22601.html

裸的二分图匹配= =

唉 楼下的楼下的楼下 号被封了啊

哈哈