Fork me on GitHub

[奇技淫巧] bitset大法吼啊

发表于 | 分类于
字数统计: 404字 | 阅读时长 ≈ 2分钟

前言

bitset不止一次听大爷们安利过了…

似乎 挺厉害的.
因为bool数组在用的时候只能够用一个byte但是byte有8个bit,0/1只要1个就够了.. 所以浪费了7个bit.

Reference:

bitset/zh-cpp-reference

bitset/cppcontainer

hfq is so toxic.!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<bits/stdc++.h>
#include<bitset>
using namespace std;

int main(int argc, char *argv[])
{
	//正常的构造 
	bitset<8>a(42); //[0,0,1,0,1,0,1,0]
	cout << a << endl;
	bitset<70>b(LLONG_MAX); 
	cout << b << endl;
	
	//字符串string构造
	string bit_s = "110010";
	bitset<8>c(bit_s);
	cout << c << endl;
	// bitset<sz>b(bit_string,x,(y));
	bitset<8>d(bit_s,2); //字符串的第 x+1(下标为x)个及之后的甩进bitset.
	cout << d << endl;
	bitset<8>e(bit_s,0,3); //字符串的第 x+1(下标为x) 及共y个甩进bitset. 
	cout << e << endl; 
	
	// string的自定义构造0,1串
	string bit_as = "HHHJJJHHJH";
	bitset<10>f(bit_as,0,bit_as.size(),'H','J'); //把H设为0，J设为1,如果出现了其他的字符就返回错误 
	cout << f << endl; 
	return 0;
}

Atcoder Grand Contest AGC 020 C Median Sum

AGC 020C

水题(我还是不会做)

用bitset维护一个类似背包的东西..

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<bits/stdc++.h>
using namespace std;
int n,ret = 0;
bitset<4000010>f;
inline int read(void)
{
	int x = 0,f = 1; char ch = getchar();
	while(!isdigit(ch)){f = ch == '-' ? -1 : 1; ch = getchar();}
	while(isdigit(ch)){x = (x << 3) + (x << 1) + ch - '0'; ch = getchar();}
	return x*f;
}

int main(int argc, char *argv[])
{
	n = read();
	f[0] = 1;
	while(n--)
	{
		int x = read();
		f = f|(f<<x);
		ret += x;
	}
	int i;
	for (i = (ret+1)/2; !f[i]; i++);
	cout << i;
	return 0;
}