摘要: 题意描述：
我们知道英语描述数字与汉语是不同的，题目要求给出英文描述的数字，输出实际的数字。
解题思路是，把所有关键字分成两类，一类是“数字”，另一类是“权重”，遇到数字就加上去，遇到权重就乘上去，最后输出结果就是了。不过这样还不行，因为这会导致权重累计相乘，比如前面有一个million，要乘1000 000，后面又有一个thousand，还要乘1000，这显然是不对的……
阅读全文
posted @
2012-08-12 09:18 小鼠标 阅读(1193) |
评论 (0) |
编辑 收藏一道简简单单的大数加法题，时间竟然卡在getchar()和putchar()上，我用scanf()和printf()硬是超时了，超时了啊亲，这么坑爹的有木有啊，有木有！！
2602 Accepted 1136K
1938MS C++ 702B
以下是本题代码：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define LEN 1000010
char num1[LEN];
int N;
int main()
{
int i, j;
char a, b;
scanf("%d", &N);
int count = N - 1;
getchar();
for(i = 0; i < N; i++)
{
a = getchar();
getchar();
b = getchar();
getchar();
num1[count] = a - '0' + b - '0';
count--;
}
int t = 0;
int t2;
for(i = 0; i < N + 2; i++)//carry bit
{
t2 = num1[i] + t;
num1[i] = t2 % 10;
t = t2 / 10;
}
for(i = N - 1; i >= 0; i--)//out
putchar(num1[i] + '0');
putchar(10);
//system("pause");
}
posted @
2012-08-11 15:33 小鼠标 阅读(315) |
评论 (0) |
编辑 收藏
不多解释，详情参阅我的相关文章。
Add()的两个参数都是逆序的整数数组，结果存在num1中。
以下是本题代码：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define LEN 1000
int Max(int a, int b)
{
if(a > b)
return a;
return b;
}
void Add(char *num1, char *num2)
{
int len1, len2;
int i, j;
i = LEN;
while(num1[--i] == 0 && i > 0);
len1 = i;
i = LEN;
while(num2[--i] == 0 && i > 0);
len2 = i;
int lenm = Max(len1, len2);
for(i = 0; i <= lenm; i++)//add
num1[i] += num2[i];
int t = 0;
int t2;
for(i = 0; i <= lenm + 2; i++)//carry bit
{
t2 = num1[i] + t;
num1[i] = t2 % 10;
t = t2 / 10;
}
}
void ToAr(char *A, int n)
{
int i, j;
i = 0;
while(n)
{
A[i++] = n % 10;
n /= 10;
}
}
void Copy(char *t, char *f)
{
for(int i = 0; i < LEN; i++)
t[i] = f[i];
}
int main()
{
int i, j;
char A0[LEN], A1[LEN], A2[LEN], A3[LEN];
char str[LEN];
while(gets(str) != NULL)
{
memset(A0, 0, sizeof(A0));
memset(A1, 0, sizeof(A0));
memset(A2, 0, sizeof(A0));
memset(A3, 0, sizeof(A0));
int a0, a1, a2;
sscanf(str, "%d%d%d", &a0, &a1, &a2);
ToAr(A0, a0);
ToAr(A1, a1);
ToAr(A2, a2);
for(j = 1; j <= 97; j++)
{
Add(A0, A1);
Add(A0, A2);
Copy(A3, A0);
Copy(A0, A1);
Copy(A1, A2);
Copy(A2, A3);
}
i = LEN;
while(A3[--i] == 0 && i > 0);
if(i == 0)
printf("0\n");
else
{
for(; i >= 0; i--)
printf("%d", A3[i]);
putchar(10);
}
}
//system("pause");
}
下面是java代码：
import java.math.*;
import java.util.*;
public class Main 
{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
try
{
while(true)
{
BigInteger b1, b2, b3, b4;
b1 = sc.nextBigInteger();
b2 = sc.nextBigInteger();
b3 = sc.nextBigInteger();
b4 = new BigInteger("0");
for(int i = 0; i <= 96; i++)
{
b1 = b1.add(b2);
b1 = b1.add(b3);
b4 = b1;
b1 = b2;
b2 = b3;
b3 = b4;
}
System.out.println(b4);
}
}catch(Exception e){};
}
}
posted @
2012-08-11 09:53 小鼠标 阅读(295) |
评论 (0) |
编辑 收藏
大数相加。字符串处理，注意细节，注意初始化。
以下是本题代码：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define LEN 200
int Max(int a, int b)
{
if(a > b)
return a;
return b;
}
void Add(char *num1, char *num2)
{
int len1, len2;
int i, j;
i = LEN - 1;
while(num1[--i] == 0 && i > 0);
len1 = i;
len2 = strlen(num2);
int lenm = Max(len1, len2);
for(i = 0; i < len2; i++)
num2[i] -= '0';
for(i = 0; i < len2 / 2; i++)//reverse num2
{
int c = num2[i];
num2[i] = num2[len2 - 1 - i];
num2[len2 - 1 - i] = c;
}
for(i = 0; i < lenm + 2; i++)//add num1 && num2
num1[i] += num2[i];
int t = 0;
int t2;
for(i = 0; i < lenm + 2; i++)//carry bit
{
t2 = num1[i] + t;
num1[i] = t2 % 10;
t = t2 / 10;
}
}
int main()
{
int i, j;
char num1[LEN];
char num2[LEN];
memset(num1, 0, sizeof(num1));
memset(num2, 0, sizeof(num2));
gets(num2);
while(strcmp(num2, "0") != 0)
{
Add(num1, num2);
memset(num2, 0, sizeof(num2));
gets(num2);
}
i = LEN - 1;
while(num1[--i] == 0 && i > 0);
if(i == 0)
printf("0\n");
else
{
for(; i >= 0; i--)
printf("%d", num1[i]);
putchar(10);
}
//system("pause");
}
posted @
2012-08-11 08:58 小鼠标 阅读(379) |
评论 (0) |
编辑 收藏进制转换，题目要求实现2-16之间任意进制的相互转换，超过10的数字用A、B、C等表示，结果不能超过7位，否则输出ERROR。思路是先将原数字转换为十进制，然后再转换为目标进制。字符串处理问题，注意细节。
表扬一下秀，又让我学到了不少东西。
代码如下：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h>
#define LEN 200
int main()
{
int i, j;
char str0[LEN];
char str1[LEN];
char str2[LEN];
int a, b;
while(gets(str0))
{
sscanf(str0, "%s%d%d", str1, &a, &b);
int len = strlen(str1);
for(i = 0; i < len; i++)
{
if(isdigit(str1[i]))
str1[i] -= '0';
else
str1[i] = str1[i] - 'A' + 10;
}
int sum = 0;
for(i = 0; i < len; i++)
{
sum *= a;
sum += str1[i];
}
int count = 0;
while(sum > 0)
{
str2[count++] = sum % b;
sum /= b;
}
if(count > 7)
printf(" ERROR");
else
{
for(i = 0; i < 7 - count; i++)
putchar(' ');
for(i = count - 1; i >= 0; i--)
printf("%c", str2[i] >= 10 ? str2[i] - 10 + 'A' : str2[i] + '0');
}
putchar(10);
}
//system("pause");
}
posted @
2012-08-10 16:58 小鼠标 阅读(155) |
评论 (0) |
编辑 收藏题意描述：求出多米诺骨牌中从开始到最后那一块骨牌倒下所花费的时间。
解题思路：先用Dijkstra算法求出每一个关键点倒下时花的时间，然后判断最后一块骨牌倒下的位置，以确定其倒下的时间。我们知道最后一块骨牌要么就是关键点，要么在两个关键点之间。如果是在关键点之间的情况，假设这两个关键点的时间为t1和题t2，两点之间的边长为t3，则最后一块骨牌倒下所花时间为(t1+t2+t3)/2。
以下是本题代码：
（渐渐发现，做题不仅仅是比着书上已有的代码抄一遍那么简单）
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<limits.h>
#define LEN 510
#define MAX INT_MAX
int mp[LEN][LEN];
int main()
{
int i, j;
int n, m;
int a, b, l;
int count = 1;
scanf("%d%d", &n, &m);
while(m + n != 0)
{
memset(mp, 0, sizeof(mp));
for(i = 0; i < m; i++)
{
scanf("%d%d%d", &a, &b, &l);
mp[a][b] = mp[b][a] = l;
}
int s[LEN] = {0};
int cost[LEN];
int cost1[LEN];
s[1] = 1;
for(i = 1; i <= n; i++)
if(mp[1][i] != 0)
cost[i] = mp[1][i];
else
cost[i] = MAX;
cost[1] = 0;
int t = 1;
for(j = 1; j <= n - 1; j++)
{
t = 1;
int min = MAX;
for(i = 1; i <= n; i++)
if(s[i] == 0 && cost[i] < min)
{
t = i;
min = cost[i];
}
s[t] = 1;
for(i = 1; i <= n; i++)
if(s[i] == 0 && mp[t][i] != 0 && mp[t][i] + cost[t] < cost[i])
cost[i] = mp[t][i] + cost[t];
}
int gard = 1;
double max = -MAX;
int p0;
for(i = 1; i <= n; i++)
if(max < cost[i])
{
max = cost[i];
p0 = i;
}
int p1 = 1;
int p2 = 1;
for(i = 1; i <= n; i++)
for(j = i + 1; j <= n; j++)
{
double x1 = 1.0 * (cost[i] + cost[j] + mp[i][j]) / 2;
if(mp[i][j] != 0 && x1 > max)
{
gard = 0;
max = x1;
p1 = i;
p2 = j;
}
}
if(count++ != 1)
putchar(10);
printf("System #%d\n", count - 1);
if(gard == 1)
{
printf("The last domino falls after %.1lf seconds, at key domino %d.\n", max, p0);
}
else
{
if(p1 > p2)
{
int t1 = p1;
p1 = p2;
p2 = t1;
}
printf("The last domino falls after %.1lf seconds, between key dominoes %d and %d.\n", max, p1, p2);
}
scanf("%d%d", &n, &m);
}
//system("pause");
}
posted @
2012-08-09 20:04 小鼠标 阅读(217) |
评论 (0) |
编辑 收藏题意描述：N头牛要从不同的节点赶到一个节点开会，开完会返回原处，所有的道路都是有向路，求出往返花费时间最长的那头牛花费的时间。
看到这题，第一感觉就是对每个节点用一次Dijkstra，1000的数据量，无情的超时了。看网上大神们的代码，发现用两遍Dijkstra就行了，第一遍是求出从目的地X出发，到达其余点的时间，第二遍还是从X出发，不过要把所有边反向使用。把每个节点两次的时间加一起，求出最大的那个即可。
代码如下：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define LEN 1010
#define MAX 200000000
int mp[LEN][LEN];
int N, M, X;
int cost[LEN];
void Dijkstrabk(int f)
{
int i, j;
int s[LEN] = {0};
s[f] = 1;
for(i = 1; i <= N; i++)
if(mp[f][i] != 0)
cost[i] = mp[f][i];
else
cost[i] = MAX;
cost[f] = 0;
for(j = 1; j <= N - 1; j++)
{
int t = f;
int min = MAX;
for(i = 1; i <= N; i++)
if(s[i] == 0 && cost[i] < min)
{
t = i;
min = cost[i];
}
s[t] = 1;
for(i = 1; i <= N; i++)
if(s[i] == 0 && mp[t][i] != 0 && mp[t][i] + cost[t] < cost[i])
cost[i] = mp[t][i] + cost[t];
}
}
void Dijkstracm(int f)
{
int i, j;
int s[LEN] = {0};
s[f] = 1;
for(i = 1; i <= N; i++)
if(mp[i][f] != 0)
cost[i] = mp[i][f];
else
cost[i] = MAX;
cost[f] = 0;
for(j = 1; j <= N - 1; j++)
{
int t = f;
int min = MAX;
for(i = 1; i <= N; i++)
if(s[i] == 0 && cost[i] < min)
{
t = i;
min = cost[i];
}
s[t] = 1;
for(i = 1; i <= N; i++)
if(s[i] == 0 && mp[i][t] != 0 && mp[i][t] + cost[t] < cost[i])
cost[i] = mp[i][t] + cost[t];
}
}
int main()
{
int i, j;
int A, B, T;
int bkcost[LEN];
int cmcost[LEN];
int allcost;
while(scanf("%d%d%d", &N, &M, &X) != EOF)
{
memset(mp, 0, sizeof(mp));
for(i = 0; i < M; i++)//reaa mp
{
scanf("%d%d%d", &A, &B, &T);
if(mp[A][B] == 0)
mp[A][B] = T;
else if(mp[A][B] > T)
mp[A][B] = T;
}
Dijkstrabk(X);
for(i = 1; i <= N; i++)
bkcost[i] = cost[i];
Dijkstracm(X);
allcost = -MAX;
for(i = 1; i <= N; i++)
if(bkcost[i] + cost[i] > allcost)
allcost = bkcost[i] + cost[i];
printf("%d\n", allcost);
}
//system("pause");
}
posted @
2012-08-09 16:18 小鼠标 阅读(223) |
评论 (0) |
编辑 收藏虽然是一道很水很水的题，但是我感觉很有必要写点东西。
这是同学让我帮她调的题，大凡人们都不爱看别人代码，我也是，以前很少看别人代码，不同的风格，不同的想法，看起来很让人纠结，不过这次彻底让我转变了思想。
这道题没什么值得多说的，就是考察对输入字符串的处理。同学虽然有很多细节没有注意到，但是她的解题思路却让我的思路焕然一新，大有醍醐灌顶之感。独学而无友，孤陋寡闻，说的不就是寡人吗。
以下是本题代码：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define LEN 200
int main()
{
int i, j;
char s0[LEN];
char s1[LEN], s2[LEN];
int cost;
int earn = 0;
char c0,c1;
while(1)
{
gets(s0);
if(strcmp(s0, "#") == 0)
break;
if(strcmp(s0,"0") == 0)
{
printf("%d\n", earn);
earn = 0;
continue;
}
sscanf(s0, "%s%s%d%c%c", s1, s2, &cost, &c1, &c0);
if(c0 == 'F')
{
earn += 2 * cost;
}
else if(c0 == 'B')
{
earn += cost + cost / 2;
}
else if(c0 == 'Y')
{
if(cost <= 500)
earn += 500;
else
earn += cost;
}
//
//printf("s0 = %s\n", s0);
//printf("s1 = %s s2 = %s cost = %d c = %c\n", s1, s2, cost, c0);
//
}
//system("pause");
}
posted @
2012-08-09 11:17 小鼠标 阅读(321) |
评论 (0) |
编辑 收藏
摘要: dijkstra算法是解决单源最短路径问题的经典算法，具有O(N^2)的时间复杂度（N为节点个数），这种算法采用的是贪心策略，它与最小生成树的Prim算法极其相似，这两种算法仅仅是cost[]代表的含义不同……
阅读全文
posted @
2012-08-08 16:27 小鼠标 阅读(1869) |
评论 (0) |
编辑 收藏题意描述：
公青蛙a要找到母青蛙b，他要跳过若干块石头到达b处，他并不关心走过总路程的长短，但是希望单次跳动的长度最短。
最短路Dijkstra算法。
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define LEN 210
#define MAX 100000
typedef struct
{
double x;
double y;
}Point;
int main()
{
int i, j;
int n;
int x, y;
double mp[LEN][LEN];
Point ps[LEN];
scanf("%d", &n);
int count = 1;
while(n != 0)
{
//
//printf("n = %d\n", n);
//
for(i = 0; i < n; i++)
scanf("%lf%lf", &ps[i].x, &ps[i].y);
for(i = 0; i < n; i++)
for(j = i + 1; j < n; j++)
{
double dx = ps[i].x - ps[j].x;
double dy = ps[i].y - ps[j].y;
mp[i][j] = mp[j][i] = sqrt(dx * dx + dy * dy);
}
for(i = 0; i < n; i++)
mp[i][i] = MAX;
double minlenall = -MAX;
int s[LEN] = {0};
double cost[LEN];
int pre[LEN];
for(i = 0; i < n; i++)
{
cost[i] = mp[0][i];
if(mp[0][i] != MAX)
pre[i] = 0;
else
pre[i] = -1;
}
s[0] = 1;
pre[0] = -1;
for(j = 0; j <= n - 2; j++)//dijkstra
{
int t = 0;
double min = MAX;
for(i = 0; i < n; i++)//find min
if(s[i] == 0 && cost[i] < min)
{
min = cost[i];
t = i;
}
s[t] = 1;// into S[]
for(i = 0; i < n; i++)//update
{
if(s[i] == 0 && mp[t][i] < cost[i])
{
cost[i] = mp[t][i];
pre[i] = t;
}
}
}
int tt = 1;
int tt1 = pre[tt];
while(pre[tt] != -1)
{
if(mp[tt][tt1] > minlenall)
minlenall = mp[tt][tt1];
tt = tt1;
tt1 = pre[tt1];
}
printf("Scenario #%d\n", count++);
printf("Frog Distance = %.3lf\n\n", minlenall);
scanf("%d", &n);
}
//system("pause");
}
posted @
2012-08-07 23:51 小鼠标 阅读(122) |
评论 (0) |
编辑 收藏