↓ 跳过正文

acm 奇技淫巧 bitset

2016-08-21·451 字·1 分钟

ACM Bitset优化

1.定义与初始化在定义 bitset 时，要明确 bitset 有多少位，这个位数是整形常量

(tips：如果长度和输入的数m有关，在做翻转操作以后再统计时候会多算，一个可以的做法是设置一个长度为m，所有位上都是1的位串，然后翻转之后先与一下。类似的技巧还有很多。)

（） bitset b; //b 有 n 位，每位都是 0 bitset b(u); //b 是 unsigned long 型 u 的一个副本 bitset b(s); //b 是 string 对象 s 中含有的位串的副本，这个s 必须是位串，也就是二进制码串 bitset b(s, pos, n); //b 是 s 中从位置 pos 开始的 n 个位的副本

2.bitset 的操作 b.any() //b 中是否存在置为 1 的二进制位？ b.none() // 和b.any() 效果一样 b.count() //b 中不存在置为 1 的二进制位吗？

b.any() //b中存在置为1的二进制位吗？ b.size() //b 中置为 1 的二进制位的个数 b[pos] //访问 b 中在 pos 处二进制位 b.test(pos) //b 中在 pos 处的二进制位置为 1 b.set() // 把 b 中所有二进制位都置为 1 b.set(pos) //把 b 中在 pos 处的二进制位置为 1 b.reset() //把 b 中所有二进制位都置为 0 b.reset(pos) //把 b 中在 pos 处的二进制位置为 0 b.flip() //把 b 中所有二进制位逐位取反 b.flip(pos) //把 b 中在 pos 处的二进制位取反 b.to_ulong() //用 b 中同样的二进制位返回一个 unsigned long 值 os « b //把 b 中的位集输出到 os 流示例：

cout « b « endl;

相关文章

codeforces #368 div 2 B. Bakery (暴力)

2016-08-21·367 字·1 分钟

ACM Brute Force

题目链接题意：n个城市，m条双向路，要从k条中选择一个，使得到其他n-k个城市中的某个城市的距离最短。思路：直接暴力枚举。1A 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年08月20日星期六 21时02分14秒 4File Name :code/cf/#368/B.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 <deque> 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 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 =1E5+7; 33int n,m,k; 34vector <pair <int,LL> >edge[N]; 35int b[N]; 36bool cangku[N]; 37int main() 38{ 39 #ifndef ONLINE_JUDGE 40 freopen("code/in.txt","r",stdin); 41 #endif 42 ios::sync_with_stdio(false); 43 cin>>n>>m>>k; 44 ms(cangku,false); 45 for ( int i = 1 ; i <= m ; i++) 46 { 47 int u,v; 48 LL w; 49 cin>>u>>v>>w; 50 edge[u].push_back(make_pair(v,w)); 51 edge[v].push_back(make_pair(u,w)); 52 } 53 if (k==0) 54 { 55 cout<<-1<<endl; 56 return 0 ; 57 } 58 for ( int i = 1 ; i <= k ; i++) 59 { 60 cin>>b[i]; 61 cangku[b[i]] = true; 62 } 63 if (k==n) 64 { 65 cout<<-1<<endl; 66 return 0; 67 } 68 LL ans = inf; 69 for (int i = 1 ; i <= k ; i++) 70 { 71 int u = b[i]; 72 int siz = edge[u].size(); 73 for (int j = 0 ; j < siz ; j++) 74 { 75 int v = edge[u][j].fst; 76 if (cangku[v]) continue; 77 LL w = edge[u][j].sec; 78 ans = min(ans,w); 79 } 80 } 81 if (ans==inf) ans = -1; 82 cout<<ans<<endl; 83 #ifndef ONLINE_JUDGE 84 fclose(stdin); 85 #endif 86 return 0; 87}

hdu 1754 I Hate It (线段树模板题，炒鸡详细注释版)

2016-08-18·1717 字·4 分钟

hdu 1754 题目链接题意：单点更新，区间查询最大值。思路：线段树。一开始借鉴了 clj 的 pointer 写法，wjmzbmr’s code 直接 MLE，看来也许只能在 cf 上用。下面是 MLE 的代码：代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年08月18日星期四 18时40分24秒 4File Name :code/hdu/1754.cpp 5************************************************ */ 6#include <cstdio> 7#include <cstring> 8#include <iostream> 9#include <algorithm> 10#include <vector> 11#include <queue> 12#include <stack> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <deque> 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=2E5+7; 33int a[N],n,m; 34int _max( int x,int y) 35{ 36 if (x==-1||y==-1) 37 return x==-1?y:x; 38 return a[x]>a[y]?x:y; 39} 40struct Tree 41{ 42 Tree *pl,*pr; 43 int l,r,mx; 44 void update() 45 { 46 mx = _max(pl->mx,pr->mx); 47 } 48 Tree(int l,int r) : 49 l(l),r(r) 50 { 51 if ( l + 1 == r) 52 { 53 mx = l ; 54 return ; 55 } 56 pl = new Tree(l,(l+r)>>1); 57 pr = new Tree((l+r)>>1,r); 58 update(); 59 } 60 void change(int p,int x) 61 { 62 if (p < l|| p>=r) return; 63 if (l+1==r) 64 { 65 a[l] = x; 66 return ; 67 } 68 pl->change(p,x); 69 pr->change(p,x); 70 update(); 71 } 72 int queryMax(int L,int R) 73 { 74 if (L <= l && r <= R) return mx; 75 if (L>=r || l >=R) 76 return -1; 77 return _max(pl->queryMax(L,R),pr->queryMax(L,R)); 78 } 79}*rt; 80int main() 81{ 82 #ifndef ONLINE_JUDGE 83 freopen("code/in.txt","r",stdin); 84 #endif 85 while (~scanf("%d%d",&n,&m)) 86 { 87 ms(a,0); 88 for ( int i = 0 ; i < n ; i++) scanf("%d",a+i); 89 rt = new Tree(0,n); 90 while (m--) 91 { 92 char opt[3]; 93 int x,y; 94 scanf("%s %d %d",opt,&x,&y); 95 x--; 96 if (opt[0]=='Q') 97 printf("%d\n",a[rt->queryMax(x,y)]); 98 else rt->change(x,y); 99 } 100 } 101 #ifndef ONLINE_JUDGE 102 fclose(stdin); 103 #endif 104 return 0; 105} 关于线段树的理解，见代码注释：