摘要: 題意描述：
我們知道英語描述數字與漢語是不同的，題目要求給出英文描述的數字，輸出實際的數字。
解題思路是，把所有關鍵字分成兩類，一類是“數字”，另一類是“權重”，遇到數字就加上去，遇到權重就乘上去，最后輸出結果就是了。不過這樣還不行，因為這會導致權重累計相乘，比如前面有一個million，要乘1000 000，后面又有一個thousand，還要乘1000，這顯然是不對的……
閱讀全文
posted @
2012-08-12 09:18 小鼠標 閱讀(1202) |
評論 (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 小鼠標 閱讀(336) |
評論 (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 小鼠標 閱讀(323) |
評論 (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 小鼠標 閱讀(399) |
評論 (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 小鼠標 閱讀(182) |
評論 (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 小鼠標 閱讀(229) |
評論 (0) |
編輯 收藏題意描述：N頭牛要從不同的節點趕到一個節點開會，開完會返回原處，所有的道路都是有向路，求出往返花費時間最長的那頭?；ㄙM的時間。
看到這題，第一感覺就是對每個節點用一次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 小鼠標 閱讀(234) |
評論 (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 小鼠標 閱讀(353) |
評論 (0) |
編輯 收藏
摘要: dijkstra算法是解決單源最短路徑問題的經典算法，具有O(N^2)的時間復雜度（N為節點個數），這種算法采用的是貪心策略，它與最小生成樹的Prim算法極其相似，這兩種算法僅僅是cost[]代表的含義不同……
閱讀全文
posted @
2012-08-08 16:27 小鼠標 閱讀(1884) |
評論 (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 小鼠標 閱讀(132) |
評論 (0) |
編輯 收藏