Posts

# 三维树状数组 容斥那里注意一下。 多组数据因为忘记清空c数组而wa了1次，细心！ 代码实现 1/************************************************************************* 2 > File Name: code/hdu/3584.cpp 3 > Author: 111qqz 4 > Email: rkz2013@126.com 5 > Created Time: 2015年08月07日 星期五 14时01分53秒 6 ************************************************************************/ 7 8#include<iostream> 9#include<iomanip> 10#include<cstdio> 11#include<algorithm> 12#include<cmath> 13#include<cstring> 14#include<string> 15#include<map> 16#include<set> 17#include<queue> 18#include<vector> 19#include<stack> 20#define y0 abc111qqz 21#define y1 hust111qqz 22#define yn hez111qqz 23#define j1 cute111qqz 24#define tm crazy111qqz 25#define lr dying111qqz 26using namespace std; 27#define REP(i, n) for (int i=0;i<int(n);++i) 28typedef long long LL; 29typedef unsigned long long ULL; 30const int inf = 0x7fffffff; 31const int N=1E2+5; 32int c[N][N][N]; 33int n,m; 34int x1,y1,z1,x2,y2,z2; 35int lowbit( int x) 36{ 37 return x&(-x); 38} 39void update ( int x,int y,int z,int delta) 40{ 41 for ( int i = x; i <= n ; i = i + lowbit(i)) 42 { 43 for ( int j = y ; j <= n ; j = j + lowbit(j)) 44 { 45 for ( int k = z ; k <= n ; k = k + lowbit(k)) 46 { 47 c[i][j][k] += delta; 48 } 49 } 50 } 51} 52 53int sum (int x,int y,int z) 54{ 55 int res = 0; 56 for ( int i = x; i >= 1 ; i -= lowbit(i)) 57 { 58 for ( int j = y ; j >= 1 ; j -= lowbit(j)) 59 { 60 for ( int k = z ; k >= 1 ; k -= lowbit(k)) 61 { 62 res = res + c[i][j][k]; 63 } 64 } 65 } 66 return res; 67} 68int main() 69{ 70 int op; 71 while (scanf("%d %d",&n,&m)!=EOF) 72 { 73 memset(c,0,sizeof(c)); 74 for ( int i = 1 ; i <= m ; i ++ ) 75 { 76 scanf("%d",&op); 77 if (op) 78 { 79 scanf("%d %d %d %d %d %d",&x1,&y1,&z1,&x2,&y2,&z2); 80 update (x1,y1,z1,1); 81 update (x1,y1,z2+1,1); 82 update (x1,y2+1,z1,1); 83 update (x2+1,y1,z1,1); 84 85 update (x2+1,y2+1,z1,1); 86 update (x2+1,y1,z2+1,1); 87 update (x1,y2+1,z2+1,1); 88 update (x2+1,y2+1,z2+1,1); 89 90 } 91 else 92 { 93 scanf("%d %d %d",&x1,&y1,&z1); 94 cout<<sum(x1,y1,z1)%2<<endl; 95 } 96 } 97 } 98 99 return 0; 100}

1 和上一道类似，也是更新区间，查询单点。 用到了容斥原理。 代码实现 1/************************************************************************* 2 > File Name: code/poj/2155.cpp 3 > Author: 111qqz 4 > Email: rkz2013@126.com 5 > Created Time: 2015年08月07日 星期五 00时42分38秒 6 ************************************************************************/ 7 8#include<iostream> 9#include<iomanip> 10#include<cstdio> 11#include<algorithm> 12#include<cmath> 13#include<cstring> 14#include<string> 15#include<map> 16#include<set> 17#include<queue> 18#include<vector> 19#include<stack> 20#define y0 abc111qqz 21#define y1 hust111qqz 22#define yn hez111qqz 23#define j1 cute111qqz 24#define tm crazy111qqz 25#define lr dying111qqz 26using namespace std; 27#define REP(i, n) for (int i=0;i<int(n);++i) 28typedef long long LL; 29typedef unsigned long long ULL; 30const int inf = 0x7fffffff; 31const int N=1E3+7; 32int c[N][N]; 33int n,m,x1,x2,y1,y2,x,y,t; 34 35int lowbit ( int x) 36{ 37 return x&(-x); 38} 39void update ( int x,int y ,int delta) 40{ 41 for ( int i = x ; i <= n ; i = i + lowbit(i)) 42 { 43 for ( int j = y; j <= n ; j = j + lowbit(j)) 44 { 45 c[i][j] = c[i][j] + delta; 46 } 47 } 48} 49int sum ( int x,int y) 50{ 51 int res = 0; 52 for ( int i = x; i >= 1 ; i = i - lowbit (i)) 53 { 54 for ( int j = y ; j >= 1 ; j = j - lowbit (j)) 55 { 56 57 res = res + c[i][j]; 58 } 59 } 60 return res; 61} 62int main() 63{ 64 int T; 65 cin>>T; 66 while (T--) 67 { 68 memset(c,0,sizeof(c)); 69 scanf("%d %d",&n,&t); 70 for ( int i = 1; i <= t; i ++ ) 71 { 72 char cmd; 73 cin>>cmd; 74 if (cmd=='C') 75 { 76 scanf("%d %d %d %d",&x1,&y1,&x2,&y2); 77// cout<<"*******"<<c[2][1]<<" "<<c[2][2]<<endl; 78 update (x1,y1,1); 79 update (x2+1,y1,1); 80 update (x1,y2+1,1); 81 update (x2+1,y2+1,1); 82// cout<<"*******"<<c[2][1]<<" "<<c[2][2]<<endl; 83 } 84 else 85 { 86 scanf("%d %d",&x,&y); 87 int tmp; 88// cout<<"sum(x)(y):"<<sum(x,y)<<endl; 89// cout<<"sum(x-1,y-1):"<<sum(x-1,y-1)<<endl; 90// cout<<"sum(x-1,y):"<<sum(x-1,y)<<endl; 91// cout<<"sum(x,y-1):"<<sum(x,y-1)<<endl; 92 tmp =sum(x,y)+sum(x-1,y-1)-sum(x-1,y)-sum(x,y-1); 93// cout<<"tmp:"<<tmp<<endl; 94 if (sum(x,y)%2==0) 95 cout<<0<<endl; 96 else cout<<1<<endl; 97 } 98// cout<<"*****************"<<endl; 99// for ( int ii = 1 ; ii <= n ; ii++) 100// { 101// for ( int jj = 1 ; jj <= n ; jj++ ) 102// { 103// cout<<c[ii][jj]<<" "; 104// } 105// cout<<endl; 106// } 107// cout<<"*************************"<<endl; 108// 109 } 110 cout<<endl; 111 } 112 113 return 0; 114}

这道题和之前做的树状数组略有不同。 以前的都是更新单点，查询区间，这次反了过来。 做法差不多。 如果更新区间【x,y】增加１ 那么只要 update (x,1),update (y+1,-1) 问单点的时候，sum(i)就是i点的值，而不是1..i的和。

Inversions **Time Limit:**250MS **Memory Limit:**4096KB 64bit IO Format:%I64d & %I64u Submit Status Description 180. Inversions # time limit per test: 0.25 sec. memory limit per test: 4096 KB input: standard output: standard There are N integers (1<=N<=65537) A1, A2,.. AN (0<=Ai<=10^9). You need to find amount of such pairs (i, j) that 1<=iA[j]. Input The first line of the input contains the number N. The second line contains N numbers A1…AN.

依然对算法，对acm充满热情。 只是比赛，组队赛。 心里满满的都是阴影，再也没有什么热情与感动。 连起队名这种事情我都不愿意想了。 起得再棒有什么用。 pacedect 这名字。 说起来好像有一个学期没和某妹子说话了。。。。。。。。

给出一个图书馆人员进出情况，问图书馆满足题意的最小容量是多少。 注意在初始之前图书馆里面可能就有人了，也就是说不是所有进入图书馆的人都会被给出。 我的做法是先统计出图书馆里面初始的人数，开一个布尔数组，初始全为false，如果一个人标记为 false 而且从 图书馆里出来了，就说明这个人初始是在图书馆里的。

给一个有序序列，问对于没一个数，和它相差最少和最多的数的位置。 代码实现 1/************************************************************************* 2 > File Name: code/cf/#314/A.cpp 3 > Author: 111qqz 4 > Email: rkz2013@126.com 5 > Created Time: 2015年08月06日 星期四 00时01分51秒 6 ************************************************************************/ 7 8#include<iostream> 9#include<iomanip> 10#include<cstdio> 11#include<algorithm> 12#include<cmath> 13#include<cstring> 14#include<string> 15#include<map> 16#include<set> 17#include<queue> 18#include<vector> 19#include<stack> 20#define y0 abc111qqz 21#define y1 hust111qqz 22#define yn hez111qqz 23#define j1 cute111qqz 24#define tm crazy111qqz 25#define lr dying111qqz 26using namespace std; 27#define REP(i, n) for (int i=0;i<int(n);++i) 28typedef long long LL; 29typedef unsigned long long ULL; 30const int inf = 0x7fffffff; 31const int N=2E5+7; 32LL a[N]; 33int main() 34{ 35 int n; 36 cin>>n; 37 a[0]=-inf; 38 a[n+1]=inf; 39 40 for ( int i = 1 ; i <= n ; i ++ ) 41 { 42 cin>>a[i]; 43 } 44 int mx = -1; 45 int mi = inf; 46 cout<<a[2]-a[1]<<" "<<a[n]-a[1]<<endl; 47 for ( int i = 2 ; i <= n-1 ; i++ ) 48 { 49 cout<<min(abs(a[i]-a[i-1]),abs(a[i+1]-a[i]))<<" "<<max(abs(a[i]-a[1]),abs(a[n]-a[i]))<<endl; 50 } 51 cout<<a[n]-a[n-1]<<" "<<a[n]-a[1]<<endl; 52 return 0; 53}

dfs 1A 代码实现 1/************************************************************************* 2 > File Name: code/whust/#9/K.cpp 3 > Author: 111qqz 4 > Email: rkz2013@126.com 5 > Created Time: 2015年08月05日 星期三 15时02分30秒 6 ************************************************************************/ 7 8#include<iostream> 9#include<iomanip> 10#include<cstdio> 11#include<algorithm> 12#include<cmath> 13#include<cstring> 14#include<string> 15#include<map> 16#include<set> 17#include<queue> 18#include<vector> 19#include<stack> 20#define y0 abc111qqz 21#define y1 hust111qqz 22#define yn hez111qqz 23#define j1 cute111qqz 24#define tm crazy111qqz 25#define lr dying111qqz 26using namespace std; 27#define REP(i, n) for (int i=0;i<int(n);++i) 28typedef long long LL; 29typedef unsigned long long ULL; 30const int inf = 0x7fffffff; 31int n ,m,ans; 32int d[50]; 33int on[50],off[50]; 34int u[50],v[50]; 35 36bool ok(int x,int y) 37{ 38 if ( !d[x] && !d[y] && on[x] == off[x] && on[y] == off[y] ) 39 return true; 40 if ( !d[x] && d[y] && on[x] == off[x] ) 41 return true; 42 if ( d[x] && !d[y] && on[y] == off[y] ) 43 return true; 44 if ( d[x] && d[y] ) 45 return true; 46 return false; 47} 48 49void dfs ( int i) 50{ 51 if (i==m) 52 { 53 ans++; 54 return; 55 } 56 int x = u[i]; 57 int y = v[i]; 58 d[x]--; 59 d[y]--; 60 on[x]++; 61 on[y]++; 62 if (ok(x,y)) 63 dfs (i+1); 64 on[x]--;on[y]--; 65 off[y]++;off[x]++; 66 if ( ok( x,y)) 67 dfs (i+1); 68 off[y]--; 69 off[x]--; 70 d[x]++; 71 d[y]++; 72} 73 74int main ( ) 75{ 76 int T; 77 cin>>T; 78 while ( T-- ) 79 { 80 ans = 0; 81 scanf ("%d %d",&n,&m); 82 memset (d,0,sizeof(d)); 83 memset (on,0,sizeof(on)); 84 memset (off,0,sizeof(off)); 85 for ( int i = 0 ; i < m ; i++ ) 86 { 87 scanf ("%d%d",&u[i],&v[i]); 88 d[u[i]]++; 89 d[v[i]]++; 90 } 91 dfs (0); 92 printf ( "%d\n" , ans ); 93 } 94}

这道题可以总结的地方不少。 １：对于一组乱序数列，每次只能交换相邻元素，达到有序交换的次数就是原数列中你逆序对的个数。 cf上好像总喜欢出这个题。。。我印象中就出现三次了。。。。。

poj 2481 题目链接 题意：给定n个区间，问对于每个区间，有多少个区间真包含该区间（真包含的意思是说，两个区间不能完全重合） 思路： 下面是一年前用树状数组过掉的时候写的题解： 和 star那道题差不多。

poj 2352题目链接 题意：给出n个星星的位置，一个星星的level定义为其左下角（不严格）星星的数量。 要求统计0到n-1 level的星星各有多少个。 下面是一年前写的树状数组的题解：

wa了两次，原因是在同一个点可能有多个基地。。。 所以用set 是错误的，应该用multiset 然后因为这道题看到了map+set实现离散化的另外一种写法 我的代码： 代码实现 1/************************************************************************* 2 > File Name: code/hdoj/4022.cpp 3 > Author: 111qqz 4 > Email: rkz2013@126.com 5 > Created Time: 2015年08月01日 星期六 04时37分20秒 6 ************************************************************************/ 7 8#include<iostream> 9#include<iomanip> 10#include<cstdio> 11#include<algorithm> 12#include<cmath> 13#include<cstring> 14#include<string> 15#include<map> 16#include<set> 17#include<queue> 18#include<vector> 19#include<stack> 20#define y0 abc111qqz 21#define y1 hust111qqz 22#define yn hez111qqz 23#define j1 cute111qqz 24#define tm crazy111qqz 25#define lr dying111qqz 26using namespace std; 27#define REP(i, n) for (int i=0;i<int(n);++i) 28typedef long long LL; 29typedef unsigned long long ULL; 30const int N=2E5+7; 31const int inf = 0x7fffffff; 32 33map<int,int>xmap,ymap; 34multiset<int>x[N]; 35multiset<int>y[N]; 36int main() 37{ 38 int n,m; 39 while (scanf("%d %d",&n,&m)!=EOF) 40 { 41 if (n==0&&m==0) break; 42 for ( int i = 1 ; i <= n ; i++) 43 { 44 x[i].clear(); 45 y[i].clear(); 46 } 47 xmap.clear(); 48 ymap.clear(); 49 int tx,ty; 50 int cntx=0,cnty=0; 51 for ( int i = 1 ; i <= n ; i++ ) 52 { 53 scanf("%d %d",&tx,&ty); 54 if (!xmap[tx]) xmap[tx]=++cntx; 55 if (!ymap[ty]) ymap[ty]=++cnty; 56 x[xmap[tx]].insert(ymap[ty]); 57 y[ymap[ty]].insert(xmap[tx]); 58 } 59 int c,d; 60 set<int>::iterator it; 61 for ( int i = 1; i <= m ; i++ ) 62 { 63 scanf("%d %d",&c,&d); 64 if (c==0) 65 { 66 cout<<x[xmap[d]].size()<<endl; 67 for ( it = x[xmap[d]].begin();it!=x[xmap[d]].end();it++) 68 { 69 y[*it].erase(xmap[d]); 70 } 71 x[xmap[d]].clear(); 72 } 73 else 74 { 75 cout<<y[ymap[d]].size()<<endl; 76 for ( it =y[ymap[d]].begin();it!=y[ymap[d]].end();it++) 77 { 78 x[*it].erase(ymap[d]); 79 80 } 81 y[ymap[d]].clear(); 82 } 83 } 84 printf("\n"); 85 } 86 87 return 0; 88}

Collision Detection # **Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1207 Accepted Submission(s): 367 ** Problem Description In physical simulations, video games and computational geometry, collision detection involves algorithms for checking for collision, i.e. intersection, of two given objects. Collision detection algorithms are a basic component of 3D video games. Without them, characters could go through walls and other obstacles. Here comes an interesting problem, given a ball and a cuboid, you need to detect whether they collide. We say that two objects collide if and only if they share at least one point.

Gunner II # **Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 1433 Accepted Submission(s): 540 ** Problem Description Long long ago, there was a gunner whose name is Jack. He likes to go hunting very much. One day he go to the grove. There are n birds and n trees. The i-th bird stands on the top of the i-th tree. The trees stand in straight line from left to the right. Every tree has its height. Jack stands on the left side of the left most tree. When Jack shots a bullet in height H to the right, the nearest bird which stands in the tree with height H will falls.