題目地址:http://oj.ecustacm.cn/viewnews.php?id=1021

目錄

• 四平方和【二分 / 預(yù)處理】
• 煤球數(shù)目【遞推】
• 湊算式【全排列】
• 平方怪圈【打表找規(guī)律】
• 冰雹數(shù)【枚舉 / 預(yù)處理】
• 搭積木【全排列】
• 有獎(jiǎng)猜謎【模擬】
• 生日蠟燭【枚舉】
• 方格填數(shù)【全排列】
• 剪郵票【組合數(shù) 連通塊】
• 交換瓶子【找環(huán)】
• 寒假作業(yè)【全排列】
• 報(bào)紙頁數(shù)【找規(guī)律】
• 卡片換位【BFS】
• 最大比例【gcd 輾轉(zhuǎn)相減法】
• 網(wǎng)友年齡【枚舉】

四平方和【二分 / 預(yù)處理】

解析：

可以很容易的想到用4層的for暴力。這樣一定會(huì)超時(shí)。
那么問題就是減少for的層數(shù)。
我們可以處理兩層的for,這樣就減少了兩維，然后用二分進(jìn)行查找即可。

#include<bits/stdc++.h> using namespace std; struct node{int a,b,c;}; bool cmp(node a,node b) {if(a.c==b.c) return a.a<b.a;return a.c<b.c; } vector<node>ve; int n; int main(void) {for(int i=0;i<=2300;i++)//預(yù)處理for(int j=i;j<=2300;j++) ve.push_back({i,j,i*i+j*j});sort(ve.begin(),ve.end(),cmp);while(cin>>n){int flag=0;for(int i=0;i*i<=n;i++){for(int j=i;j*j+i*i<=n;j++){int temp=n-i*i-j*j;int l=0,r=ve.size()-1;while(l<r)//二分{int mid=l+r>>1;if(ve[mid].c>=temp) r=mid;else l=mid+1;}if(ve[l].c==temp)//找到了{cout<<i<<" "<<j<<" "<<ve[l].a<<" "<<ve[l].b<<'\n';flag=1;}if(flag) break;}if(flag) break;}}return 0; }

煤球數(shù)目【遞推】

#include<bits/stdc++.h> using namespace std; typedef long long int LL; LL sum=0; int main(void) {for(int i=1,j=1,k=1;i<=100;i++,j=j+k) sum+=j,k++;cout<<sum;return 0; }

湊算式【全排列】

#include<bits/stdc++.h> using namespace std; int s[10],cnt; int main(void) {for(int i=0;i<9;i++) s[i]=i+1;do{double a=s[0],b=s[1],c=s[2];double d=s[3]*100+s[4]*10+s[5];double e=s[6]*100+s[7]*10+s[8];if(a+b/c+d/e==10) cnt++;}while(next_permutation(s,s+9));cout<<cnt;return 0; }

平方怪圈【打表找規(guī)律】

其實(shí)不要慌，按照題目模擬就好了。
你可以按照題目寫個(gè)程序，然后隨意的輸入一個(gè)起始值，你會(huì)發(fā)現(xiàn)無論你輸入的是啥，最后一定會(huì)有一個(gè)循環(huán)的圈。
然后輸出這個(gè)圈的最大值即可。

#include<bits/stdc++.h> using namespace std; map<int,int>mp; int n,ans; int main(void) {/*cin>>n;ans=n;while(1){mp[n]++;string s=to_string(n);cout<<n<<endl;n=0;for(int i=0;i<s.size();i++) n+=(s[i]-'0')*(s[i]-'0');ans=max(ans,n);if(mp[n]) {//cout<<"********";cout<<n<<endl;break;}}//cout<<ans;*/cout<<145;return 0; }

冰雹數(shù)【枚舉 / 預(yù)處理】

題目的意思就是 1-n中所有的數(shù)按照上面的步驟，求其中最大的值。
直接對(duì)于每次的輸入，我們暴力的按照上面的步驟執(zhí)行一定會(huì)超時(shí)。那么我們可以處理里所有的結(jié)果。
對(duì)于每次查詢，O(1)的輸出即可。

#include<bits/stdc++.h> using namespace std; typedef long long int LL; const int N=1e6+10; LL a[N]; void init() {map<LL,int>mp;for(int i=1;i<N;i++){LL temp=i,cnt=1;while(temp!=1&&!mp[temp]){mp[temp]++;if(temp&1) temp=temp*3+1;else temp/=2;cnt=max(cnt,temp);}a[i]=cnt;}for(int i=1;i<N;i++) a[i]=max(a[i],a[i-1]); } int main(void) {init();int n; while(cin>>n) cout<<a[n]<<endl; return 0; } #include<bits/stdc++.h> using namespace std; typedef long long int LL; map<LL,LL>mp; LL n; LL dfs(LL u) {if(mp[u]) return mp[u];if(u==1) return 1;if(u&1) return mp[u]=max(u*3+1,dfs(u*3+1));else return mp[u]=dfs(u/2); } int main(void) {while(cin>>n){LL ans=n;for(int i=1;i<=n;i++) ans=max(ans,dfs(i));cout<<ans<<endl;}return 0; }

搭積木【全排列】

#include<bits/stdc++.h> using namespace std; int a[10],cnt; int main(void) {for(int i=0;i<10;i++) a[i]=i;do{bool flag=1;if(a[3]>a[6]||a[3]>a[7]) flag=0;if(a[4]>a[7]||a[4]>a[8]) flag=0;if(a[5]>a[8]||a[5]>a[9]) flag=0;if(a[1]>a[3]||a[1]>a[4]) flag=0;if(a[2]>a[4]||a[2]>a[5]) flag=0;if(a[0]>a[1]||a[0]>a[2]) flag=0;if(flag) cnt++;}while(next_permutation(a,a+10));cout<<cnt; return 0; }

有獎(jiǎng)猜謎【模擬】

#include<bits/stdc++.h> using namespace std; int cnt=777; string s="vxvxvxvxvxvxvvx"; int main(void) {for(int i=0;i<s.size();i++) if(s[i]=='v') cnt=cnt*2;else cnt=max(0,cnt-555);cout<<cnt; return 0; }

生日蠟燭【枚舉】

#include<bits/stdc++.h> using namespace std; int main(void) {for(int i=0;i<=100;i++){int sum=0;for(int j=i;sum<236;j++) sum+=j;if(sum==236) {cout<<i;break;}}return 0; }

方格填數(shù)【全排列】

#include<bits/stdc++.h> using namespace std; int a[15],cnt; bool f(int x,int y) {int t=abs(a[x]-a[y]);if(t==1) return true;return false; } int main(void) {for(int i=0;i<10;i++) a[i]=i;do{bool flag=1;if(f(0,1) || f(0,3) || f(0,4) || f(0,5) ) flag=0;if(f(1,2) || f(1,4) || f(1,5) || f(1,6)) flag=0;if(f(2,5) || f(2,6)) flag=0;if(f(3,4) || f(3,7) || f(3,8)) flag=0;if(f(4,5) || f(4,7) || f(4,8) || f(4,9)) flag=0;if(f(5,6) || f(5,8) || f(5,9)) flag=0;if(f(6,9)) flag=0;if(f(7,8)) flag=0;if(f(8,9)) flag=0;if(flag) cnt++;}while(next_permutation(a,a+10));cout<<cnt;return 0; }

剪郵票【組合數(shù) 連通塊】

首先，我們思考一下如何枚舉，本質(zhì)就是12個(gè)數(shù)里選5個(gè)數(shù)。然后判斷這5個(gè)數(shù)在不在同一個(gè)聯(lián)通塊里。

#include<bits/stdc++.h> using namespace std; typedef pair<int,int> pii; int a[15],st[15],cnt; int dx[4]={-1,0,0,1}; int dy[4]={0,-1,1,0}; bool check() {vector<pii>ve;map<pii,int>mp;queue<pii>q; q.push({a[0]/4,a[0]%4});while(q.size()){auto temp=q.front(); q.pop();mp[temp]++;int x=temp.first,y=temp.second;for(int i=0;i<4;i++){int tempx=x+dx[i],tempy=y+dy[i];if(tempx<0||tempx>=3||tempy<0||tempy>=4) continue;if(!st[tempx*4+tempy]) continue;if(mp[{tempx,tempy}]) continue;q.push({tempx,tempy});}}return mp.size()==5;//連通塊內(nèi)的個(gè)數(shù)是不是5 } void dfs(int index) {if(index==5){if(check()) cnt++;return;}for(int i=0;i<=11;i++){if(!st[i]){a[index]=i,st[i]=1;dfs(index+1);st[i]=0;}} } int main(void) {dfs(0);//A12選5 int temp=1;for(int i=1;i<=5;i++) temp=temp*i;//除以重復(fù)的5!cout<<cnt/temp;return 0; }

交換瓶子【找環(huán)】

#include<bits/stdc++.h> using namespace std; const int N=1e4+10; int n,a[N],st[N]; int main(void) {while(cin>>n) {memset(st,0,sizeof st);for(int i=1;i<=n;i++) cin>>a[i];int ans=0;for(int i=1;i<=n;i++){int cnt=0;for(int j=a[i];!st[j];j=a[j]) {st[j]=1,cnt++;}if(cnt) ans+=cnt-1;//環(huán)的邊數(shù)減1}cout<<ans<<endl;}return 0; }

寒假作業(yè)【全排列】

#include<cstring> #include<cstdio> #include<iostream> #include<string> #include<algorithm> using namespace std; int b[15]={1,2,3,4,5,6,7,8,9,10,11,12,13}; int ans=0; int main(void) {do{if(b[0]+b[1]==b[2])if(b[3]-b[4]==b[5])if(b[6]*b[7]==b[8])if( ( b[9]/b[10]==b[11] )&& (b[9]%b[10]==0) )ans++;}while(next_permutation(b,b+13));printf("%d\n",ans);//cout<<64;return 0; }

報(bào)紙頁數(shù)【找規(guī)律】

題解
1728+1125-1

卡片換位【BFS】

#include<bits/stdc++.h> using namespace std; string s1,s2,a,b; int dx[4]={-1,0,0,1}; int dy[4]={0,-1,1,0}; int A,B; int bfs() {map<string,int>mp;queue<string>q; q.push(s1);mp[s1]=0;while(q.size()){string s=q.front(); q.pop();int x1=s.find('A'),x2=s.find('B');if(x1==A&&x2==B){return mp[s];}int index=s.find(' '),x=index/3,y=index%3;for(int i=0;i<4;i++){int tempx=x+dx[i],tempy=y+dy[i];if(tempx<0||tempx>=2||tempy<0||tempy>=3) continue;string temp=s;int c1=index,c2=tempx*3+tempy;swap(temp[c1],temp[c2]);if(mp.count(temp)) continue;mp[temp]=mp[s]+1;q.push(temp);}} } int main(void) {while(getline(cin,a)){getline(cin,b);s1=a+b;A=s1.find('B'),B=s1.find('A');cout<<bfs()<<endl;}return 0; }

最大比例【gcd 輾轉(zhuǎn)相減法】

#include<bits/stdc++.h> using namespace std; typedef long long int LL; typedef pair<LL,LL> pii; const int N=110; LL n; LL gcd(LL a,LL b) {return b?gcd(b,a%b):a; } LL gcd_sub(LL a,LL b) {if(a<b) swap(a,b); //始終保證a比b大if(b==1) return a; //這里到了邊界，為什么是1？說明上一層的時(shí)候a和b已經(jīng)相等，這時(shí)候最大公約數(shù)是他們中的任一個(gè)return gcd_sub(b,a/b); } int main(void) {while(cin>>n){vector<LL>a;for(int i=0;i<n;i++){LL x; cin>>x;a.push_back(x);}sort(a.begin(),a.end());a.erase(unique(a.begin(),a.end()),a.end());vector<pii>ve;for(int i=1;i<a.size();i++){LL temp=gcd(a[i],a[0]);ve.push_back( {a[i]/temp,a[0]/temp} );}LL ansx=ve[0].first,ansy=ve[0].second;for(int i=1;i<ve.size();i++){ansx=gcd_sub(ansx,ve[i].first);ansy=gcd_sub(ansy,ve[i].second);}cout<<ansx<<"/"<<ansy<<endl;}return 0; }

網(wǎng)友年齡【枚舉】

#include<bits/stdc++.h> using namespace std; int cnt; int main(void) {for(int i=27;i<=100;i++){int s=i/10+(i%10)*10;if(s+27==i) cnt++;}cout<<cnt;return 0; }

總結(jié)

以上是生活随笔為你收集整理的2016年蓝桥杯省赛题解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。