IP聚合
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 65536/65536 K (Java/Others)
Problem's Link: http://bestcoder.hdu.edu.cn/contests/contest_showproblem.php?cid=584&pid=1003
Mean:
略
analyse:
贪心
Time complexity: O(n)
Source code:
/* * this code is made by crazyacking * Verdict: Accepted * Submission Date: 2015-05-25-14.59 * Time: 0MS * Memory: 137KB */ #include <queue> #include <cstdio> #include <set> #include <string> #include <stack> #include <cmath> #include <climits> #include <map> #include <cstdlib> #include <iostream> #include <vector> #include <algorithm> #include <cstring> #define LL long long #define ULL unsigned long long using namespace std; struct IP { int a, b, c, d; }; int i, j, k, l, m, n, o, p, q, x, y, z, aa, bb, cc, dd; struct IP a[1010], b, c[50010], d; char ch[100]; int dfs() { int i; for ( i = 1; i <= q; i++ ) if ( ( c[i].a == d.a ) && ( c[i].b == d.b ) && ( c[i].c == d.c ) && ( c[i].d == d.d ) ) { return 0; } return 1; } int main() { scanf( "%d", &n ); for ( l = 1; l <= n; l++ ) { memset( a, 0, sizeof( a ) ); memset( c, 0, sizeof( c ) ); q = 0; scanf( "%d%d", &x, &y ); for ( j = 1; j <= x; j++ ) { scanf( "%s", &ch ); z = 0; p = 0; while ( ( ch[z] > 47 ) && ( ch[z] <= 48 + 9 ) ) {p = p * 10 + ch[z] - 48; z++;} a[j].a = p; z = z + 1; p = 0; while ( ( ch[z] > 47 ) && ( ch[z] <= 48 + 9 ) ) {p = p * 10 + ch[z] - 48; z++;} a[j].b = p; z = z + 1; p = 0; while ( ( ch[z] > 47 ) && ( ch[z] <= 48 + 9 ) ) {p = p * 10 + ch[z] - 48; z++;} a[j].c = p; z = z + 1; p = 0; while ( ( ch[z] > 47 ) && ( ch[z] <= 48 + 9 ) ) {p = p * 10 + ch[z] - 48; z++;} a[j].d = p; } printf( "Case #%d:\n", l ); for ( j = 1; j <= y; j++ ) { q = 0; memset( c, 0, sizeof( c ) ); scanf( "%s", &ch ); z = 0; p = 0; while ( ( ch[z] > 47 ) && ( ch[z] <= 48 + 9 ) ) {p = p * 10 + ch[z] - 48; z++;} b.a = p; z = z + 1; p = 0; while ( ( ch[z] > 47 ) && ( ch[z] <= 48 + 9 ) ) {p = p * 10 + ch[z] - 48; z++;} b.b = p; z = z + 1; p = 0; while ( ( ch[z] > 47 ) && ( ch[z] <= 48 + 9 ) ) {p = p * 10 + ch[z] - 48; z++;} b.c = p; z = z + 1; p = 0; while ( ( ch[z] > 47 ) && ( ch[z] <= 48 + 9 ) ) {p = p * 10 + ch[z] - 48; z++;} b.d = p; for ( k = 1; k <= x; k++ ) { aa = ( a[k].a ) & ( b.a ); bb = ( a[k].b ) & ( b.b ); cc = ( a[k].c ) & ( b.c ); dd = ( a[k].d ) & ( b.d ); d.a = aa; d.b = bb; d.c = cc; d.d = dd; if ( q == 0 ) {q++; c[q] = d; continue;} if ( dfs() ) {q++; c[q] = d;} } printf( "%d\n", q ); } } return 0; }
