题目链接: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; }