题解：CF159B Matchmaker

· · 题解

看见没有 01Trie 的，赶紧来交一篇。

题意简述

笔和笔盖分别有两个属性 x 和 y，y 相同的笔和笔盖可以组成配对，x 和 y 都相同的笔和笔盖可以组成优秀的配对。问最多有几个配对，几个优秀的配对。

思路

配对很简单，开两个桶，把不同东西的 y 分别统计一下，答案就是 \sum\min(b_1(i),b_2(i))。

优秀的配对虽然也可以开桶，但是如果数据范围再大一点就会爆空间。发现桶的大部分空间都被浪费，这个时候我们就可以用到 map 了。然而 map 常数略大，更好的选择是动态开点的字典树。对于每一个物品，我们把它的两个属性压进一个 int，然后扔进一个 01Trie，就能优美地统计优秀的配对了。

实现

动态开点字典树可以用数组模拟。

#include<cstdio>
#include<cstring>
using namespace std;

#define ll long long
#define ull unsigned long long
namespace io{
    const int size=(1<<20)+1;
    char buf[size],*p1=buf,*p2=buf;
    char buffer[size];
    int op1=-1;
    const int op2=size-1;

    inline char readchar() {
        if(p1!=p2) {
            return *p1++;
        }
        return p1==(p2=(p1=buf)+fread(buf,1,size-1,stdin))?EOF:*p1++;
    }

    inline void flush() {
        fwrite(buffer,1,op1+1,stdout),op1=-1;
    }

    inline void writechar(const char &x) {
        if(op1==op2) flush();
        buffer[++op1]=x;
    }
    #define gc readchar
    #define pc writechar
    #define el pc(10)
    #define sp pc(32)

    template<typename Tp>
    inline Tp read(){
        Tp x=0;
        bool w=0;
        char ch=gc();
        while(ch<'0'||ch>'9')ch=='-'&&(w=1),ch=gc();
        while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gc();
        return x;
    }

    template<typename Tp>
    void write(Tp x){
        if(x<0)pc('-'),x=-x;
        if(x>9)write(x/10);
        pc((x%10)^48);
    }
};
using namespace io;

struct node{
    int l,r,v,v2;
}t[2000005];
int tcnt;

struct node2{
    int v,v2;
}b[1005];

#define newnode (++tcnt)
#define s(x,y) ((x)<<10)|(y)

void add(int k,int v){
    if(!v){
        t[k].v++;
        return;
    }
    if(v&1){ // 1->r
        if(t[k].r) add(t[k].r,v>>1);
        else t[k].r=newnode,add(t[k].r,v>>1);
    }else{ // 0->l
        if(t[k].l) add(t[k].l,v>>1);
        else t[k].l=newnode,add(t[k].l,v>>1);
    }
}

void add2(int k,int v){
    if(!v){
        t[k].v2++;
        return;
    }
    if(v&1){ // 1->r
        if(t[k].r) add2(t[k].r,v>>1);
        else t[k].r=newnode,add2(t[k].r,v>>1);
    }else{ // 0->l
        if(t[k].l) add2(t[k].l,v>>1);
        else t[k].l=newnode,add2(t[k].l,v>>1);
    }
}

template<typename Tp>
inline const Tp& min(const Tp& x,const Tp& y){
    return x<y?x:y;
}

int main(){
    int n=read<int>(),m=read<int>();
    newnode;
    for(int i=1;i<=n;i++){
        int x,y;
        x=read<int>(),y=read<int>();
        add(1,s(x,y));
        b[y].v++;
    }

    for(int i=1;i<=m;i++){
        int x,y;
        x=read<int>(),y=read<int>();
        add2(1,s(x,y));
        b[y].v2++;
    }

    int cnt=0;
    for(int i=1;i<=1000;i++){
        cnt+=min(b[i].v,b[i].v2);
    }
    write(cnt);sp;

    cnt=0;
    for(int i=1;i<=2000000;i++){
        cnt+=min(t[i].v,t[i].v2);
    }
    write(cnt);el;

    flush();
    return 0;
}