本文共 3108 字，大约阅读时间需要 10 分钟。
当今世界，网络已经无处不在了，小度熊由于犯了错误，当上了度度公司的网络管理员，他手上有大量的 IP列表，小度熊想知道在某个固定的子网掩码下，有多少个网络地址。网络地址等于子网掩码与 IP 地址按位进行与运算后的结果，例如：
子网掩码：A.B.C.D
IP 地址：a.b.c.d
网络地址：(A&a).(B&b).(C&c).(D&d)
第一行包含一个整数T，（1≤T≤50）代表测试数据的组数，
接下来T组测试数据。每组测试数据包含若干行，
第一行两个正整数N（1≤N≤1000,1≤M≤50）,M。接下来N行，每行一个字符串，代表一个 IP 地址，
再接下来M行，每行一个字符串代表子网掩码。IP 地址和子网掩码均采用 A.B.C.D的形式，其中A、B、C、D均为非负整数，且小于等于255。
对于每组测试数据，输出两行：
第一行输出: "Case #i:" 。i代表第i组测试数据。
第二行输出测试数据的结果，对于每组数据中的每一个子网掩码，输出在此子网掩码下的网络地址的数量。
25 2192.168.1.0192.168.1.101192.168.2.5192.168.2.7202.14.27.235255.255.255.0255.255.0.04 2127.127.0.110.134.52.0127.0.10.110.134.0.2235.235.0.01.57.16.0
Case #1:32Case #2:34
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 #include #include #include #include #include #include #include #include #include #include #include #include #define LL long long#define ULL unsigned long longusing 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;}
转载地址：http://istea.baihongyu.com/
