http://acm.nyist.net/JudgeOnline/problem.php?pid=540今年省賽時的第一道題。歡迎大家去刷河南省賽題。
一周沒有刷題，回生了，這么一道題花了兩個多小時。真不該跟妹子聊天。
題意：按數(shù)字倒序后的大小排序。
本打算把數(shù)字轉(zhuǎn)為字符串，然后對字符串用strcmy()，發(fā)現(xiàn)這樣是不對的，應(yīng)為"11"會小于"8"，而事實(shí)是相反的。后來想到用兩個數(shù)組存原數(shù)和倒序后的數(shù)，按倒序后的數(shù)排序后輸出正序的數(shù)字，終于A了。汗啊。
注意cmp()函數(shù)的寫法。
。
#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 小鼠標(biāo) 閱讀(262) |
評論 (0) |
編輯 收藏
摘要: 回溯算法的經(jīng)典例題。大一的時候就有耳聞，卻一直沒有實(shí)現(xiàn)，今天終于有機(jī)會把它寫出來，小有成就感啊。這里算法采用的是深度優(yōu)先搜索，從第一個節(jié)點(diǎn)開始，按行優(yōu)先的原則逐個掃描每個點(diǎn)，如果該點(diǎn)合法，可以選擇放一個queen也可以選擇不放，當(dāng)該點(diǎn)不合法時，就跳過該點(diǎn)接著判斷下一個點(diǎn)。有人把回溯算法說成是“萬能算法”，這么說的原因是回溯實(shí)際上就是枚舉，它的最壞情況始終是指數(shù)或階乘級的。對...
閱讀全文
posted @
2012-05-11 20:24 小鼠標(biāo) 閱讀(413) |
評論 (0) |
編輯 收藏大數(shù)加法，字符串處理。關(guān)鍵是細(xì)節(jié)，這方面的問題我老是把邊界下標(biāo)搞錯，比如這次就是因?yàn)樵L問到了數(shù)組的len元素而導(dǎo)致結(jié)果出錯。
關(guān)與加法的策略：
以前未解決兩個家數(shù)的對齊問題，我會先把兩個字符串倒序，相加、進(jìn)位后再倒回來，感覺這樣到來倒去的實(shí)在麻煩。
現(xiàn)在頓悟了，果斷不再倒序，從字符串的高下標(biāo)處開始相加兩個數(shù)，只要有數(shù)字的下標(biāo)低于1（0位用來保存進(jìn)位）就停止。具體做法是：
1.用c（指針）記錄較長的那個數(shù)字
2.預(yù)處理：把a(bǔ)、b數(shù)組內(nèi)的字符轉(zhuǎn)化為數(shù)字
3.從a、b數(shù)組的高下標(biāo)處（實(shí)際加數(shù)的低位）開始相加數(shù)字a、b
4.從數(shù)字的高下標(biāo)處開始處理進(jìn)位
5.完成處理：把數(shù)字轉(zhuǎn)化為字符
注意：消除和的前導(dǎo)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 小鼠標(biāo) 閱讀(145) |
評論 (0) |
編輯 收藏完全背包。
要點(diǎn)：
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 小鼠標(biāo) 閱讀(151) |
評論 (0) |
編輯 收藏
看了這么多天的背包，總算漸漸開始理解了。
背包問題有很多種，基本的有兩種：0-1背包和完全背包。多重背包可由這兩種組合得來。
本題是多重背包問題，可以簡單的將多重背包直接轉(zhuǎn)化為0-1背包來求解，但是這種轉(zhuǎn)化很有可能導(dǎo)致超時，因?yàn)槲锲窋?shù)量太多了。可行的辦法是利用 二進(jìn)制狀態(tài)壓縮，這樣可以大大減少物品數(shù)量（實(shí)際物品數(shù)量只有l(wèi)og（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 小鼠標(biāo) 閱讀(158) |
評論 (0) |
編輯 收藏赤裸裸的0-1背包，很水。聽說省賽要出DP題，我們隊(duì)三個人都不擅長DP，于是乎我開始從背包問題入手學(xué)習(xí)動態(tài)規(guī)劃。看了幾天的背包，頭都大了，還是不理解，今天終于A掉了一道水題，值得紀(jì)念一下。
關(guān)于背包這里就不多說了，感興趣的童鞋可以參考《背包問題九講》。
#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 小鼠標(biāo) 閱讀(235) |
評論 (0) |
編輯 收藏
摘要: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3204一道很直接的最小生成樹，題中給出了權(quán)值矩陣，本應(yīng)給用Prim的，但是為了練習(xí)一下并查集的使用，選擇了Kruskal。前面我寫過Kruskal，但是集合的表示用的是線性表，每次合并都要花費(fèi)O(N)的時間，效率較低。這次用了并查集——集合的樹形表示，...
閱讀全文
posted @
2012-04-26 10:01 小鼠標(biāo) 閱讀(327) |
評論 (0) |
編輯 收藏最小生成樹prim算法。
最近剛學(xué)過Dijkstra的最短路算法，仔細(xì)分析一下，Dijkstra與Prim算法十分相似，區(qū)別在于更新點(diǎn)時的標(biāo)準(zhǔn)不同。前者是該點(diǎn)到起點(diǎn)的距離（用dist[]記錄）最小，則將該點(diǎn)加入s，并更新相應(yīng)的dist[]，后者是該點(diǎn)到s中任意一點(diǎn)的距離（用lowcost[]記錄）最小，則將該點(diǎn)加入s，并更新相應(yīng)的lowcost[]。
說來慚愧，這一題錯在了格式上，沒有認(rèn)真讀題，多保留了一位小數(shù)。
經(jīng)驗(yàn)總結(jié)：認(rèn)真讀題。
#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 小鼠標(biāo) 閱讀(134) |
評論 (0) |
編輯 收藏成語接龍問題，抽象出來就是簡單的最簡單的單源最短路徑問題，Dijkstra算法。
算法設(shè)計(jì)課上剛講過貪心算法，Dijkstra算法書上有代碼實(shí)現(xiàn)，比著書上的代碼copy了一遍，提交后居然奇跡般的出現(xiàn)了段錯誤！這叫我情何以堪啊。FAQ上說段錯誤有兩種情況：數(shù)組下標(biāo)越界和棧溢出。算法中沒有遞歸，不可能爆棧，認(rèn)真檢查每一個用到下標(biāo)的地方、每個for的起始點(diǎn)，看不出任何毛病。難道代碼比著書上抄錯了，對照了一下，發(fā)現(xiàn)第二個循環(huán)開始時沒有初始化u，問題就出在這里，u是用來記錄下一個可加入集合s的節(jié)點(diǎn)的，它的更新來自于所有可利用的dist[]中最下的那個。
經(jīng)驗(yàn)總結(jié)：變量不要忘記初始化。
#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 小鼠標(biāo) 閱讀(312) |
評論 (0) |
編輯 收藏
算法的效率異常重要，對于一個專業(yè)的計(jì)算機(jī)人員來說，應(yīng)將效提高算法率放在心里，時刻注意。這種思想應(yīng)該深入我們的骨髓，成為一種習(xí)慣。
以前我寫過pow函數(shù)，不過那都沒動腦子，簡單的線性時間運(yùn)算。這里有一個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;
} 算法雖然簡單，但卻體現(xiàn)了編程工作者應(yīng)具備的基本素質(zhì)。
posted @
2012-04-23 09:14 小鼠標(biāo) 閱讀(323) |
評論 (0) |
編輯 收藏