1. 逆序數
所謂逆序數，就是指一個序列S[i]，統計處于序列的每個數的比這個數大并且排在它前面的數的數目，然后對于所有數，把這個數目加起來求和就是了。
比如 4 3 1 2
4第一個，所以數目為0
3的前面是4，大于3的數目為1
1的前面是4 3 ，大于1的數目為2
2的前面是4 3 1，大于2的數目為2
所以逆序數為1+2+2 = 5
求逆序數的兩種方法
常規方法是按照逆序數的規則做，結果復雜度是O(n*n)，一般來說，有兩種快速的求逆序數的方法
分別是歸并排序和樹狀數組法
2. 歸并排序
歸并排序是源于分而治之思想，詳細的過程可以查閱其他資料，總體思想是劃分一半，各自排好序后將兩個有序序列合并起來。
如何修改歸并排序求逆序數?
首先我們假設兩個有序序列 a[i]和b[i]，當合并時：
由于a[i]已是有序，所以對于a[i]的各個元素來說，排在它前面且比它大的數目都是0
當b[i]中含有比a[i]小的元素時，我們必然將b[i]元素插到前面，那么就是說，在b[i]原先位置到該插的位置中，所有數都比b[i]大且排在它前面
所以這是b[i]的數目為新插入位置newPos - 原來位置oldPos
那么對于一半的序列又怎么做呢？我們知道，歸并排序會繼續向下遞歸，而遞歸完成返回后將是兩組有序的序列，并且拿到局部的逆序數，
所以在Merge函數中添加這一計數操作即可
代碼示例如下：
int L[M];
int R[M];
const int Max = 1 <<30;
__int64 change = 0;
void Merge(int *data,int left,int divide,int right)
{
int lengthL = divide - left;
int lengthR = right - divide;
for(int i = 0; i < lengthL; ++i)
{
L[i] = data[left + i];
}
for(int i = 0; i < lengthR; ++i)
{
R[i] = data[divide + i];
}
L[lengthL] = R[lengthR] = Max;
int i = 0;
int j = 0;
for(int k = left; k < right; ++k)
{
if(L[i] <= R[j])
{
data[k] = L[i];
++i;
}
else
{
change += divide - i - left ;
data[k] = R[j];
++j;
}
}
}
void MergeSort(int *data,int left,int right)
{
if(left < right -1)
{
int divide = (left + right)/2;
MergeSort(data,left,divide);
MergeSort(data,divide,right);
Merge(data,left,divide,right);
}
}
3. 樹狀數組
求逆序數的另外一種方法是使用樹狀數組
對于小數據，可以直接插入樹狀數組，對于大數據，則需要離散化，所謂離散化，就是將
100 200 300 400 500 ---> 1 2 3 4 5
這里主要利用樹狀數組解決計數問題。
首先按順序把序列a[i]每個數插入到樹狀數組中，插入的內容是1，表示放了一個數到樹狀數組中。
然后使用sum操作獲取當前比a[i]小的數，那么當前i - sum則表示當前比a[i]大的數，如此反復直到所有數都統計完，
比如
4 3 1 2
i = 1 : 插入 4 : update(4,1)，sum(4)返回1，那么當前比4大的為 i - 1 = 0;
i = 2 : 插入 3 : update(3,1)，sum(3)返回1，那么當前比3大的為 i - 1 = 1;
i = 3 : 插入 1 : update(1,1)，sum(1)返回1，那么當前比1大的為 i - 1 = 2;
i = 4 : 插入 2 : update(2,1)，sum(2)返回2，那么當前比2大的為 i - 2 = 2;
過程很明了，所以逆序數為1+2+2=5
代碼示例如下：
//樹狀數組
__int64 sums[1005];
int len;
inline int lowbit(int t)
{
return t & (t^(t-1));
}
void update(int _x,int _value)
{
while(_x <= len)
{
sums[_x] += _value;
_x += lowbit(_x);
}
}
__int64 sum(int _end)//get sum[1_end]
{
__int64 ret = 0;
while(_end > 0)
{
ret += sums[_end];
_end -= lowbit(_end);
}
return ret;
}
//求逆序數
__int64 ret = 0;
for (__int64 i = 0; i < k; ++i)
{
update(a[i],1);
ret += (i+1) - sum(a[i]);
}
求逆序數的題目有：
http://poj.org/problem?id=2299
http://poj.org/problem?id=3067
posted @
2011-11-17 20:46 bennycen 閱讀(10811) |
評論 (0) |
編輯 收藏
摘要: 題意：判斷一個給定的圖，沒有環，而且存在一個鏈，圖上的所有點或者在這條鏈上或者在其的鄰居題解：1.判斷環：對于無向圖：如果 點 < 邊 + 1，則存在環；然后使用并查集進一步判斷環的存在2.判斷是否存在鏈首先統計各個點的度，然后對于度為1的點，將其相連的邊刪掉，再統計新圖的度，這時新圖應該剩下一條鏈，也就是說，新圖的不存在大于2個度為1的點，而且這個點在舊圖的度是大于1的。代碼：
Code...
閱讀全文
posted @
2011-11-17 10:50 bennycen 閱讀(6014) |
評論 (0) |
編輯 收藏
題意：烘干機，給出一堆衣服的水分a[i]，在不加烘干機情況下自動每一分鐘減少1水分，每分鐘可以變改衣服(i)到烘干機中，每分鐘減少k水分，求最少需要多少時間。
題解：第一時間就想到使用二分枚據答案+驗證這種思路，不過這題還是有些陷阱需要注意。
1. 驗證答案時，如果 a[i] <= mid，讓它自然烘干即可 ； 如果a[i] > mid，那么烘干這件衣服可以分成兩段時間：使用烘干機時間x1 + 自然烘干時間x2，那么可以列出等式：mid = x1 + x2; a[i] <= kx1+x2；于是得x1 >= (a[i] -mid)/(k-1);即得使用烘干機的最少時間x1
2.注意當k==1時，k-1 == 0，需要特殊處理，直接打出ans = maxV
3.注意當求left+right時，結果可能超出范圍，正確的方法應該是left + (right - left)*0.5;
#include <stdio.h>
const int N = 100005;
int n;
int a[N];
int k;
bool check(int _value)
{
int cnt = 0;
for (int i = 0; i < n; ++i)
{
if (a[i] > _value)
{
double kk = ((double)(a[i] - _value))/(k-1);
cnt += (int)kk;
if (kk - (int)kk > 0)
{
++cnt;
}
if (cnt > _value)
{
return false;
}
}
}
return (cnt <= _value);
}
int BinarySearch(int _low,int _high)
{
int left = _low;
int right = _high;
int mid;
int ans = _high;
while(left <= right)
{
mid = (left+(right-left)*0.5);
if (check(mid))
{
ans = mid;
right = mid - 1;
}
else
{
left = mid + 1;
}
}
return ans;
}
void Test()
{
int maxV = 0;
for (int i = 0; i < n; ++i)
{
scanf("%d",&a[i]);
if (maxV < a[i])
{
maxV = a[i];
}
}
scanf("%d",&k);
if (k == 1)
{
printf("%d\n",maxV);
}
else
printf("%d\n",BinarySearch(0,maxV));
}
int main()
{
while(scanf("%d",&n) != EOF)
{
Test();
}
return 0;
}
posted @
2011-11-09 12:45 bennycen 閱讀(1532) |
評論 (1) |
編輯 收藏
摘要: 大意：給出一個區域圖和Click的坐標，求擊中區域的周長題解：爆搜，BFS出整個連通域，注意求周長是上下左右的連通域，所以將8連域分成兩個4連域，然后在BFS時一并計算出周長代碼：
Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/-->#include&n...
閱讀全文
posted @
2011-11-09 12:34 bennycen 閱讀(1535) |
評論 (1) |
編輯 收藏
摘要: 題目大意：對以下數組：struct Cow { int score; int aid;}cows[C];共C個cow，選出N個(N為奇數)，使其aid的和在不大于給定的數F下，使這N個數的score的中位數最大。題解：依然使用堆，我們首先對牛的score進行排序，然后我們從第N/2頭牛開始，到第C-N/2頭牛結束。每次假設第i頭牛就是中位數的牛，所以我們只需要計算這頭牛的前N/...
閱讀全文
posted @
2011-10-19 11:04 bennycen 閱讀(2503) |
評論 (1) |
編輯 收藏
摘要: 編譯過的二進制代碼本身是一種數據結構，在代碼被載入內存執行的時候，由操作系統對這種數據結構進行操作，具體到Win32平臺，就是所謂的PE文件頭。 對于Windows系統,源代碼是如何轉化為二進制代碼?全局變量存儲在什么地方,如何初始化?共享變量是如何工作?理解PE文件格式能更好地理解上面的問題.舉個例子，我們使用C++編寫源代碼，這些源代碼被編譯器翻譯成obj格式的目標文件，...
閱讀全文
posted @
2011-09-02 20:18 bennycen 閱讀(2392) |
評論 (2) |
編輯 收藏這幾天研究了一下CUDA，發現其并行的思想和普通的CPU多線程思想不太一致，但還是挺不錯。主要是將任務劃分成一個個block，然后每個block里面再劃分成細的線程。然后每個線程做自己做的
事情。這種并行思想很適用于像矩陣運算這些元素與元素之間的運算并不耦合得很厲害，但整體數據很大的情況，這只是我對CUDA的初步感覺。
矩陣相乘的CPU程序如下：
//C = A*B
void MatrixMulCPU(float* _C,const float *_A,const float *_B,int _wa,int _ha,int _wb)
{
float sum = 0;
for (int i = 0; i < _ha; ++i)
{
for (int j = 0; j < _wb; ++j)
{
sum = 0;
for (int k = 0; k < _wa; ++k)
{
sum += (float)_A[i*_wa+k]*(float)_B[k*_wb+ j];
}
_C[i*_wb+j] = (float)sum;
}
}
}
從上面可以看出，C(i,j) = sum { A(i,k)*B(k,j) } 0<=k < _wa;耦合程度很小，所以我們可以通過劃分區域的方法，讓每個線程負責一個區域。
怎么劃分呢？首先最初的想法是讓每一個線程計算一個C(i,j)，那么估算一下，應該需要height_c*width_c，也就是ha*wb個線程。進一步，我們將矩陣按一個大方格Grid劃分，如果一個
方格Grid大小是16*16，那么矩陣80*48的可以表示為5(*16) * 3(*16)，即16*16個大格子(block)，每一個格子內，自然就是(height_c/16) *(width_c/16)個線程了。
好了，劃分完后，內核代碼如下：
計算版本0：
__global__ void matrix_kernel_0(float* _C,const float* _A,const float *_B,int _wa,int _wb)
{
float sum = 0;
//找出該線程所在的行列
int row = blockIdx.y*blockDim.y + threadIdx.y;
int col = blockIdx.x*blockDim.x + threadIdx.x;
//線程Thread(row,col)負責計算C(row,col)
for (int i = 0; i < _wa; ++i)
{
sum += _A[row*_wa + i]*_B[i*_wb + col];
}
_C[row*_wb + col] = sum;
}
另外一種思路，我們不讓每一個線程完整計算一個C(i,j)，通過C(i,j) = sum { A(i,k)*B(k,j) }發現，我們還可以再細度劃分：
Csub(i,j) = sum{A(i,ksub+offsetA)*B(ksub+offsetB,j)} 0<=ksub < blockSize
C(i,j) = sum{Csub(i,j)}
就是把矩陣分成n*n個大的子塊，然后每一個block負責計算子塊i 和 子塊j的子乘積，計算完畢后加起來則可。這里主要使用了共享顯存作優化。
計算版本1：
__global__ void matrix_kernel_1(float* _C,const float* _A,const float *_B,int _wa,int _wb)
{
int bx = blockIdx.x;
int by = blockIdx.y;
int tx = threadIdx.x;
int ty = threadIdx.y;
//該block要處理的A
int aBegin = _wa*(by*BLOCK_SIZE);//A(0,by)
int aEnd = aBegin + _wa - 1;
int aStep = BLOCK_SIZE;//offsetA
int bBegin = BLOCK_SIZE*bx;//B(bx,0)
int bStep = BLOCK_SIZE*_wb;//offsetB
float cSub = 0;
for (int a = aBegin,b = bBegin; a <= aEnd; a += aStep,b += bStep)
{
__shared__ float As[BLOCK_SIZE][BLOCK_SIZE];
__shared__ float Bs[BLOCK_SIZE][BLOCK_SIZE];
//每個線程負責一個元素拷貝
As[ty][tx] = _A[a + _wa*ty + tx];
Bs[ty][tx] = _B[b + _wb*ty + tx];
__syncthreads();
//每個線程負責計算一個子塊i 和 子塊j的子乘積
for (int k = 0; k < BLOCK_SIZE; ++k)
{
cSub += As[ty][k]*Bs[k][tx];
}
__syncthreads();
}
//全局地址，向全局寄存器寫回去
//一個線程負責一個元素，一個block負責一個子塊
int cIndex = (by*BLOCK_SIZE + ty)*_wb + (bx*BLOCK_SIZE + tx);
_C[cIndex] = cSub;
}
最后寫一個面向Host的接口函數：
void matrixMulGPU(float* _C,const float *_A,const float *_B,int _wa,int _ha,int _wb)
{
float* d_a = myNewOnGPU<float>(_wa*_ha);
float* d_b = myNewOnGPU<float>(_wb*_wa);
float* d_c = myNewOnGPU<float>(_wb*_ha);
copyFromCPUToGPU(_A,d_a,_wa*_ha);
copyFromCPUToGPU(_B,d_b,_wb*_wa);
dim3 threads(BLOCK_SIZE,BLOCK_SIZE);
dim3 blocks(WC/BLOCK_SIZE,HC/BLOCK_SIZE);
matrix_kernel_0<<<blocks,threads>>>(d_c,d_a,d_b,_wa,_wb);
cudaThreadSynchronize();
copyFromGPUToCPU(d_c,_C,_wb*_ha);
myDeleteOnGPU(d_a);
myDeleteOnGPU(d_b);
myDeleteOnGPU(d_c);
}
調用的主函數如下：
#include <stdio.h>
#include <cuda_runtime.h>
#include <cutil.h>
#include <cutil_inline.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <string.h>
#include <Windows.h>
#include "CUDACommon.h"
#include "MatrixMulCPU.h"
#include "MatrixMulGPU.h"
void randomInit(float* _data,int _size)
{
for (int i = 0; i < _size; ++i)
{
_data[i] = rand()/(float)RAND_MAX;
}
}
bool checkError(const float* _A,const float* _B,int _size)
{
for (int i = 0 ; i < _size; ++i)
{
if (fabs(_A[i] - _B[i]) > 1.0e-3)
{
printf("%f \t %f\n",_A[i],_B[i]);
return false;
}
}
return true;
}
int main(int argc, char* argv[])
{
srand(13);
if(!InitCUDA()) {
return 0;
}
float* A = myNewOnCPU<float>(WA*HA);
float* B = myNewOnCPU<float>(WB*HB);
randomInit(A,WA*HA);
randomInit(B,WB*HB);
float* C = myNewOnCPU<float>(WC*HC);
memset(C,0,sizeof(float)*WC*HC);
float* C2 = myNewOnCPU<float>(WC*HC);
memset(C2,0,sizeof(float)*WC*HC);
unsigned int tick1 = GetTickCount();
MatrixMulCPU(C2,A,B,WA,HA,WB);
printf("CPU use Time : %dms\n",GetTickCount() - tick1);
unsigned int timer = 0;
cutilCheckError(cutCreateTimer(&timer));
cutilCheckError(cutStartTimer(timer));
{
matrixMulGPU(C,A,B,WA,HA,WB);
}
cutilCheckError(cutStopTimer(timer));
printf("GPU use time: %f (ms) \n", cutGetTimerValue(timer));
cutilCheckError(cutDeleteTimer(timer));
if (checkError(C,C2,WC*HC))
{
printf("Accept\n");
}
else
{
printf("Worng Answer\n");
}
myDeleteOnCPU(A);
myDeleteOnCPU(B);
myDeleteOnCPU(C);
myDeleteOnCPU(C2);
return 0;
}
運算結果如下：
版本0：
版本1：
可以看出，GPU并行性能比CPU好很多，而且版本1優于版本0
整個工程下載：
/Files/bennycen/CUDAMatrixMul.rar
posted @
2011-07-26 17:01 bennycen 閱讀(4649) |
評論 (1) |
編輯 收藏
題意：
給出兩種操作：ADD(x)，將x添加到有序列表中；GET()返回全局迭代器所指的值，其中迭代器在GET操作后會自添加1
題解：
剛開始直接手打鏈表模擬，結果超時。這時應使用另外一種方法：使用大頂堆和小頂堆。
其中，對于序列S[1..n]，及表示迭代器位置的index，大頂堆維護排序后的S[1..index-1]，小頂堆維護
排序后的S[index..n],例如S[1..n] = 1,2,3,4,5,6,7，index = 4，則大頂堆為{1,2,3}，小頂堆為{4,5,6,7}
為什么要這樣維護呢？因為當小堆最小的元素都大于大堆最大的元素時，那么序列中排第n個就是小堆最小的數了。
我們假設第k趟GET()后，有以下情景(GET后k自動加1)：
大頂堆：S[1..k]，堆頂元素為S[k]，小頂堆：S[k+1,n]，堆頂元素為S[k+1]，然后每當添加一個元素newE時，先添加到大頂堆中，這時如果出現大頂堆數大于小頂堆的數時，理應交換。
代碼：
#include <queue>
#include <stdio.h>
using namespace std;
int m,n;
int sequence[30005];
struct cmp1
{
bool operator()(const int a,const int b)
{
return a>b;
}
};
struct cmp2
{
bool operator()(const int a,const int b)
{
return a<b;
}
};
void Test()
{
priority_queue<int,vector<int>,cmp1>q1;//小堆
priority_queue<int,vector<int>,cmp2>q2;//大堆
for (int i = 0; i < m; ++i)
{
scanf("%d",&sequence[i]);
}
int op;
int k = 0;
for (int i = 0; i < n; ++i)
{
scanf("%d",&op);
while(k < op)
{
q1.push(sequence[k]);
if (!q2.empty() && q1.top() < q2.top())
{
int t1 = q1.top();
q1.pop();
int t2 = q2.top();
q2.pop();
q1.push(t2);
q2.push(t1);
}
++k;
}
printf("%d\n",q1.top());
q2.push(q1.top());
q1.pop();
}
}
int main()
{
while(scanf("%d %d",&m,&n) != EOF)
{
Test();
}
return 0;
}
posted @
2011-06-02 15:34 bennycen 閱讀(1713) |
評論 (0) |
編輯 收藏
摘要: 題意：如果單詞A的結尾字母與單詞B的首字母相同，那么可以認為是A到B相通。給出一系列單詞，求這些詞按照某種排列能否串通。題解：如果直接按照題意建模，以單詞為頂點，邊表示兩兩相通，那么將會得到哈密頓回路模型。顯然是很難解的。換一種方式，以字母為頂點，邊表示傳送的單詞，那么就得到歐拉回路模型的圖，可以按照歐拉定理求解。以下給出Euler圖的相關知識：Euler回路：G中經過每條邊一次且僅一次的回路Eu...
閱讀全文
posted @
2011-06-02 11:56 bennycen 閱讀(1553) |
評論 (0) |
編輯 收藏
摘要: 題意：給出一個無向圖，求在已知頂點v0的度不超過K的情況下，所得的最小生成樹題解：首先不考慮v0點，先求得v1-v(n-1)的MST，然后分兩種情況考慮：令d為v0的度情況1 ： 當d == 1，時 ，答案顯然是min{edge(0,i)}+MST{v1-v(n-1)}當 1 < d <= K時，考慮逐步添加一條{0-i}邊，添加邊后勢必構成回路，然后在回路中找到權值最大的邊，然后在M...
閱讀全文
posted @
2011-06-02 11:49 bennycen 閱讀(1378) |
評論 (0) |
編輯 收藏