I - Triple HDU - 5517

題意：

由多重集A和多重集B，<a,b>∈A，<c,d,e>∈B，集合C=A * B{<a,c,d>|<a,b>∈A，<c,d,e>∈B and b=e}。
現(xiàn)在需要你求出有多少個(gè)<a,c,d>滿足：不存在屬于C的一個(gè)三元組<u,v,w>使得，u>=a,v>=c,w>=d，<u,v,w>!=<a,c,d>

題解：

C=A*B,<a,b>∈A，<c,d,e>∈B,<a,c,d>∈C
在A中，對(duì)于同一個(gè)b可能存在多個(gè)a，而我們只需要最大的那個(gè)，因?yàn)榻M成的<ai,c,d>,只有ai不同，而只有最大的ai才滿足題目要求
這樣對(duì)于生成的C<a,c,d>,a確定了，我們可以將<c,d>一起考慮，按照a從大到小的順序?qū)?#xff08;c，d）看作平面坐標(biāo)插入到二維樹狀數(shù)組里，每次插入前查看當(dāng)前點(diǎn)的右上部分是否存在點(diǎn)？因?yàn)樵诘貓D上，如果(x,y)在(a,b)的右上部分，說(shuō)明x>=a,y>=b,如果右上不存在點(diǎn)，說(shuō)明沒有點(diǎn)比他大(a是從大到小順序插入，所以只需要考慮已插入的點(diǎn))

代碼：

#include<bits/stdc++.h> using namespace std; const int MAXN = 100010; const int N = 1010; int bit[N + 10][N + 10]; struct node{int x, y, z, num;node(){}node(int _x, int _y, int _z, int _num) : x(_x), y(_y), z(_z), num(_num) {}bool operator < (node a) const{if(x != a.x) return x < a.x;if(y != a.y) return y < a.y;return z < a.z;}bool operator == (node a) const{return (x == a.x && y == a.y && z == a.z);} }p[MAXN]; int w[MAXN], cnt[MAXN]; int top; void add(int i, int j, int x) {for(int u = i; u <= N; u += u & -u)for(int v = j; v <= N; v += v & -v)bit[u][v] += x; } int sum(int i, int j) {int res = 0;for(int u = i; u; u -= u & -u)for(int v = j; v; v -= v & -v)res += bit[u][v];return res; } int query(int x1, int y1, int x2, int y2) {return sum(x2, y2) - sum(x1 - 1, y2) - sum(x2, y1 - 1) + sum(x1 - 1, y1 - 1); } int solve() {memset(bit, 0, sizeof(bit));int ans = 0;for(int i = top; i >= 0; i--) //注意是逆序處理{if(query(p[i].y, p[i].z, N, N) == 0) ans += p[i].num;add(p[i].y, p[i].z, 1);}return ans; } int main() {int T, n, m, a, b, c,d,e;cin >> T;for(int kase = 1; kase <= T; kase++){memset(w, 0, sizeof(w));memset(cnt, 0, sizeof(cnt));scanf("%d %d", &n, &m);for(int i = 1; i <= n; i++){scanf("%d %d", &a, &b);if(w[b] < a) w[b] = a, cnt[b] = 1;else if(w[b] == a) cnt[b]++;}top = 0;for(int i = 1; i <= m; i++){scanf("%d %d %d", &c, &d, &e);if(w[e]) p[top++] = node(w[e], c, d, cnt[e]);}sort(p, p + top);int tmp = top; top = 0;for(int i = 1; i < tmp; i++){if(p[top] == p[i]) p[top].num += p[i].num;else p[++top] = p[i];}printf("Case #%d: %d\n", kase, solve());}return 0; }

總結(jié)

以上是生活随笔為你收集整理的I - Triple HDU - 5517的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。