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 小鼠標 閱讀(254) |
評論 (0) |
編輯 收藏
摘要: 回溯算法的經典例題。大一的時候就有耳聞，卻一直沒有實現，今天終于有機會把它寫出來，小有成就感啊。這里算法采用的是深度優先搜索，從第一個節點開始，按行優先的原則逐個掃描每個點，如果該點合法，可以選擇放一個queen也可以選擇不放，當該點不合法時，就跳過該點接著判斷下一個點。有人把回溯算法說成是“萬能算法”，這么說的原因是回溯實際上就是枚舉，它的最壞情況始終是指數或階乘級的。對...
閱讀全文
posted @
2012-05-11 20:24 小鼠標 閱讀(404) |
評論 (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 小鼠標 閱讀(140) |
評論 (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 小鼠標 閱讀(141) |
評論 (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 小鼠標 閱讀(147) |
評論 (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 小鼠標 閱讀(226) |
評論 (0) |
編輯 收藏
摘要: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3204一道很直接的最小生成樹，題中給出了權值矩陣，本應給用Prim的，但是為了練習一下并查集的使用，選擇了Kruskal。前面我寫過Kruskal，但是集合的表示用的是線性表，每次合并都要花費O(N)的時間，效率較低。這次用了并查集——集合的樹形表示，...
閱讀全文
posted @
2012-04-26 10:01 小鼠標 閱讀(304) |
評論 (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 小鼠標 閱讀(123) |
評論 (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 小鼠標 閱讀(303) |
評論 (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 小鼠標 閱讀(313) |
評論 (0) |
編輯 收藏