XM14. ipv4地址白名单
描述
我们的小齐同学是一名很辛苦的实习DBA，他每天的工作就是为一个帐号添加授权，今天给这200个ipv4添加授权，明天又要把这200个授权删掉，有一天小齐同学在删除授权的时候不小心把所有的授权都删了，被领导很批了一顿。痛定思痛，小齐同学开始反思他每天的工作，发现无非就是我每天要让那些ip访问数据库而已，他决定写一个效率很高的ip白名单，请帮小齐同学说一下实现思路，并用结构化编程语言（c/c++/python/golang/java等）写一个ip白名单吧，他需要这个白名单有添加ip的功能，删除ip的功能，查找这个ip在不在白名单中，以及打印白名单中的内容，以上四个功能中查找ip是否在白名单中效率一定要高。并帮小齐分析一下各个功能的时间复杂度，写的好小齐同学会请你吃饭哦。输入描述
每行一条输入，格式为 type:ip输出描述
输出每行一条对应输入示例1
输入:
i:127.0.0.1 i:10.0.0.1 s:10.0.0.1 d:10.0.0.1 s:10.0.0.1 s:127.0.0.1 end
输出:
ok ok true ok false true
示例2
输入:
i:127.0.0.3 i:127.0.0.3 d:127.0.0.4 s:127.0.0.3 i:127.0.0.5 d:127.0.0.5 s:127.0.0.4 i:127.0.0.4 s:127.0.0.3 d:127.0.0.4 end
输出:
ok ok ok true ok ok false ok true ok
C++14 解法, 执行用时: 38ms, 内存消耗: 5124KB, 提交时间: 2020-05-20
#ifdef DEBUG
#else
#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define si set<int>
#define pii pair<int,int>
#define piii pair<int, pii>
#define piiii pair<int, piii>
#define umii unordered_map<int,int>
#define lowbit(t) t&(-t)
#define x first
#define y second
#define sqr(x) ((x) * (x))
#define eps 1e-9
#define m_init(arr, val) memset(arr, val, sizeof arr)
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define SZ(x) int(x.size())
#define pi acos(-1)
#define mod 1000000007
#define MOD 1000000003
#define INF 0x3f3f3f3f3f3f3f3f
#define ll long long
#define DBG(x) cerr<<(#x)<<"="<<x<<"\n";
#define bcase break;case
#define bdefault break;default
#define repi(i, a, b) for(int i = (a),i##len=(b); i<i##len; i++)
#define peri(i,a,b) for(int i=(a);i>=(b);i--)
#define perll(i,a,b) for(ll i=(a);i>=(b);i--)
#define repll(i, a, b) for(ll i = a; i<b; i++)
#define has_e(s,e) (s.find(e)!=s.end())
#define ceili(a, b) \
((a)/(b) + ((a)%(b) ? 1 : 0))
template <class U, class T> void Max(U &x, T y) { if (x<y)x = y; }
template <class U, class T> void Min(U &x, T y) { if (x>y)x = y; }
template <class T> void add(int &a, T b) { a = (a + b) % mod; }
int dx[] = {1,0,0,-1,1,1,-1,-1};
int dy[] = {0,1,-1,0,-1,1,-1,1};
ll qmul_mod(ll a, ll b, ll m) {
ll ans = 0LL;
while (b) {
if (b & 1)ans = (ans + a) % m;
a = (a + a) % m, b >>= 1;
}
return ans % m;
}
ll qpow_mod(ll x, ll y, ll m) {
ll res=1;
while(y)
{
if(y%2)(res*=x)%=m;
(x*=x)%=m;
y>>=1;
}
return res;
}
const int msize = 15;
struct Matrix {
int m[msize][msize];
Matrix() { memset(m, 0, sizeof m); }
void print() {
repi(i,0,msize) {
repi(j,0,msize) {
printf("%d%c", m[i][j], " \n"[j==msize-1]);
}
}
puts("");
}
void Unit() { repi(i, 0, msize) m[i][i] = 1; }
};
inline Matrix operator * (Matrix a, Matrix b) {
Matrix res;
repi(i, 0, msize)
repi(k, 0, msize)
if (a.m[i][k])
repi(j, 0, msize)
(res.m[i][j] += 1LL * a.m[i][k] * b.m[k][j] % mod) %= mod;
return res;
}
Matrix qmat_pow(Matrix a, int n) {
Matrix res;
res.Unit();
while (n)
{
if (n & 1) {
res = res * a;
}
n >>= 1;
a = a * a;
}
return res;
}
template <class T>
inline T lcm(T x,T y)
{
T a, b, c;
a = x;
b = y;
c = x%y;
while(c!=0)
{
x = y;
y = c;
c = x%y;
}
return a*b/y;
}
template <class T>
inline T gcd(T __m, T __n)
{
while (__n != 0)
{
T __t = __m % __n;
__m = __n;
__n = __t;
}
return __m;
}
#define N 10005
//ll f[N], inv[N];
//
//ll Combination(int a, int b) {
// return b > a ? 0 : 1LL * f[a] * inv[b] % mod*inv[a - b] % mod;
//}
//
//void C_init() {
// f[0] = 1;
// repi(i, 1, N) {
// f[i] = 1LL * i* f[i - 1] % mod;
// }
// inv[N - 1] = qpow_mod(f[N - 1], mod - 2, mod);
// peri(i, N - 2, 0) {
// inv[i] = 1LL * (i + 1)*inv[i + 1] % mod;
// }
//}
//int prime[N];
//bool vis[N];
//int cnt = 0;
//
//void sift_prime() {
// vis[0]=vis[1]=1;
// repi(i,2,N) {
// if(!vis[i]) {
// prime[cnt++] = i;
// }
// for(int j = 0; j<cnt && i*prime[j] < N; j++) {
// vis[prime[j]*i] = 1;
// if(i%prime[j]==0)break;
// }
// }
//}
int T = 1;
int n, m, k;
struct node {
int val;
}tree[N<<2];
bool flag[N>>1];
void down(int p,int L,int R) {
if (tree[p].val!=-1) {
tree[p<<1].val = tree[p<<1|1].val = tree[p].val;
tree[p].val = -1;
}
}
//void up(int p,int L,int R) {
//// lsum[p] = lsum[p << 1];
//// rsum[p] = rsum[p << 1 | 1];
//// int mid = (L + R) >> 1;
//// if (lsum[p] == md - L + 1) {
//// lsum[p] += lsum[p << 1 | 1];
//// }
//// if (rsum[p] == R - md) {
//// rsum[p] += rsum[p << 1];
//// }
// if(L>R)
// return;
// tree[p].mmax = max(tree[p<<1].mmax, tree[p<<1|1].mmax);
// tree[p].max = max(min(tree[p<<1].mmax, tree[p<<1|1].mmax), max(tree[p<<1].max, tree[p<<1|1].max));
//}
void build(int p, int L, int R) {
tree[p].val = -1;
if (L == R) {
return;
}
int mid = (L + R) >> 1;
build(p << 1, L, mid);
build(p << 1 | 1, mid + 1, R);
}
void upd(int p, int l, int r, int L, int R, int v) {
if (l <= L && R <= r) {
tree[p].val = v;
return;
}
down(p, L, R);
int mid = (L + R) >> 1;
if (l <= mid)
upd(p << 1, l, r, L, mid, v);
if (r > mid)
upd(p << 1 | 1, l, r, mid + 1, R, v);
// up(p,L,R);
}
void query(int p, int l, int r, int L, int R, int v) {
if (tree[p].val != -1) {
flag[tree[p].val] = 1;
return;
}
if(L==R)
return;
// down(p,L,R);
int mid = (L + R) >> 1;
if (l <= mid) {
query(p << 1, l, r, L, mid, v);
}
if (r > mid) {
query(p << 1 | 1, l, r, mid + 1, R, v);
}
}
#ifdef BTREE
#define lowbit(t) t&(-t)
int a[50005];
void Update(int i, int v, int n) {
while (i<=n) {
a[i]+=v;
i+=lowbit(i);
}
}
int Sum(int i) {
int res = 0;
while (i) {
res+=a[i];
i-=lowbit(i);
}
return res;
}
#endif
//int prime[1000005], sift[1000005];
//
//void sift_prime(int num) {
// sift[1]=1;
// repi(i,2,num+1) {
// if(!sift[i]) {
// prime[k++] = i;
// }
// for(int j=0; j<k && i*prime[j]<=num; j++) {
// sift[i*prime[j]] = 1;
// if (i%prime[j] == 0)
// break;
// }
// }
//}
//int fa[100005];
//int cnt[100005];
//
//void Init(int n) {
// for (int i = 0; i < n; ++i) {
// fa[i] = i;
// cnt[i] = 1;
// }
//}
//
//int Find(int x) {
// int y = x;
// while (x != fa[x]) {
// x = fa[x];
// }
// return fa[y] = x;
//}
//
//void Union(int x, int y) {
// x = Find(x), y = Find(y);
// if (x != y) {
// cnt[x] += cnt[y];
// fa[y] = x;
// }
//}
char ip[35];
int main()
{
srand(time(NULL)+clock());
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
// freopen("out1.txt", "w", stdout);
#endif
// scanf("%d", &T);
while (T--)
// while (~scanf("%s", str))
// repi(c,1,T+1)
{
char op;
unordered_set<int> ips;
while ((op = getchar()) != 'e') {
getchar();
scanf("%s", ip);
getchar();
int num = 0;
n = strlen(ip);
unsigned int ipnum = 0;
repi(i,0,n) {
if (ip[i] != '.') {
num = num*10+ip[i]-'0';
} else {
ipnum = (ipnum<<8)|num;
num = 0;
}
}
ipnum = (ipnum<<8)|num;
if (op == 'i') {
ips.emplace(ipnum);
puts("ok");
} else if (op == 'd') {
ips.erase(ipnum);
puts("ok");
} else {
if (ips.count(ipnum)) {
puts("true");
} else {
puts("false");
}
}
}
}
#ifndef ONLINE_JUDGE
fclose(stdin);
// fclose(stdout);
#endif
return 0;
}
#endif
C++14 解法, 执行用时: 38ms, 内存消耗: 6408KB, 提交时间: 2020-05-15
#ifdef DEBUG
#else
#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define si set<int>
#define pii pair<int,int>
#define piii pair<int, pii>
#define piiii pair<int, piii>
#define umii unordered_map<int,int>
#define lowbit(t) t&(-t)
#define x first
#define y second
#define sqr(x) ((x) * (x))
#define eps 1e-9
#define m_init(arr, val) memset(arr, val, sizeof arr)
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define SZ(x) int(x.size())
#define pi acos(-1)
#define mod 1000000007
#define MOD 1000000003
#define INF 0x3f3f3f3f3f3f3f3f
#define ll long long
#define DBG(x) cerr<<(#x)<<"="<<x<<"\n";
#define bcase break;case
#define bdefault break;default
#define repi(i, a, b) for(int i = (a),i##len=(b); i<i##len; i++)
#define peri(i,a,b) for(int i=(a);i>=(b);i--)
#define perll(i,a,b) for(ll i=(a);i>=(b);i--)
#define repll(i, a, b) for(ll i = a; i<b; i++)
#define has_e(s,e) (s.find(e)!=s.end())
#define ceili(a, b) \
((a)/(b) + ((a)%(b) ? 1 : 0))
template <class U, class T> void Max(U &x, T y) { if (x<y)x = y; }
template <class U, class T> void Min(U &x, T y) { if (x>y)x = y; }
template <class T> void add(int &a, T b) { a = (a + b) % mod; }
int dx[] = {1,0,0,-1,1,1,-1,-1};
int dy[] = {0,1,-1,0,-1,1,-1,1};
ll qmul_mod(ll a, ll b, ll m) {
ll ans = 0LL;
while (b) {
if (b & 1)ans = (ans + a) % m;
a = (a + a) % m, b >>= 1;
}
return ans % m;
}
ll qpow_mod(ll x, ll y, ll m) {
ll res=1;
while(y)
{
if(y%2)(res*=x)%=m;
(x*=x)%=m;
y>>=1;
}
return res;
}
const int msize = 15;
struct Matrix {
int m[msize][msize];
Matrix() { memset(m, 0, sizeof m); }
void print() {
repi(i,0,msize) {
repi(j,0,msize) {
printf("%d%c", m[i][j], " \n"[j==msize-1]);
}
}
puts("");
}
void Unit() { repi(i, 0, msize) m[i][i] = 1; }
};
inline Matrix operator * (Matrix a, Matrix b) {
Matrix res;
repi(i, 0, msize)
repi(k, 0, msize)
if (a.m[i][k])
repi(j, 0, msize)
(res.m[i][j] += 1LL * a.m[i][k] * b.m[k][j] % mod) %= mod;
return res;
}
Matrix qmat_pow(Matrix a, int n) {
Matrix res;
res.Unit();
while (n)
{
if (n & 1) {
res = res * a;
}
n >>= 1;
a = a * a;
}
return res;
}
template <class T>
inline T lcm(T x,T y)
{
T a, b, c;
a = x;
b = y;
c = x%y;
while(c!=0)
{
x = y;
y = c;
c = x%y;
}
return a*b/y;
}
template <class T>
inline T gcd(T __m, T __n)
{
while (__n != 0)
{
T __t = __m % __n;
__m = __n;
__n = __t;
}
return __m;
}
#define N 10005
//ll f[N], inv[N];
//
//ll Combination(int a, int b) {
// return b > a ? 0 : 1LL * f[a] * inv[b] % mod*inv[a - b] % mod;
//}
//
//void C_init() {
// f[0] = 1;
// repi(i, 1, N) {
// f[i] = 1LL * i* f[i - 1] % mod;
// }
// inv[N - 1] = qpow_mod(f[N - 1], mod - 2, mod);
// peri(i, N - 2, 0) {
// inv[i] = 1LL * (i + 1)*inv[i + 1] % mod;
// }
//}
//int prime[N];
//bool vis[N];
//int cnt = 0;
//
//void sift_prime() {
// vis[0]=vis[1]=1;
// repi(i,2,N) {
// if(!vis[i]) {
// prime[cnt++] = i;
// }
// for(int j = 0; j<cnt && i*prime[j] < N; j++) {
// vis[prime[j]*i] = 1;
// if(i%prime[j]==0)break;
// }
// }
//}
int T = 1;
int n, m, k;
struct node {
int val;
}tree[N<<2];
bool flag[N>>1];
void down(int p,int L,int R) {
if (tree[p].val!=-1) {
tree[p<<1].val = tree[p<<1|1].val = tree[p].val;
tree[p].val = -1;
}
}
//void up(int p,int L,int R) {
//// lsum[p] = lsum[p << 1];
//// rsum[p] = rsum[p << 1 | 1];
//// int mid = (L + R) >> 1;
//// if (lsum[p] == md - L + 1) {
//// lsum[p] += lsum[p << 1 | 1];
//// }
//// if (rsum[p] == R - md) {
//// rsum[p] += rsum[p << 1];
//// }
// if(L>R)
// return;
// tree[p].mmax = max(tree[p<<1].mmax, tree[p<<1|1].mmax);
// tree[p].max = max(min(tree[p<<1].mmax, tree[p<<1|1].mmax), max(tree[p<<1].max, tree[p<<1|1].max));
//}
void build(int p, int L, int R) {
tree[p].val = -1;
if (L == R) {
return;
}
int mid = (L + R) >> 1;
build(p << 1, L, mid);
build(p << 1 | 1, mid + 1, R);
}
void upd(int p, int l, int r, int L, int R, int v) {
if (l <= L && R <= r) {
tree[p].val = v;
return;
}
down(p, L, R);
int mid = (L + R) >> 1;
if (l <= mid)
upd(p << 1, l, r, L, mid, v);
if (r > mid)
upd(p << 1 | 1, l, r, mid + 1, R, v);
// up(p,L,R);
}
void query(int p, int l, int r, int L, int R, int v) {
if (tree[p].val != -1) {
flag[tree[p].val] = 1;
return;
}
if(L==R)
return;
// down(p,L,R);
int mid = (L + R) >> 1;
if (l <= mid) {
query(p << 1, l, r, L, mid, v);
}
if (r > mid) {
query(p << 1 | 1, l, r, mid + 1, R, v);
}
}
#ifdef BTREE
#define lowbit(t) t&(-t)
int a[50005];
void Update(int i, int v, int n) {
while (i<=n) {
a[i]+=v;
i+=lowbit(i);
}
}
int Sum(int i) {
int res = 0;
while (i) {
res+=a[i];
i-=lowbit(i);
}
return res;
}
#endif
//int prime[1000005], sift[1000005];
//
//void sift_prime(int num) {
// sift[1]=1;
// repi(i,2,num+1) {
// if(!sift[i]) {
// prime[k++] = i;
// }
// for(int j=0; j<k && i*prime[j]<=num; j++) {
// sift[i*prime[j]] = 1;
// if (i%prime[j] == 0)
// break;
// }
// }
//}
//int fa[100005];
//int cnt[100005];
//
//void Init(int n) {
// for (int i = 0; i < n; ++i) {
// fa[i] = i;
// cnt[i] = 1;
// }
//}
//
//int Find(int x) {
// int y = x;
// while (x != fa[x]) {
// x = fa[x];
// }
// return fa[y] = x;
//}
//
//void Union(int x, int y) {
// x = Find(x), y = Find(y);
// if (x != y) {
// cnt[x] += cnt[y];
// fa[y] = x;
// }
//}
char ip[35];
int main()
{
srand(time(NULL)+clock());
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
// freopen("out1.txt", "w", stdout);
#endif
// scanf("%d", &T);
while (T--)
// while (~scanf("%s", str))
// repi(c,1,T+1)
{
char op;
unordered_set<int> ips;
while ((op = getchar()) != 'e') {
getchar();
scanf("%s", ip);
getchar();
int num = 0;
n = strlen(ip);
unsigned int ipnum = 0;
repi(i,0,n) {
if (ip[i] != '.') {
num = num*10+ip[i]-'0';
} else {
ipnum = (ipnum<<8)|num;
num = 0;
}
}
ipnum = (ipnum<<8)|num;
if (op == 'i') {
ips.emplace(ipnum);
puts("ok");
} else if (op == 'd') {
ips.erase(ipnum);
puts("ok");
} else {
if (ips.count(ipnum)) {
puts("true");
} else {
puts("false");
}
}
}
}
#ifndef ONLINE_JUDGE
fclose(stdin);
// fclose(stdout);
#endif
return 0;
}
#endif