|
|
2. 尋找入口點(diǎn)
--- 獲得源碼
直接在主頁就可以下載到了，用ubuntu的可以很方便的get到：
apt-get source bash
我的ubuntu是9.04，get到的是bash-3.2。沒有打debian的補(bǔ)丁。
--- Makefile
bash的Makefile是由autoconf工具根據(jù)Makefile.in和configure.in來生成的。
Makefile中只有小部分的配置是可更改的，一般來說這小部分都是不重要的部分。
所以./configure后生成出來的Makefile與Makefile.in相比差別不大。我們把Makefile.in視為Makefile。
--- 主要依賴關(guān)系
打開Makefile.in。從all開始跟下去。
all -> .made -> $(Program)
Program = bash$(EXEEXT)
$(Program): .build $(OBJECTS) $(BUILTINS_DEP) $(LIBDEP)
LIBDEP = $(SHLIB_DEP) $(INTL_DEP) $(READLINE_DEP) $(HISTORY_DEP) $(TERMCAP_DEP) $(GLOB_DEP) \
$(TILDE_DEP) $(MALLOC_DEP)
BUILTINS_DEP = $(BUILTINS_LIBRARY)
BUILTINS_LIBRARY = $(DEFDIR)/libbuiltins.a
# Matching object files.
OBJECTS = shell.o eval.o y.tab.o general.o make_cmd.o print_cmd.o $(GLOBO) \
dispose_cmd.o execute_cmd.o variables.o copy_cmd.o error.o \
expr.o flags.o $(JOBS_O) subst.o hashcmd.o hashlib.o mailcheck.o \
trap.o input.o unwind_prot.o pathexp.o sig.o test.o version.o \
alias.o array.o arrayfunc.o braces.o bracecomp.o bashhist.o \
bashline.o $(SIGLIST_O) list.o stringlib.o locale.o findcmd.o redir.o \
pcomplete.o pcomplib.o syntax.o xmalloc.o $(SIGNAMES_O)
簡(jiǎn)要的看了一下，LIBDEP和BUILTINS_DEP是一些靜態(tài)庫，單獨(dú)實(shí)現(xiàn)一些功能的模塊。我們可以先不看。
而OBJECTS看起來就是bash的核心部分了。
其中形似$(xxx_O)的變量是在./configure中指定的，不用理會(huì)。
--- 關(guān)鍵文件列表
整理了一下
1795 shell.c
275 eval.c
6277 y.tab.c
1029 general.c
856 make_cmd.c
1307 print_cmd.c
329 dispose_cmd.c
4143 execute_cmd.c
4270 variables.c
422 copy_cmd.c
452 error.c
1348 expr.c
355 flags.c
8140 subst.c
196 hashcmd.c
442 hashlib.c
438 mailcheck.c
983 trap.c
627 input.c
318 unwind_prot.c
438 pathexp.c
595 sig.c
825 test.c
83 version.c
574 alias.c
932 array.c
837 arrayfunc.c
630 braces.c
200 bracecomp.c
823 bashhist.c
3199 bashline.c
137 list.c
284 stringlib.c
509 locale.c
598 findcmd.c
1086 redir.c
1394 pcomplete.c
225 pcomplib.c
193 xmalloc.c
47564 總用量
可見bash并不是個(gè)省油的燈，區(qū)區(qū)30多個(gè)核心文件就4w多行代碼。比linux0.11還大。
其中的subst.c更是巔峰造極，8000行。
統(tǒng)計(jì)一下bash工程的總代碼量：
find -name '*.[ch]' | xargs cat | wc -l
結(jié)果是13w+行。。真挺多的
--- 入口點(diǎn)
這么多文件，沒有理由一個(gè)個(gè)去找main函數(shù)。首先在源碼根目錄下執(zhí)行ctags -R *。
ctags看源碼的時(shí)候也會(huì)用到的。然后 vi -t main。就可以列出所有main函數(shù)的定義。
這時(shí)候我們發(fā)現(xiàn)有幾十個(gè)main函數(shù)，就像劍圣的分身一樣，真假難辯。
從程序員的直覺可以得出shell.c里面的main函數(shù)是真身。
其他的main函數(shù)都是測(cè)試用的。
形如：
#ifdef xxx_TEST
main() { ... }
#endif
下一篇我們就從 shell.c 里的 main 開始分析。
--- bash 的生日
shell.c 文件開頭的那一段注釋尾部：
...
Birthdate:
Sunday, January 10th, 1988.
Initial author: Brian Fox
*/
bash 居然已經(jīng)誕生了20多年了，比我還大9個(gè)月。這么說來，也是個(gè)80后呢。
呵呵，bash 都算是個(gè)富二代了：
貴族出身（GNU），身邊不乏追求者（貢獻(xiàn)者），還搭上了一個(gè)90后mm（linux）。
--- bash是大多數(shù)linux發(fā)行版的默認(rèn)shell
Ubuntu、Fedora、Puppy。。。
查詢你現(xiàn)在使用的shell的方法：
env | grep SHELL
--- bash是內(nèi)核與應(yīng)用程序之間的橋梁
linux絕大部分操作是基于命令行，也就是通過bash來調(diào)用程序。
當(dāng)運(yùn)行了一個(gè)腳本，bash就要負(fù)責(zé)管理一系列進(jìn)程，處理好進(jìn)程的文件、管道、信號(hào)、同步等等。
而了解這些細(xì)節(jié)，對(duì)于我們?nèi)粘Ｊ褂靡彩呛苡袔椭摹?br>
--- Just for fun
這不是什么一定要完成的任務(wù)，純粹是為了消磨時(shí)間，有一天我找到事情做了，我就不會(huì)繼續(xù)寫下去了，這很正常。
摘要: 這題基本上沒有算法，只用了一個(gè)字符串的hash。但代碼很長，200+行。非常榮幸的1ac了！
#include <stdio.h>#include <string.h>#define MAX_LINES 2048#define MAX_LINE_LEN 128#define MAX_DOCS ... 閱讀全文
并查集加上分?jǐn)?shù)運(yùn)算就可以了。 兩種物品之間的兌換比率可以用分?jǐn)?shù)來表示，兩種物品之間是否存在聯(lián)系用并查集來表示。
#include <stdio.h>
#include <string.h>
typedef struct {
int a, b;
} frac ;
#define MAX_ITEM 64
char item[MAX_ITEM][32];
int item_cnt;
struct {
frac f;
int p;
} set[MAX_ITEM];
int gcd(int a, int b)
{
int t;
if (a > b) {
a ^= b;
b ^= a;
a ^= b;
}
while (a) {
t = a;
a = b % a;
b = t;
}
return b;
}
frac init(int a, int b)
{
frac r;
int g = gcd(a, b);
r.a = a / g;
r.b = b / g;
return r;
}
frac mul(frac a, frac b)
{
return init(a.a * b.a, a.b * b.b);
}
frac div(frac a, frac b)
{
return init(a.a * b.b, a.b * b.a);
}
int find(int i)
{
int p;
if (set[i].p == i)
return i;
p = find(set[i].p);
set[i].f = mul(set[set[i].p].f, set[i].f);
set[i].p = p;
return p;
}
int insert(char *s)
{
int i;
for (i = 0; i < item_cnt; i++)
if (!strcmp(s, item[i]))
return i;
strcpy(item[item_cnt], s);
return item_cnt++;
}
int main()
{
char op[16], sa[32], sb[32];
int a, b, ia, ib, i, p;
frac f;
for (i = 0; i < MAX_ITEM; i++) {
set[i].p = i;
set[i].f = init(1, 1);
}
while (scanf("%s", op), op[0] != '.') {
if (op[0] == '!') {
scanf("%d%s%*s%d%s", &a, sa, &b, sb);
ia = insert(sa);
ib = insert(sb);
find(ia);
p = set[ia].p;
set[p].p = ib;
set[p].f = div(init(b, a), set[ia].f);
} else {
scanf("%s%*s%s", sa, sb);
ia = insert(sa);
ib = insert(sb);
find(ia);
find(ib);
if (set[ia].p == set[ib].p) {
f = div(set[ia].f, set[ib].f);
printf("%d %s = %d %s\n", f.b, item[ia], f.a, item[ib]);
} else
printf("? %s = ? %s\n", item[ia], item[ib]);
}
}
return 0;
}
思路如下： 匹配的遞歸過程如下。 把單詞和正文都轉(zhuǎn)換成mos碼來表示。 從正文的頭部開始匹配。 如果某個(gè)單詞是正文的前綴，那么從前綴后面的部分遞歸下去。 統(tǒng)計(jì)一下所有方案的數(shù)目，就是答案了。 子問題就是“從位置k開始匹配，有多少種方案”，數(shù)組保存即可。 關(guān)鍵在于怎樣快速發(fā)現(xiàn)某個(gè)單詞是正文的前綴。 如果順序查找，復(fù)雜度O(N)，超時(shí)。 如果枚舉單詞長度后二分查找，復(fù)雜度O(L*lgN)，應(yīng)該不會(huì)超時(shí)，但代碼不太自然，比較難寫。 如果枚舉單詞長度后用hash查找，復(fù)雜度O(L)，不會(huì)超時(shí)，而且代碼比較好寫。 事實(shí)證明，經(jīng)典的字符串hash函數(shù)同樣可以用于mos碼，在65536格的閉hash里面沒有產(chǎn)生沖突！
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
char *mos[] = {
".-",
"- ",
"-.-.",
"-..",
".",
"..-.",
"--.",
".",
"..",
".---",
"-.-",
".-..",
"--",
"-.",
"---",
".--.",
"--.-",
".-.",
"",
"-",
"..-",
"-",
".--",
"-..-",
"-.--",
"--..",
};
#define HASH_SIZE 65536
#define INPUT_LEN 10032
struct _hash {
int val, cnt;
};
struct _hash hash[HASH_SIZE];
int dp[INPUT_LEN];
int max_len;
int strhash(char *str, int len)
{
int val;
for (val = 0; len--; str++)
val = val*31 + *str;
return val & 0x7fffffff;
}
struct _hash *find(int val)
{
int h;
for (h = val % HASH_SIZE;
hash[h].cnt && hash[h].val != val;
h = (h + 1) % HASH_SIZE
);
return &hash[h];
}
void insert(char *str)
{
int len = strlen(str);
int val = strhash(str, len);
struct _hash *h = find(val);
// printf("insert %s\n", str);
if (len > max_len)
max_len = len;
h->val = val;
h->cnt++;
}
int calc(char *str, int start)
{
struct _hash *h;
int i, s;
// printf("start %d %s\n", start, str + start);
if (!str[start])
return 1;
if (dp[start] != -1)
return dp[start];
s = 0;
for (i = 1; str[start + i - 1] && i <= max_len; i++) {
h = find(strhash(str + start, i));
// printf("len %d %s cnt %d\n", i, str + start, h->cnt);
if (h->cnt)
s += calc(str, start + i) * h->cnt;
}
dp[start] = s;
return s;
}
void solve()
{
int i, j, d, n;
static char word[32], str[256], in[10032];
memset(dp, -1, sizeof(dp));
memset(hash, 0, sizeof(hash));
scanf("%s%d", in, &n);
for (i = 0; i < n; i++) {
scanf("%s", word);
str[0] = 0;
for (j = 0; word[j]; j++)
strcat(str, mos[word[j] - 'A']);
insert(str);
}
// printf("max_len %d\n", max_len);
printf("%d\n", calc(in, 0));
}
int main()
{
int d;
scanf("%d", &d);
while (d--)
solve();
return 0;
}
回家待了幾天，我覺得再繼續(xù)頹廢下去也不是個(gè)辦法。還是得他媽的振作！振作！ 跟以前一樣，按照計(jì)劃行事。 每天2題，難度隨意。做不出來絕對(duì)不死磕，找標(biāo)程或者數(shù)據(jù)弄懂再說。管他媽什么算法，我只管寫代碼。 項(xiàng)目緊的時(shí)候做項(xiàng)目，不緊的時(shí)候看點(diǎn)代碼或者寫點(diǎn)代碼，啥都行，主要是保持一個(gè)感覺。 剩下的時(shí)間就練吉他。 今天開始做了第一題，結(jié)果悲劇。 我日你媽poj，能不能不要他媽的加數(shù)據(jù)，為啥子官方數(shù)據(jù)都過了還是過不了你那的。。
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 50032
int K, N, V;
struct node {
int base, area, sign;
};
struct node arr[MAX_N*2];
int cmp(const void *a, const void *b)
{
return ((struct node *)a)->base - ((struct node *)b)->base;
}
int main()
{
int b, h, w, d, i, a, v;
scanf("%d", &K);
while (K--) {
scanf("%d", &N);
for (i = 0; i < N; i++) {
scanf("%d%d%d%d", &b, &d, &w, &h);
arr[i*2].base = b;
arr[i*2].area = w * h;
arr[i*2].sign = 1;
arr[i*2 + 1].base = b + d;
arr[i*2 + 1].area = w * h;
arr[i*2 + 1].sign = -1;
}
scanf("%d", &V);
qsort(arr, N*2, sizeof(arr[0]), cmp);
a = 0;
for (i = 0; i < N*2; i++) {
v = i ? a * (arr[i].base - arr[i - 1].base) : 0;
if (V <= v) {
printf("%.2lf\n", (double)V / a + arr[i - 1].base);
break;
}
V -= v;
a += arr[i].sign * arr[i].area;
}
if (i == N*2)
printf("OVERFLOW\n");
}
return 0;
}
摘要: 這題看上去很冷門~其實(shí)也是的，第一眼看上去想不到好的解法，但是將問題稍稍轉(zhuǎn)化一下就很好辦了。思路：兩個(gè)pattern匹配的過程，如果沒有通配符，那就是從左到右，逐個(gè)逐個(gè)的匹配。由于存在通配符，a的一個(gè)節(jié)點(diǎn)有可能匹配b的數(shù)個(gè)節(jié)點(diǎn)，同樣，b的一個(gè)節(jié)點(diǎn)也有可能匹配a的數(shù)個(gè)節(jié)點(diǎn)。這就需要搜索了。但是一開始發(fā)現(xiàn)搜索的時(shí)候通配符的處理真的很麻煩。感覺就是代碼稍微寫錯(cuò)一點(diǎn)就會(huì)WA。于是想簡(jiǎn)化一下問題。重新定義三... 閱讀全文
思路： 將每個(gè)字符串的原文的所有后綴和反轉(zhuǎn)后的所有后綴都插入到Trie中。 同時(shí)Trie中的節(jié)點(diǎn)維護(hù)一個(gè)值 --- 該節(jié)點(diǎn)下面包含了多少個(gè)不同單詞的節(jié)點(diǎn)。 然后統(tǒng)計(jì)這個(gè)值等于N的最深的節(jié)點(diǎn)，其深度就是答案了。 后綴Trie并不是好的解法。有人說用后綴數(shù)組也能做的，但是想不出來。
 #include <stdio.h>
#include <string.h>
  struct node {
 char ch;
int ts, cnt;
struct node *sib, *child;
 };
struct node nodes[65536], root;
int nodes_cnt;
int N, T;
int ts, ans;
inline struct node *insert(struct node *q, char ch, int depth)
{
struct node *t;
for (t = q->child; t; t = t->sib)
if (t->ch == ch)
break;
  if (!t) {
t = &nodes[nodes_cnt++];
t->ch = ch;
t->cnt = 0;
t->child = NULL;
t->sib = q->child;
q->child = t;
 }
if (t->ts != ts) {
t->ts = ts;
t->cnt++;
}
if (t->cnt == N && depth > ans)
ans = depth;
return t;
}
int main()
{
int i, j, k, len;
char str[128];
struct node *t;
scanf("%d", &T);
while (T--) {
scanf("%d", &N);
ans = 0;
nodes_cnt = 0;
root.child = root.sib = NULL;
root.cnt = 0;
for (i = 0; i < N; i++) {
scanf("%s", str);
ts++;
len = strlen(str);
for (j = 0; j < len; j++) {
t = &root;
for (k = j; k < len; k++)
t = insert(t, str[k], k - j + 1);
}
for (j = len - 1; j >= 0; j--) {
t = &root;
for (k = j; k >= 0; k--)
t = insert(t, str[k], j - k + 1);
}
}
printf("%d\n", ans);
}
return 0;
}
思路： 考慮最左邊的需要移除墻的列。這列是必定要移除一些墻的。 不妨移除右邊界較大的那些墻。 實(shí)現(xiàn)的時(shí)候，可以用基數(shù)排序的方式來找到右邊界較大的墻。 開兩個(gè)數(shù)組如下： map[i][j] = { 第i列中，從該列開始向右延伸，長度為j的墻的數(shù)目} cnt[i] = {第i列中墻的數(shù)目} 這樣代碼比較方便，速度也快。
#include <stdio.h>
#include <string.h>
int T, N, K;
char map[128][128];
int cnt[128];
int main()
{
int x1, x2, y;
int i, j, i2, j2, ans;
scanf("%d", &T);
while (T--) {
scanf("%d%d", &N, &K);
memset(map, 0, sizeof(map));
memset(cnt, 0, sizeof(cnt));
while (N--) {
scanf("%d%d%d%d", &x1, &y, &x2, &y);
if (x1 > x2) {
x1 ^= x2;
x2 ^= x1;
x1 ^= x2;
}
for (i = x1; i <= x2; i++) {
map[i][x2 - i + 1]++;
cnt[i]++;
}
}
ans = 0;
for (i = 0; i <= 100; i++) {
if (cnt[i] <= K)
continue;
for (j = 100; cnt[i] > K && j > 0; j--) {
while (cnt[i] > K && map[i][j]) {
i2 = i;
j2 = j;
while (j2) {
map[i2][j2]--;
cnt[i2]--;
j2--;
i2++;
}
ans++;
}
}
}
printf("%d\n", ans);
}
return 0;
}
近來實(shí)驗(yàn)室給派了新活，跟原來做的東西，以及我們熟悉的東西都比較不搭邊的，郁悶。
折騰了兩個(gè)星期，昨天終于有了些進(jìn)展。
今天做了兩道水題~ 都是貪心
思路： 這題看上去挺唬人，提交的人也不多，實(shí)際上都是水題來的。 1. 對(duì)于同一種字母，求出它出現(xiàn)位置的最左邊、最右邊、最上邊、最下邊。這就構(gòu)成了一個(gè)矩形。 2. 對(duì)于在x軸上投影重合的一系列矩形，他們必定處在同一個(gè)方格內(nèi)。給這些方格編號(hào)。 3. 對(duì)于在y軸上投影重合的一系列矩形，如果其中兩個(gè)編號(hào)相同，就不符合條件了。
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
struct rect {
int left, right, top, bottom;
int rank_x;
} rec[32];
int T, K, P;
int cmp_x(const void *a, const void *b)
{
return ((struct rect *)a)->left - ((struct rect *)b)->left;
}
int cmp_y(const void *a, const void *b)
{
return ((struct rect *)a)->top - ((struct rect *)b)->top;
}
inline int solve()
{
int i, last, rank, mask;
qsort(rec, K, sizeof(rec[0]), cmp_x);
rank = 0;
for (i = 0; i < K; ) {
last = rec[i].right;
while (i < K && rec[i].left <= last) {
rec[i].rank_x = rank;
last = max(last, rec[i].right);
i++;
}
rank++;
}
qsort(rec, K, sizeof(rec[0]), cmp_y);
for (i = 0; i < K; ) {
mask = 0;
last = rec[i].bottom;
while (i < K && rec[i].top <= last) {
if (mask & (1 << rec[i].rank_x))
return 0;
mask |= 1 << rec[i].rank_x;
last = max(last, rec[i].bottom);
i++;
}
}
return 1;
}
int main()
{
int i, j, x, y;
scanf("%d", &T);
while (T--) {
scanf("%d%d", &K, &P);
for (i = 0; i < K; i++) {
rec[i].left = rec[i].top = 1000000;
rec[i].right = rec[i].bottom = 0;
for (j = 0; j < P; j++) {
scanf("%d%d", &x, &y);
if (x < rec[i].left)
rec[i].left = x;
if (x > rec[i].right)
rec[i].right = x;
if (y < rec[i].top)
rec[i].top = y;
if (y > rec[i].bottom)
rec[i].bottom = y;
}
}
printf("%s\n", solve() ? "YES" : "NO");
}
return 0;
}
|