title: C++奧賽一本通刷題記錄(遞歸)
date: 2017-11-09
tags:
一本通
openjudege
categories: OI
2017.11.9 By gwj1139177410
逆波蘭表達(dá)式 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
//直接套模板，據(jù)說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
分解因數(shù) openjudge1751
//這題我第一個(gè)想法是排列組合，數(shù)論，然后。。。。 #include using namespace std; int f(int n, int m){ //找n的分解方案數(shù) if(n == 1)return 0; int ans = 1; //加上題目自己算一個(gè)值 for(int i = m; i*i <= n; i++)//枚舉n的每個(gè)約數(shù)，每次除掉(從小到大去重) 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
斐波那契數(shù)列 openjudge1755
//╮(￣▽￣)╭數(shù)據(jù)太水我也沒辦法 #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數(shù)列 openjudge1788
//(? ???ω??? ?)這個(gè)沒有記憶化藥丸了 #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
括號(hào)匹配問題 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
//這種就是經(jīng)常出現(xiàn)在初賽看程序?qū)懡Y(jié)果里面的 //ha2():將n個(gè)盤子從a經(jīng)過c移動(dòng)到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個(gè)盤子移動(dòng)到輔助的桿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
//已經(jīng)很水啦，貌似遞推做過呢 #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
求最大公約數(shù)問題 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
分?jǐn)?shù)求和 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
//感覺有點(diǎn)繞，拿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;//強(qiáng)行搞事情 } 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
//開個(gè)玩笑的,不過這也算遞歸? #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++
版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實(shí)的內(nèi)容，請聯(lián)系我們jiasou666@gmail.com 處理，核實(shí)后本網(wǎng)站將在24小時(shí)內(nèi)刪除侵權(quán)內(nèi)容。
