摘要: 題意描述：
我們知道英語(yǔ)描述數(shù)字與漢語(yǔ)是不同的，題目要求給出英文描述的數(shù)字，輸出實(shí)際的數(shù)字。
解題思路是，把所有關(guān)鍵字分成兩類(lèi)，一類(lèi)是“數(shù)字”，另一類(lèi)是“權(quán)重”，遇到數(shù)字就加上去，遇到權(quán)重就乘上去，最后輸出結(jié)果就是了。不過(guò)這樣還不行，因?yàn)檫@會(huì)導(dǎo)致權(quán)重累計(jì)相乘，比如前面有一個(gè)million，要乘1000 000，后面又有一個(gè)thousand，還要乘1000，這顯然是不對(duì)的……
閱讀全文
posted @
2012-08-12 09:18 小鼠標(biāo) 閱讀(1219) |
評(píng)論 (0) |
編輯 收藏一道簡(jiǎn)簡(jiǎn)單單的大數(shù)加法題，時(shí)間竟然卡在getchar()和putchar()上，我用scanf()和printf()硬是超時(shí)了，超時(shí)了啊親，這么坑爹的有木有啊，有木有！！
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 小鼠標(biāo) 閱讀(350) |
評(píng)論 (0) |
編輯 收藏
不多解釋?zhuān)斍閰㈤單业南嚓P(guān)文章。
Add()的兩個(gè)參數(shù)都是逆序的整數(shù)數(shù)組，結(jié)果存在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 小鼠標(biāo) 閱讀(340) |
評(píng)論 (0) |
編輯 收藏
大數(shù)相加。字符串處理，注意細(xì)節(jié)，注意初始化。
以下是本題代碼：
#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 小鼠標(biāo) 閱讀(411) |
評(píng)論 (0) |
編輯 收藏進(jìn)制轉(zhuǎn)換，題目要求實(shí)現(xiàn)2-16之間任意進(jìn)制的相互轉(zhuǎn)換，超過(guò)10的數(shù)字用A、B、C等表示，結(jié)果不能超過(guò)7位，否則輸出ERROR。思路是先將原數(shù)字轉(zhuǎn)換為十進(jìn)制，然后再轉(zhuǎn)換為目標(biāo)進(jìn)制。字符串處理問(wèn)題，注意細(xì)節(jié)。
表?yè)P(yáng)一下秀，又讓我學(xué)到了不少東西。
代碼如下：
#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 小鼠標(biāo) 閱讀(197) |
評(píng)論 (0) |
編輯 收藏題意描述：求出多米諾骨牌中從開(kāi)始到最后那一塊骨牌倒下所花費(fèi)的時(shí)間。
解題思路：先用Dijkstra算法求出每一個(gè)關(guān)鍵點(diǎn)倒下時(shí)花的時(shí)間，然后判斷最后一塊骨牌倒下的位置，以確定其倒下的時(shí)間。我們知道最后一塊骨牌要么就是關(guān)鍵點(diǎn)，要么在兩個(gè)關(guān)鍵點(diǎn)之間。如果是在關(guān)鍵點(diǎn)之間的情況，假設(shè)這兩個(gè)關(guān)鍵點(diǎn)的時(shí)間為t1和題t2，兩點(diǎn)之間的邊長(zhǎng)為t3，則最后一塊骨牌倒下所花時(shí)間為(t1+t2+t3)/2。
以下是本題代碼：
（漸漸發(fā)現(xiàn)，做題不僅僅是比著書(shū)上已有的代碼抄一遍那么簡(jiǎn)單）
#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 小鼠標(biāo) 閱讀(243) |
評(píng)論 (0) |
編輯 收藏題意描述：N頭牛要從不同的節(jié)點(diǎn)趕到一個(gè)節(jié)點(diǎn)開(kāi)會(huì)，開(kāi)完會(huì)返回原處，所有的道路都是有向路，求出往返花費(fèi)時(shí)間最長(zhǎng)的那頭牛花費(fèi)的時(shí)間。
看到這題，第一感覺(jué)就是對(duì)每個(gè)節(jié)點(diǎn)用一次Dijkstra，1000的數(shù)據(jù)量，無(wú)情的超時(shí)了。看網(wǎng)上大神們的代碼，發(fā)現(xiàn)用兩遍Dijkstra就行了，第一遍是求出從目的地X出發(fā)，到達(dá)其余點(diǎn)的時(shí)間，第二遍還是從X出發(fā)，不過(guò)要把所有邊反向使用。把每個(gè)節(jié)點(diǎn)兩次的時(shí)間加一起，求出最大的那個(gè)即可。
代碼如下：
#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 小鼠標(biāo) 閱讀(249) |
評(píng)論 (0) |
編輯 收藏雖然是一道很水很水的題，但是我感覺(jué)很有必要寫(xiě)點(diǎn)東西。
這是同學(xué)讓我?guī)退{(diào)的題，大凡人們都不愛(ài)看別人代碼，我也是，以前很少看別人代碼，不同的風(fēng)格，不同的想法，看起來(lái)很讓人糾結(jié)，不過(guò)這次徹底讓我轉(zhuǎn)變了思想。
這道題沒(méi)什么值得多說(shuō)的，就是考察對(duì)輸入字符串的處理。同學(xué)雖然有很多細(xì)節(jié)沒(méi)有注意到，但是她的解題思路卻讓我的思路煥然一新，大有醍醐灌頂之感。獨(dú)學(xué)而無(wú)友，孤陋寡聞，說(shuō)的不就是寡人嗎。
以下是本題代碼：
#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 小鼠標(biāo) 閱讀(367) |
評(píng)論 (0) |
編輯 收藏
摘要: dijkstra算法是解決單源最短路徑問(wèn)題的經(jīng)典算法，具有O(N^2)的時(shí)間復(fù)雜度（N為節(jié)點(diǎn)個(gè)數(shù)），這種算法采用的是貪心策略，它與最小生成樹(shù)的Prim算法極其相似，這兩種算法僅僅是cost[]代表的含義不同……
閱讀全文
posted @
2012-08-08 16:27 小鼠標(biāo) 閱讀(1900) |
評(píng)論 (0) |
編輯 收藏題意描述：
公青蛙a要找到母青蛙b，他要跳過(guò)若干塊石頭到達(dá)b處，他并不關(guān)心走過(guò)總路程的長(zhǎng)短，但是希望單次跳動(dòng)的長(zhǎng)度最短。
最短路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 小鼠標(biāo) 閱讀(140) |
評(píng)論 (0) |
編輯 收藏