Solved Problem ID Title Ratio(Accepted / Submitted)
1001 小兔的棋盘 54.05%(20/37)
1002 连线游戏 70.00%(14/20)
1003 Train Problem II 40.00%(12/30)
1004 Buy the Ticket 35.71%(5/14)
小兔的棋盘
Time Limit : 1000/1000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 37 Accepted Submission(s) : 20
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
小兔的叔叔从外面旅游回来给她带来了一个礼物，小兔高兴地跑回自己的房间，拆开一看是一个棋盘，小兔有所失望。不过没过几天发现了棋盘的好玩之处。从起点(0，0)走到终点(n,n)的最短路径数是C(2n,n),现在小兔又想如果不穿越对角线(但可接触对角线上的格点)，这样的路径数有多少?小兔想了很长时间都没想出来，现在想请你帮助小兔解决这个问题，对于你来说应该不难吧!
Input
每次输入一个数n(1<=n<=35)，当n等于－1时结束输入。
Output
对于每个输入数据输出路径数，具体格式看Sample。
Sample Input
1
3
12
-1
Sample Output
1 1 2
2 3 10
3 12 416024
Author
Rabbit
Source
RPG专场练习赛
#include using namespace std; typedef long long LL; const int maxn = 1e5+10; LL f[50]; int main(){ f[0] = f[1] = 1; for(int i = 2; i <= 35; i++) for(int j = 0; j <= i-1; j++) f[i] += f[j]*f[i-1-j]; int n; for(int i = 1; cin>>n&&n!=-1; i++){ cout<
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
连线游戏
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 20 Accepted Submission(s) : 14
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
这是个古老的小游戏。
假设在地上按照顺时针方向依次写下2n个数字1,2,3,4…2n围成一个圆，然后用n条直线连接这2n个数字，每个数字都和一个数字相连，并且仅仅和一个数字相连。要求所有的连线都不能有交点。
请计算一共有多少种不同的连线方式。
比如，当n等于2时，地上一共有4个数字，有2种不同的连线方式。
Input
输入包含多组测试用例。
每行输入数据包含一个正整数n（ 1 <= n <=35），除了最后一行的-1，它表示输入数据的结束。
Output
对于每组输入数据的n，请计算2n个数字的不同的连线方式数目。
每组数据输出一行。
Sample Input
2
3
-1
Sample Output
2
5
#include using namespace std; typedef long long LL; const int maxn = 1e5+10; LL f[50]; int main(){ f[0] = f[1] = 1; for(int i = 2; i <= 35; i++) for(int j = 0; j <= i-1; j++) f[i] += f[j]*f[i-j-1]; int n; while(cin>>n && n!=-1){ cout<
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Train Problem II
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 65536/32768K (Java/Other)
Total Submission(s) : 30 Accepted Submission(s) : 12
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
As we all know the Train Problem I, the boss of the Ignatius Train Station want to know if all the trains come in strict-increasing order, how many orders that all the trains can get out of the railway.
Input
The input contains several test cases. Each test cases consists of a number N(1<=N<=100). The input is terminated by the end of file.
Output
For each test case, you should output how many ways that all the trains can get out of the railway.
Sample Input
1
2
3
10
Sample Output
1
2
5
16796
Hint
The result will be very large, so you may not process it by 32-bit integers.
Author
Ignatius.L
//C[n] = C[n-1]*(4*n-2)/(n+1) #include using namespace std; struct BigInteger { typedef unsigned long long LL; static const int BASE = 100000000; static const int WIDTH = 8; vector s; BigInteger& clean(){while(!s.back()&&s.size()>1)s.pop_back(); return *this;} BigInteger(LL num = 0) {*this = num;} BigInteger(string s) {*this = s;} BigInteger& operator = (long long num) { s.clear(); do { s.push_back(num % BASE); num /= BASE; } while (num > 0); return *this; } BigInteger& operator = (const string& str) { s.clear(); int x, len = (str.length() - 1) / WIDTH + 1; for (int i = 0; i < len; i++) { int end = str.length() - i*WIDTH; int start = max(0, end - WIDTH); sscanf(str.substr(start,end-start).c_str(), "%d", &x); s.push_back(x); } return (*this).clean(); } BigInteger operator + (const BigInteger& b) const { BigInteger c; c.s.clear(); for (int i = 0, g = 0; ; i++) { if (g == 0 && i >= s.size() && i >= b.s.size()) break; int x = g; if (i < s.size()) x += s[i]; if (i < b.s.size()) x += b.s[i]; c.s.push_back(x % BASE); g = x / BASE; } return c; } BigInteger operator - (const BigInteger& b) const { assert(b <= *this); // 减数不能大于被减数 BigInteger c; c.s.clear(); for (int i = 0, g = 0; ; i++) { if (g == 0 && i >= s.size() && i >= b.s.size()) break; int x = s[i] + g; if (i < b.s.size()) x -= b.s[i]; if (x < 0) {g = -1; x += BASE;} else g = 0; c.s.push_back(x); } return c.clean(); } BigInteger operator * (const BigInteger& b) const { int i, j; LL g; vector v(s.size()+b.s.size(), 0); BigInteger c; c.s.clear(); for(i=0;i= v.size()) break; LL x = v[i] + g; c.s.push_back(x % BASE); g = x / BASE; } return c.clean(); } BigInteger operator / (const BigInteger& b) const { assert(b > 0); // 除数必须大于0 BigInteger c = *this; // 商:主要是让c.s和(*this).s的vector一样大 BigInteger m; // 余数:初始化为0 for (int i = s.size()-1; i >= 0; i--) { m = m*BASE + s[i]; c.s[i] = bsearch(b, m); m -= b*c.s[i]; } return c.clean(); } BigInteger operator % (const BigInteger& b) const { //方法与除法相同 BigInteger c = *this; BigInteger m; for (int i = s.size()-1; i >= 0; i--) { m = m*BASE + s[i]; c.s[i] = bsearch(b, m); m -= b*c.s[i]; } return m; } // 二分法找出满足bx<=m的最大的x int bsearch(const BigInteger& b, const BigInteger& m) const{ int L = 0, R = BASE-1, x; while (1) { x = (L+R)>>1; if (b*x<=m) {if (b*(x+1)>m) return x; else L = x;} else R = x; } } BigInteger& operator += (const BigInteger& b) {*this = *this + b; return *this;} BigInteger& operator -= (const BigInteger& b) {*this = *this - b; return *this;} BigInteger& operator *= (const BigInteger& b) {*this = *this * b; return *this;} BigInteger& operator /= (const BigInteger& b) {*this = *this / b; return *this;} BigInteger& operator %= (const BigInteger& b) {*this = *this % b; return *this;} bool operator < (const BigInteger& b) const { if (s.size() != b.s.size()) return s.size() < b.s.size(); for (int i = s.size()-1; i >= 0; i--) if (s[i] != b.s[i]) return s[i] < b.s[i]; return false; } bool operator >(const BigInteger& b) const{return b < *this;} bool operator<=(const BigInteger& b) const{return !(b < *this);} bool operator>=(const BigInteger& b) const{return !(*this < b);} bool operator!=(const BigInteger& b) const{return b < *this || *this < b;} bool operator==(const BigInteger& b) const{return !(b < *this) && !(b > *this);} }; ostream& operator << (ostream& out, const BigInteger& x) { out << x.s.back(); for (int i = x.s.size()-2; i >= 0; i--) { char buf[20]; sprintf(buf, "%08d", x.s[i]); for (int j = 0; j < strlen(buf); j++) out << buf[j]; } return out; } istream& operator >> (istream& in, BigInteger& x) { string s; if (!(in >> s)) return in; x = s; return in; } BigInteger a[110]; int main(){ a[0] = 1; for(int i = 1; i <= 100; i++){ a[i] = a[i-1]*(4*i-2); a[i] = a[i]/(i+1); } int n; while(cin>>n){ cout<
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
Buy the Ticket
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 65536/32768K (Java/Other)
Total Submission(s) : 14 Accepted Submission(s) : 5
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
The “Harry Potter and the Goblet of Fire” will be on show in the next few days. As a crazy fan of Harry Potter, you will go to the cinema and have the first sight, won’t you?
Suppose the cinema only has one ticket-office and the price for per-ticket is 50 dollars. The queue for buying the tickets is consisted of m + n persons (m persons each only has the 50-dollar bill and n persons each only has the 100-dollar bill).
Now the problem for you is to calculate the number of different ways of the queue that the buying process won’t be stopped from the first person till the last person.
Note: initially the ticket-office has no money.
The buying process will be stopped on the occasion that the ticket-office has no 50-dollar bill but the first person of the queue only has the 100-dollar bill.
Input
The input file contains several test cases. Each test case is made up of two integer numbers: m and n. It is terminated by m = n = 0. Otherwise, m, n <=100.
Output
For each test case, first print the test number (counting from 1) in one line, then output the number of different ways in another line.
Sample Input
3 0
3 1
3 3
0 0
Sample Output
Test #1:
6
Test #2:
18
Test #3:
180
Author
HUANG, Ninghai
//ans=(C(m+n,n)-C(m+n,m+1))*m!*n!=(m+n)!*(m-n+1)/(m+1) #include using namespace std; struct BigInteger { typedef unsigned long long LL; static const int BASE = 100000000; static const int WIDTH = 8; vector s; BigInteger& clean(){while(!s.back()&&s.size()>1)s.pop_back(); return *this;} BigInteger(LL num = 0) {*this = num;} BigInteger(string s) {*this = s;} BigInteger& operator = (long long num) { s.clear(); do { s.push_back(num % BASE); num /= BASE; } while (num > 0); return *this; } BigInteger& operator = (const string& str) { s.clear(); int x, len = (str.length() - 1) / WIDTH + 1; for (int i = 0; i < len; i++) { int end = str.length() - i*WIDTH; int start = max(0, end - WIDTH); sscanf(str.substr(start,end-start).c_str(), "%d", &x); s.push_back(x); } return (*this).clean(); } BigInteger operator + (const BigInteger& b) const { BigInteger c; c.s.clear(); for (int i = 0, g = 0; ; i++) { if (g == 0 && i >= s.size() && i >= b.s.size()) break; int x = g; if (i < s.size()) x += s[i]; if (i < b.s.size()) x += b.s[i]; c.s.push_back(x % BASE); g = x / BASE; } return c; } BigInteger operator - (const BigInteger& b) const { assert(b <= *this); // 减数不能大于被减数 BigInteger c; c.s.clear(); for (int i = 0, g = 0; ; i++) { if (g == 0 && i >= s.size() && i >= b.s.size()) break; int x = s[i] + g; if (i < b.s.size()) x -= b.s[i]; if (x < 0) {g = -1; x += BASE;} else g = 0; c.s.push_back(x); } return c.clean(); } BigInteger operator * (const BigInteger& b) const { int i, j; LL g; vector v(s.size()+b.s.size(), 0); BigInteger c; c.s.clear(); for(i=0;i= v.size()) break; LL x = v[i] + g; c.s.push_back(x % BASE); g = x / BASE; } return c.clean(); } BigInteger operator / (const BigInteger& b) const { assert(b > 0); // 除数必须大于0 BigInteger c = *this; // 商:主要是让c.s和(*this).s的vector一样大 BigInteger m; // 余数:初始化为0 for (int i = s.size()-1; i >= 0; i--) { m = m*BASE + s[i]; c.s[i] = bsearch(b, m); m -= b*c.s[i]; } return c.clean(); } BigInteger operator % (const BigInteger& b) const { //方法与除法相同 BigInteger c = *this; BigInteger m; for (int i = s.size()-1; i >= 0; i--) { m = m*BASE + s[i]; c.s[i] = bsearch(b, m); m -= b*c.s[i]; } return m; } // 二分法找出满足bx<=m的最大的x int bsearch(const BigInteger& b, const BigInteger& m) const{ int L = 0, R = BASE-1, x; while (1) { x = (L+R)>>1; if (b*x<=m) {if (b*(x+1)>m) return x; else L = x;} else R = x; } } BigInteger& operator += (const BigInteger& b) {*this = *this + b; return *this;} BigInteger& operator -= (const BigInteger& b) {*this = *this - b; return *this;} BigInteger& operator *= (const BigInteger& b) {*this = *this * b; return *this;} BigInteger& operator /= (const BigInteger& b) {*this = *this / b; return *this;} BigInteger& operator %= (const BigInteger& b) {*this = *this % b; return *this;} bool operator < (const BigInteger& b) const { if (s.size() != b.s.size()) return s.size() < b.s.size(); for (int i = s.size()-1; i >= 0; i--) if (s[i] != b.s[i]) return s[i] < b.s[i]; return false; } bool operator >(const BigInteger& b) const{return b < *this;} bool operator<=(const BigInteger& b) const{return !(b < *this);} bool operator>=(const BigInteger& b) const{return !(*this < b);} bool operator!=(const BigInteger& b) const{return b < *this || *this < b;} bool operator==(const BigInteger& b) const{return !(b < *this) && !(b > *this);} }; ostream& operator << (ostream& out, const BigInteger& x) { out << x.s.back(); for (int i = x.s.size()-2; i >= 0; i--) { char buf[20]; sprintf(buf, "%08d", x.s[i]); for (int j = 0; j < strlen(buf); j++) out << buf[j]; } return out; } istream& operator >> (istream& in, BigInteger& x) { string s; if (!(in >> s)) return in; x = s; return in; } int main(){ int n, m; for(int i = 1; cin>>m>>n; i++){ if(n==0 &&m==0)break; cout<<"Test #"<m){cout<<"0\n"; continue;} BigInteger a = 1; for(int i = 2; i <= m+n; i++)a *= i; a = a*(m-n+1)/(m+1); cout<
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
5G游戏
版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。
