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
ACM
2015
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个区间，问对于每个区间，有多少个区间真包含该区间（真包含的意思是说，两个区间不能完全重合）
hdoj 2436 Collision Detection
Collision Detection # **Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1207 Accepted Submission(s): 367 **
hdu 5233 Gunner II (bc #42 B) （离散化）
Gunner II # **Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 1433 Accepted Submission(s): 540 **
bc #43(hdu 5265) pog loves szh II （单调性优化）
pog loves szh II # **Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 2115 Accepted Submission(s): 609 **
sgu 455. Sequence analysis （floyd 判圈算法，O(1)空间复杂度求循环节）
455. Sequence analysis # 比赛的时候逗了，往看空间限制了….