摘要: 數(shù)組初始化的時候常用for()循環(huán)，不過如果考慮效率的話，最好用memset()，下面簡單介紹以下memset()。
函數(shù)原型：
void *memset(void *s, int ch, size_t n)
函數(shù)解釋：將s中前n個字節(jié)替換為ch并返回s；
……
sizeof是C/C++中的一個操作符（operator），而不是函數(shù)……
閱讀全文
posted @
2012-08-07 23:38 小鼠標 閱讀(3202) |
評論 (2) |
編輯 收藏
#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
#define LEN 510
#define MAX 100000
int main()
{
int i, j;
int N, E;
int A, B, K;
int T;
int mp[LEN][LEN];
scanf("%d", &T);
while(T--)
{
scanf("%d%d", &N, &E);
for(i = 0; i < LEN; i++)
for(j = i; j < LEN; j++)
mp[i][j] = mp[j][i] = MAX;
for(i = 0; i < E; i++)//read map
{
scanf("%d%d%d", &A, &B, &K);
mp[B][A] = mp[A][B] = K;
}
int s[LEN] = {0};
int cost[LEN];
int lenall = 0;
s[0] = 1;
for(i = 0; i < N; i++)
cost[i] = mp[0][i];
for(j = 0; j < N - 1; j++)
{
int t = 0;
int min = MAX;
for(i = 0; i < N; i++)
if(s[i] == 0 && cost[i] <= min)
{
t = i;
min = cost[i];
}
s[t] = 1;
lenall += min;
for(i = 0; i < N; i++)
if(s[i] == 0 && mp[t][i] < cost[i])
cost[i] = mp[t][i];
}
printf("%d\n", lenall);
}
//system("pause");
}
posted @
2012-08-07 11:23 小鼠標 閱讀(136) |
評論 (0) |
編輯 收藏
#include<stdio.h>
#include<stdlib.h>
#define LEN 60
#define MAX 1000
int main()
{
int i, j;
int P, R;
int mp[LEN][LEN];
scanf("%d", &P);
while(P != 0)
{
scanf("%d", &R);
for(i = 0; i < LEN; i++)
for(j = 0; j < LEN; j++)
mp[i][j] = MAX;
int a, b, len;
for(i = 1; i <= R; i++)//read road
{
scanf("%d%d%d", &a, &b, &len);
if(len < mp[a][b])
{
mp[a][b] = mp[b][a] = len;
}
}
int s[LEN] = {0};
int cost[LEN];
int lenall = 0;
s[1] = 1;//init
for(i = 1; i <= P; i++)
cost[i] = mp[1][i];
for(i = 1; i <= P - 1; i++)//prim
{
int t = 1;
int min = MAX;
for(j = 1; j <= P; j++)
if(s[j] == 0 && cost[j] <= min)
{
t = j;
min = cost[j];
}
s[t] = 1;
lenall += min;
for(j = 1; j <= P; j++)//updat cost[]
if(s[j] == 0 && mp[t][j] < cost[j])
cost[j] = mp[t][j];
}
printf("%d\n", lenall);
scanf("%d", &P);
}
//system("pause");
}
posted @
2012-08-07 10:47 小鼠標 閱讀(129) |
評論 (0) |
編輯 收藏最小生成樹有兩個經(jīng)典算法：Prim算法和Kruskal算法，Prim適合于點較少的圖，對于一個節(jié)點數(shù)為N的連通圖來說，其時間復雜度為O(N^2)；Kruskal適合于邊較少的圖，對一個邊為E的連通圖來說，其時間復雜度為O(ElogE)，因此要根據(jù)不同情況選擇合適的算法。
這里說一下Prim算法。
Prim的具體步驟為把所有點分為兩個部分：屬于集合S，或不屬于S，當所有點都屬于S時，算法結(jié)束。
1.初始條件先將第一個點p0劃到S中，然后利用p0關聯(lián)的所有邊更新cost[]（sost[i]表示pi與S中點相連的最短的那條邊長）
2.每次從sost[]中選出最小的那一個cost[i]（i不能屬于S），將i加入到S中，并利用與i相關的邊更新cost[]（已加入到S中的點不用再更新）
3.反復執(zhí)行第二步，直到圖連通。（我們知道一個有n個節(jié)點的圖，最少只需要n-1條邊就可以連通了，所以第二步會執(zhí)行n-1次，每次都會在圖中加入一條邊）
關于Kruskal請參閱：
http://www.shnenglu.com/hoolee/archive/2012/08/04/186253.html下面是zoj1203的Prim算法代碼：
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define MAX 1000000
#define LENN 110
typedef struct
{
double x;
double y;
}Point;
int main()
{
int i, j, k;
int N, n;
Point ps[LENN];
double mp[LENN][LENN];
double cost[LENN];
int bl[LENN];
scanf("%d", &N);
n = 0;
int gard = 0;
while(N != 0)
{
for(i = 0; i < N; i++)
scanf("%lf%lf", &ps[i].x, &ps[i].y);
for(i = 0; i < N; i++)// make map[][]
for(j = i + 1; j < N; j++)
{
double dx = ps[i].x - ps[j].x;
double dy = ps[i].y - ps[j].y;
double lent = sqrt(dx * dx + dy * dy);
mp[i][j] = mp[j][i] = lent;
}
for(i = 0; i < N; i++)
mp[i][i] = MAX;
double len = 0;
bl[0] = 1;
for(i = 1; i < N; i++)
{
cost[i] = mp[0][i];
bl[i] = 0;
}
for(i = 0; i < N - 1; i++)//prim
{
double min = MAX;
int t;
for(k = 0; k < N; k++)
if(bl[k] == 0 && cost[k] < min)
{
min = cost[k];
t = k;
}
bl[t] = 1;
len += min;
for(j = 0; j < N; j++)// update
if(bl[j] == 0 && mp[t][j] < cost[j])
cost[j] = mp[t][j];
}
if(gard++ != 0)
putchar(10);
printf("Case #%d:\n", ++n);
printf("The minimal distance is: %.2lf\n", len);
scanf("%d", &N);
}
//system("pause");
}
posted @
2012-08-06 17:46 小鼠標 閱讀(3146) |
評論 (0) |
編輯 收藏這是實驗室集訓開始第一次比賽的D題。
題意描述：給你n張卡片，每張卡片正反面都有顏色（兩面的顏色可能相同，或不同），將這些卡片放在桌面上，每次操作你可以將一張卡片翻面。問的是能否通過最少的翻面次數(shù)使得正面有一種顏色的數(shù)量>=卡片數(shù)的一半，并輸出翻面次數(shù)。
解題的大致思路是，用A[]統(tǒng)計出所有可能出現(xiàn)的顏色以及該種顏色出現(xiàn)的總次數(shù)，用B[]統(tǒng)計正面的顏色以及該種顏色出現(xiàn)的次數(shù)。如果A[]中有某種顏色出現(xiàn)的次數(shù)>=(n+1)/2，說明通過若干次翻面操作我們是可以達到目的的，這時只需再參照B[]，即可算出翻面次數(shù)。
思路很清晰，可是有一些不得不注意的細節(jié)。
1.當卡片兩面的顏色相同時，只能統(tǒng)計一次。
2.數(shù)據(jù)量很大，查找時要用二分。
3.如果一種顏色在只在反面出現(xiàn)，B[]中是找不到它的。以下是本題代碼：
#include<stdio.h>
#include<stdlib.h>
#define LEN 2000200
#define LENC 200010
#define MAX 10000000
typedef struct
{
int c;//color
int n;//time
}Node;
typedef struct
{
int c;
int f;//front or down, 1 or 0
}Color;
Color C[LENC];
int lenc;
Node A[LEN];
int lena;
Node B[LEN];
int lenb;
int cmpc(const void *a, const void *b)
{
Color *a0 = (Color*)a;
Color *b0 = (Color*)b;
return a0 -> c - b0 -> c;
}
int Min(int a, int b)
{
if(a < b)
return a;
return b;
}
int main()
{
int i, j;
int n;
while(scanf("%d", &n) != EOF)
{
int c1, c2;
lenc = 0;
for(i = 0; i < n; i++)
{
scanf("%d%d", &c1, &c2);
C[lenc].c = c1;
C[lenc++].f = 1;
if(c2 != c1)
{
C[lenc].c = c2;
C[lenc++].f = 0;
}
}
qsort(C, lenc, sizeof(Color), cmpc);
lenb = 0;//init B[]
for(i = 0; i < lenc; i++)
if(C[i].f == 1)
{
B[0].c = C[i].c;
B[0].n = 1;
lenb = 1;
i++;
break;
}
for(; i < lenc; i++)
{
if(C[i].f == 1)
{
if(C[i].c == B[lenb - 1].c)
{
B[lenb - 1].n++;
}
else
{
B[lenb].c = C[i].c;
B[lenb++].n = 1;
}
}
}
lena = 0;//init A[]
A[0].c = C[0].c;
A[0].n = 1;
lena = 1;
for(i = 1; i < lenc; i++)
{
if(C[i].c == A[lena - 1].c)
{
A[lena - 1].n++;
}
else
{
A[lena].c = C[i].c;
A[lena++].n = 1;
}
}
int psb = 0;
int mint = MAX;
for(i = 0; i < lena; i++)
{
int t = (n + 1) / 2;
if(A[i].n >= t)
{
int ii = 0;
int jj = lenb - 1;
int find = 0;
int mid;
while(ii <= jj)//binSearch
{
mid = (ii + jj) / 2;
if(B[mid].c == A[i].c)
{
find = 1;
break;
}
else if(A[i].c < B[mid].c)
{
jj = mid - 1;
}
else
ii = mid + 1;
}
if(find == 1)
{
int k = t - B[mid].n;
mint = Min(mint, k);
}
else
mint = Min(mint, t);
psb = 1;
}
}
if(psb == 1)
{
if(mint >= 0)
printf("%d\n", mint);
else
printf("0\n");
}
else
printf("-1\n");
}
//system("pause");
}
posted @
2012-08-06 15:16 小鼠標 閱讀(368) |
評論 (0) |
編輯 收藏
這里不再贅述了，關于最小生成樹Kruskal算法可以參閱：
http://www.shnenglu.com/hoolee/archive/2012/08/04/186253.html以下是本題代碼：
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define LEN1 110
#define LEN0 10000
typedef struct
{
double x;
double y;
}Point;
typedef struct
{
int f;
int t;
double len;
}Edge;
typedef struct
{
int p;
int d;
}Set;
Set set[LEN1];
Point ps[LEN1];
Edge egs[LEN0];
int cmp(const void *a, const void *b)
{
Edge *a0 = (Edge*)a;
Edge *b0 = (Edge*)b;
return a0 -> len > b0 -> len ? 1 : -1;
}
int Belong(int i)
{
while(set[i].p != i)
i = set[i].p;
return i;
}
int main()
{
int i, j;
int n;
int count = 0;
scanf("%d", &n);
for(i = 0; i < n; i++)
scanf("%lf%lf", &ps[i].x, &ps[i].y);
for(i = 0; i < n; i++)//make edges
for(j = i + 1; j < n; j++)
{
egs[count].f = i;
egs[count].t = j;
double dx = ps[i].x - ps[j].x;
double dy = ps[i].y - ps[j].y;
egs[count++].len = sqrt(dx * dx + dy * dy);
}
qsort(egs, count, sizeof(Edge), cmp);
for(i = 0; i < n; i++)
{
set[i].p = i;
set[i].d = 0;
}
double len = 0;
for(i = 0; i < count; i++)
{
int fb = Belong(egs[i].f);
int tb = Belong(egs[i].t);
if(fb != tb)
{
len += egs[i].len;
int df = set[fb].d;
int dt = set[tb].d;
if(df > dt)
set[tb].p = fb;
else if(df == dt)
{
set[tb].p = fb;
set[fb].d++;
}
else
set[fb].p = tb;
}
}
printf("%.2lf\n", len);
//system("pause");
}
posted @
2012-08-04 16:40 小鼠標 閱讀(142) |
評論 (0) |
編輯 收藏這兩天在做最小生成樹，用的一直是Kruskal，不知道用Prim能把代碼寫的短點兒。。。
這是有些被催的一題，題中兩個衛(wèi)星連接的點之間可以理解為沒有長度，偶錯誤的將
衛(wèi)星個數(shù)S理解為
沒有長度的邊的個數(shù)，忘記了它們之間是有1之差的。O_O
關于Kruskal，可以先參閱：
http://www.shnenglu.com/hoolee/archive/2012/08/04/186253.html以下是本題代碼：
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define LEN0 250000
#define LEN1 510
typedef struct
{
double x;
double y;
}Point;
typedef struct
{
int f;
int t;
double len;
}Edge;
typedef struct
{
int p;
int d;
}Set;
Set set[LEN1];
Point ps[LEN1];
Edge egs[LEN0];
int cmp(const void *a, const void *b)
{
Edge *a0 = (Edge*)a;
Edge *b0 = (Edge*)b;
return a0 -> len > b0 -> len ? 1 : -1;
}
int Belong(int i)
{
while(set[i].p != i)
i = set[i].p;
return i;
}
int main()
{
int i, j;
int N, S, P;
scanf("%d", &N);
while(N--)
{
scanf("%d%d", &S, &P);
for(i = 0; i < P; i++)
scanf("%lf%lf", &ps[i].x, &ps[i].y);
int count = 0;
for(i = 0; i < P; i++)//make edges
for(j = i + 1; j < P; j++)
{
egs[count].f = i;
egs[count].t = j;
double dx = ps[i].x - ps[j].x;
double dy = ps[i].y - ps[j].y;
egs[count++].len = sqrt(dx * dx + dy * dy);
}
qsort(egs, count, sizeof(Edge), cmp);
for(i = 0; i < P; i++)
{
set[i].p = i;
set[i].d = 0;
}
int setnum = P;
double len = 0;
for(i = 0; i < count && setnum - S > 0; i++)
{
int fb = Belong(egs[i].f);
int tb = Belong(egs[i].t);
if(fb != tb)
{
setnum--;
len = egs[i].len;
int df = set[fb].d;
int dt = set[tb].d;
if(df > dt)
set[tb].p = fb;
else if(df == dt)
{
set[tb].p = fb;
set[fb].d++;
}
else
set[fb].p = tb;
}
}
printf("%.2lf\n", len);
}
//system("pause");
}
posted @
2012-08-04 16:21 小鼠標 閱讀(299) |
評論 (0) |
編輯 收藏最小生成樹有兩種算法：Prim和Kruskal，這里說一下Kruskal算法。
其具體算法描述為（我們假設給定的圖是連通的）：
1.初始化總花費allcost=0
2.將所有邊按邊長len從小到大的順序排序
3.從頭到尾依次遍歷個邊edge[i], 如果該邊關聯(lián)的兩個定點不屬于同一個集合，則將這兩個集合合并，并更新allcost。
Kruskal算法牽涉到集合操作，包括集合的建立和集合的合并，這里用并查集解決，下面簡單介紹以下并查集。
并查集用森林來表示，他有以下操作：
初始化：把每個節(jié)點所在結(jié)合初始化為自身。
查找：查找元素所在的集合，即根節(jié)點
合并：將兩個在不同集合的元素合并為一個集合，為了保持數(shù)的深度的平衡性，在合并之前，應判斷兩個集合樹的深度，如果深度不同，應將深度小的合并到深度大的上面。
關于維持集合樹深度的問題，還有另一種做法，就是合并集合的時候并不考慮樹的深度，而是在查詢的時候改變樹的深度。因為沒有寫過，這里不多說了。下面是poj1258的代碼，最直接的最小生成樹。
#include<stdio.h>
#include<stdlib.h>
#define LEN 10000
typedef struct//邊，包括與邊相關的兩個定點，以及邊長
{
int f;
int t;
int len;
}Edge;
typedef struct //集合，只有根節(jié)點的深度才有意義
{
int d;//深度
int p;//父親
}Set;
Edge egs[LEN];
Set set[110];
int cmp(const void *a, const void *b)
{
Edge *a0 = (Edge*)a;
Edge *b0 = (Edge*)b;
return a0 -> len - b0 -> len;
}
int Belong(int i)//找到該節(jié)點所屬集合
{
while(set[i].p != i)
i = set[i].p;
return i;
}
int main()
{
int i, j;
int N;
int len;
int count;
while(scanf("%d", &N) != EOF)
{
count = 0;
for(i = 0; i < N; i++)
for(j = 0; j < N; j++)
{
scanf("%d", &len);
if(j > i)
{
egs[count].f = i;
egs[count].t = j;
egs[count++].len = len;
}
}
for(i = 0; i < N; i++)
{
set[i].d = 0;
set[i].p = i;
}
qsort(egs, count, sizeof(Edge), cmp);
int lenall = 0;
for(i = 0; i < count; i++)//依次遍歷各邊
{
int f = egs[i].f;
int t = egs[i].t;
int fb = Belong(f);
int tb = Belong(t);
if(fb != tb)//不屬于同一個集合，合并
{
lenall += egs[i].len;
if(set[fb].d > set[tb].d)
{
set[tb].p = fb;
}
else if(set[fb].d == set[tb].d)
{
set[tb].p = fb;
set[fb].d++;
}
else
set[fb].p = tb;
}
}
printf("%d\n", lenall);
}
//system("pause");
}
posted @
2012-08-04 14:24 小鼠標 閱讀(1627) |
評論 (0) |
編輯 收藏大數(shù)問題。C語言中沒有大整數(shù)類型，當一個數(shù)超過long long時我們就沒辦法直接表示，只能通過數(shù)組模擬（字符數(shù)組，或者整形數(shù)組），與Java相比，這一點真是夠折磨人的，記得今年省賽的時候，有一題是關于大數(shù)的，有人直接用Java中的BigInteger類，很輕松的就搞定了，C語言真是無法望其項背。這里我們用C解一道大數(shù)乘法題，
其實模擬大數(shù)運算就是在模擬小學生算算術，這一題只牽涉到了加法和乘法，我就說著兩種操作。
加法Add()：1.對位，將權(quán)值相同的各位對其
2.相加，將相應的每一位相加
3.進位，從低位到高位依次進位
乘法：a*b乘法是在加法的基礎上完成的，跟我們手算乘法的過程一樣，依次將b的每一位與a相乘，加到一起就行了。需要注意的是b中的每一位權(quán)值是不一樣的。
為了對位方便，我們通常是將數(shù)字倒置過來，即低位在左邊，高位在右邊。字符串處理都是些細節(jié)，不小心就會犯錯誤。
以下是poj3167的代碼：
題意：給兩個數(shù)K、M，求n，使得M^n的第K為是數(shù)字7。
#include<stdio.h>
#include<stdlib.h>//zoj3167
#define LEN 310
void Add(int *A, int *B)//A[]=A[]+B[]
{
int i, j;
for(i = 0; i < LEN; i++)
{
A[i] += B[i];
}
int t = 0;
for(i = 0; i < LEN; i++)
{
int t1 = (A[i] + t) / 10;
A[i] = (A[i] + t) % 10;
t = t1;
}
}
void MultiOne(int *B, int i, int w)//B[]*(i*10^(w-1))
{
int j, k;
for(j = LEN - 1; j >= w - 1; j--)
B[j] = B[j - w + 1];
for(k = 0; k < w - 1; k++)
B[k] = 0;
for(j = 0; j < LEN; j++)
B[j] *= i;
int t = 0;
for(i = 0; i < LEN; i++)
{
int t1 = (B[i] + t) / 10;
B[i] = (B[i] + t) % 10;
t = t1;
}
}
void Set0(int *A)
{
for(int i = 0; i < LEN; i++)
A[i] = 0;
}
void Copy(int *F, int *T)
{
int i;
for(i = 0; i < LEN; i++)
T[i] = F[i];
}
int main()
{
int i, j;
int K, M;
int A[LEN];//存儲M^t，這是當前乘方計算的結(jié)果
int B[LEN];//B[]和C[]一起完成對M^(t+1)的計算，B[]存儲M^t與b的某一位i相乘的結(jié)果，
int C[LEN];//C[]用來存儲計算到b的當前位時的累加結(jié)果
while(scanf("%d%d", &K, &M) != EOF)
{
int n = 1;
Set0(A);
Set0(B);
Set0(C);
int t = M;
for(i = 0; t > 0; i++)//init A as M^1
{
A[i] = t % 10;
t /= 10;
}
while(A[K - 1] != 7)
{
Set0(C);
int t = M;
int w = 1;
while(t > 0)
{
Copy(A, B);
int ii = t % 10;
MultiOne(B, ii, w);
Add(C, B);//每一次算完B[]，累加到C[]上
w++;
t /= 10;
}
Copy(C, A);
n++;
}
printf("%d\n", n);
}
//system("pause");
}posted @
2012-08-04 09:31 小鼠標 閱讀(1186) |
評論 (0) |
編輯 收藏最直接的廣度優(yōu)先搜索題。求最短路一般用廣搜，廣搜要用到隊列；與廣搜對應的是深搜，深搜要用到棧，它能找到所有路，這里不展開說了。剛?cè)腴T的同學可以先看看隊列這種數(shù)據(jù)結(jié)構(gòu)。
無論廣搜還是深搜，走過的節(jié)點一定要標記，以免多次走過同一個節(jié)點。
以下是本題代碼：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define LEN 100
typedef struct
{
int x;
int y;
int p;
}Node;
Node queue[LEN];
int r, f;
char mp[10][10];
int d[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
void traceBack(int n)
{
if(n == -1)
return;
else
{
traceBack(queue[n].p);
printf("(%d, %d)\n", queue[n].x - 1, queue[n].y - 1);
}
}
int main()
{
int i, j;
int n = 5;
int amx = 5;
int amy = 5;
for(i = 1; i <= n; i++)
{
for(j = 1; j <= n; j++)
scanf("%d", &mp[i][j]);
}
for(i = 0; i <= n + 1; i++)
{
mp[0][i] = mp[n + 1][i] = 1;
mp[i][0] = mp[i][n + 1] = 1;
}
f = 0;
queue[f].x = 1;
queue[f].y = 1;
queue[f].p = -1;
r = 1;
int find = 0;
while(f != r && find == 0)
{
int x = queue[f].x;
int y = queue[f].y;
f++;
for(i = 0; i < 4; i++)
{
int x1 = x + d[i][0];
int y1 = y + d[i][1];
if(mp[x1][y1] == 0)
{
queue[r].x = x1;
queue[r].y = y1;
queue[r].p = f - 1;
mp[x1][y1] = 1;
r++;
}
if(amx == x1 && amy == y1)
{
find = 1;
break;
}
}
}
traceBack(r - 1);
//system("pause");
}posted @
2012-08-02 19:51 小鼠標 閱讀(223) |
評論 (0) |
編輯 收藏