题解

34 条题解

  • 0
    @ 2017-10-11 15:41:53

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

    注意,由于题目要求 "不足的数高位补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;
    }
    
    
    
    
    
    
  • 0
    @ 2017-08-26 17:06:26
    #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");
    }
    
  • 0
    @ 2017-08-26 17:05:54

    #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");
    }

  • 0
    @ 2016-10-21 10:09:14

    高质量代码

    #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;
    }

  • 0
    @ 2015-11-25 21:05:37

    #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;
    }
    我感到这世间深深的恶意

  • 0
    @ 2015-11-08 00:10:13

    二分图匹配模板题
    #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;
    }

  • 0
    @ 2015-10-18 20:11:24

    最近智商捉鸡。。。二进制写错几次然后看了神犇的题解【其实貌似不用这么麻烦我只是顺便练模板
    #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;
    }

  • 0
    @ 2015-07-09 00:27:27

    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

  • 0
    @ 2014-07-17 22:53:20

    借用了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;
    }

  • 0
    @ 2013-12-11 23:28:20

    其实就是一道模拟题嘛。。
    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.

  • 0
    @ 2013-07-28 19:53:47

    匈牙利算法。
    我是这样判对称音的。。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));
    }

  • 0
    @ 2013-05-12 10:09:31

    之前一直超时 交了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;
    }

    • @ 2013-05-12 10:10:41

      终于0了
      编译成功

      测试数据 #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 = 0 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 = 0 ms, mem = 1188 KiB, score = 100

  • 0
    @ 2009-11-14 12:12:44

    这题出的...

  • 0
    @ 2009-11-14 10:35:35

    原来中间变量超出了longint~

    难怪TLE了一次~

  • 0
    @ 2009-11-14 09:47:57

    位运算判断对音:

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

    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 算法

  • 0
    @ 2009-11-13 17:35:12

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

    无语了

    位运算求配位音:

    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;

    写的是挺丑 莫见怪……

  • 0
    @ 2009-11-13 17:11:28

    裸的二分图匹配= =

  • 0
    @ 2009-11-13 17:01:26

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

    哈哈

信息

ID
1693
难度
7
分类
图结构 | 二分图匹配 点击显示
标签
递交数
2045
已通过
350
通过率
17%
上传者