摘要: 数组初始化的时候常用for()循环，不过如果考虑效率的话，最好用memset()，下面简单介绍以下memset()。
函数原型：
void *memset(void *s, int ch, size_t n)
函数解释：将s中前n个字节替换为ch并返回s；
……
sizeof是C/C++中的一个操作符（operator），而不是函数……
阅读全文
posted @
2012-08-07 23:38 小鼠标 阅读(3149) |
评论 (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 小鼠标 阅读(112) |
评论 (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 小鼠标 阅读(106) |
评论 (0) |
编辑 收藏最小生成树有两个经典算法：Prim算法和Kruskal算法，Prim适合于点较少的图，对于一个节点数为N的连通图来说，其时间复杂度为O(N^2)；Kruskal适合于边较少的图，对一个边为E的连通图来说，其时间复杂度为O(ElogE)，因此要根据不同情况选择合适的算法。
这里说一下Prim算法。
Prim的具体步骤为把所有点分为两个部分：属于集合S，或不属于S，当所有点都属于S时，算法结束。
1.初始条件先将第一个点p0划到S中，然后利用p0关联的所有边更新cost[]（sost[i]表示pi与S中点相连的最短的那条边长）
2.每次从sost[]中选出最小的那一个cost[i]（i不能属于S），将i加入到S中，并利用与i相关的边更新cost[]（已加入到S中的点不用再更新）
3.反复执行第二步，直到图连通。（我们知道一个有n个节点的图，最少只需要n-1条边就可以连通了，所以第二步会执行n-1次，每次都会在图中加入一条边）
关于Kruskal请参阅：
http://www.cppblog.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 小鼠标 阅读(3112) |
评论 (0) |
编辑 收藏这是实验室集训开始第一次比赛的D题。
题意描述：给你n张卡片，每张卡片正反面都有颜色（两面的颜色可能相同，或不同），将这些卡片放在桌面上，每次操作你可以将一张卡片翻面。问的是能否通过最少的翻面次数使得正面有一种颜色的数量>=卡片数的一半，并输出翻面次数。
解题的大致思路是，用A[]统计出所有可能出现的颜色以及该种颜色出现的总次数，用B[]统计正面的颜色以及该种颜色出现的次数。如果A[]中有某种颜色出现的次数>=(n+1)/2，说明通过若干次翻面操作我们是可以达到目的的，这时只需再参照B[]，即可算出翻面次数。
思路很清晰，可是有一些不得不注意的细节。
1.当卡片两面的颜色相同时，只能统计一次。
2.数据量很大，查找时要用二分。
3.如果一种颜色在只在反面出现，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 小鼠标 阅读(337) |
评论 (0) |
编辑 收藏
这里不再赘述了，关于最小生成树Kruskal算法可以参阅：
http://www.cppblog.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 小鼠标 阅读(118) |
评论 (0) |
编辑 收藏这两天在做最小生成树，用的一直是Kruskal，不知道用Prim能把代码写的短点儿。。。
这是有些被催的一题，题中两个卫星连接的点之间可以理解为没有长度，偶错误的将
卫星个数S理解为
没有长度的边的个数，忘记了它们之间是有1之差的。O_O
关于Kruskal，可以先参阅：
http://www.cppblog.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 小鼠标 阅读(266) |
评论 (0) |
编辑 收藏最小生成树有两种算法：Prim和Kruskal，这里说一下Kruskal算法。
其具体算法描述为（我们假设给定的图是连通的）：
1.初始化总花费allcost=0
2.将所有边按边长len从小到大的顺序排序
3.从头到尾依次遍历个边edge[i], 如果该边关联的两个定点不属于同一个集合，则将这两个集合合并，并更新allcost。
Kruskal算法牵涉到集合操作，包括集合的建立和集合的合并，这里用并查集解决，下面简单介绍以下并查集。
并查集用森林来表示，他有以下操作：
初始化：把每个节点所在结合初始化为自身。
查找：查找元素所在的集合，即根节点
合并：将两个在不同集合的元素合并为一个集合，为了保持数的深度的平衡性，在合并之前，应判断两个集合树的深度，如果深度不同，应将深度小的合并到深度大的上面。
关于维持集合树深度的问题，还有另一种做法，就是合并集合的时候并不考虑树的深度，而是在查询的时候改变树的深度。因为没有写过，这里不多说了。下面是poj1258的代码，最直接的最小生成树。
#include<stdio.h>
#include<stdlib.h>
#define LEN 10000
typedef struct//边，包括与边相关的两个定点，以及边长
{
int f;
int t;
int len;
}Edge;
typedef struct //集合，只有根节点的深度才有意义
{
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)//找到该节点所属集合
{
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 小鼠标 阅读(1586) |
评论 (0) |
编辑 收藏大数问题。C语言中没有大整数类型，当一个数超过long long时我们就没办法直接表示，只能通过数组模拟（字符数组，或者整形数组），与Java相比，这一点真是够折磨人的，记得今年省赛的时候，有一题是关于大数的，有人直接用Java中的BigInteger类，很轻松的就搞定了，C语言真是无法望其项背。这里我们用C解一道大数乘法题，
其实模拟大数运算就是在模拟小学生算算术，这一题只牵涉到了加法和乘法，我就说着两种操作。
加法Add()：1.对位，将权值相同的各位对其
2.相加，将相应的每一位相加
3.进位，从低位到高位依次进位
乘法：a*b乘法是在加法的基础上完成的，跟我们手算乘法的过程一样，依次将b的每一位与a相乘，加到一起就行了。需要注意的是b中的每一位权值是不一样的。
为了对位方便，我们通常是将数字倒置过来，即低位在左边，高位在右边。字符串处理都是些细节，不小心就会犯错误。
以下是poj3167的代码：
题意：给两个数K、M，求n，使得M^n的第K为是数字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，这是当前乘方计算的结果
int B[LEN];//B[]和C[]一起完成对M^(t+1)的计算，B[]存储M^t与b的某一位i相乘的结果，
int C[LEN];//C[]用来存储计算到b的当前位时的累加结果
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 小鼠标 阅读(1148) |
评论 (0) |
编辑 收藏最直接的广度优先搜索题。求最短路一般用广搜，广搜要用到队列；与广搜对应的是深搜，深搜要用到栈，它能找到所有路，这里不展开说了。刚入门的同学可以先看看队列这种数据结构。
无论广搜还是深搜，走过的节点一定要标记，以免多次走过同一个节点。
以下是本题代码：
#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 小鼠标 阅读(200) |
评论 (0) |
编辑 收藏