這一題題目有些長，不過這不影響它是一道水題。
題意描述：
題中描述了兩種情況，當輸入數據以'P'開頭時，表示輸入的是1~N的一個排列，要求輸出每個數前面比該數大的數字的個數，輸出結果時順序為數字1的在前，數字N的在最后。第二種情況正好相反，給出每個數字前面比該數大的數字的個數，要求輸出原序列。
第一種情況好說，主要是第二種情況。情況二的解法是按從后往前順序確定原序列，即先確定數字N的位置，再確定數字N-1的位置……直到所有數字位置確定。期間主要是元素的插入操作。
#include<stdio.h>
#include<stdlib.h>
#define LEN 60
int num[LEN]; //輸入，
int rs[LEN];//所求結果，兩種情況的結果都用rs[]記錄。
int N;
void fP()
{
int i, j, k;
int ps;
for(i = 1; i <= N; i++)
{
ps = 0;
while(num[++ps] != i);
int count = 0;
for(k = 1; k < ps; k++)
if(num[k] > i)
count++;
rs[i] = count;
}
}
void Insert(int ps, int insertnum, int len)//插入函數
{
int i, j;
for(i = len; i >= ps; i--)
rs[i + 1] = rs[i];
rs[ps] = insertnum;
}
void fI()
{
int i, j;
int len;
rs[1] = N;
len = 1;
for(i = N - 1; i >= 1; i--)
{
int ps = num[i] + 1;
Insert(ps, i, len);
len++;
}
}
int main()
{
int i, j;
char c;
scanf("%d", &N);
while(N != 0)
{
getchar();
c = getchar();
for(i = 1; i <= N; i++)
scanf("%d", &num[i]);
if(c == 'P')
fP();
else
fI();
for(i = 1; i < N; i++)
printf("%d ", rs[i]);
printf("%d\n", rs[i]);
scanf("%d", &N);
}
//system("pause");
}posted @
2012-08-02 16:19 小鼠標 閱讀(254) |
評論 (0) |
編輯 收藏二分查找，是一種針對有序序列的查找方式，每次迭代會縮小一半的查找范圍，一次查找的時間復雜度為O(logN)。
簡單說一下二分查找過程：在有序序列seq[]中找一個數n，假設這個序列的起始下標分別為a，b，mid=(a+b)/2，那么n要么就是seq[mid]（n=seq[mid]），要么在mid左邊（n<seq[mid]），要么在mid右邊（n>seq[mid]），要么這個數根本不在seq[]中。
下面這道題是二分查找的典型應用：
zoj1101
題意描述：在給定整數序列（<=1000）中找出四個不同的數，使得三個數的和等于另外一個數。
直接用四層循環鐵定超時，這里采用了一種拿空間換時間的方式。
假設有a+b+d=c，這等價于a+b=c-d，我們可以把所有的a+b存起來（<=10^6個），把所有的c-d也存起來（<=10^6個），當拿到每一個a+b時我們只需要在所有c-d的序列中查找就行了。先把c-d序列排序，排序時間復雜度O(NlogN)，查找過程可以用二分，這樣就不會超時啦。
以下是本題代碼：
#include<stdio.h>
#include<stdlib.h>
#define MAX 2100000000
#define LEN 1000010
#define LEN1 1010
typedef struct
{
int rs;
int a;
int b;
}Node;
Node addseq[LEN];
Node subseq[LEN];
int num[LEN1];
int seqlen;
int wagamount;
int binSch(int n, int bg, int ed)//二分查找——遞歸方式
{
if(bg > ed)
return -1;
if(bg == ed)
{
if(n == subseq[bg].rs)
return bg;
return -1;
}
int mid = (bg + ed) / 2;
if(n == subseq[mid].rs)
return mid;
if(n < subseq[mid].rs)
return binSch(n, bg, mid - 1);
if(n > subseq[mid].rs)
return binSch(n, mid + 1, ed);
}
int binSch2(int n, int bg, int ed)//二分查找——非遞歸方式
{
while(bg <= ed)
{
int mid = (bg + ed) / 2;
if(n == subseq[mid].rs)
return mid;
if(n < subseq[mid].rs)
ed = mid - 1;
else
bg = mid + 1;
}
return -1;
}
int findWinner()
{
int i, j;
int n;
for(i = 0; i < seqlen; i++)
{
n = addseq[i].rs;
int a = addseq[i].a;
int b = addseq[i].b;
int find = binSch(n, 0, seqlen - 1);
if(find != -1)
{
int c = subseq[find].a;
int d = subseq[find].b;
if(a != b && a != c && a != d && b != c && b != d && c != d)
{
if(c > wagamount)
wagamount = c;
}
}
}
}
int cmp(const void *a, const void *b)
{
Node *a0 = (Node*)a;
Node *b0 = (Node*)b;
return a0 -> rs - b0 -> rs;
}
int main()
{
int i, j;
int n;
scanf("%d", &n);
while(n != 0)
{
for(i = 0; i < n; i++)
scanf("%d", &num[i]);
seqlen = 0;
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
if(j != i)
{
addseq[seqlen].rs = num[i] + num[j];
addseq[seqlen].a = num[i];
addseq[seqlen].b = num[j];
subseq[seqlen].rs = num[i] - num[j];
subseq[seqlen].a = num[i];
subseq[seqlen].b = num[j];
seqlen++;
}
qsort(subseq, seqlen, sizeof(Node), cmp);
wagamount = -MAX;
findWinner();
if(wagamount != -MAX)
printf("%d\n", wagamount);
else
printf("no solution\n");
scanf("%d", &n);
}
//system("pause");
}
posted @
2012-08-01 21:39 小鼠標 閱讀(1084) |
評論 (0) |
編輯 收藏
今天寫C代碼的時候用到了字符串結束標記，猛然感覺有些陌生，索性復習一下C語言的轉義字符。
轉義字符——當然也是字符，引用的時候要加單引號。C語言中之說以會出現轉義字符，無非處于以下幾個原因：
1.有些字符是不可見的，無法通過鍵盤輸入（比如換行符、回車符、響鈴等）。
2.有些字符已經有特殊的用途，無法直接引用（比如:'\'，單引號、雙引號等）。
3.使用轉義字符能夠使意圖更清楚（比如字符串結束標志，我們更傾向于寫成'\0'，而不是直接賦0值）。
下表列出了C語言中所有的轉義字符：
| 轉義字符 |
意義 |
ASCII碼值（十進制） |
| \a |
響鈴(BEL) |
007 |
| \b |
退格(BS) ，將當前位置移到前一列 |
008 |
| \f |
換頁(FF)，將當前位置移到下頁開頭 |
012 |
| \n |
換行(LF) ，將當前位置移到下一行開頭 |
010 |
| \r |
回車(CR) ，將當前位置移到本行開頭 |
013 |
| \t |
水平制表(HT) （跳到下一個TAB位置） |
009 |
| \v |
垂直制表(VT) |
011 |
| \\ |
代表一個反斜線字符''\' |
092 |
| |
|
|
| \' |
代表一個單引號（撇號）字符 |
039 |
| \" |
代表一個雙引號字符 |
034 |
| \0 |
空字符(NULL) |
000 |
| \ddd |
1到3位八進制數所代表的任意字符 |
三位八進制 |
| \xhh |
1到2位十六進制所代表的任意字符 |
二位十六進制 |
posted @
2012-07-31 23:09 小鼠標 閱讀(1748) |
評論 (0) |
編輯 收藏
線段樹題，本題對線段樹的操作有建樹（MakeTree()）、查找（Query()）、更新（update()）。
建樹一次完成，時間花費為O(LogN)；查詢的時間復雜度鄙人還不會分析O(∩_∩)O~，最壞可能是O(N)，不過這種情況應該很難出現；更新的算法值得商榷，不同的策略時間復雜度會相差很大。下面講解兩種比較用以想到的更新策略。
更新方法一：
每次都將所有能更新的節點更新，這種方式最壞情況下將會更新樹中所有節點，此時時間復雜度為O(N)。本題使用這種方法會TLE。
更新方法二：
每次都盡量少的更新節點信息，與第一種方法相比，Node內會多一個變量en，我把它形象的稱之為“勢能”，計算結果時要將該的所有父節點的“勢能”也考慮在內。這種方法的時間復雜度也不好分析，但明顯優于第一種方法。
這一題對時間卡的很緊，主要是花在樹的更新上。
關于線段樹可以先參閱：
http://m.shnenglu.com/hoolee/archive/2012/07/29/185531.html以下是本題代碼：
#include<stdio.h>
#include<stdlib.h>
#define LEN 100010
#define LEN0 6550000
typedef struct
{
int a, b;
int l, r;
long long sum;//記錄該區間內的部分和
long long en;//記錄該節點“勢能”。
}Node;
int count;
Node A[LEN0];
int allNum[LEN];
void MakeTree(int i)
{
A[i].en = 0;
int a = A[i].a;
int b = A[i].b;
int mid = (a + b) / 2;
if(a == b)
{
A[i].sum = allNum[a];
return;
}
int l = ++count;
int r = ++count;
A[l].a = a;
A[l].b = mid;
A[r].a = mid + 1;
A[r].b = b;
MakeTree(l);
MakeTree(r);
A[i].sum = A[l].sum + A[r].sum;
A[i].l = l;
A[i].r = r;
}
long long Query(int t, int aa, int bb, long long en)
{
int a = A[t].a;
int b = A[t].b;
if(a == aa && b == bb)//1
{
return A[t].sum + en * (bb - aa + 1);
}
int mid = (a + b) / 2;
if(bb <= mid)//2
return Query(A[t].l, aa, bb, en + A[t].en);
if(aa >= mid + 1)//3
return Query(A[t].r, aa, bb, en + A[t].en);
long long suml = Query(A[t].l, aa, mid, en + A[t].en);//4
long long sumr = Query(A[t].r, mid + 1, bb, en + A[t].en);
return suml + sumr;
}
void Update(int t, int aa, int bb, int c)
{
int a = A[t].a;
int b = A[t].b;
int mid = (a + b) / 2;
int l = A[t].l;
int r = A[t].r;
A[t].sum += (bb - aa + 1) * c;
if(aa == a && bb == b)
{
A[t].en += c;
return;
}
if(bb <= mid)
Update(l, aa, bb, c);
else if(aa >= mid + 1)
Update(r, aa, bb, c);
else
{
Update(l, aa, mid, c);
Update(r, mid + 1, bb, c);
}
}
int main()
{
int i, j;
int N, Q;
int a, b, c;
scanf("%d%d", &N, &Q);
for(i = 1; i <= N; i++)
scanf("%d", &allNum[i]);
count = 0;
int t = ++count;
A[t].a = 1;
A[t].b = N;
MakeTree(t);
char str[50];
getchar();
for(i = 0; i < Q; i++)
{
gets(str);
if(str[0] == 'Q')
{
sscanf(&str[1], "%d%d", &a, &b);
long long sum = Query(1, a, b, 0);
printf("%lld\n", sum);
}
else if(str[0] == 'C')
{
sscanf(&str[1], "%d%d%d", &a, &b, &c);
Update(1, a, b, c);
}
}
//system("pause");
}posted @
2012-07-31 20:40 小鼠標 閱讀(3666) |
評論 (0) |
編輯 收藏
即使是沒有算法的題，也應該想清楚了再寫，特別是關于字符串處理的，細節很多，稍不注意就會發生錯誤。
下面這道題是經典的“回文”題，要求輸出每句話中每個單詞的回文，但是單詞在句子中的位置不變。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define LEN 20000
void Reversal(char *str)
{
int i, j;
int len = strlen(str);
int bg;
for(i = 0; i <= len; i++)//跳過句首的空格
if(str[i] == ' ')
putchar(str[i]);
else
{
bg = i;
break;
}
for(; i <= len; i++)
{
if(str[i] == ' ' || i == len)//一個單詞結束，輸出該單詞的回文
{
for(j = i - 1; j >= bg; j--)
putchar(str[j]);
if(i != len)
putchar(str[i]);
}
if(str[i] == ' ' && str[i + 1] != ' ')//新單詞的開始標志
bg = i + 1;
}
}
int main()
{
int i, j;
int N, M;
int gard;
char str[LEN];
scanf("%d", &N);
gard = 0;
for(i = 0; i < N; i++)
{
if(gard++ != 0)
printf("\n");
scanf("%d", &M);
getchar();
for(j = 0; j < M; j++)
{
gets(str);
Reversal(str);
putchar(10);
}
}
//system("pause");
}
posted @
2012-07-31 16:58 小鼠標 閱讀(352) |
評論 (1) |
編輯 收藏徹底的水題，因為沒有說數據量，我把數組開小了，SF了四次，最后把數字串長
度開到4000才過，真是坑爹啊。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define LEN 4000
int isZero(char *str)
{
int len = strlen(str);
for(int i = 0; i < len; i++)
if(str[i] != '0')
return 0;
return 1;
}
int RootOne(int n)
{
int sum = 0;
while(n != 0)
{
sum += n % 10;
n /= 10;
}
return sum;
}
int Root(char *str)
{
int i, j;
int n = 0;
int len = strlen(str);
for(i = 0; i < len; i++)
{
n += str[i] - '0';
}
int sum = n;
while(sum / 10)
{
sum = RootOne(sum);
}
return sum;
}
int main()
{
int i, j;
char str[LEN];
while(scanf("%s", str) != NULL && !isZero(str))
{
int n = Root(str);
printf("%d\n", n);
//scanf("%s", str);
}
//system("pause");
}
posted @
2012-07-31 16:15 小鼠標 閱讀(188) |
評論 (0) |
編輯 收藏
摘要: 這是我寫的第一道線段樹，思路還算清晰，不過之前走了不少彎路。主要錯在：誤以為線段樹是一棵滿二叉樹，建樹時吃了苦頭。//線段樹除了最后一層可能不滿足滿二叉樹性質外，上面的所有層構成完全二叉樹，因此仍然可以用滿二叉樹的性質：如果樹根節點從1開始編號，則對任意編號的節點t，左子樹編號為t*2，右子樹編號為t*2+1，父節點編號為t/2。這樣，建樹的時候節點內就不用記錄兒子或父節點的信息了。下面結合poj...
閱讀全文
posted @
2012-07-29 10:44 小鼠標 閱讀(1893) |
評論 (2) |
編輯 收藏
科學家發明了一種新的生物，這種生物能夠兩兩合并，重量為m1的生物與重量為m2的生物合并后變為一個生物，該生物的重量為2*sqrt(m1*m2)。求給定數量的生物合并成一個生物后的最小重量。
貪心算法，每次選取重量最大的兩個生物合并成一個即可。下面的代碼是有優先隊列（大頂堆）實現的。
不過，深入分析一下，由數學公式可以證明：m1+m2 >= 2*sqrt(m1*m2)，因此當兩個生物合并后，重量一定是剩余生物中最大的，由此只要將原重量按降序排序一次，然后依次合并即可。
優先隊列有些大材小用了。
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define LEN 110
void f(double *a, int top, int r)
{//篩選函數，保持大頂堆的性質。
int i, j;
for(j = 2 * top; j <= r; j *= 2)
{
if(j < r && a[j] < a[j + 1])
j++;
if(a[j] <= a[j / 2])
break;
double t = a[j];
a[j] = a[j / 2];
a[j / 2] = t;
}
}
double DeQueue(double *a, int *r)
{
double t = a[1];
a[1] = a[*r];
--*r;
f(a, 1, *r);
return t;
}
void EnQueue(double *a, int *r, double num)
{
++*r;
a[*r] = num;
int i = *r;
while(1)
{
if(i > 1 && a[i] > a[i / 2])
{
double t = a[i];
a[i] = a[i / 2];
a[i / 2] = t;
i /= 2;
}
else
break;
}
}
int main()
{
int i, j;
int N;
int r;
double a[LEN];
double w;
while(scanf("%d", &N) != EOF)
{
for(i = 1; i <= N; i++)
scanf("%lf", &a[i]);
for(i = N / 2; i >= 1; i--)//建立大頂堆，即是初始化隊列
f(a, i, N);
r = N;
while(r > 1)
{
double m1 = DeQueue(a, &r);
double m2 = DeQueue(a, &r);
w = 2.0 * sqrt(m1 * m2);
EnQueue(a, &r, w);
}
printf("%.3lf\n", a[1]);
}
}
posted @
2012-07-21 22:22 小鼠標 閱讀(813) |
評論 (0) |
編輯 收藏
摘要: 優先隊列，其實我一直不愿承認“優先隊列”是一種“隊列”，現實世界的隊列（比如排隊）告訴我們，隊列最明顯的性質就是先進先出。而優先隊列，似乎跟這個規則沒什么關系……
閱讀全文
posted @
2012-07-20 10:36 小鼠標 閱讀(3325) |
評論 (0) |
編輯 收藏
摘要: 單調隊列，顧名思義就是具有單調性的隊列O(∩_∩)O~，一般的隊列只能從隊尾入隊、隊首出隊；為了保持單調隊列的單調性，單調隊列除具有這兩種性質外，還可以從隊尾出隊……
閱讀全文
posted @
2012-07-19 12:21 小鼠標 閱讀(5515) |
評論 (0) |
編輯 收藏