HDU ACM-Steps RECORD
Chapter 1
Section 1 暖手题
1.1.1 A+B for Input-Output Practice (I)
#include <stdio.h>
int main()
{
int a,b;
while(scanf("%d %d",&a,&b)==2)
printf("%d\n",a+b);
return 0;
}
1.1.2 A+B for Input-Output Practice (II)
#include <stdio.h>
int main()
{
int n;
scanf("%d",&n);
while(n--)
{
int a,b;
scanf("%d %d",&a,&b);
printf("%d\n",a+b);
}
return 0;
}
1.1.3 A+B for Input-Output Practice (III)
#include <iostream>
using namespace std;
int main(){
int a, b;
while(cin >> a >> b && (a || b)) cout << a + b << endl;
return 0;
}
1.1.4 A+B for Input-Output Practice (IV)
#include <iostream>
using namespace std;
int main(){
int n, t;
while(cin >> n && n){
int ans = 0;
while(n--){
cin >> t;
ans += t;
}
cout << ans << endl;
}
return 0;
}
1.1.5 A+B for Input-Output Practice (V)
#include <iostream>
using namespace std;
int main(){
int t;
cin >> t;
while(t--){
int n;
cin >> n;
int ans = 0;
while(n--){
int t;
cin >> t;
ans += t;
}
cout << ans << endl;
}
return 0;
}
1.1.6 A+B for Input-Output Practice (VI)
#include <iostream>
using namespace std;
int main(){
int n;
while(cin >> n){
int ans = 0;
while(n--){
int t;
cin >> t;
ans += t;
}
cout << ans << endl;
}
return 0;
}
1.1.7 A+B for Input-Output Practice (VII)
#include <iostream>
using namespace std;
int main(){
int a, b;
while(cin >> a >> b) cout << a + b << endl << endl;
return 0;
}
1.1.8 A+B for Input-Output Practice (VIII)
#include <iostream>
using namespace std;
int main(){
int t;
cin >> t;
for(int i = 0; i < t; ++i){
if(i) cout << endl;
int n;
cin >> n;
int ans = 0;
while(n--){
int tmp;
cin >> tmp;
ans += tmp;
}
cout << ans << endl;
}
return 0;
}
Section 2 水题
1.2.1 Text Reverse
#include <stack>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
int n;
cin >> n;
cin.get();
stack<char> s;
while(n--){
char ch;
while(true){
ch = cin.get();
if(ch == ' ' || ch == '\n'){
while(s.size()){
cout << s.top();
s.pop();
}
if(ch == '\n'){
cout << endl;
break;
}
else
cout << " ";
}
else
s.push(ch);
}
}
return 0;
}
1.2.2 find your present (2)
#include <iostream>
using namespace std;
int main(){
ios::sync_with_stdio(false); // 取消同步 or 别用iostream or TLE
int n;
while(cin >> n && n){
int num, ans = 0;
while(n--){
cin >> num;
ans ^= num;
}
cout << ans << endl;
}
return 0;
}
1.2.3 Quicksum
#include <iostream>
using namespace std;
int main(){
ios::sync_with_stdio(false);
string s;
while(getline(cin, s) && s != "#"){
int ans = 0;
for(int i = 1; i <= s.length(); ++i){
if(s[i-1] == ' ') continue;
ans += i * (s[i-1] - 'A' + 1);
}
cout << ans << endl;
}
return 0;
}
1.2.4 IBM Minus One
#include <string>
#include <iostream>
using namespace std;
int main(){
int n;
cin >> n;
for(int i = 0; i < n; ++i){
string s;
cin >> s;
cout << "String #" << i + 1 << endl;
for(int i = 0; i < s.length(); ++i)
cout << char(s[i] == 'Z' ? 'A' : s[i] + 1);
cout << endl << endl;
}
return 0;
}
1.2.5 Lowest Bit
#include <iostream>
using namespace std;
int main(){
int n;
while(cin >> n && n)
cout << (n & (-n)) << endl; // 位运算求二进制最低位1(树状数组lowbit函数)
return 0;
}
1.2.6 ASCII
#include <iostream>
using namespace std;
int main(){
int n;
while(cin >> n){
int num;
while(n--){
cin >> num;
cout << char(num);
}
}
return 0;
}
1.2.7 Identity Card
#include <string>
#include <iostream>
using namespace std;
typedef long long ll;
int main(){
int n;
cin >> n;
while(n--){
string s;
cin >> s;
string region = "Shanghai";
if (s[0] == '3' && s[1] == '3')
region = "Zhejiang";
else if (s[0] == '1' && s[1] == '1')
region = "Beijing";
else if (s[0] == '7' && s[1] == '1')
region = "*";
else if (s[0] == '8' && s[1] == '1')
region = "*";
else if (s[0] == '8' && s[1] == '2')
region = "Macao";
else if (s[0] == '5' && s[1] == '4')
region = "Tibet";
else if (s[0] == '2' && s[1] == '1')
region = "Liaoning";
cout << "He/She is from " << region << ",and his/her birthday is on "
<< s[10] << s[11] << ","
<< s[12] << s[13] << ","
<< s[6] << s[7] << s[8] << s[9]
<< " based on the table." << endl;
}
return 0;
}
1.2.8 AC Me
#include <map>
#include <string>
#include <iostream>
using namespace std;
typedef long long ll;
int main(){
string s;
while(getline(cin, s)){
map<char, int> ans;
for(int i = 0; i < s.length(); ++i) ++ans[s[i]];
for(int i = 'a'; i <= 'z'; ++i)
cout << char(i) << ":" << ans[char(i)] << endl;
cout << endl;
}
return 0;
}
Section 3 简单的贪心/模拟题
1.3.1 Moving Tables
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 555;
int cnt[MAXN];
int main(){
ios::sync_with_stdio(false);
int t;
cin >> t;
while(t--){
memset(cnt, 0, sizeof(cnt));
int n;
cin >> n;
while(n--){
int s, e;
cin >> s >> e;
if(s > e) swap(s, e);
if(s & 1 == 0) --s;
if(e & 1 == 1) ++e;
for(int i = s; i <= e; ++i) cnt[i] += 10; // 统计每个房间被占用的时间
}
cout << *max_element(cnt, cnt+MAXN) << endl;
}
return 0;
}
1.3.2 今年暑假不AC
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
struct show{
int s, e;
bool operator < (show& other){
// 以 结束早，开始晚 为优先
return e != other.e ? e < other.e : s > other.s;
}
};
const int MAXN = 111;
show arr[MAXN];
int main(){
ios::sync_with_stdio(false);
int n;
while(cin >> n, n){
for(int i = 0; i < n; ++i) cin >> arr[i].s >> arr[i].e;
sort(arr, arr+n);
int ans = 0, flag = 0;
// 遍历统计不重叠区间数量
for(int i = 0; i < n; ++i){
if(arr[i].s >= flag){
++ans;
flag = arr[i].e;
}
}
cout << ans << endl;
}
return 0;
}
1.3.3 百步穿杨
#include <iostream>
#include <algorithm>
using namespace std;
struct arrow{
int len, num;
bool operator < (arrow& other){
return len < other.len;
}
};
const int MAXN = 55;
arrow arr[MAXN];
int main(){
ios::sync_with_stdio(false);
int t;
cin >> t;
while(t--){
int n;
cin >> n;
for(int i = 0; i < n; ++i) cin >> arr[i].len >> arr[i].num;
sort(arr, arr + n);
for(int i = 0; i < n; ++i){
int len = arr[i].len - 2, num = arr[i].num;
while(num--){
cout << ">+";
for(int k = 0; k < len; ++k) cout << "-";
cout << "+>" << endl;
}
cout << endl; // 每种箭后面需要一个空行
}
}
return 0;
}
1.3.4 What Is Your Grade?
好像写的有点乱......QAQ
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 111;
struct stu{
int num, index, score;
string time;
bool operator < (const stu& other){
return num != other.num ? num > other.num : time < other.time;
}
};
bool cmp(stu a, stu b){ return a.index < b.index; }
stu arr[MAXN];
int cnt[MAXN];
int main(){
int n;
while(cin >> n, ~n){
memset(cnt, 0, sizeof(cnt));
for(int i = 0; i < n; ++i){
cin >> arr[i].num >> arr[i].time;
arr[i].index = i;
++cnt[arr[i].num];
}
sort(arr, arr + n);
int prank = cnt[arr[0].num];
for(int i = 0; i < n; ++i){
if(!prank) prank = cnt[arr[i].num];
arr[i].score = arr[i].num * 20 + (5 - arr[i].num) * 10;
if(arr[i].score == 50 || arr[i].score == 100){
--prank;
continue;
}
if(cnt[arr[i].num] == 1 || prank > int(ceil(cnt[arr[i].num] / 2.0))) arr[i].score += 5;
--prank;
}
sort(arr, arr + n, cmp);
for(int i = 0; i < n; ++i) printf("%d\n", arr[i].score);
puts("");
}
return 0;
}
1.3.5 第二小整数
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 11;
int arr[MAXN];
int main(){
ios::sync_with_stdio(false);
int t;
cin >> t;
while(t--){
int n;
cin >> n;
for(int i = 0; i < n; ++i) cin >> arr[i];
sort(arr, arr + n);
cout << arr[1] << endl;
}
return 0;
}
1.3.6 考试排名
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 11111;
struct info{
char name[22];
char status[15][11];
int solve, time;
bool operator < (const info& o){
return solve != o.solve ? solve > o.solve : time < o.time;
}
};
info arr[MAXN];
int problem, punish;
int ifind(char* str, char ch){
int pos = 0, len = strlen(str);
for( ; pos < len; ++pos){
if(str[pos] == ch) return pos;
}
return pos;
}
void calc(int index){
arr[index].solve = arr[index].time = 0;
info tmp = arr[index];
for(int i = 0; i < problem; ++i){
if(tmp.status[i][0] == '-' || tmp.status[i][0] == '0') continue;
++arr[index].solve;
int lpos = ifind(tmp.status[i], '(');
int tmptime = 0;
for(int j = 0; j < lpos; ++j) tmptime = tmptime * 10 + tmp.status[i][j] - '0';
arr[index].time += tmptime;
int rpos = ifind(tmp.status[i], ')');
if(rpos == strlen(tmp.status[i])) continue;
tmptime = 0;
for(int j = lpos + 1; j < rpos; ++j) tmptime = tmptime * 10 + tmp.status[i][j] - '0';
arr[index].time += (tmptime * punish);
}
}
void read(int index, int n){
for(int i = 0; i < n; ++i) scanf("%s", arr[index].status[i]);
calc(index);
}
int main(){
scanf("%d %d", &problem, &punish);
char* name; int index = 0;
while(~scanf("%s", arr[index].name)){
read(index, problem);
++index;
}
sort(arr, arr + index);
for(int i = 0; i < index; ++i) printf("%-10s %2d %4d\n", arr[i].name, arr[i].solve, arr[i].time);
return 0;
}
1.3.7 排列2
排序后用STL的next_permutation生成排列进行遍历检查
#include <bits/stdc++.h>
using namespace std;
int main(){
int arr[4];
bool checkbegin = true; // 是否是第一组数据
while(cin >> arr[0] >> arr[1] >> arr[2] >> arr[3]){
if(!(arr[0] || arr[1] || arr[2] || arr[3])) break;
if(!checkbegin) cout << endl; // 两组数据×之间×空行
sort(arr, arr + 4);
while(!arr[0]) next_permutation(arr, arr + 4); // 去掉首位为0的数
int flag = arr[0]; // 记录前一个数的千位
bool checkfirst = true; // 是否是千位为flag的第一个数
do{
if(flag != arr[0]){
cout << endl; // 千位数不同，换行
flag = arr[0];
checkfirst = true;
}
if(!checkfirst) cout << " ";
for(int i = 0; i < 4; ++i) cout << arr[i];
checkfirst = false;
}while(next_permutation(arr, arr + 4));
cout << endl;
checkbegin = false;
}
return 0;
}
1.3.8 Crixalis's Equipment
#include <iostream>
#include <algorithm>
using namespace std;
struct info{
int a, b;
bool operator < (const info& other){
int val1 = b - a, val2 = other.b - other.a;
// 按差值排序，尽量让剩余空间大，差值相同的以搬运所需空间大的为优先
return val1 == val2 ? b > other.b : val1 > val2;
}
};
info arr[1111];
int v, n;
int main(){
int t;
cin >> t;
while(t--){
cin >> v >> n;
for(int i = 0; i < n; ++i) cin >> arr[i].a >> arr[i].b;
sort(arr, arr + n);
bool flag = true;
for(int i = 0; i < n; ++i){
if(arr[i].b > v){
flag = false;
break;
}
v -= arr[i].a;
}
cout << (flag ? "Yes" : "No") << endl;
}
return 0;
}
Chapter 2
Section 1
2.1.1 最小公倍数
#include <iostream>
#include <algorithm>
using namespace std;
// int gcd(int a, int b){ reutrn b ? gcd(b, a % b) : a; }
int main(){
int a, b;
while(cin >> a >> b) cout << a / __gcd(a, b) * b << endl; // algorithm内置的__gcd() O(∩_∩)O
return 0;
}
2.1.2 How many prime numbers
这题......数据好水...... 0.0
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
bool checkprime(int num){
int lmt = sqrt(num);
for(int i = 2; i <= lmt; ++i)
if(num % i == 0)
return false;
return true;
}
int main(){
ios::sync_with_stdio(false);
int n;
while(cin >> n){
int ans = 0, tmp;
while(n--){
cin >> tmp;
if(checkprime(tmp)) ++ans;
}
cout << ans << endl;
}
return 0;
}
2.1.3 Cake
先分 \(k = gcd(a, b)\) 块，每份可以当做 \(\dfrac{a}{k}\) 块，也可以当做 \(\dfrac{b}{k}\) 块
按照切的刀数看，总共切了 \(a + b - k\) 刀，分成 \(a + b - k\) 块
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
int a, b;
while(cin >> a >> b) cout << (a + b - __gcd(a, b)) << endl;
return 0;
}
2.1.4 又见GCD
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
int n;
cin >> n;
while(n--){
int a, b;
cin >> a >> b;
a = a / b;
for(int i = 2; ; ++i)
if(__gcd(a, i) == 1){
cout << i * b << endl;
break;
}
}
return 0;
}
2.1.5 七夕节
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
ios::sync_with_stdio(false);
int t;
cin >> t;
while(t--){
int n;
cin >> n;
int ans = 1;
int lmt = sqrt(n);
for(int i = 2; i <= lmt; ++i)
if(n % i == 0)
ans += (i + n / i);
if(n == lmt * lmt) ans -= lmt;
cout << ans << endl;
}
return 0;
}
2.1.6 整数对
将原来的数\(A\) 分为低位\(a\)、去掉的一位\(b\)、高位\(c\)，设\(b\)为第\(k\)位，则有\(A = a + b * 10 ^ k + c * 10 ^ {k+1}\)
对于得到的新数字\(B\) 有：\(B = a + c * 10 ^ k\)
对于输入数据\(N\) 有:\(N = A + B = 2 * a + b * 10 ^ k + 11 * c * 10 ^ k\)
设 \(T = \dfrac{N}{10^k} = 11 * c + b\)
\(\dfrac{T}{11} = 11 * c \cdots\cdots b\)
则：
\(c = \dfrac{N}{11*10^k}\)， \(b = \dfrac{N}{10^k} - 11 * c\)， \(a = \dfrac{N - 11 * c * 10 ^ k - b * 10 ^ k}{2}\)
\(2 * a\) 可能会产生进位对 \(b\) 造成影响，但是对 \(a\) 无影响(b 最大为10，计算\(c\)时为除以11)
所以应对\(b\)分类讨论
#include <set>
#include <iostream>
using namespace std;
int main(){
int n;
while(cin >> n, n){
set<int> ans; // 去除重复 + 排序
int a, b, c;
for(int k = 1; k <= n; k *= 10){
c = n / 11 / k;
b = (n / k) - 11 * c;
if((b || c) && b < 10){ // 2*a 无进位
a = (n - 11 * c * k - b * k) >> 1;
if(2 * a + b * k + 11 * k * c == n) ans.insert(a + b * k + c * k * 10);
}
--b;
if((b || c) && b >= 0){ // 2*a 进位
a = (n - 11 * c * k - b * k) >> 1;
if(2 * a + b * k + 11 * k * c == n) ans.insert(a + b * k + c * k * 10);
}
}
if(ans.empty()) cout << "No solution." << endl;
else{
for(set<int>::iterator it = ans.begin(); it != ans.end(); ++it){
if(it != ans.begin()) cout << " ";
cout << *it;
}
cout << endl;
}
}
return 0;
}
2.1.7 The area
P1(x1, y1) P2(x2, y2) P3(x3, y3)
设直线 \(y_l = kx + h\)， 抛物线 \(y_p = ax^2+bx+c\)
对于\(y_l\)有 \(k = \dfrac{y_2-y_3}{x_2-x_3}\)， \(h = y_2 - k * x_2\)
对于\(y_p\): \(x_1 = -\dfrac{b}{2a}\)， \(y_1 = \dfrac{4ac-b^2}{4a}\)
则: \(b = -2ax_1\)
又有: \(a{x_1}^2 + bx_1 + c = y_1\)， \(a{x_2}^2 + bx_2 + c = y_2\)
\(\therefore a({x_2}^2 - {x_1}^2) - 2ax_1(x_2-x_1) = y_2-y_1\)
\(a = \dfrac{y_2-y_1}{{(x_2-x_1)}^2}\)， \(b = -2ax_1\)， \(c = y_1 - a{x_1}^2 - bx_1\)
设面积为\(S\)
\(y_p - y_l = ax^2 + (b-k)x + (c-h)\)
\(\displaystyle{S = \int_{x_2}^{x_3}(y_p - y_l) \, dx = \int_{x_2}^{x_3}(ax^2 + (b-k)x + (c-h)) \, dx}\)
求个定积分 \(\left(\left(\dfrac{a}{3}\right)({x_3}^3-{x_2}^3)+\left(\dfrac{b-k}{2}\right)({x_3}^2-{x_2}^2)+(c-h)(x_3-x_2)\right)\Bigg|_{x_2}^{x_3}\)
#include <cstdio>
int t;
double x1, y1, x2, y2, x3, y3;
int main(){
scanf("%d", &t);
while(t--){
scanf("%lf %lf %lf %lf %lf %lf", &x1, &y1, &x2, &y2, &x3, &y3);
double k = (y2-y3)/(x2-x3), h = y2-k*x2, a = (y2-y1)/(x2-x1)/(x2-x1), b = -2*a*x1, c = y1-a*x1*x1-b*x1;
printf("%.2f\n", ((a/3)*(x3*x3*x3-x2*x2*x2)+((b-k)/2)*(x3*x3-x2*x2)+(c-h)*(x3-x2)));
}
return 0;
}
2.1.8 Leftmost Digit
typedef long long ll;
科学计数法表示: \(n^n = a * 10^x\)
等号两边取对数: \(n*lg(n) = x + \lg(a)\) 由于\(0\le \lg(n) \le 1\)，所以\(x\)为\(n*lg(n)\)的整数部分
\(\lg(a) = n*\lg(n) - x\)
\(\lg(a) = n*\lg(n) - ll(n*\lg(n))\)
\(a = 10^{n*\lg(n) - ll(n*\lg(n))}\)
#include <cmath>
#include <iostream>
using namespace std;
typedef long long ll;
int main(){
ios::sync_with_stdio(false);
int t;
cin >> t;
while(t--){
ll n;
cin >> n;
cout << ll(pow(10, (n*log10(n) - ll(n*log10(n))))) << endl;
}
return 0;
}
Section 2
2.2.1 Fibonacci
Fibonacci公式: \(\displaystyle{F_n = \dfrac{1}{\sqrt5}\left[{\left(\dfrac{1+\sqrt5}{2}\right)}^n-{\left(\dfrac{1-\sqrt5}{2}\right)}^n\right]}\)
按照[Leftmost Digit](#Leftmost Digit)的方法求解
直接求\(F_n\)不太科学，考虑到用的是\(F_n\)的对数，对等号两边取对数，化简:
\(\lg(F_n) = \lg\left(\dfrac{1}{\sqrt5}\right) + n\,\lg\left(\dfrac{1 + \sqrt5}{2}\right) + \lg\left[1-{\left(\dfrac{1-\sqrt5}{1+\sqrt5}\right)}^n\right]\)
#include <math.h>
#include <stdio.h>
int main(){
int n;
int fib[233] = {0, 1};
for(int i = 2; i < 21; ++i) fib[i] = (fib[i-1] + fib[i-2]) % 10000;
while(~scanf("%d", &n)){
if(n < 21) {
printf("%d\n", fib[n]);
continue;
}
double logFn = log10((1/sqrt(5))) + n*log10((1+sqrt(5))/2) + log10(1-pow((1-sqrt(5))/(1+sqrt(5)),n));
double a = pow(10, logFn - int(logFn));
printf("%d\n", int(a * 1000));
}
return 0;
}
2.2.2 Fibonacci
相当于每次将ban掉的人去掉
#include <iostream>
using namespace std;
int main(){
ios::sync_with_stdio(false);
int arr[15];
for(int i = 1; i < 15; ++i)
for(int ans = i+1; ; ++ans){
int p = 0, left;
bool flag = true;
for(left = 2*i; left > i; --left){
// 将从1开头的编号对应到从0开头的编号以满足取模的需求
p = (p + ans - 1) % left;
// 不管ban了多少人，只要每次求出来的p比i小就代表杀死好人
if(p < i){ flag = false; break; }
}
if(flag && left == i){ arr[i] = ans; break; }
}
int n;
while(cin >> n, n) cout << arr[n] << endl;
return 0;
}
2.2.3
类似于递归检查是否满足条件
如果起始柱或目标柱上盘子数等于当前检查的盘子总数则是满足条件
否则，检查最大的盘子，如果在借助柱则不满足条件，如果不在借助柱则检查当前盘子总数-1的情况
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 66;
int t, N, n[3], id[3][MAXN], pos[3];
int main(){
ios::sync_with_stdio(false);
cin >> t;
while(t--){
int aa = 0, bb = 1, cc = 2;
pos[aa] = pos[bb] = pos[cc] = 0;
cin >> N;
cin >> n[0]; for(int i = 0; i < n[0]; ++i) cin >> id[aa][i];
cin >> n[1]; for(int i = 0; i < n[1]; ++i) cin >> id[bb][i];
cin >> n[2]; for(int i = 0; i < n[2]; ++i) cin >> id[cc][i];
bool flag = true;
while(true){
if(n[aa] == N || n[cc] == N){ flag = true; break; }
if(n[bb] && id[bb][pos[bb]] == N){ flag = false; break; }
if(n[aa] && id[aa][pos[aa]] == N){
--N;
--n[aa];
++pos[aa];
swap(bb, cc);
continue;
}
if(n[cc] && id[cc][pos[cc]] == N){
--N;
--n[cc];
++pos[cc];
swap(aa, bb);
continue;
}
}
cout << (flag ? "true" : "false") << endl;
}
return 0;
}
2.2.4 Wolf and Rabbit
n, m最大公约数为1时代表wolf能从hole0走到hole1，也就能走到其他所有的hole
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
ios::sync_with_stdio(false);
int t, n, m;
cin >> t;
while(t--){
cin >> n >> m;
cout << (__gcd(n, m) == 1 ? "NO" : "YES") << endl;
}
return 0;
}
2.2.5 Number Sequence
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
ios::sync_with_stdio(false);
int a, b, n;
while(cin >> a >> b >> n, a || b || n){
int i, arr[55] = {0, 1, 1};
for(i = 3; i < 50; ++i){
arr[i] = (a * arr[i-1] + b * arr[i-2]) % 7;
if(arr[i] == 1 && arr[i-1] == 1) break; // 找循环节，最多不会超过50
}
n %= (i - 2);
cout << (n ? arr[n] : arr[i-2]) << endl;
}
return 0;
}
2.2.6 Train Problem II
Catalan公式: \(Catalan_{n} = \dfrac{C_{2n}^n}{n + 1}\)
Catalan递推公式: \(Catalan_{n} = \dfrac{(4n-2)Catalan_{n-1}}{n+1}\)
import java.util.*;
import java.math.*;
public class Main{
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
BigInteger[] ans = new BigInteger[111];
ans[0] = ans[1] = new BigInteger("1");
for(int i = 2; i < 111; ++i)
ans[i] = ans[i-1].multiply(new BigInteger(Integer.toString(4*i-2))).divide(new BigInteger(Integer.toString(i+1)));
while(scan.hasNext()){
int n = scan.nextInt();
System.out.println(ans[n]);
}
scan.close();
}
}
```cpp
[2.2.7]()
```cpp
2.2.8 Big Number
对于一个数k，求位数：\(\lg(k) + 1\)
\(1 \le n \le 10^7\)范围内可以直接用循环求: \(\lg(n!) = \lg(1) + \lg(2) + \cdots + \lg(n)\)
对于大数阶乘的值\(n!\)还可以用斯特林公式: \(n! \approx \sqrt{2{\pi}n}\left(\dfrac{n}{e}\right)^n\) 即使在n较小时取值也非常准确
则: \(\lg(n!) = \lg\left(\sqrt{2{\pi}n}\left(\dfrac{n}{e}\right)^n\right) = \dfrac{1}{2}\lg(2{\pi}n) + n\lg\left(\dfrac{n}{e}\right)\)
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
const double pi = acos(-1.0);
const double e = exp(1.0);
int main(){
ios::sync_with_stdio(false);
// 直接运算
//int t, n;
//cin >> t;
//while(t--){
// cin >> n;
// double ans = 0.0;
// for(int i = 1; i <= n; ++i) ans += log10(i);
// cout << int(ans) + 1 << endl;
//}
// 运用斯特林公式运算
int t, n;
cin >> t;
while(t--){
cin >> n;
cout << int(0.5*log10(2*pi*n)+n*log10(n/e)+1) << endl;
}
}