|
|
2. 尋找入口點
--- 獲得源碼
直接在主頁就可以下載到了，用ubuntu的可以很方便的get到：
apt-get source bash
我的ubuntu是9.04，get到的是bash-3.2。沒有打debian的補丁。
--- Makefile
bash的Makefile是由autoconf工具根據Makefile.in和configure.in來生成的。
Makefile中只有小部分的配置是可更改的，一般來說這小部分都是不重要的部分。
所以./configure后生成出來的Makefile與Makefile.in相比差別不大。我們把Makefile.in視為Makefile。
--- 主要依賴關系
打開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)
簡要的看了一下，LIBDEP和BUILTINS_DEP是一些靜態庫，單獨實現一些功能的模塊。我們可以先不看。
而OBJECTS看起來就是bash的核心部分了。
其中形似$(xxx_O)的變量是在./configure中指定的，不用理會。
--- 關鍵文件列表
整理了一下
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并不是個省油的燈，區區30多個核心文件就4w多行代碼。比linux0.11還大。
其中的subst.c更是巔峰造極，8000行。
統計一下bash工程的總代碼量：
find -name '*.[ch]' | xargs cat | wc -l
結果是13w+行。。真挺多的
--- 入口點
這么多文件，沒有理由一個個去找main函數。首先在源碼根目錄下執行ctags -R *。
ctags看源碼的時候也會用到的。然后 vi -t main。就可以列出所有main函數的定義。
這時候我們發現有幾十個main函數，就像劍圣的分身一樣，真假難辯。
從程序員的直覺可以得出shell.c里面的main函數是真身。
其他的main函數都是測試用的。
形如：
#ifdef xxx_TEST
main() { ... }
#endif
下一篇我們就從 shell.c 里的 main 開始分析。
--- bash 的生日
shell.c 文件開頭的那一段注釋尾部：
...
Birthdate:
Sunday, January 10th, 1988.
Initial author: Brian Fox
*/
bash 居然已經誕生了20多年了，比我還大9個月。這么說來，也是個80后呢。
呵呵，bash 都算是個富二代了：
貴族出身（GNU），身邊不乏追求者（貢獻者），還搭上了一個90后mm（linux）。
--- bash是大多數linux發行版的默認shell
Ubuntu、Fedora、Puppy。。。
查詢你現在使用的shell的方法：
env | grep SHELL
--- bash是內核與應用程序之間的橋梁
linux絕大部分操作是基于命令行，也就是通過bash來調用程序。
當運行了一個腳本，bash就要負責管理一系列進程，處理好進程的文件、管道、信號、同步等等。
而了解這些細節，對于我們日常使用也是很有幫助的。
--- Just for fun
這不是什么一定要完成的任務，純粹是為了消磨時間，有一天我找到事情做了，我就不會繼續寫下去了，這很正常。
摘要: 這題基本上沒有算法，只用了一個字符串的hash。但代碼很長，200+行。非常榮幸的1ac了！
#include <stdio.h>#include <string.h>#define MAX_LINES 2048#define MAX_LINE_LEN 128#define MAX_DOCS ... 閱讀全文
并查集加上分數運算就可以了。 兩種物品之間的兌換比率可以用分數來表示，兩種物品之間是否存在聯系用并查集來表示。
#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;
}
思路如下： 匹配的遞歸過程如下。 把單詞和正文都轉換成mos碼來表示。 從正文的頭部開始匹配。 如果某個單詞是正文的前綴，那么從前綴后面的部分遞歸下去。 統計一下所有方案的數目，就是答案了。 子問題就是“從位置k開始匹配，有多少種方案”，數組保存即可。 關鍵在于怎樣快速發現某個單詞是正文的前綴。 如果順序查找，復雜度O(N)，超時。 如果枚舉單詞長度后二分查找，復雜度O(L*lgN)，應該不會超時，但代碼不太自然，比較難寫。 如果枚舉單詞長度后用hash查找，復雜度O(L)，不會超時，而且代碼比較好寫。 事實證明，經典的字符串hash函數同樣可以用于mos碼，在65536格的閉hash里面沒有產生沖突！
#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;
}
回家待了幾天，我覺得再繼續頹廢下去也不是個辦法。還是得他媽的振作！振作！ 跟以前一樣，按照計劃行事。 每天2題，難度隨意。做不出來絕對不死磕，找標程或者數據弄懂再說。管他媽什么算法，我只管寫代碼。 項目緊的時候做項目，不緊的時候看點代碼或者寫點代碼，啥都行，主要是保持一個感覺。 剩下的時間就練吉他。 今天開始做了第一題，結果悲劇。 我日你媽poj，能不能不要他媽的加數據，為啥子官方數據都過了還是過不了你那的。。
#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;
}
摘要: 這題看上去很冷門~其實也是的，第一眼看上去想不到好的解法，但是將問題稍稍轉化一下就很好辦了。思路：兩個pattern匹配的過程，如果沒有通配符，那就是從左到右，逐個逐個的匹配。由于存在通配符，a的一個節點有可能匹配b的數個節點，同樣，b的一個節點也有可能匹配a的數個節點。這就需要搜索了。但是一開始發現搜索的時候通配符的處理真的很麻煩。感覺就是代碼稍微寫錯一點就會WA。于是想簡化一下問題。重新定義三... 閱讀全文
思路： 將每個字符串的原文的所有后綴和反轉后的所有后綴都插入到Trie中。 同時Trie中的節點維護一個值 --- 該節點下面包含了多少個不同單詞的節點。 然后統計這個值等于N的最深的節點，其深度就是答案了。 后綴Trie并不是好的解法。有人說用后綴數組也能做的，但是想不出來。
 #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;
}
思路： 考慮最左邊的需要移除墻的列。這列是必定要移除一些墻的。 不妨移除右邊界較大的那些墻。 實現的時候，可以用基數排序的方式來找到右邊界較大的墻。 開兩個數組如下： map[i][j] = { 第i列中，從該列開始向右延伸，長度為j的墻的數目} cnt[i] = {第i列中墻的數目} 這樣代碼比較方便，速度也快。
#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;
}
近來實驗室給派了新活，跟原來做的東西，以及我們熟悉的東西都比較不搭邊的，郁悶。
折騰了兩個星期，昨天終于有了些進展。
今天做了兩道水題~ 都是貪心
思路： 這題看上去挺唬人，提交的人也不多，實際上都是水題來的。 1. 對于同一種字母，求出它出現位置的最左邊、最右邊、最上邊、最下邊。這就構成了一個矩形。 2. 對于在x軸上投影重合的一系列矩形，他們必定處在同一個方格內。給這些方格編號。 3. 對于在y軸上投影重合的一系列矩形，如果其中兩個編號相同，就不符合條件了。
#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;
}
|