文章提示：戳擊圖示展開 fancybox，隨後可用方向鍵更換圖片。

「我不明白！作為弱者的心情。」

『即使不帥氣、即使不強大、即使不正確、即使不美麗、即使不可愛、即使不乾淨，我也想贏過那些帥氣、強大、正確、美麗、可愛、乾淨的傢伙』
－又沒贏呢。

大學三年就這麼過去，資工系在大四之後就沒有必修課，而系選修學分也相當足夠，當然如果跟其他學校比起來，專業領域的學分限制沒有這麼多，也就是說可以採用其他的一般課程通過畢業門檻。

撇開這不談，畢業門檻見鬼去吧！

女王雖然不錯，但是球球精神仍在心中。『我啊，一直是弱者的同伴。』沒有辦法贏，但是也不能輸。但是，最近也開始疲累了，拖動著愚蠢的自己－一台簡單化的學習機器，毫無思考與突變的物種，在那段日子下，不斷地被迫前進，在茫茫的道路下行走，走過得足跡也逐漸淡去。山因為累積起的土堆而高起，然而人卻不斷地失憶，這樣要如何驗證自己的進步呢。

每個人都是迷惘的，但不斷在此周旋也不是辦法。

三年下來，說明白就是太混，成績好不好似乎也不是太重要。可謂窮得只剩下過去。

現在的我正過著每天獨自一個人的生活，偶爾才會見見真人的朋友，而對方認為是不是朋友也無法得知，有人會說這樣疑神疑鬼，會這樣也是理所當然的。

最近仍舊寫寫 UVa 混混日子，也達到 2200+ 的題目數量，隨後也在 Github 在弄中文翻譯 link，慢慢整理吧，有興趣者也可以參與翻譯部分。

對 repo fork 出來後，發送 pull request 即可，雖然明白也不會有多少人去注目。「逃避英文是不好的」這句話已經聽膩了，什麼正向面對，人類會悲觀對事是經過數年的演化得來，悲觀才能對事情進行縝密的思考 (採取自《羅輯思維》)，我才沒有向你們這麼樂觀去看待學習自己一直弄不來的項目。

有段時間沒有上 QQ，居然還有人向我投來關心的留言，都不知道上次對話是哪個時候了，自己也曾會向數年不見的人傳封簡訊，但隨著年齡增加就會開始膽怯去做這件事情。浪漫天真呢。

花點時間打了這一篇，畢竟相對於之前打文章的頻率，這一半年來說的確下降了許多，準確來講是沒有作什麼偉大的事情，或者是有所成長的體悟，反倒是黑歷史不斷地增加。害怕第一字都不想要紀錄。

這個暑假有幾件事情得做

• 先把不小心答應的暑期課程給結束掉－跟碩班上課什麼的，雖然已經升大四不是藉口，但那是吾等沒辦法突破的障礙，課程作為補品實在是太補了，總覺得會學不來。
• 活下去的目標－談到要好朋友到底要怎麼共事，對於別人，吾等實在太過於沉重。
• 推甄研究所的話，必須準備自傳等相關項目。反之，就準備吊高高。
• 做點成就項目－看到目前做了什麼項目，還真是慘不忍睹
• 其他－天真浪漫的事情就不奢求，自由隨興的糟糕習慣，想做什麼就去做什麼，連墮落也是。

最近在 facebook 常流行大學內的相關情緒討論粉絲頁，說說咱們的 “靠北中央” (諸多如 “魯蛇/表特/靠北/告白/道歉 …” + “台大/清華/交大/成大/中央 …”)，熱門的話題就是「到底要不要繳交系學會費 $\$ 5000$ 」這筆款項說少不少，說多也大不至於，四年下來差不多就繳交這麼一次，相當於學費的五分之一。

尤其在該版面上，資工系的靠北文異常地多，雖然皆採用匿名制 (撇開自曝其名的人不談)，針對咱們資工的文章還真是不少，更增添給系上不少的黑歷史，相關文章集中在編號 #1500 之前。

每次看到戰文真是又氣又笑，當然收錢那方的擁護者不少，但是有時候不是年年政策都一樣，之前的擁護者可能不知道現在到底是怎麼黑箱作業。

在轉學之前，在中興的確有繳交一樣是 $\$ 5000 $ 的款項，但是在許多活動沒有參與下，系學會的確有將款項退給我，而系服雖然設計不好，但仍然是有拿到，中興那邊人少好辦事，因此也不至於偷偷地將款項給吃了。

轉學之後，沒有繳交系費的款項，當然也盡可能地不參與系上活動，畢竟那是要花錢的，而系上活動免費的餐飲 buffet 到底能不能去吃，讓我也相當困惑。使用者付費，仔細想想沒有白吃的午餐，這項舉動還是少做為之。除了系費之外，系隊費用、轉聯會費用 … 等，通常費用會有關服裝或者是活動參與，在很多的活動下得知會有社團衣服，雖然繳交那筆錢之後，沒有去拿衣服是我的不對，但沒有像中興那種有人會來發送衣服的情況，就算遇到負責人在不同場合也不會談到這件事情，因此服裝就這麼消散，小錢是沒有什麼，但是觀感就不怎麼好，我這種宅宅不是那麼主動會想要去搭訕混熟。

平常沒有什麼機會談話，藉由發送這些活動相關項目，也可以藉此打好關係和認識吧！也許是我的幻象，這何等的幼稚思維。之後就一項活動都沒有去參與，異類就在此，總不能假裝與你們相同，這對你們來說是不尊重的。

尤其是在資工系諸如此類的人還不少，因此在很多人正常的宅宅學弟們就會明白，這筆款項是交給陽光般參與活動的人花費，而他們只是繳錢的金主 (除非是 M，否則誰願意繳交)。吾等活在黑暗中展現自己的思維與磨練自身，參與活動的記憶模式，早已被不斷地學習給淡化了，不是不願意參與活動，而是不懂得如何參與。

這場戰爭還在繼續，肯定是不會停止的。

不過裡面最令人又哭又笑的是其中一段，學弟反攻學長的制度，中間一段用了程序上的設計來比喻他們的做事行為，但是學長 (跟我同屆) 則以「學弟好好讀書行嗎 ? 這個不是這樣比喻的 …」類似的口吻回覆，結果被別系同學糾正學長對學弟指導的程序概念。在旁人眼中，到底誰才是學資工專業呢？因此也有人表示「資工系怎麼如此地殘缺」，看到貼人當下還真不知道要保持什麼心態，護衛自己系的好頓時不是主要意識，跟室友談到這一段時「就說說只是資工系少部分人就好啦！」但是心想，也許是大部分人都會錯，在渾渾噩噩的學習情境下，能真正明白自己在做什麼的人的確很少，連我也不例外。

Problem

You probably know what a set of collinear points is: a set of points such that there exists a straight line that passes through all of them. A set of cocircular points is defined in the same fashion, but instead of a straight line, we ask that there is a circle such that every point of the set lies over its perimeter.

The International Collinear Points Centre (ICPC) has assigned you the following task: given a set of points, calculate the size of the larger subset of cocircular points.

Input

Each test case is given using several lines. The first line contains an integer N representing the number of points in the set (1$ \le$N$ \le$100). Each of the next N lines contains two integers X and Y representing the coordinates of a point of the set (- 104$ \le$X, Y$ \le$104). Within each test case, no two points have the same location.

The last test case is followed by a line containing one zero.

Output

For each test case output a single line with a single integer representing the number of points in one of the largest subsets of the input that are cocircular.

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

7 
-10 0 
0 -10 
10 0 
0 10 
-20 10 
-10 20 
-2 4 
4 
-10000 10000 
10000 10000 
10000 -10000 
-10000 -9999 
3 
-1 0 
0 0 
1 0 
0

Sample Output

1
2
3

5 
3 
2

Solution

題目描述：

給平面上 n 個點，最多有多少個點共圓？

題目解法：

窮舉三點拉外心，隨後找共圓的點，最慘會到 O(n^4)。

完全沒有剪枝，也就是說可以刻意將點保留標記，防止窮舉到相同組合，又或者是先按照 x 軸排序，直接在區間內搜索可能的共圓點之類的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103

#include <stdio.h> 
#include <stdio.h> 
#include <math.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define eps 1e-6
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    	x(a), y(b) {}
    bool operator<(const Pt &a) const {
        if(fabs(x-a.x) > eps)
            return x < a.x;
        return y < a.y;
    }
    Pt operator+(const Pt &a) const {
        return Pt(x + a.x, y + a.y);
    }
	Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
    Pt operator/(const double a) const {
        return Pt(x/a, y/a);
    }
};
double dist(Pt a, Pt b) {
	return hypot(a.x - b.x, a.y - b.y);
}
double dist2(Pt a, Pt b) {
	return (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y);
}
double length(Pt a) {
	return hypot(a.x, a.y);
}
double dot(Pt a, Pt b) {
	return a.x * b.x + a.y * b.y;
}
double cross2(Pt a, Pt b) {
	return a.x * b.y - a.y * b.x;
}
double cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y) - (a.y-o.y)*(b.x-o.x);
}
double angle(Pt a, Pt b) {
	return acos(dot(a, b) / length(a) / length(b));
}
Pt rotateRadian(Pt a, double radian) {
	double x, y;
	x = a.x * cos(radian) - a.y * sin(radian);
	y = a.x * sin(radian) + a.y * cos(radian);
	return Pt(x, y);
}
Pt getIntersection(Pt p, Pt l1, Pt q, Pt l2) {
	double a1, a2, b1, b2, c1, c2;
	double dx, dy, d;
	a1 = l1.y, b1 = -l1.x, c1 = a1 * p.x + b1 * p.y;
	a2 = l2.y, b2 = -l2.x, c2 = a2 * q.x + b2 * q.y;
	d = a1 * b2 - a2 * b1;
	dx = b2 * c1 - b1 * c2;
	dy = a1 * c2 - a2 * c1;
	return Pt(dx / d, dy / d);
}
Pt circle(Pt a, Pt b, Pt c) {
	Pt mab = (a + b)/2;
	Pt mbc = (b + c)/2;
	Pt lab = b - a, lbc = c - b;
	swap(lab.x, lab.y);
	swap(lbc.x, lbc.y);
	lab.x = -lab.x;
	lbc.x = -lbc.x;
	return getIntersection(mab, lab, mbc, lbc);
}
int main() {
	int n;
	Pt D[128];
	while(scanf("%d", &n) == 1 && n) {
		for(int i = 0; i < n; i++) {
			scanf("%lf %lf", &D[i].x, &D[i].y);
		}
		int ret = min(2, n);
		for(int i = 0; i < n; i++) {
			for(int j = i + 1; j < n; j++) {
				for(int k = j + 1; k < n; k++) {
					if(fabs(cross(D[i], D[j], D[k])) < eps)
						continue;
					Pt o = circle(D[i], D[j], D[k]);
//					printf("%lf %lf %lf %lf %lf %lf\n", D[i].x, D[i].y, D[j].x, D[j].y, D[k].x, D[k].y);
//					printf("circle %lf %lf\n", o.x, o.y);
					double d = dist2(o, D[i]);
					int cnt = 0;
					for(int p = 0; p < n; p++) {
						if(fabs(d - dist2(D[p], o)) < eps)
							cnt++;
					}
					ret = max(ret, cnt);
				}
			}
		}
		printf("%d\n", ret);
	}
	return 0;
}

Problem

Dr. Ellie Arroway has established contact with an extraterrestrial civilization. However, all efforts to decode their messages have failed so far because, as luck would have it, they have stumbled upon a race of stuttering aliens! Her team has found out that, in every long enough message, the most important words appear repeated a certain number of times as a sequence of consecutive characters, even in the middle of other words. Furthermore, sometimes they use contractions in an obscure manner. For example, if they need to say bab twice, they might just send the message babab, which has been abbreviated because the second b of the first word can be reused as the first b of the second one.

Thus, the message contains possibly overlapping repetitions of the same words over and over again. As a result, Ellie turns to you, S.R. Hadden, for help in identifying the gist of the message.

Given an integer m, and a string s, representing the message, your task is to find the longest substring of s that appears at least m times. For example, in the message baaaababababbababbab, the length-5 word babab is contained 3 times, namely at positions 5, 7 and 12 (where indices start at zero). No substring appearing 3 or more times is longer (see the first example from the sample input). On the other hand, no substring appears 11 times or more (see example 2).

In case there are several solutions, the substring with the rightmost occurrence is preferred (see example 3).

Input

The input contains several test cases. Each test case consists of a line with an integer m (m$ \ge$1), the minimum number of repetitions, followed by a line containing a string s of length between m and 40 000, inclusive. All characters in s are lowercase characters from a'' toz’’. The last test case is denoted by m = 0 and must not be processed.

Output

Print one line of output for each test case. If there is no solution, output none; otherwise, print two integers in a line, separated by a space. The first integer denotes the maximum length of a substring appearing at least m times; the second integer gives the rightmost possible starting position of such a substring.

Sample Input

1
2
3
4
5
6
7

3
baaaababababbababbab
11
baaaababababbababbab
3
cccccc
0

Sample Output

1
2
3

5 12
none
4 2

Solution

題目描述：

對於一個字串，找到一段最長子字串出現至少 m 次，若存有多個輸出最右邊位置的子字串。

題目解法：

建造後綴數組，得到高度數組後，二分搜索長度，然後掃描高度數組找尋是否有連續大於等於 m 次的區間。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
using namespace std;
struct SuffixArray {
    int sa[40005], h[40005], n;
    int w[40005], ta[40005], tb[40005];
    char str[40005];
    void sort(int *x, int *y, int m) {
        static int i;
        for(i = 0; i < m; i++)
            w[i] = 0;
        for(i = 0; i < n; i++)
            w[x[y[i]]]++;
        for(i = 1; i < m; i++)
            w[i] += w[i-1];
        for(i = n-1; i >= 0; i--)
            sa[--w[x[y[i]]]] = y[i];
    }
    bool cmp(int *r, int a, int b, int l) {
        if(r[a] == r[b]) {
            if(a+l >= n || b+l >= n)
                return false;
            return r[a+l] == r[b+l];
        }
        return false;
    }
    void build_h() {
        int i, j, k;
        for(i = 0; i < n; i++)  ta[sa[i]] = i;
        for(i = 0; i < n; i++) {
            if(ta[i] == 0) {
                h[ta[i]] = 0;
                continue;
            }
            if(i == 0 || h[ta[i-1]] <= 1)
                k = 0;
            else
                k = h[ta[i-1]]-1;
            while(str[sa[ta[i]-1]+k] == str[sa[ta[i]]+k])
                k++;
            h[ta[i]] = k;
        }
    }
    void build() {// x: rank, y: second key
        int i, k, m = 128, p;
        int *x = ta, *y = tb, *z;
        n = strlen(str);
        x[n] = 0;
        for(i = 0; i < n; i++)
            x[i] = str[i], y[i] = i;
        sort(x, y, m);
        for(k = 1, p = 1; p < n; k *= 2, m = p) {
            for(p = 0, i = n-k; i < n; i++)
                y[p++] = i;
            for(i = 0; i < n; i++) {
                if(sa[i] >= k) {
                    y[p++] = sa[i]-k;
                }
            }
            sort(x, y, m);
            z = x, x = y, y = z;
            for(i = 1, p = 1, x[sa[0]] = 0; i < n; i++)
                x[sa[i]] = cmp(y, sa[i-1], sa[i], k) ? p-1 : p++;
        }
    }
};
SuffixArray in;
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
    int m;
    while(scanf("%d", &m) == 1 && m) {
    	scanf("%s", in.str);
        in.build();
        in.build_h();
        if(m == 1) {
        	printf("%d %d\n", in.n, 0);
        	continue;
    	}
//        for(int i = 0; i < in.n; i++)
//        	printf("%s %d\n", in.str + in.sa[i], in.h[i]);
        int l = 1, r = in.n, mid, ret = -1, retpos;
        while(l <= r) {
        	mid = (l + r)/2;
        	int cnt = 1, mxtime = 0, mxpos = 0;
        	for(int i = 0; i <= in.n; i++) {
        		if(i != in.n && in.h[i] >= mid)
        			cnt++;
        		else {
        			if(mxtime < cnt)
        				mxtime = cnt;
        			if(cnt >= m) {
        				int j = i;
        				do {
        					j--;
        					mxpos = max(mxpos, in.sa[j]);
        				} while(in.h[j] >= mid && j >= 0);
        			}
        			cnt = 1;
        		}
        	}
        	if(mxtime >= m)
        		l = mid + 1, ret = mid, retpos = mxpos;
        	else
        		r = mid - 1;
        }
        if(ret == -1)
        	puts("none");
        else
        	printf("%d %d\n", ret, retpos);
    }
    return 0;
}
/*
1
aaaaa
2
ufzyetzjulljnkbaohjsqpiucxjo
*/

Problem

A given triangle can be either equilateral (three sides of the same length), scalene (three sides of different lengths), or isosceles (two sides of the same length and a third side of a different length). It is a known fact that points with all integer coordinates cannot be the vertices of an equilateral triangle.

You are given a set of different points with integer coordinates on the XY plane, such that no three points in the set lay on the same line. Your job is to calculate how many of the possible choices of three points are the vertices of an isosceles triangle.

Input

There are several test cases. Each test case is given in several lines. The first line of each test case contains an integer N indicating the number of points in the set (3$ \le$N$ \le$1000). Each of the next N lines describes a different point of the set using two integers X and Y separated by a single space (1$ \le$X, Y$ \le$106); these values represent the coordinates of the point on the XY plane. You may assume that within each test case no two points have the same location and no three points are collinear.

The last test case is followed by a line containing a single zero.

Output

For each test case output a single line with a single integer indicating the number of subsets of three points that are the vertices of an isosceles triangle.

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14

5 
1 2 
2 1 
2 2 
1 1 
1000 1000000 
6 
1000 1000 
996 1003 
996 997 
1003 996 
1003 1004 
992 1000 
0

Sample Output

1
2

4
10

Solution

題目描述：

給平面 N 個點，任挑三個點有多少以某個節點為頂點的等腰三角形。

題目解法：

直接對單一頂點找到對於其他頂點的的所有距離，排序後找重複的長度進行組合計算，將複雜度 O(n^3) 降到 O(n^2 log n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

#include <stdio.h> 
#include <algorithm>
using namespace std;
int main() {
	int N;
	long long X[1024], Y[1024];
	while(scanf("%d", &N) == 1 && N) {
		for(int i = 0; i < N; i++)
			scanf("%lld %lld", &X[i], &Y[i]); 
		long long d[1024];
		long long ret = 0;
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++)
				d[j] = (X[i] - X[j]) * (X[i] - X[j]) +
						(Y[i] - Y[j]) * (Y[i] - Y[j]);
			sort(d, d+N);
			long long cnt = 1;
			d[N] = -1;
			for(int j = 1; j <= N; j++) {
				if(d[j] != d[j-1]) {
					ret += cnt * (cnt-1) /2;
					cnt = 1;
				} else {
					cnt++;
				}
			} 
		}
		printf("%lld\n", ret);
	}
	return 0;
}

Problem

Your school has a computer that is used as a web server for hosting its institutional web site, personal pages of the staff, sites for research groups, subjects, and many others.

Recently, the hard disk table was corrupted, so the organization of all the files was lost. Sadly enough, there are no backups of that information. The only hope is to look through the entire disk data and try to find out which parts correspond to each file. Fortunately, the disk was using a file system that kept each individual file contiguous, so only contiguous pieces of data need to be inspected.

The disk data is a sequence of bytes. Each byte in this particular disk can store an English alphabet letter (distinguishing lowercase and uppercase), a decimal digit, a point or a comma, making a total of 64 different characters.

While you were thinking about how to solve the problem, you suddenly remembered that the file system also maintained multiple copies of each file, so only the pieces of contiguous bytes that are repeated had a chance of being a file. Moreover, for each repetition of the same contiguous bytes, only one copy needs to be checked. For instance, if the data is ababcabb', the contiguous subsequencesa’, b' andab’ are repeated, but nothing containing c', norba’ or `bb’ is. Therefore, we have 3 pieces of contiguous bytes that need checking in this case.

You decide to write a program that computes exactly how many sequences need checking, that is, the number of different sequences of contiguous bytes that appear at least twice in the data.

Input

There are several test cases. The input of each test case is given in exactly one line, containing a non-empty string of at most 105 characters that represents the disk data. Each character in the string is either a lowercase letter, an uppercase letter, a digit, a point or a comma.

The last test case is followed by a line containing a single asterisk.

Output

For each test case output a single line with an integer, representing the number of different contiguous subsequences that appear at least twice in the input string.

Sample Input

1
2
3
4
5
6

ababcabb 
mississippi 
aaaaaaaaaaaaaaaaaaaaaaaaaa 
012345678,abcdefg.STUVWXYZ 
say.twice,say.twice 
*

Sample Output

1
2
3
4
5

3 
9 
25 
0 
45

Solution

題目描述：

有多少不同的子字串符合出現至少兩次的條件。

題目解法：

建造後綴數組，得到高度數組後，根據遞增的情況進行計算不同字符串的個數。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct SuffixArray {
    int sa[100005], h[100005], n;
    int w[100005], ta[100005], tb[100005];
    char str[100005];
    void sort(int *x, int *y, int m) {
        static int i;
        for(i = 0; i < m; i++)
            w[i] = 0;
        for(i = 0; i < n; i++)
            w[x[y[i]]]++;
        for(i = 1; i < m; i++)
            w[i] += w[i-1];
        for(i = n-1; i >= 0; i--)
            sa[--w[x[y[i]]]] = y[i];
    }
    bool cmp(int *r, int a, int b, int l) {
        if(r[a] == r[b]) {
            if(a+l >= n || b+l >= n)
                return false;
            return r[a+l] == r[b+l];
        }
        return false;
    }
    void build_h() {
        int i, j, k;
        for(i = 0; i < n; i++)  ta[sa[i]] = i;
        for(i = 0; i < n; i++) {
            if(ta[i] == 0) {
                h[ta[i]] = 0;
                continue;
            }
            if(i == 0 || h[ta[i-1]] <= 1)
                k = 0;
            else
                k = h[ta[i-1]]-1;
            while(str[sa[ta[i]-1]+k] == str[sa[ta[i]]+k])
                k++;
            h[ta[i]] = k;
        }
    }
    void build() {// x: rank, y: second key
        int i, k, m = 128, p;
        int *x = ta, *y = tb, *z;
        n = strlen(str);
        x[n] = 0;
        for(i = 0; i < n; i++)
            x[i] = str[i], y[i] = i;
        sort(x, y, m);
        for(k = 1, p = 1; p < n; k *= 2, m = p) {
            for(p = 0, i = n-k; i < n; i++)
                y[p++] = i;
            for(i = 0; i < n; i++) {
                if(sa[i] >= k) {
                    y[p++] = sa[i]-k;
                }
            }
            sort(x, y, m);
            z = x, x = y, y = z;
            for(i = 1, p = 1, x[sa[0]] = 0; i < n; i++)
                x[sa[i]] = cmp(y, sa[i-1], sa[i], k) ? p-1 : p++;
        }
    }
};
SuffixArray in;
int main() {
    while(scanf("%s", in.str)) {
    	if(!strcmp("*", in.str))
    		break;
        in.build();
        in.build_h();
//		for(int i = 0; i < in.n; i++)
//			printf("%s %d\n", in.str + in.sa[i], in.h[i]);
		long long ret = 0, base = 0;
		in.h[in.n] = -1;
		for(int i = 1; i <= in.n; i++) {
			if(in.h[i] < in.h[i-1])
				ret += in.h[i-1] - base, base = in.h[i];
		}
		printf("%lld\n", ret);
    }
    return 0;
}

Problem

One of the essential activities of a knight is to compete in tournaments. Frequently, groups of knights gather around the country to compare their skills. On such a typical contest day, everyone has five hours to do ten disciplines, such as sword fighting, bow and arrow, and various forms of horseback riding. Needless to say, you have to bring your own horse.

This is not as easy as it seems. It often takes a knight several days to go from the castle where he lives to the place where a tournament is held. But horses sometimes are very, very stubborn. After having covered a certain distance on a single day, they sometimes simply stop and refuse to go any further. Luckily, they start anew on the next day. To make sure that the horse does not refuse service before the scheduled day trip is completed, a knight wants to choose an itinerary on which the longest day trip is as short as possible. Hence, a trip that takes many days with short distances is preferable over a shorter route that has the risk of a refusing horse.

Write a program which answers queries from knights spread all over the country about the best way to go from their castles to a tournament site. Given a description of the relevant places (i.e. castles, locations of tournaments, and hostels for overnight stays), the program should tell them the largest distance they have to cover on a single day so that this distance is minimal among all possible itineraries.

The places are designated by consecutive integers from 1 to $ N$, while a road is represented by three integers, namely its place of origin, its destination, and its length. Every road can be used in both directions, and there is at least one route (i.e. a sequence of roads) between any two places. The knights stick to the given roads while travelling and spend their nights only at one of the $ N$ places.

Input

The first line contains the total number of test cases that follow.

Each test case begins with a line that first holds the number $ N$ of places ( $ 1 \le N \le 3000$ ) followed by the number $ R$ of roads ( $ 1 \le R \le 100000$ ). Then there are $ R$ lines with three integers each ($ a$ , $ b$ , and $ l$ ), each of which defines a road connecting the places $ a$ and $ b$ ( $ 1 \le a, b \le N$ ) with length $ l$ ( $ 1 \le l \le 1000000$ ).

Thereafter, each test case continues with the number $ Q$ of queries on a line by itself ( $ 1 \le Q \le 1000$ ). Each of the next $ Q$ lines holds two integers $ k$ and $ t$ , indicating a query by a knight who lives at place $ k$ and needs to go to a tournament at place $ t$ ( $ 1 \le k, t \le N$ , $ k \neq t$ ).

Output

For each test case output a line containing the word ``Case’’, a single space, and its serial number (starting with $ 1$ for the first test case). Then, print one line for each query in this test case, containing the smallest maximal day trip distance as described above. Print a blank line after each test case.

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

2
4 4
1 2 100
2 3 100
3 4 100
4 1 200
1
1 4
6 9
2 4 5
5 1 7
3 6 6
3 1 4
2 3 2
1 2 1
6 5 42
4 5 3
4 6 5
4
1 3
3 4
5 4
6 1

Sample Output

1
2
3
4
5
6
7
8

Case 1
100
Case 2
2
5
3
5

Solution

題目描述：

騎士每天活動只會從該點移動到盡可能短的路徑到下一個點，求從起點到終點之間的最小的最長路為何。

題目解法：

由於詢問兩個點之間的路徑上的最小值最大邊，不外乎地可以先做一次最小成本樹，根據定義，拆分成 s - t 集合，最小成本樹的邊一定是 s - t 之間的最小邊。

接著詢問在樹上進行即可，因此每次詢問最慘會到 O(n)。

那我們稍微加速，採用 dp 的方式，將樹變成有根樹，記錄每一個節點向上攀升 1 個節點, 2 個節點, 4 個節點 …, 2^n 個節點的路徑上的最大最小值。

因此狀態會是 O(n log n), 建表也能在 O(n log n) 完成，接著調整兩個詢問節點的高度，先想辦法調整到兩個節點到水平高度，藉由之前的計算，高度不超過 n，因此理應可以在 O(log n) 時間內完成到調整到同一水平高度。

在同一水平下，還是需要知道 LCA 的所在高度，否則也可以水平線不斷地一步一步往上提，雖然最慘也許是 O(n) 但是經由之前的調整已經很加速很多。

本來應該套用 LCA Tarjan 的作法來加速，但是還沒有做到這樣的地步速度就很快。如果詢問次數再多一點就必須做到這一步。

有點懶惰 Orz。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <vector>
using namespace std;
struct E {
    int x, y, v;
    E(int a=0, int b=0, int c=0):
        x(a), y(b), v(c) {}
    bool operator<(const E &a) const {
        return  v < a.v;
    }
};
E D[100005];
vector<E> tree[3005];
int p[3005], rank[3005];
int findp(int x) {
    return p[x] == x ? x : (p[x] = findp(p[x]));
}
int joint(int x, int y) {
    x = findp(x), y = findp(y);
    if(x == y)
        return 0;
    if(rank[x] > rank[y])
        rank[x] += rank[y], p[y] = x;
    else
        rank[y] += rank[x], p[x] = y;
    return 1;
}
int kruscal(int n, int m) {
    int sum = 0;
    
    sort(D, D+m);
    for(int i = 0; i <= n; i++) {
        p[i] = i, rank[i] = 1;
        tree[i].clear();
    }
    
    for(int i = 0; i < m; i++) {
        if(joint(D[i].x, D[i].y)) {
        	sum += D[i].v;
        	tree[D[i].x].push_back(E(D[i].x, D[i].y, D[i].v));
        	tree[D[i].y].push_back(E(D[i].y, D[i].x, D[i].v));
//        	printf("mmm %d %d %d\n", D[i].x, D[i].y, D[i].v);
        }
    }
    return sum;
}
int dp[4096][20], dpw[4096][20];
int treeLevel[4096], treePath[4096];
void dfs(int u, int p, int level) {
	treeLevel[u] = level, treePath[level] = u;	
	for(int i = 1; (1<<i) < level; i++) {
		dp[u][i] = max(dp[u][i-1], dp[dpw[u][i-1]][i-1]);
		dpw[u][i] = treePath[level-(1<<i)];
	}
	for(int i = 0; i < tree[u].size(); i++) {
		int v = tree[u][i].y;
		if(v == p)	continue;		
		dp[v][0] = tree[u][i].v;
		dpw[v][0] = u;
		dfs(v, u, level + 1);
	}
}
int query(int x, int y) {
	int hx = treeLevel[x], hy = treeLevel[y];
	int ret = 0;
	while(x != y && hx != hy) {
		for(int i = 15; i >= 0; i--) {
			if(abs(hx-hy) >= (1<<i)) {
				if(hx > hy) {
					ret = max(ret, dp[x][i]);
					x = dpw[x][i];
					hx -= (1<<i);
				} else {
					ret = max(ret, dp[y][i]);
					y = dpw[y][i];
					hy -= (1<<i); 
				}
			}
		}
	}
	while(x != y) {
		ret = max(ret, dp[x][0]);
		x = dpw[x][0];
		hx -= (1<<0);
		ret = max(ret, dp[y][0]);
		y = dpw[y][0];
		hy -= (1<<0); 
	}
	return ret;
}
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while(testcase--) {
        int n, m, q, x, y;
        scanf("%d %d", &n, &m);
        for(int i = 0; i < m; i++) {
        	scanf("%d %d %d", &D[i].x, &D[i].y, &D[i].v);        	
        }
        
		int mstcost = kruscal(n, m);
		memset(dp, 0, sizeof(dp));
		memset(dpw, 0, sizeof(dpw));
		dfs(1, -1, 1);
		
//		for(int i = 1; i <= n; i++, puts("")) {
//			printf("[%2d] :", i);
//			for(int j = 0; (1<<j) <= n; j++)
//				printf("%d %d, ", dp[i][j], dpw[i][j]);
//		}
		scanf("%d", &q);
		printf("Case %d\n", ++cases);
		while(q--) {
			scanf("%d %d", &x, &y);
			printf("%d\n", query(x, y));
		}
		puts("");
	}
    return 0;
}
/*
5
10 45
1 2 15
1 3 11
1 4 48
1 5 24
1 6 45
1 7 18
1 8 12
1 9 40
1 10 11
2 3 4
2 4 9
2 5 44
2 6 23
2 7 39
2 8 48
2 9 48
2 10 22
3 4 42
3 5 37
3 6 10
3 7 18
3 8 29
3 9 8
3 10 47
4 5 7
4 6 17
4 7 25
4 8 23
4 9 32
4 10 27
5 6 26
5 7 21
5 8 38
5 9 40
5 10 39
6 7 35
6 8 11
6 9 39
6 10 1
7 8 15
7 9 10
7 10 47
8 9 28
8 10 11
9 10 1
30
1 6
5
10 45
1 2 9
1 3 12
1 4 21
1 5 4
1 6 32
1 7 20
1 8 14
1 9 28
1 10 16
2 3 12
2 4 23
2 5 27
2 6 34
2 7 43
2 8 2
2 9 33
2 10 35
3 4 41
3 5 26
3 6 16
3 7 39
3 8 2
3 9 49
3 10 44
4 5 24
4 6 2
4 7 17
4 8 26
4 9 20
4 10 2
5 6 23
5 7 5
5 8 41
5 9 12
5 10 15
6 7 48
6 8 45
6 9 13
6 10 28
7 8 25
7 9 12
7 10 37
8 9 4
8 10 5
9 10 41
30
5 4
1 7
8 4
*/

Problem

Zibon just started his courses in Computer science. After having some lectures on programming courses he fell in love with strings. He started to play with strings and experiments on them. One day he started a string of arbitrary (of course positive) length consisting of only {a, b}. He considered it as 1st string and generated subsequent strings from it by replacing all the b’s with ab and all the a’s with b. For example, if he ith string is abab, (i+1)th string will be b(ab)b(ab) = babbab. He found that the Nth string has the length X and Mth string has the length Y. He wondered what will be length of the Kth string. Can you help him?

Input

The first line of the input file contains an integer T (T ≤ 1000) which denotes the total number of test cases. The description of each test case is given below:

Five integers N, X, M, Y and K where (0 < N, M, X, Y, K < 109 and N ≠ M).

Output

For each test case produce one line of output giving either the number which is desired length (modulo 1000000007) or the string “Impossible”. You output Impossible if the given input is not possible.

Sample Input

1
2
3

2
3 16 5 42 6
5 1 6 10 9

Sample Output

1
2

68
Impossible

Solution

題目描述：

一開始由 a, b 構成的字串，每一次操作會將 a 換成 b, 將 b 換成 ab。
在第 N 次之後長度為 X、第 M 次之後長度為 Y，求第 K 次之後長度為何？

題目解法：

看到 a 換成 b, 將 b 換成 ab，其實只考量數量關係，很明顯是一個費式數列的關係。
因此，只要假設一開始有多少個 a，有多少個 b 在一開始的字串中，利用兩條方程式求解，之後再帶入費式數列的快速運算即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
struct Matrix {
	long long v[2][2];
	Matrix(long long a = 0) {
		memset(&v, 0, sizeof(v));
		for(int i = 0; i < 2; i++)
			v[i][i] = a;
	}
};
const long long mod = 1000000007LL;
Matrix multiply(Matrix x, Matrix y) {
	Matrix z;
	for(int i = 0; i < 2; i++)
		for(int j = 0; j < 2; j++)
			for(int k = 0; k < 2; k++) {
				z.v[i][j] += x.v[i][k] * y.v[k][j] %mod;
				z.v[i][j] %= mod;
			}
	return z;
}
Matrix pow(Matrix x, long long y) {
	Matrix v(1);
	while(y) {
		if(y&1)
			v = multiply(v, x);
		y = y>>1, x = multiply(x, x); 
	}
	return v;
}
int main() {
	int testcase;
	long long N, X, M, Y, K;
	scanf("%d", &testcase);
	while(testcase--) {
		scanf("%lld %lld %lld %lld %lld", &N, &X, &M, &Y, &K);
		Matrix mm, na, nb, nc;
		mm.v[0][0] = mm.v[0][1] = mm.v[1][0] = 1;
		na = pow(mm, N);
		nb = pow(mm, M);
		nc = pow(mm, K);
		long long a1, b1, c1, a2, b2, c2;
		long long d, dx, dy;
		a1 = na.v[0][0], b1 = na.v[1][0], c1 = X;
		a2 = nb.v[0][0], b2 = nb.v[1][0], c2 = Y;
		d = a1 * b2 - a2 * b1;
		dx = X * b2 - Y * b1, dy = a1 * Y - a2 * X;
		if(d == 0 || dx%d || dy%d || dx/d < 0 || dy/d < 0)
			puts("Impossible");
		else {
			long long a = dx/d, b = dy/d;
			printf("%lld\n", (a * nc.v[0][0]%mod + b * nc.v[1][0]%mod)%mod);
		}
//		printf("%lld A + %lld B = %lld\n", na.v[0][0], na.v[1][0], X);
//		printf("%lld A + %lld B = %lld\n", nb.v[0][0], nb.v[1][0], Y);
//		printf("%lld A + %lld B = ????\n", nc.v[0][0], nc.v[1][0]);
	}
	return 0;
}

Problem

Little Mou is very fond of eggs. She has n baskets for keeping her colorful eggs. Each basket contains eggs of different colors. The baskets are numbered from 1 to n. She has a strange hobby about these eggs. On each day, she takes each basket starting from the nth basket. When she is doing this for basket i, she counts all eggs placed in baskets 1 to i (inclusive) and takes their sum. Let this value of sum be counti. She removes all old eggs from the ith basket and keeps counti new eggs in the ith basket. After that she puts all the old eggs of the ith basket in the (i-1)th basket removing the old eggs of the (i-1)th basket. As Mou is very fond of eggs, she eats all old eggs of the (i-1)th basket. And when she has finished eating, she repeats the work for this (i-1)th basket. If she reaches the 1st basket, she stops her work and doesn’t eat any more eggs and goes to sleep!

For example let Mou has 3 baskets at day 1. 1st basket contains 1 egg, 2nd basket contains 1 egg and the 3rd basket contains 2 eggs.

So simulation for day 3 follows:

Basket Index => 3 2 1

….. 略

Now the problem is given n, d and the number of eggs in each basket eggi, your job is to find the number of eggs in each basket after d days. As the number can be very big output answer modulo 1,000,000,007.

Input

The first line of the input file contains an integer T (T ≤ 111) which denotes the total number of test cases. The description of each test case is given below:

Two integers N (1 ≤ n ≤ 60) and d (1 ≤ d ≤ 1,000,000,000), followed by n integers denoting the number of eggs in each basket starting from 1 to n.
Output

For each test case print one line of output containing the number of eggs in each basket after d days have passed separated by single spaces between them. See the sample output for more details. As the numbers can be very big output answer modulo 1,000,000,007.

Sample Input

1
2
3
4
5
6
7

3
3 7
1 2 3
2 2
4 5
2 1
1 10

Sample Output

1
2
3

129 189 277
5 9
1 10

Solution

題目描述：

一開始有 n 籃雞蛋，每一籃有各自個雞蛋數量。

每一次的操作從最右邊 (編號大的那籃開始) 進行，將所有比它小的編號的雞蛋總數加到這一籃，並且將原本的雞蛋總數指派給下一個籃。

問第 d 天後的結果。

題目解法：

建造轉移矩陣，使用 D&C 完成。

觀察一下可以發現，矩陣肯定長成這副德性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

[1, 1, 1, ..., 1, 1, 1]
[1, 0, 1, ..., 1, 1, 1]
[1, 0, 0, 1, ..., 1, 1] = M
[1, 0, 0, 0, ..., 1, 1]
...
[1, 0, 0, 0, ..., 0, 0]
[an]
[an-1]
[an-2] = A(1)
...
[a1]
M x A(1) = A(2)
M x M x A(1) = A(3)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

#include <stdio.h> 
#include <string.h>
const long long mod = 1000000007LL;
struct Matrix {
	long long v[64][64];
	int row, col; // row x col
	Matrix(int n, int m, long long a = 0) {
		memset(v, 0, sizeof(v));
		row = n, col = m;
		for(int i = 0; i < row && i < col; i++)
			v[i][i] = a;
	}
	Matrix operator*(const Matrix& x) const {
		Matrix ret(row, x.col);
		for(int i = 0; i < row; i++)
			for(int j = 0; j < x.col; j++)
				for(int k = 0; k < col; k++)
					ret.v[i][j] += v[i][k] * x.v[k][j] %mod,
					ret.v[i][j] %= mod;
		return ret;
	}
	Matrix operator^(const int& n) const {
		Matrix ret(row, col, 1), x = *this;
		int y = n;
		while(y) {
			if(y&1)	ret = ret * x;
			y = y>>1, x = x * x;
		}
		return ret;
	}
};
int main() {
	int testcase, n, d, a[105];
	scanf("%d", &testcase);
	while(testcase--) {
		scanf("%d %d", &n, &d);
		d--;
		for(int i = 0; i < n; i++)
			scanf("%d", &a[i]);
		Matrix x(n, n), A(n, 1);
		for(int i = 0; i < n; i++)
			A.v[i][0] = a[n-i-1];
		for(int i = 0; i < n; i++)
			x.v[0][i] = 1;
		for(int i = 1; i < n; i++) {
			for(int j = i+1; j < n; j++) {
				x.v[i][j] = 1;
			}
			x.v[i][0] = 1;
		}
		Matrix y = x ^ d;
		Matrix r = y * A;
		for(int i = r.row-1; i >= 0; i--) { 
			printf("%lld", r.v[i][0]);
			if(i)	putchar(' ');
		} 
		puts("");
	}
	return 0;
}

Problem

Some people believe that 13 is an unlucky number. So they always want to avoid the number 13. But I believe that 7 is an unlucky number and want to avoid it. So unlucky number is different for man to man. If 13 is an unlucky number and in a number there is no 13 (i.e. no ‘1’ is followed by a ‘3’) then we can call it a lucky number. For example, if we consider 13 as an unlucky number then 12345 is a lucky number. But if any number contains 13 then it is not a lucky number, such as 13254 and 21345 are not lucky numbers. Given the number of digits N in a number and the unlucky number M, you have to find out how many lucky numbers are possible with N digits considering that M is unlucky number. Note that leading 0’s are not allowed. So, 011 is not a valid three digit number.

Input

The first line of the input file contains an integer T (T ≤ 1000) which denotes the total number of test cases. The description of each test case is given below:

Two positive integers N (1 ≤ N ≤ 100), M (1 ≤ M ≤ 10100).

Output

For each test case print the number of lucky numbers of N digits considering that M is the unlucky number. The result may be very large. You have to output the result modulo 10000007.

Sample Input

1
2
3
4

3
1 3
2 13
2 1

Sample Output

1
2
3

9
89
72

Solution

題目描述：

找到長度為 n 的數字，並且數字中不會出現指定的數字為 substring，求符合數字的總數。

題目解法：

特別考慮以 0 開頭的情況 (n 位數字前導不可為 0，但 n = 1 位數字可以是 0)。
最後，建造一台 AC 自動機，接著對於每一個節點著手 dp 轉移。

也就是考慮再將字串進行 AC 自動機匹配時所會遇到的所有轉移情況，因此我們要避免出現指定的字符串時，在結尾處標記不可轉移即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145

// http://mypaper.pchome.com.tw/zerojudge/post/1324462879
// AC 自動機 DP
#include <stdio.h>
#include <vector>
#include <queue>
#include <iostream>
#include <string.h>
using namespace std;
struct Node {
    Node *next[10], *fail, *prev;
    int eos;//prefix has a string end
    long long dp[105]; // [string length]
    int ASCII;
    Node() {
        fail = NULL, prev = NULL;
        memset(next, 0, sizeof(next));
        memset(dp, 0, sizeof(dp));
        eos = 0;
        ASCII = 0;
    }
};
void insertTrie(const char str[], Node *root, int label) {
    static Node *p;
    static int i, idx, eos;
    p = root, eos = 0;
    for(i = 0; str[i]; i++) {
        idx = str[i] - '0';
        if(p->next[idx] == NULL) {
            p->next[idx] = new Node();
            p->next[idx]->prev = p;
            p->next[idx]->ASCII = idx;
        }
        eos |= p->eos;
        p = p->next[idx];
        p->eos |= eos;
    }
    p->eos |= label;
}
void freeTrie(Node *root) {
    queue<Node*> Q;
    Node *nd;
    Q.push(root);
    while(!Q.empty()) {
        nd = Q.front(), Q.pop();
        for(int i = 0; i < 10; i++) {
            if(nd->next[i] != NULL)
                Q.push(nd->next[i]);
        }
        delete nd;
    }
}
void buildACautomation(Node *root) {
    queue<Node*> Q;
    Node *nd, *p;
    root->fail = NULL;
    Q.push(root);
    while(!Q.empty()) {
        nd = Q.front(), Q.pop();
        for(int i = 0; i < 10; i++) {
            if(nd->next[i] == NULL)
                continue;
            Q.push(nd->next[i]);
            p = nd->fail;
            while(p != NULL && p->next[i] == NULL)
                p = p->fail;
            if(p == NULL)
                nd->next[i]->fail = root;
            else {
                nd->next[i]->fail = p->next[i];
                nd->next[i]->eos |= p->next[i]->eos;//special for dp
            }
        }
    }
}
const int mod = 10000007;
long long dp(Node *root, int len) {
    queue<Node*> Q;
    Node *nd, *p;
    root->dp[0] = 1;
    int k, i, j;
    long long ans, ret = 0;
    for(k = 0; k <= len; k++) {
        Q.push(root);
        ans = 0;
        while(!Q.empty()) {
            nd = Q.front(), Q.pop();
            for(i = (k == 0); i < 10; i++) { // leading 0's are not allowed
                if(nd->next[i] != NULL) {
                    if(nd->next[i]->eos)
                        continue;//not safe
                    nd->next[i]->dp[k+1] += nd->dp[k];
                    nd->next[i]->dp[k+1] %= mod;
                    Q.push(nd->next[i]);
                } else {
                    p = nd;
                    while(p != root && p->next[i] == NULL)
                        p = p->fail;
                    p = p->next[i];
                    if(p == NULL) // error message
                        puts("NULL");
                    if(p->eos)
                        continue;//not safe
                    p->dp[k+1] += nd->dp[k];
                    p->dp[k+1] %= mod;
                }
            }
            ans += nd->dp[k];
            ans %= mod;
        }
        if(k == len) {
            ret += ans;
            ret %= mod;
        }
    }
    return ret;
}
int main() {
    int n, p, i;
    int cases = 0, testcase;
    char pattern[105], s[105];
    scanf("%d", &testcase);
    while(testcase--) {
        Node *root = new Node();
        scanf("%d %s", &n, pattern);
        insertTrie(pattern, root, 1);
        for(int i = 0; i < 10; i++) {
        	s[0] = i + '0', s[1] = '\0';
        	insertTrie(s, root, 0);
        }
        buildACautomation(root);
        long long ret = dp(root, n);
        freeTrie(root);
        if(n == 1 && strcmp("0", pattern))
        	ret++;
        printf("%lld\n", ret);
    }
    return 0;
}
/*
3
1 3
2 13
2 1
*/

Problem

Professor Z. always gives his students lots of boring homework. Last week, after explaining binary search trees (BSTs), he asked his students to draw a picture of BST according to the list of numbers inserted into the tree sequentially. Maryanna spent so much time playing the game “Starcraft II” that she can’t finish her homework in time. She needs your help.

• A binary search tree, which may sometimes also be called ordered or sorted binary tree, is a node-based binary tree data structure which has the following properties:
• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• Both the left and right subtrees must also be binary search trees.
  -from Wikipedia

To draw a picture of BST, you may follow the rules listed below:

• The picture of a 1-node BST, whose size is 1*1, is a single ‘o’ (15th small Latin letter).
• If a BST has a non-empty subtree, draw a single ‘|’ just above the subtree’s root, and a single ‘+’ just above previous drawn ‘|’. Finally, in the row of ‘+’, use the least number (including 0) of ‘-‘s to connect ‘+’ (denoting the left subtree and right subtree) and ‘o’ (denoting the parent node of the subtree)
• The left subtree (if exists) must be drawn on the left side of its parent. Similarly, the right subtree (if exists) must be drawn on the right side of its parent.
• The column of the BST’s root must not contain any character from left subtree or right subtree.
• Any column containing any characters from BST’s left subtree must not contain any characters from BST’s right subtree, and vice versa. That is, for a node of the BST, the picture of its left subtree and the picture of its right subtree do not share common columns in the picture of the whole tree.

The sample output may give a clear clarification about the format of the picture.

Input

The first line contains T ( T$ \le$2500), the number of test cases. T lines follow. Each line contains a positive integer N (N < 80), followed by N integers - a permutation of 1 to N. The permutation indicates the insert order for the BST.

Output

For each test case:

Output the case number counting from 1 in the first line. The next lines should be the image described above without any trailing spaces. See the sample for more format details.

Note: Notice that no trailing whitespaces after the last visible characters of each line are allowed.

Sample Input

1
2
3
4

3
3 3 1 2
6 4 5 6 1 3 2
5 3 4 5 2 1

Sample Output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

Case #1:
+-o
|
o+
 |
 o
Case #2:
+--o+
|   |
o-+ o+
  |  |
 +o  o
 |
 o
Case #3:
 +o+
 | |
+o o+
|   |
o   o

Solution

題目描述：

請先依序插入節點，並且建造一棵二分搜尋樹，接著打印出來。

以 o 表示節點，而用 + 表示左右子樹的存在，並且用 - 來移動其位置。盡可能用最少的 - 來完成。並且每一列 (縱向) 只會有一個 o 存在。

題目解法：

根據中序搜索，可以得到由左至右的打印節點順序，根據這個打印順序著手左右的 - 計算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

#include <stdio.h>
#include <string.h>
struct Node {
	int v, l, r, porder;
};
Node BST[128];
char g[256][128];
int porder = 0, mxdep;
void build(int nd, int dep) {
	if(dep > mxdep)	mxdep = dep;
	if(BST[nd].l != -1)
		build(BST[nd].l, dep+2);
	BST[nd].porder = porder++;	
	if(BST[nd].r != -1)
		build(BST[nd].r, dep+2);
		
	if(BST[nd].l != -1) {
		g[dep][BST[BST[nd].l].porder] = '+';
		g[dep+1][BST[BST[nd].l].porder] = '|';
		for(int i = BST[BST[nd].l].porder + 1; i < BST[nd].porder; i++)
			g[dep][i] = '-';
	}
	g[dep][BST[nd].porder] = 'o';
	if(BST[nd].r != -1) {
		for(int i = BST[BST[nd].r].porder - 1; i > BST[nd].porder; i--)
			g[dep][i] = '-';
		g[dep][BST[BST[nd].r].porder] = '+';
		g[dep+1][BST[BST[nd].r].porder] = '|';
	}
}
int main() {
	int testcase, cases = 0, N;
	scanf("%d", &testcase);
	while(testcase--) {
		scanf("%d", &N);
		memset(BST, -1, sizeof(BST));
		scanf("%d", &BST[0].v);
		int size = 1, x;
		for(int i = 1; i < N; i++) {
			scanf("%d", &x);
			int idx = 0;
			do {
				if(x < BST[idx].v) {
					if(BST[idx].l != -1)
						idx = BST[idx].l;
					else
						BST[idx].l = size, BST[size++].v = x, idx = 0;
				} else {
					if(BST[idx].r != -1)
						idx = BST[idx].r;
					else
						BST[idx].r = size, BST[size++].v = x, idx = 0;
				}
			} while(idx);
		}
		porder = 0, mxdep = 0;
		memset(g, ' ', sizeof(g));
		build(0, 0);
		printf("Case #%d:\n", ++cases);
		for(int i = 0; i <= mxdep; i++) {
			for(int j = N; g[i][j] == ' '; j--)
				g[i][j] = '\0';
			printf("%s\n", g[i]);
		}
	}
	return 0;
}