[TIOJ] 1998. 網路遮罩
題目連結:http://tioj.infor.org/problems/1998
可以發現其實每個IP都是一個32-bit的東東,所以可以直接用個unsigned int或long long存下來。而遮罩的那個區間其實就是那些x全填0到全填1,而我們要詢問一堆IP是不是在一堆區間內,其實就直接把那些區間當作區間加值,那查詢就只要查詢那個點是不是大於一就好了。不過因為範圍有點大,要先離散化掉就是了。
可以發現其實每個IP都是一個32-bit的東東,所以可以直接用個unsigned int或long long存下來。而遮罩的那個區間其實就是那些x全填0到全填1,而我們要詢問一堆IP是不是在一堆區間內,其實就直接把那些區間當作區間加值,那查詢就只要查詢那個點是不是大於一就好了。不過因為範圍有點大,要先離散化掉就是了。
#include <bits/stdc++.h>
using namespace std;
#define PB push_back
#define ALL(x) begin(x), end(x)
typedef long long lld;
typedef pair<lld,lld> PLL;
#define FF first
#define SS second
const int M = 200000 + 5;
const int N = 300000 + 5;
class LiSan{
private:
vector<lld> vv;
public:
inline void init(){vv.clear();}
inline void insert(lld x){vv.PB(x);}
inline void done(){
sort(ALL(vv));
vv.resize(distance(vv.begin(), unique(ALL(vv))));
}
inline int size(){return vv.size();}
inline int get(lld x){
return distance(vv.begin(), lower_bound(ALL(vv), x));
}
} lisan;
PLL msk[M];
lld que[N];
int arr[2*M+N];
int main(){
lisan.init();
int m, n; scanf("%d%d",&m,&n);
for(int i=0;i<m;i++){
int a, b, c, d, x; scanf("%d.%d.%d.%d/%d",&a,&b,&c,&d,&x);
lld ret = a;
ret = ret*256 + b;
ret = ret*256 + c;
ret = ret*256 + d;
bitset<32> bb(ret);
for(int _=0;_<32-x;_++) bb[_]=0;
msk[i].FF = bb.to_ulong();
lisan.insert(msk[i].FF);
for(int _=0;_<32-x;_++) bb[_]=1;
msk[i].SS = bb.to_ulong();
lisan.insert(msk[i].SS);
}
for(int i=0;i<n;i++){
int a, b, c, d; scanf("%d.%d.%d.%d",&a,&b,&c,&d);
lld ret = a;
ret = ret*256 + b;
ret = ret*256 + c;
ret = ret*256 + d;
que[i]=ret;
lisan.insert(que[i]);
}
lisan.done();
for(int i=0;i<m;i++){
arr[lisan.get(msk[i].FF)]++;
arr[lisan.get(msk[i].SS)+1]--;
}
int nn = lisan.size();
for(int i=1;i<=nn;i++) arr[i]+=arr[i-1];
for(int i=0;i<n;i++){
int cur = lisan.get(que[i]);
puts(arr[cur]?"TRUE":"FALSE");
}
return 0;
}
留言
張貼留言