↓ 跳过正文
  1. Posts/

【叉姐的魔法训练第一课_初级魔法练习】poj 2443 Set Operation ( bitset加速)

·549 字·2 分钟

poj 2443题目链接

题意:给出n个可重集…以及集合中的元素。。。现在若干查询,每个查询给出一对数x,y,询问是否存在某个集合,同时拥有x,y两个元素(x,y可以相同)

思路:由于x,y最大时10000,容易想到对每一个元素开一个集合,记录这个元素出现的集合的标号,然后用 set_intersection 来做…

就是询问的时候交一下两个集合,看是否为空,结果Tle了。。。

正解其实也是这个思路,不过用到了bitset加速一下。因为我求集合相交的时候,并不需要知道交了以后的结果,只需要知道是否为空,那么我们不妨用bitset

对每个元素开一个bitset,每个bitset上,第i位为1表示,该元素在第i个集中中出现了。

求相交的时候,只需要两个bitset 位与一下,然后看结果中是否有1出现就好了。

代码实现
 1/* ***********************************************
 2Author :111qqz
 3Created Time :2016年11月17日 星期四 09时31分16秒
 4File Name :code/poj/2442.cpp
 5 ************************************************ */
 6#include <cstdio>
 7#include <cstring>
 8#include <iostream>
 9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <set>
13#include <map>
14#include <string>
15#include <cmath>
16#include <cstdlib>
17#include <ctime>
18#include <bitset>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27using namespace std;
28const double eps = 1E-8;
29const int dx4[4]={1,0,0,-1};
30const int dy4[4]={0,-1,1,0};
31const int inf = 0x3f3f3f3f;
32const int N=1E4+7;
33int n;
34set<int>se[N];
35bitset<1005>bse[N],tmp;
36set<int>myset;
37int main()
38{
39#ifndef  ONLINE_JUDGE
40    freopen("code/in.txt","r",stdin);
41#endif
42    scanf("%d",&n);
43    for ( int i =1 ; i <= n ; i++)
44    {
45	int c;
46	scanf("%d",&c);
47	myset.clear();
48	while (c--)
49	{
50	    int x;
51	    scanf("%d",&x);
52	    bse[x].set(i);
53	}
54    }
55    int q;
56    scanf("%d",&q);
57    while (q--)
58    {
59	int x,y;
60	scanf("%d%d",&x,&y);
61	tmp = bse[x]&bse[y];
62	if (tmp.any()) puts("Yes");
63	else puts("No");
64    }
65#ifndef ONLINE_JUDGE
66    fclose(stdin);
67#endif
68    return 0;
69}

相关文章

hdu 5036 Explosion||2014 北京区域赛网络赛 (概率+bitset优化的状态压缩+floyd传递闭包)

题目链接 题意:有n扇门,n种钥匙,一一对应。每扇门打开后可能得到k把钥匙(k可能为0)。一扇门还可以用一颗炸弹炸开。现在问要开所有门,使用炸弹的期望个数。 思路:状态压缩。用一个二进制串表示每扇门能打开的门的信息,对应的位上为1表示能打开,为0表示不能打开。

hdu 2051 bitset (水)

·320 字·1 分钟
题目链接 题意:把一个数n(n<1000)转化成二进制输出。。。 思路:。。。搜acm bitset 搜到这题。。。所以其实这并不是“bitset”优化的题。。。只是题目名字交这个了2333。

acm 奇技淫巧 bitset

·451 字·1 分钟
1.定义与初始化 在定义 bitset 时,要明确 bitset 有多少位,这个位数是整形常量 (tips:如果长度和输入的数m有关,在做翻转操作以后再统计时候会多算,一个可以的做法是设置一个长度为m,所有位上都是1的位串,然后翻转之后先与一下。类似的技巧还有很多。)

(dp专题006)hdu 2602 Bone Collector(01背包)

·296 字·1 分钟
题目链接 题意:容量为V的背包,n个骨头,给出价值和体积,问最多能装多少价值的背包。 思路:01背包裸体。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年11月16日 星期三 15时14分36秒 4File Name :code/hdu/2602.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <ctime> 19#define fst first 20#define sec second 21#define lson l,m,rt<<1 22#define rson m+1,r,rt<<1|1 23#define ms(a,x) memset(a,x,sizeof(a)) 24typedef long long LL; 25#define pi pair < int ,int > 26#define MP make_pair 27 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const int N=1E3+7; 34int dp[N],value[N],cost[N]; 35int n,V; 36void solve(int v,int c) 37{ 38 for ( int i = V; i >= c; i --) 39 dp[i] = max(dp[i],dp[i-c]+v); 40} 41int main() 42{ 43 #ifndef ONLINE_JUDGE 44 freopen("code/in.txt","r",stdin); 45 #endif 46 int T; 47 cin>>T; 48 while (T--) 49 { 50 scanf("%d%d",&n,&V); 51 ms(dp,0); 52 for ( int i = 1 ;i <= n ; i++) scanf("%d",&value[i]); 53 for ( int i = 1; i <= n ; i++) scanf("%d",&cost[i]); 54 for ( int i = 1 ; i <= n ; i++) solve(value[i],cost[i]); 55 int ans = 0 ; 56 57 for ( int i = 0 ; i <= V ; i++) ans = max(ans,dp[i]); 58 printf("%d\n",ans); 59 } 60 61 #ifndef ONLINE_JUDGE 62 fclose(stdin); 63 #endif 64 return 0; 65}

[dp专题005]hdu 1864最大报销额(01背包,垃圾题)

·467 字·1 分钟
hdu1864题目链接 题意:中文题目,不多说了。 思路:正解是01背包,呵呵呵。 出题人是傻逼吗? 不给数据范围? 以及,正解的01背包基于所有的发票额度的只有2位小数。这是让人猜? 本来看到这题这么恶心时不打算写的…