1. 逆序數(shù)
所謂逆序數(shù)，就是指一個(gè)序列S[i]，統(tǒng)計(jì)處于序列的每個(gè)數(shù)的比這個(gè)數(shù)大并且排在它前面的數(shù)的數(shù)目，然后對(duì)于所有數(shù)，把這個(gè)數(shù)目加起來(lái)求和就是了。
比如 4 3 1 2
4第一個(gè)，所以數(shù)目為0
3的前面是4，大于3的數(shù)目為1
1的前面是4 3 ，大于1的數(shù)目為2
2的前面是4 3 1，大于2的數(shù)目為2
所以逆序數(shù)為1+2+2 = 5
求逆序數(shù)的兩種方法
常規(guī)方法是按照逆序數(shù)的規(guī)則做，結(jié)果復(fù)雜度是O(n*n)，一般來(lái)說(shuō)，有兩種快速的求逆序數(shù)的方法
分別是歸并排序和樹(shù)狀數(shù)組法
2. 歸并排序
歸并排序是源于分而治之思想，詳細(xì)的過(guò)程可以查閱其他資料，總體思想是劃分一半，各自排好序后將兩個(gè)有序序列合并起來(lái)。
如何修改歸并排序求逆序數(shù)?
首先我們假設(shè)兩個(gè)有序序列 a[i]和b[i]，當(dāng)合并時(shí)：
由于a[i]已是有序，所以對(duì)于a[i]的各個(gè)元素來(lái)說(shuō)，排在它前面且比它大的數(shù)目都是0
當(dāng)b[i]中含有比a[i]小的元素時(shí)，我們必然將b[i]元素插到前面，那么就是說(shuō)，在b[i]原先位置到該插的位置中，所有數(shù)都比b[i]大且排在它前面
所以這是b[i]的數(shù)目為新插入位置newPos - 原來(lái)位置oldPos
那么對(duì)于一半的序列又怎么做呢？我們知道，歸并排序會(huì)繼續(xù)向下遞歸，而遞歸完成返回后將是兩組有序的序列，并且拿到局部的逆序數(shù)，
所以在Merge函數(shù)中添加這一計(jì)數(shù)操作即可
代碼示例如下：
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. 樹(shù)狀數(shù)組
求逆序數(shù)的另外一種方法是使用樹(shù)狀數(shù)組
對(duì)于小數(shù)據(jù)，可以直接插入樹(shù)狀數(shù)組，對(duì)于大數(shù)據(jù)，則需要離散化，所謂離散化，就是將
100 200 300 400 500 ---> 1 2 3 4 5
這里主要利用樹(shù)狀數(shù)組解決計(jì)數(shù)問(wèn)題。
首先按順序把序列a[i]每個(gè)數(shù)插入到樹(shù)狀數(shù)組中，插入的內(nèi)容是1，表示放了一個(gè)數(shù)到樹(shù)狀數(shù)組中。
然后使用sum操作獲取當(dāng)前比a[i]小的數(shù)，那么當(dāng)前i - sum則表示當(dāng)前比a[i]大的數(shù)，如此反復(fù)直到所有數(shù)都統(tǒng)計(jì)完，
比如
4 3 1 2
i = 1 : 插入 4 : update(4,1)，sum(4)返回1，那么當(dāng)前比4大的為 i - 1 = 0;
i = 2 : 插入 3 : update(3,1)，sum(3)返回1，那么當(dāng)前比3大的為 i - 1 = 1;
i = 3 : 插入 1 : update(1,1)，sum(1)返回1，那么當(dāng)前比1大的為 i - 1 = 2;
i = 4 : 插入 2 : update(2,1)，sum(2)返回2，那么當(dāng)前比2大的為 i - 2 = 2;
過(guò)程很明了，所以逆序數(shù)為1+2+2=5
代碼示例如下：
//樹(shù)狀數(shù)組
__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;
}
//求逆序數(shù)
__int64 ret = 0;
for (__int64 i = 0; i < k; ++i)
{
update(a[i],1);
ret += (i+1) - sum(a[i]);
}
求逆序數(shù)的題目有：
http://poj.org/problem?id=2299
http://poj.org/problem?id=3067
posted @
2011-11-17 20:46 bennycen 閱讀(10803) |
評(píng)論 (0) |
編輯 收藏
摘要: 題意：判斷一個(gè)給定的圖，沒(méi)有環(huán)，而且存在一個(gè)鏈，圖上的所有點(diǎn)或者在這條鏈上或者在其的鄰居題解：1.判斷環(huán)：對(duì)于無(wú)向圖：如果 點(diǎn) < 邊 + 1，則存在環(huán)；然后使用并查集進(jìn)一步判斷環(huán)的存在2.判斷是否存在鏈?zhǔn)紫冉y(tǒng)計(jì)各個(gè)點(diǎn)的度，然后對(duì)于度為1的點(diǎn)，將其相連的邊刪掉，再統(tǒng)計(jì)新圖的度，這時(shí)新圖應(yīng)該剩下一條鏈，也就是說(shuō)，新圖的不存在大于2個(gè)度為1的點(diǎn)，而且這個(gè)點(diǎn)在舊圖的度是大于1的。代碼：
Code...
閱讀全文
posted @
2011-11-17 10:50 bennycen 閱讀(6004) |
評(píng)論 (0) |
編輯 收藏
題意：烘干機(jī)，給出一堆衣服的水分a[i]，在不加烘干機(jī)情況下自動(dòng)每一分鐘減少1水分，每分鐘可以變改衣服(i)到烘干機(jī)中，每分鐘減少k水分，求最少需要多少時(shí)間。
題解：第一時(shí)間就想到使用二分枚據(jù)答案+驗(yàn)證這種思路，不過(guò)這題還是有些陷阱需要注意。
1. 驗(yàn)證答案時(shí)，如果 a[i] <= mid，讓它自然烘干即可 ； 如果a[i] > mid，那么烘干這件衣服可以分成兩段時(shí)間：使用烘干機(jī)時(shí)間x1 + 自然烘干時(shí)間x2，那么可以列出等式：mid = x1 + x2; a[i] <= kx1+x2；于是得x1 >= (a[i] -mid)/(k-1);即得使用烘干機(jī)的最少時(shí)間x1
2.注意當(dāng)k==1時(shí)，k-1 == 0，需要特殊處理，直接打出ans = maxV
3.注意當(dāng)求left+right時(shí)，結(jié)果可能超出范圍，正確的方法應(yīng)該是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 閱讀(1523) |
評(píng)論 (1) |
編輯 收藏
摘要: 大意：給出一個(gè)區(qū)域圖和Click的坐標(biāo)，求擊中區(qū)域的周長(zhǎng)題解：爆搜，BFS出整個(gè)連通域，注意求周長(zhǎng)是上下左右的連通域，所以將8連域分成兩個(gè)4連域，然后在BFS時(shí)一并計(jì)算出周長(zhǎng)代碼：
Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/-->#include&n...
閱讀全文
posted @
2011-11-09 12:34 bennycen 閱讀(1530) |
評(píng)論 (1) |
編輯 收藏
摘要: 題目大意：對(duì)以下數(shù)組：struct Cow { int score; int aid;}cows[C];共C個(gè)cow，選出N個(gè)(N為奇數(shù))，使其aid的和在不大于給定的數(shù)F下，使這N個(gè)數(shù)的score的中位數(shù)最大。題解：依然使用堆，我們首先對(duì)牛的score進(jìn)行排序，然后我們從第N/2頭牛開(kāi)始，到第C-N/2頭牛結(jié)束。每次假設(shè)第i頭牛就是中位數(shù)的牛，所以我們只需要計(jì)算這頭牛的前N/...
閱讀全文
posted @
2011-10-19 11:04 bennycen 閱讀(2498) |
評(píng)論 (1) |
編輯 收藏
摘要: 編譯過(guò)的二進(jìn)制代碼本身是一種數(shù)據(jù)結(jié)構(gòu)，在代碼被載入內(nèi)存執(zhí)行的時(shí)候，由操作系統(tǒng)對(duì)這種數(shù)據(jù)結(jié)構(gòu)進(jìn)行操作，具體到Win32平臺(tái)，就是所謂的PE文件頭。 對(duì)于Windows系統(tǒng),源代碼是如何轉(zhuǎn)化為二進(jìn)制代碼?全局變量存儲(chǔ)在什么地方,如何初始化?共享變量是如何工作?理解PE文件格式能更好地理解上面的問(wèn)題.舉個(gè)例子，我們使用C++編寫(xiě)源代碼，這些源代碼被編譯器翻譯成obj格式的目標(biāo)文件，...
閱讀全文
posted @
2011-09-02 20:18 bennycen 閱讀(2379) |
評(píng)論 (2) |
編輯 收藏這幾天研究了一下CUDA，發(fā)現(xiàn)其并行的思想和普通的CPU多線程思想不太一致，但還是挺不錯(cuò)。主要是將任務(wù)劃分成一個(gè)個(gè)block，然后每個(gè)block里面再劃分成細(xì)的線程。然后每個(gè)線程做自己做的
事情。這種并行思想很適用于像矩陣運(yùn)算這些元素與元素之間的運(yùn)算并不耦合得很厲害，但整體數(shù)據(jù)很大的情況，這只是我對(duì)CUDA的初步感覺(jué)。
矩陣相乘的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;耦合程度很小，所以我們可以通過(guò)劃分區(qū)域的方法，讓每個(gè)線程負(fù)責(zé)一個(gè)區(qū)域。
怎么劃分呢？首先最初的想法是讓每一個(gè)線程計(jì)算一個(gè)C(i,j)，那么估算一下，應(yīng)該需要height_c*width_c，也就是ha*wb個(gè)線程。進(jìn)一步，我們將矩陣按一個(gè)大方格Grid劃分，如果一個(gè)
方格Grid大小是16*16，那么矩陣80*48的可以表示為5(*16) * 3(*16)，即16*16個(gè)大格子(block)，每一個(gè)格子內(nèi)，自然就是(height_c/16) *(width_c/16)個(gè)線程了。
好了，劃分完后，內(nèi)核代碼如下：
計(jì)算版本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)負(fù)責(zé)計(jì)算C(row,col)
for (int i = 0; i < _wa; ++i)
{
sum += _A[row*_wa + i]*_B[i*_wb + col];
}
_C[row*_wb + col] = sum;
}
另外一種思路，我們不讓每一個(gè)線程完整計(jì)算一個(gè)C(i,j)，通過(guò)C(i,j) = sum { A(i,k)*B(k,j) }發(fā)現(xiàn)，我們還可以再細(xì)度劃分：
Csub(i,j) = sum{A(i,ksub+offsetA)*B(ksub+offsetB,j)} 0<=ksub < blockSize
C(i,j) = sum{Csub(i,j)}
就是把矩陣分成n*n個(gè)大的子塊，然后每一個(gè)block負(fù)責(zé)計(jì)算子塊i 和 子塊j的子乘積，計(jì)算完畢后加起來(lái)則可。這里主要使用了共享顯存作優(yōu)化。
計(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];
//每個(gè)線程負(fù)責(zé)一個(gè)元素拷貝
As[ty][tx] = _A[a + _wa*ty + tx];
Bs[ty][tx] = _B[b + _wb*ty + tx];
__syncthreads();
//每個(gè)線程負(fù)責(zé)計(jì)算一個(gè)子塊i 和 子塊j的子乘積
for (int k = 0; k < BLOCK_SIZE; ++k)
{
cSub += As[ty][k]*Bs[k][tx];
}
__syncthreads();
}
//全局地址，向全局寄存器寫(xiě)回去
//一個(gè)線程負(fù)責(zé)一個(gè)元素，一個(gè)block負(fù)責(zé)一個(gè)子塊
int cIndex = (by*BLOCK_SIZE + ty)*_wb + (bx*BLOCK_SIZE + tx);
_C[cIndex] = cSub;
}
最后寫(xiě)一個(gè)面向Host的接口函數(shù)：
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);
}
調(diào)用的主函數(shù)如下：
#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;
}
運(yùn)算結(jié)果如下：
版本0：
版本1：
可以看出，GPU并行性能比CPU好很多，而且版本1優(yōu)于版本0
整個(gè)工程下載：
/Files/bennycen/CUDAMatrixMul.rar
posted @
2011-07-26 17:01 bennycen 閱讀(4641) |
評(píng)論 (1) |
編輯 收藏
題意：
給出兩種操作：ADD(x)，將x添加到有序列表中；GET()返回全局迭代器所指的值，其中迭代器在GET操作后會(huì)自添加1
題解：
剛開(kāi)始直接手打鏈表模擬，結(jié)果超時(shí)。這時(shí)應(yīng)使用另外一種方法：使用大頂堆和小頂堆。
其中，對(duì)于序列S[1..n]，及表示迭代器位置的index，大頂堆維護(hù)排序后的S[1..index-1]，小頂堆維護(hù)
排序后的S[index..n],例如S[1..n] = 1,2,3,4,5,6,7，index = 4，則大頂堆為{1,2,3}，小頂堆為{4,5,6,7}
為什么要這樣維護(hù)呢？因?yàn)楫?dāng)小堆最小的元素都大于大堆最大的元素時(shí)，那么序列中排第n個(gè)就是小堆最小的數(shù)了。
我們假設(shè)第k趟GET()后，有以下情景(GET后k自動(dòng)加1)：
大頂堆：S[1..k]，堆頂元素為S[k]，小頂堆：S[k+1,n]，堆頂元素為S[k+1]，然后每當(dāng)添加一個(gè)元素newE時(shí)，先添加到大頂堆中，這時(shí)如果出現(xiàn)大頂堆數(shù)大于小頂堆的數(shù)時(shí)，理應(yīng)交換。
代碼：
#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 閱讀(1706) |
評(píng)論 (0) |
編輯 收藏
摘要: 題意：如果單詞A的結(jié)尾字母與單詞B的首字母相同，那么可以認(rèn)為是A到B相通。給出一系列單詞，求這些詞按照某種排列能否串通。題解：如果直接按照題意建模，以單詞為頂點(diǎn)，邊表示兩兩相通，那么將會(huì)得到哈密頓回路模型。顯然是很難解的。換一種方式，以字母為頂點(diǎn)，邊表示傳送的單詞，那么就得到歐拉回路模型的圖，可以按照歐拉定理求解。以下給出Euler圖的相關(guān)知識(shí)：Euler回路：G中經(jīng)過(guò)每條邊一次且僅一次的回路Eu...
閱讀全文
posted @
2011-06-02 11:56 bennycen 閱讀(1550) |
評(píng)論 (0) |
編輯 收藏
摘要: 題意：給出一個(gè)無(wú)向圖，求在已知頂點(diǎn)v0的度不超過(guò)K的情況下，所得的最小生成樹(shù)題解：首先不考慮v0點(diǎn)，先求得v1-v(n-1)的MST，然后分兩種情況考慮：令d為v0的度情況1 ： 當(dāng)d == 1，時(shí) ，答案顯然是min{edge(0,i)}+MST{v1-v(n-1)}當(dāng) 1 < d <= K時(shí)，考慮逐步添加一條{0-i}邊，添加邊后勢(shì)必構(gòu)成回路，然后在回路中找到權(quán)值最大的邊，然后在M...
閱讀全文
posted @
2011-06-02 11:49 bennycen 閱讀(1374) |
評(píng)論 (0) |
編輯 收藏