title: C++奥赛一本通刷题记录(递归)
date: 2017-11-09
tags:
一本通
openjudege
categories: OI
2017.11.9 By gwj1139177410
逆波兰表达式 openjudge1696
//栈比较坑。。。 #include #include #include #include char a[3010]; double trans(){ //float is bugs scanf("%s",a); if(strlen(a)==1){ if(a[0]=='+')return trans()+trans(); if(a[0]=='-')return trans()-trans(); if(a[0]=='*')return trans()*trans(); if(a[0]=='/')return trans()/trans(); }else{ return atof(a); } } int main(){ printf("%f\n", trans()); return 0; }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
全排列 openjudge1750
//直接套模板，据说STL也能水 #include #include const int maxn = 110; char a[maxn], b[maxn]; int n, vis[maxn]; void dfs(int cur){ if(cur == n){ for(int i = 0; i < n; i++)putchar(b[i]); printf("\n"); }else for(int i = 0; i < n; i++){ if(!vis[i]){ vis[i] = 1; b[cur] = a[i]; dfs(cur+1); vis[i] = 0; } } } int main(){ scanf("%s", a); n = strlen(a); dfs(0); return 0; }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
分解因数 openjudge1751
//这题我第一个想法是排列组合，数论，然后。。。。 #include using namespace std; int f(int n, int m){ //找n的分解方案数 if(n == 1)return 0; int ans = 1; //加上题目自己算一个值 for(int i = m; i*i <= n; i++)//枚举n的每个约数，每次除掉(从小到大去重) if(n%i==0)ans += f(n/i,i); return ans; } int main(){ int T; cin>>T; while(T--){ int n; cin>>n; cout<1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
斐波那契数列 openjudge1755
//╮(￣▽￣)╭数据太水我也没办法 #include using namespace std; int f(int n){ return n==1||n==2?1:f(n-1)+f(n-2); } int main(){ int T; cin>>T; while(T--){ int n; cin>>n; cout<1
2
3
4
5
6
7
8
9
10
11
12
13
14
pell数列 openjudge1788
//(⁄ ⁄•⁄ω⁄•⁄ ⁄)这个没有记忆化药丸了 #include using namespace std; int f[1000010]; int fn(int n){ return f[n]?f[n]:f[n]=(2*fn(n-1)+fn(n-2))%32767; } int main(){ f[1]=1; f[2]=2; int T; cin>>T; while(T--){ int n; cin>>n; cout<1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
括号匹配问题 openjudge2705
//模拟题一番水 #include #include #include using namespace std; int main(){ string s, t; stacksk, tk; while(getline(cin,s)){ t.resize(s.size()); for(int i = 0; i < s.size(); i++){ t[i] = ' '; if(s[i]=='(')sk.push(i); if(s[i]==')'){ if(sk.size())sk.pop(); else tk.push(i); } } while(sk.size()){ t[sk.top()] = '$'; sk.pop(); } while(tk.size()){ t[tk.top()] = '?'; tk.pop(); } 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
爬楼梯 openjudge3089
#include using namespace std; int a[50]; int f(int n){ return a[n]?a[n]:a[n]=f(n-1)+f(n-2); } int main(){ a[1]=1; a[2]=2; //稍微注意一下边界就好啦 int n; while(cin>>n){ cout<1
2
3
4
5
6
7
8
9
10
11
12
13
14
汉诺塔问题 openjudge6261
//这种就是经常出现在初赛看程序写结果里面的 //ha2():将n个盘子从a经过c移动到b #include using namespace std; void ha2(int n, char a, char b, char c){ if(!n)return ; ha2(n-1,a,c,b); //把前n-1个盘子移动到辅助的杆c cout<"<"<>n>>a>>b>>c; ha2(n,a,b,c); return 0; }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
放苹果 openjudge666
//已经很水啦，貌似递推做过呢 #include using namespace std; int f(int m, int n){ if(m==0 || n==1)return 1; return n>m?f(m,m):f(m,n-1)+f(m-n,n); } int main(){ int T; cin>>T; while(T--){ int m, n; cin>>m>>n; cout<1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
求最大公约数问题 openjudge7592
#include using namespace std; typedef long long LL; LL gcd(LL a, LL b){ return !b?a:gcd(b,a%b); } int main(){ LL a, b; cin>>a>>b; cout<1
2
3
4
5
6
7
8
9
10
11
2的幂次方表示 openjudge8758
//直接模拟就好啦 #include using namespace std; void dfs(int dep, int n){ //if(n<=2){ cout<= 0; i--){ if(n&(1<>n; dfs(30,n); return 0; }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
分数求和 openjudge12
//gcd&lcm #include using namespace std; int gcd(int a, int b){ return !b?a:gcd(b,a%b); } int lcm(int a, int b){ return a/gcd(a,b)*b; } int main(){ int a=0, b=1; int T; cin>>T; while(T--){ int c, d; cin>>c; cin.get(); cin>>d; int t = lcm(b,d); a = a*(t/b)+c*(t/d); b = t; while((t=gcd(a,b))!=1){ a/=t; b/=t; } } if(b==1||a==0)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
因子分解 openjudge22
#include using namespace std; int main(){ int n, flag=0; cin>>n; for(int i = 2; i <= n; i++){ int cnt = 0; while(n%i==0){ n /= i; cnt++; } if(cnt){ if(flag)cout<<"*"; if(cnt==1)cout<1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
判断元素是否存在 openjudge41
//感觉有点绕，拿set水了 #include #include using namespace std; sets; int main(){ int k, x, t; cin>>k; cin.get(); cin>>x; s.insert(k); t = k; int cnt = 0; for(set::iterator it = s.begin(); it!=s.end(); it++){ s.insert(2*(*it)+1); s.insert(3*(*it)+1); if(*(--s.end())>x)cnt++; if(cnt>1000)break;//强行搞事情 } if(s.count(x))cout<<"YES\n";else cout<<"NO\n"; return 0; }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//开个玩笑的,不过这也算递归? #include using namespace std; const int maxn = 300010; int a[maxn]; void enlarge(int x){ if(x>k; cin.get(); cin>>x; enlarge(k); if(a[x])cout<<"YES\n";else cout<<"NO\n"; return 0; }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
C++
版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。
