C. Sonya and Queries

http://codeforces.com/contest/714/problem/C

看到这题目,想想,肯定不能暴力啊,如果用map,如何快速找到满足要求的数目,然后,长度18,我想,这不是熟悉的trie树么,还犹豫什么,把所有的输入都处理成长度为18的字符串,处理就行了,然后调试了一会,就交了,然后tle了,我就怀疑了,难道不是这样的套路么?!然后就开始查答案,一看官方题解,恍然大悟,这道题目有个很好的性质,就是插入11和插入33的效果是一样的,删除11和删除33的效果是一致的,同一种模型,我们不必具体的区分该位具体是什么,比如奇数(1,3,5,7,9)都可以简单用1来表示,偶数(0,2,4,6,8)都可以用0表示,这样题目就化简很多,还要trie树做什么,同一种模式可以归为一类,总共1 << 18种方式,然后单独统计,单独输出,就ok!就完了,感觉还是太笨了!也没仔细去分析。

 #include<bits/stdc++.h>
#define pb push_back
#define FOR(i, n) for (int i = 0; i < (int)n; ++i)
#define dbg(x) cout << #x << " at line " << __LINE__ << " is: " << x << endl
typedef long long ll;
using namespace std;
typedef pair<int, int> pii;
const int maxn = << ;
int a[maxn];
int n;
char ch[];
ll x;
ll d[];
void solve() {
d[] = ;
for (int i = ; i < ; i++) d[i] = d[i - ] * ;
scanf("%d", &n);
while(n--) {
scanf("%s", ch);
//cout << ch << endl;
if(ch[] == '?') {
scanf("%s", ch);
int l = strlen(ch);
int t = ;
for (int i = ; i < l; i++) {
if(ch[i] == '')
t |= ( << (l - i - ));
}
//cout << "ask " << t << endl;
printf("%d\n", a[t]);
} else {
scanf("%I64d", &x);
int t = ;
for (int i = ; i >= ; i--) {
int td = x / d[i];
x %= d[i];
if(td & ) t |= ( << i);
}
//cout << "test "<< t << endl;
if(ch[] == '+')
a[t]++;
else a[t]--;
}
}
}
int main() { //freopen("test.in", "r", stdin);
//freopen("test.out", "w", stdout);
solve();
return ;
}
上一篇:Hibernate的10个常见面试问题及答案


下一篇:剑指Offer 55. 链表中环的入口结点 (链表)