2015 ACM-ICPC 沈阳区域赛 I:Triple


题目链接:2015 ACM-ICPC 沈阳区域赛 I:Triple


Description
给定一个N个元素的二元组集合A和M个元素的三元组集合B。
定义:C=A∗B={⟨a,c,d⟩∣⟨a,b⟩∈A, ⟨c,d,e⟩∈B and b=e}​
BETTERC(⟨a,b,c⟩)={⟨u,v,w⟩∈C∣⟨u,v,w⟩≠⟨a,b,c⟩, u≥a, v≥b, w≥c},
TOP(C)={⟨a,b,c⟩∈C∣BETTERC(⟨a,b,c⟩)=∅}
求TOP(C)集合的大小
1≤n,m,ai,bi,ei≤10^5, 1≤ci,di≤10^3


Sample Input
2
5 9
1 1 2 2 3 3 3 3 4 2
1 4 1 2 2 1 4 1 1 1 3 2 3 2 2 4 1 2 2 4 3 3 2 3 4 1 3
3 4
2 7 2 7 2 7
1 4 7 2 3 7 3 2 7 4 1 7


Sample Output
Case #1: 5
Case #2: 12


Solution
有可能最优且本质不同的三元组C只有不超过M个,所以先处理二元组集合A,对于每个元素(a,b),我们只保留b相同中的a最大的,然后直接预处理出可能的TOP(C)集合。
注意到1≤ci,di≤10^3,这提示我们可以先按a排序,然后对c,d用二维树状数组统计答案。
%%%pps


Code

#include<map>
#include<set>
#include<list>
#include<queue>
#include<vector>
#include<string>
#include<time.h>
#include<math.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#define Judge
#define Online
#define maxm 1100
#define maxn 100100
#define reg register
#define ll long long
#define mod 1000000007
#define inf 2147483647
#define lowbit(x) ((x)&-(x))
#define abs(x) ((x)<0?-(x):(x))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define isd(c) ('0'<=(c)&&(c)<='9')
#define isa(c) ('a'<=(c)&&(c)<='z')
#define isA(c) ('A'<=(c)&&(c)<='Z')
#define ckmax(a,b) ((a)=max((a),(b)))
#define ckmin(a,b) ((a)=min((a),(b)))
using namespace std;
#ifdef Judge
#define puts io.put
#define getchar io.gc
#define putchar io.wchar
#ifdef Online
FILE*in=stdin;
FILE*out=stdout;
#else
FILE*in=fopen(".in","r+");
FILE*out=fopen(".out","w+");
#endif
struct FastIO{
    #define S 1000000
    int wpos,len,pos;char wbuf[S],buf[S];
    FastIO(){wpos=0,len=0,pos=0;}
    inline char gc(){
        if (pos==len) pos=0,len=fread(buf,1,S,in);
        if (pos==len) return 0; return buf[pos++];
    }
    inline void wchar(int x) {
        if (wpos==S) fwrite(wbuf,1,S,out),wpos=0;
        wbuf[wpos++]=x;
    }
    inline void put(const char*s) {for(; *s; ) wchar(*s++);}
    ~FastIO() {
        if (wpos) fwrite(wbuf,1,wpos,out),wpos=0;
    }
}io;
#endif
template<typename T> inline void read(T&x){T f=1;x=0;char c;
    for (c=getchar(); !isd(c); c=getchar()) f=(c=='-')?-1:f;
    for (; isd(c); c=getchar()) x=(x<<3)+(x<<1)+(c^48);x*=f;
}
template<typename T> inline void wt(T x,char c=0){char ch[(sizeof(T)+1)<<1];if (x<0) x=-x,putchar('-');
    int t=-1; do ch[++t]=x%10+'0',x/=10; while(x); do putchar(ch[t]); while(t--); if (c!=0) putchar(c);
}
int n,m,ba[maxn],cntba[maxn],tr[maxm][maxm],cnt,cnt1,ans;
struct node {
    int a,c,d,cnt;node():a(0),c(0),d(0),cnt(0){}
    node(int _a,int _c,int _d,int _cnt):a(_a),c(_c),d(_d),cnt(_cnt){}
    inline int operator <(const node&oth)const{
        return a!=oth.a?a>oth.a:c!=oth.c?c>oth.c:d>oth.d;
    }
    inline int operator ==(const node&oth)const{
        return a==oth.a&&c==oth.c&&d==oth.d;
    }
} trpC[maxn],tpc[maxn];
inline int query(int x,int y) {
    for (int i=x; i; i-=lowbit(i)) for (int j=y; j; j-=lowbit(j))
        if(tr[i][j]) return 1; return 0;
}
inline void update(int x,int y){
    for (int i=x; i<maxm; i+=lowbit(i)) for (int j=y; j<maxm; j+=lowbit(j))
        if (!tr[i][j]) tr[i][j]=1;
}
int main(int argv,char*argc[]){
    int T;read(T);
    for (int a,b,c,d,e,cas=1; cas<=T; ++cas){
        read(n),read(m),cnt=cnt1=0;
        memset(ba,0,sizeof ba),memset(cntba,0,sizeof cntba);
        for (int i=1; i<=n; ++i){read(a),read(b);
            if (ba[b]<a) ba[b]=a,cntba[b]=1;
            else if (ba[b]==a) cntba[b]++;
        }
        for (int i=1; i<=m; ++i){
            read(c),read(d),read(e);
            if (ba[e]) trpC[++cnt]=node(ba[e],c,d,cntba[e]);
        }
        sort(trpC+1,trpC+cnt+1);tpc[1]=trpC[1];
        for (int i=1; i<=cnt; ++i)
            if (tpc[cnt1]==trpC[i]) tpc[cnt1].cnt+=trpC[i].cnt;
            else tpc[++cnt1]=trpC[i];
        memset(tr,0,sizeof tr);ans=0;
        for (int i=1; i<=cnt1; ++i) {
            if (!query(1001-tpc[i].c,1001-tpc[i].d)) ans+=tpc[i].cnt;
            update(1001-tpc[i].c,1001-tpc[i].d);
        }
        printf("Case #%d: %d\n",cas,ans);
    }
    return 0;
}


点我回到主页

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

You are commenting using your WordPress.com account. Log Out /  更改 )

Google+ photo

You are commenting using your Google+ account. Log Out /  更改 )

Twitter picture

You are commenting using your Twitter account. Log Out /  更改 )

Facebook photo

You are commenting using your Facebook account. Log Out /  更改 )

Connecting to %s