http://acm.nyist.net/JudgeOnline/problem.php?pid=540今年省赛时的第一道题。欢迎大家去刷河南省赛题。
一周没有刷题，回生了，这么一道题花了两个多小时。真不该跟妹子聊天。
题意：按数字倒序后的大小排序。
本打算把数字转为字符串，然后对字符串用strcmy()，发现这样是不对的，应为"11"会小于"8"，而事实是相反的。后来想到用两个数组存原数和倒序后的数，按倒序后的数排序后输出正序的数字，终于A了。汗啊。
注意cmp()函数的写法。
。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define LEN 60
int N, A, B;
int AB[LEN][2];
int Change(int n)
{
int t = 0;
while(n != 0)
{
t = t * 10 + n % 10;
n = n / 10;
}
return t;
}
int cmp(const void *a, const void *b)
{
int *a0 = (int*)a;
int *b0 = (int*)b;
return a0[1] - b0[1];
}
int main()
{
int i ,j;
int gard;
scanf("%d", &N);
while(N--)
{
scanf("%d%d", &A, &B);
for(i = A, j = 0; i <= B; i++, j++)
{
AB[j][0] = i;
AB[j][1] = Change(i);
}
qsort(AB, B - A + 1, sizeof(int) * 2, cmp);
gard = 0;
for(i = 0; i < B - A + 1; i++)
{
if(gard != 0)
printf(" %d", AB[i][0]);
else
printf("%d", AB[i][0]);
gard++;
}
printf("\n");
}
//system("pause");
}
posted @
2012-05-23 23:28 小鼠标 阅读(250) |
评论 (0) |
编辑 收藏
摘要: 回溯算法的经典例题。大一的时候就有耳闻，却一直没有实现，今天终于有机会把它写出来，小有成就感啊。这里算法采用的是深度优先搜索，从第一个节点开始，按行优先的原则逐个扫描每个点，如果该点合法，可以选择放一个queen也可以选择不放，当该点不合法时，就跳过该点接着判断下一个点。有人把回溯算法说成是“万能算法”，这么说的原因是回溯实际上就是枚举，它的最坏情况始终是指数或阶乘级的。对...
阅读全文
posted @
2012-05-11 20:24 小鼠标 阅读(401) |
评论 (0) |
编辑 收藏大数加法，字符串处理。关键是细节，这方面的问题我老是把边界下标搞错，比如这次就是因为访问到了数组的len元素而导致结果出错。
关与加法的策略：
以前未解决两个家数的对齐问题，我会先把两个字符串倒序，相加、进位后再倒回来，感觉这样到来倒去的实在麻烦。
现在顿悟了，果断不再倒序，从字符串的高下标处开始相加两个数，只要有数字的下标低于1（0位用来保存进位）就停止。具体做法是：
1.用c（指针）记录较长的那个数字
2.预处理：把a、b数组内的字符转化为数字
3.从a、b数组的高下标处（实际加数的低位）开始相加数字a、b
4.从数字的高下标处开始处理进位
5.完成处理：把数字转化为字符
注意：消除和的前导0
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define LEN 110
#define MOD 20
int toNumber(char c)
{
if(c >= '0' && c <= '9')
return c - '0';
else if(c >= 'a' && c <= 'j')
return c - 'a' + 10;
}
int toChar(int n)
{
if(n >= 0 && n <= 9)
return n + '0';
else if(n >= 10 && n <= 19)
return n + 'a' - 10;
}
char *Add(char *a, char *b)
{
int i, j, k;
int lena, lenb, lenc;
char *c;
lena = strlen(a);
lenb = strlen(b);
if(lena > lenb)
{
lenc = lena;
c = a;
}
else
{
lenc = lenb;
c = b;
}
for(i = 0; i < lena; i++)
a[i] = toNumber(a[i]);
for(j = 0; j < lenb; j++)
b[j] = toNumber(b[j]);
for(i = lena - 1, j = lenb - 1, k = lenc - 1; i >= 0 && j >= 0; i--, j--, k--)
{
c[k] = a[i] + b[j];
}
int t, n;
t = 0;
for(i = lenc - 1; i >= 0; i--)
{
n = c[i] + t;
t = n / MOD;
c[i] = n % MOD;
}
for(i = 0; i <= lenc - 1; i++)
c[i] = toChar(c[i]);
return c;
}
int main()
{
int i, j;
char a[LEN], b[LEN];
char *c;
a[0] = b[0] = '0';
while(scanf("%s%s", &a[1], &b[1]) == 2)
{
c = Add(a, b);
if(c[0] == '0')
{
printf("%s\n", &c[1]);
}
else
{
printf("%s\n", c);
}
a[0] = b[0] = '0';
}
}
posted @
2012-05-11 19:05 小鼠标 阅读(137) |
评论 (0) |
编辑 收藏完全背包。
要点：
1.要求价值的最小值
2.要求背包正好装满
#include<stdio.h>//pku1384
#include<string.h>
#include<stdlib.h>
#define LENEF 10010
#define LENNP 510
#define MAX 1000000000
int f[LENEF];
int N, T, E, F;
int P[LENNP], W[LENNP];
int min(int a, int b)
{
if(a < b)
return a;
return b;
}
void CPack()
{
int i, j;
int V = F - E;
for(i = 1; i <= V; i++)
f[i] = MAX;
f[0] = 0;
for(i = 1; i <= N; i++)
{
for(j = W[i]; j <= V; j++)
f[j] = min(f[j], f[j - W[i]] + P[i]);
}
}
int main()
{
int i, j;
scanf("%d", &T);
for(int k = 0; k < T; k++)
{
scanf("%d%d%d", &E, &F, &N);
for(i = 1; i <= N; i++)
scanf("%d%d", &P[i], &W[i]);
//
//printf("E = %d F = %d N = %d\n", E, F, N);
//
CPack();
if(f[F - E] != MAX)
printf("The minimum amount of money in the piggy-bank is %d.\n", f[F - E]);
else
printf("This is impossible.\n");
}
}
posted @
2012-05-09 18:23 小鼠标 阅读(136) |
评论 (0) |
编辑 收藏
看了这么多天的背包，总算渐渐开始理解了。
背包问题有很多种，基本的有两种：0-1背包和完全背包。多重背包可由这两种组合得来。
本题是多重背包问题，可以简单的将多重背包直接转化为0-1背包来求解，但是这种转化很有可能导致超时，因为物品数量太多了。可行的办法是利用 二进制状态压缩，这样可以大大减少物品数量（实际物品数量只有log（N）件）。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define LENN 12
#define LENF 100010
int cash, N;
int n[LENN], D[LENN];
int f[LENF];
int max(int a, int b)
{
if(a > b)
return a;
return b;
}
void MPack()//MultiplePack
{
int i, j;
for(i = 0; i <= cash; i++)
f[i] = 0;
for(i = 0; i < N; i++)
{
if(n[i] * D[i] >= cash)//completePack
{
for(j = D[i]; j <= cash; j++)
f[j] = max(f[j], f[j - D[i]] + D[i]);
}
else//ZeroOnePack
{
int k = 1;
int M = n[i];
while(k < M)
{
for(j = cash; j >= k * D[i]; j--)
{
f[j] = max(f[j], f[j - k * D[i]] + k * D[i]);
}
M -= k;
k *= 2;
}
for(j = cash; j >= M * D[i]; j--)
f[j] = max(f[j], f[j - M * D[i]] + M * D[i]);
}
}
}
int main()
{
int i, j;
while(scanf("%d", &cash) == 1)
{
scanf("%d", &N);
for(i = 0; i < N; i++)
scanf("%d%d", &n[i], &D[i]);
if(cash != 0 && N != 0)
{
MPack();
printf("%d\n", f[cash]);
}
else
printf("0\n");
}
}
posted @
2012-05-09 09:51 小鼠标 阅读(143) |
评论 (0) |
编辑 收藏赤裸裸的0-1背包，很水。听说省赛要出DP题，我们队三个人都不擅长DP，于是乎我开始从背包问题入手学习动态规划。看了几天的背包，头都大了，还是不理解，今天终于A掉了一道水题，值得纪念一下。
关于背包这里就不多说了，感兴趣的童鞋可以参考《背包问题九讲》。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define LEN 14000
int N, M;
int W[LEN];
int D[LEN];
int f[LEN];
int max(int a, int b)
{
if(a > b)
return a;
else
return b;
}
void bag()
{
int i, j;
for(i = 0; i <= N; i++)
f[i] = 0;
for(i = 1; i <= N; i++)
for(j = M; j >= W[i]; j--)
f[j] = max(f[j], f[j - W[i]] + D[i]);
}
int main()
{
int i, j;
scanf("%d%d", &N, &M);
for(i = 1; i <= N; i++)
{
scanf("%d%d", &W[i], &D[i]);
}
bag();
printf("%d\n", f[M]);
//system("pause");
}
posted @
2012-05-08 09:47 小鼠标 阅读(222) |
评论 (0) |
编辑 收藏
摘要: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3204一道很直接的最小生成树，题中给出了权值矩阵，本应给用Prim的，但是为了练习一下并查集的使用，选择了Kruskal。前面我写过Kruskal，但是集合的表示用的是线性表，每次合并都要花费O(N)的时间，效率较低。这次用了并查集——集合的树形表示，...
阅读全文
posted @
2012-04-26 10:01 小鼠标 阅读(296) |
评论 (0) |
编辑 收藏最小生成树prim算法。
最近刚学过Dijkstra的最短路算法，仔细分析一下，Dijkstra与Prim算法十分相似，区别在于更新点时的标准不同。前者是该点到起点的距离（用dist[]记录）最小，则将该点加入s，并更新相应的dist[]，后者是该点到s中任意一点的距离（用lowcost[]记录）最小，则将该点加入s，并更新相应的lowcost[]。
说来惭愧，这一题错在了格式上，没有认真读题，多保留了一位小数。
经验总结：认真读题。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#define LEN 510
#define MAX 1000000.0
typedef struct
{
double x;
double y;
}Point;
Point point[LEN];
int P;
double C[LEN][LEN];
double Dis(Point a, Point b)
{
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
void MakeEdges()
{
int i, j;
for(i = 0; i < P - 1; i++)
for(j = i + 1; j < P; j++)
{
C[i][j] = C[j][i] = Dis(point[i], point[j]);
}
}
double usedLine[LEN];
void Prim()
{
double lowcost[P];
int i, j, k;
int set[P];
// init
for(i = 0; i < P; i++)// init
{
lowcost[i] = C[0][i];
set[i] = 0;
}
set[0] = 1;
for(i = 0; i < P - 1; i++)
{
double min = MAX;
j = 0;
for(k = 1; k < P; k++)
{
if(lowcost[k] < min && set[k] == 0)
{
min = lowcost[k];
j = k;
}
}
set[j] = 1;
usedLine[i] = min;
for(k = 1; k < P; k++)
{
if(set[k] == 0 && C[j][k] < lowcost[k])
{
lowcost[k] = C[j][k];
}
}
}
}
int cmp(const void *a, const void *b)
{
double *a0 = (double*)a;
double *b0 = (double*)b;
if(*a0 > *b0)
return -1;
else
return 1;
}
int main()
{
int i, j, k;
int N, S;
scanf("%d", &N);
for(k = 0; k < N; k++)
{
scanf("%d%d", &S, &P);
for(j = 0; j < P; j++)
{
scanf("%lf%lf", &point[j].x, &point[j].y);
}
for(i = 0; i < P; i++)
for(j = 0; j < P; j++)
C[i][j] = MAX;
MakeEdges();
Prim();
qsort(usedLine, P - 1, sizeof(double), cmp);
printf("%.2lf\n", usedLine[S - 1]);
}
}
posted @
2012-04-25 21:58 小鼠标 阅读(122) |
评论 (0) |
编辑 收藏成语接龙问题，抽象出来就是简单的最简单的单源最短路径问题，Dijkstra算法。
算法设计课上刚讲过贪心算法，Dijkstra算法书上有代码实现，比着书上的代码copy了一遍，提交后居然奇迹般的出现了段错误！这叫我情何以堪啊。FAQ上说段错误有两种情况：数组下标越界和栈溢出。算法中没有递归，不可能爆栈，认真检查每一个用到下标的地方、每个for的起始点，看不出任何毛病。难道代码比着书上抄错了，对照了一下，发现第二个循环开始时没有初始化u，问题就出在这里，u是用来记录下一个可加入集合s的节点的，它的更新来自于所有可利用的dist[]中最下的那个。
经验总结：变量不要忘记初始化。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define LENID 1050
#define RMAX 10000
#define LENS 8
typedef struct
{
char *a;
char *b;
int t;
}Idiom;
int N;
int dist[LENID];
int c[LENID][LENID];
int Dijkstra()
{
int i, j;
int s[LENID];
for(i = 0; i < N; i++)// init
{
dist[i] = c[0][i];
s[i] = 0;
}
dist[0] = 0;
s[0] = 1;
int u = 0;// remeber to init u!!
for(i = 0; i < N - 1; i++)
{
int temp = RMAX;
for(j = 0; j < N; j++)
{
if(s[j] == 0 && dist[j] < temp)
{
u = j;
temp = dist[j];
}
}
s[u] = 1;
if(u == N - 1)
{
return dist[u];
}
for(j = 0; j < N; j++)
{
if(s[j] == 0 && c[u][j] < RMAX)
{
int newdist = dist[u] + c[u][j];
if(newdist < dist[j])
dist[j] = newdist;
}
}
}
return dist[N - 1];
}
int main()
{
int T;
int i, j;
Idiom id[LENID];
char str[100], sa[8], sb[LENS];
scanf("%d", &N);
while(N != 0)
{
for(i = 0; i < N; i++)
{
scanf("%d%s", &T, str);
int len = strlen(str);
for(j = 0; j < 4; j++)
{
sa[j] = str[j];
sb[j] = str[len - 4 + j];
}
sa[j] = sb[j] = '\0';
id[i].a = (char *)malloc(sizeof(char) * LENS);
id[i].b = (char *)malloc(sizeof(char) * LENS);
strcpy(id[i].a, sa);
strcpy(id[i].b, sb);
id[i].t = T;
}
for(i = 0; i < N; i++)// init c[][]
for(j = 0; j < N; j++)
c[i][j] = RMAX;
for(i = 0; i < N; i++)
for(j = i + 1; j < N; j++)
{
if(strcmp(id[i].b, id[j].a) == 0)
c[i][j] = id[i].t;
else if(strcmp(id[j].b, id[i].a) == 0)
c[j][i] = id[j].t;
}
int r = Dijkstra();
if(r == RMAX)
printf("-1\n");
else
printf("%d\n", r);
scanf("%d", &N);
}
}
posted @
2012-04-25 18:08 小鼠标 阅读(301) |
评论 (0) |
编辑 收藏
算法的效率异常重要，对于一个专业的计算机人员来说，应将效提高算法率放在心里，时刻注意。这种思想应该深入我们的骨髓，成为一种习惯。
以前我写过pow函数，不过那都没动脑子，简单的线性时间运算。这里有一个O(logN)的算法，值得一提。
int Pow(int x, int n)
{
if(n == 0)
return 1;
if(n == 1)
return x;
if(n % 2 == 0)
return Pow(x * x, n / 2);
else
return Pow(x * x, n / 2) * x;
} 算法虽然简单，但却体现了编程工作者应具备的基本素质。
posted @
2012-04-23 09:14 小鼠标 阅读(309) |
评论 (0) |
编辑 收藏