Posts
2015
hdu 3333 Turing Tree (求区间中不相同数的和，离线+线段树/树状数组)
# 题目链接
喵呜，离散树状数组。
这道题由于相同的值加和的时候只算一次，所以比较伤脑筋==
hdu 4267/poj 3468 A Simple Problem with Integers （分状态的树状数组）
树状数组，更新区间，查询单点，区别是加了一个a%k==0的条件限制…. 我们观察到k很小，于是按照k分类…. 每一类再按照余数分类，一共55棵树（1+2+3+…+10）
poj 2155- Matrix (树状数组，二维，更新区间，查询单点)
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}
sgu 180 - Inversions （离散化+树状数组）
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
hdu 5305 Friends （dfs）
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}
poj 2299 Ultra-QuickSort （树状数组＋离散化）
这道题可以总结的地方不少。
１：对于一组乱序数列，每次只能交换相邻元素，达到有序交换的次数就是原数列中你逆序对的个数。
poj 2481 Cows(树状数组||线段树)
poj 2481 题目链接
题意：给定n个区间，问对于每个区间，有多少个区间真包含该区间（真包含的意思是说，两个区间不能完全重合）