题目传送门:http://poj.org/problem?id=1903
中文题面:《算法竞赛·入门经典·训练指南》P57
对于每一个字符串,不难将其转化为26维的0/1向量
于是求一个线性基就可以辣!
当然不会线性基该怎么搞?
白书上面给了一个很常用、实用的方法:
将向量分成两组,组内暴力
然后组间使用map来支持查询即可
题目传送门:http://poj.org/problem?id=1903
中文题面:《算法竞赛·入门经典·训练指南》P57
对于每一个字符串,不难将其转化为26维的0/1向量
于是求一个线性基就可以辣!
当然不会线性基该怎么搞?
白书上面给了一个很常用、实用的方法:
将向量分成两组,组内暴力
然后组间使用map来支持查询即可
题目传送门:http://oi.cyo.ng/wp-content/uploads/2016/11/20161104.pdf
这题如果是亦或之类的,大家应该都会做吧!
但这题是&的话,有些时候就需要同时进入左右子树了QAQ
这个我们不难想到:http://uoj.ac/problem/176
简直一毛一样有木有?
然而这么做有一个问题:这货只能用Fat Node的持久化形式
这样的话,在最后复制左右子树的时候,复杂度还是不对啊QAQ
所以这样似乎没法做了QAQ
如果可以的话,可不可以给我讲一讲? _(:з」∠)_
还是来说一说std吧:
将二进制下前八位作为数组的一维下标
将二进制的后八位作为数组的二维下标
然后在查询时暴力第二维,修改时暴力第一维
时间复杂度O(n*2^8)
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 300; const int MX = 256; int f[N][N],n; char pat[10]; inline int read(){ char c=getchar(); int ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret*f; } inline void modify(int w, int delta) { for (int i=0;i<MX;i++) { if ((i&w)==(w&255)) { f[i][w>>8] += delta; } } } inline int query(int w) { int ret = 0; for (int i=0,sta=w>>8;i<MX;i++) { if ((i&sta)==i) { ret += f[w&255][i]; } } return ret; } int main(){ freopen("subset.in","r",stdin); freopen("subset.out","w",stdout); n = read(); for (int i=1;i<=n;i++) { scanf("%s",pat+1); if (pat[1] == 'a') modify(read(),1); else if (pat[1]=='d') modify(read(),-1); else printf("%d\n",query(read())); } return 0; }