差F
问题 A: 煤球数目
注意是求总数目而不是每一层的数目
#include<bits/stdc++.h> using namespace std; const int maxn=1e6+7,mod=1e9+7; int a[maxn],n; int main(){ int res=0; for(int i=1;i<=100;i++) for(int j=1;j<=i;j++) res+=j; cout<<res; return 0; }
问题 B: 生日蜡烛
#include<bits/stdc++.h> using namespace std; const int maxn=1e6+7,mod=1e9+7; int a[maxn],n; int main(){ int sum=0,x,s=0; for(int i=1;i<=100;i++){///枚举年龄起点 sum=0; for(int j=i;j<=100;j++){ sum+=j; if(sum==236){ cout<<i<<endl; break; } } } return 0; }
问题 C: 凑算式
美丽的for循环版
#include<bits/stdc++.h> using namespace std; int main(){ int res=0; for(double a=1;a<10;a++) for(double b=1;b<10;b++) if(a!=b) for(double c=1;c<10;c++) if(a!=c&&b!=c) for(double d=1;d<10;d++) if(a!=d&&b!=d&&c!=d) for(double e=1;e<10;e++) if(a!=e&&b!=e&&c!=e&&d!=e) for(double f=1;f<10;f++) if(a!=f&&b!=f&&c!=f&&d!=f&&e!=f) for(double g=1;g<10;g++) if(a!=g&&b!=g&&c!=g&&d!=g&&e!=g&&f!=g) for(double h=1;h<10;h++) if(a!=h&&b!=h&&c!=h&&d!=h&&e!=h&&f!=h&&g!=h) for(double i=1;i<10;i++) if(a!=i&&b!=i&&c!=i&&d!=i&&e!=i&&f!=i&&g!=i&&h!=i) if(a+(b/c)+((d*100+e*10+f)/(g*100+h*10+i))==10) res++; cout<<res; return 0; }
简洁的dfs版
#include<bits/stdc++.h> using namespace std; double a[10]; bool st[10]; int res=0; void dfs(int u){ if(u==10) if(a[1]+a[2]/a[3]+(a[4]*100+a[5]*10+a[6])/(a[7]*100+a[8]*10+a[9])==10){ res++; return ; } for(int i=1;i<=9;i++) if(!st[i]){ a[u]=i; st[i]=1; dfs(u+1); st[i]=0; } return ; } int main(){ dfs(1); cout<<res; return 0; }
C++ stl 的next_permutation()
#include <bits/stdc++.h> using namespace std; int main() { int a[10]={0,1,2,3,4,5,6,7,8,9}; int sum=0; while(next_permutation(a+1,a+10)) { double lala=(double)a[1]+(double)a[2]/a[3]+(double)(a[4]*100+a[5]*10+a[6])/(a[7]*100+a[8]*10+a[9]); if(lala==10.0) sum++; } cout<<sum; return 0; }
问题 D: 抽签
#include<bits/stdc++.h> using namespace std; int main(){ cout<<"f(a,k+1,m-i,b)"<<endl; ///cout<<"f(a,k+1,m-j,b)"<<endl; return 0; }
问题 E: 方格填数
dfs版本
#include<bits/stdc++.h> using namespace std; bool st[10]; int a[4][5]; int res=0; bool judge(){ for(int i=0;i<3;i++) for(int j=0;j<4;j++) if(abs(a[i][j]-a[i][j+1])==1||abs(a[i][j]-a[i+1][j])==1||abs(a[i][j]-a[i+1][j-1])==1||abs(a[i][j]-a[i+1][j+1])==1) return 0; return 1; } void dfs(int u){ if(u==11) if(judge()){ res++;return ; } for(int i=0;i<10;i++) if(!st[i]){ st[i]=1; a[u/4][u%4]=i; dfs(u+1); st[i]=0; } } void E(){ memset(a,0x2f,sizeof a); dfs(1); cout<<res; } int main(){ E(); return 0; }
全排列版本 传送门
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int a[12]={-2,0,1,2,3,4,5,6,7,8,9,-2}; int dx[8]={1,1,1,0,-1,-1,-1,0}; int dy[8]={-1,0,1,1,1,0,-1,-1}; int res; bool judge() { for(int i=1;i<=10;i++) { int y=i/4; int x=i%4; for(int k=0;k<8;k++) { int ny=y+dy[k]; int nx=x+dx[k]; int j=ny*4+nx; if(0<=ny&&ny<3&&0<=nx&&nx<4) { if(abs(a[j]-a[i])==1) return false; } } } return true; } int main() { do{ if(judge()) res++; }while(next_permutation(a+1,a+11)); printf("%d\n",res); return 0; } /* res:1580 */ ///出自:vCoders
问题 F: 剪邮票
问题 G: 四平方和
暴力解法（O（n^3））
#include<bits/stdc++.h> using namespace std; int main(){ int n; while(scanf("%d",&n)!=EOF){ for(int a=0;a*a<=n;a++) for(int b=a;a*a+b*b<=n;b++) for(int c=b;a*a+b*b+c*c<=n;c++){ int t=n-a*a-b*b-c*c; int d=sqrt(t); if(t==d*d){ printf("%d %d %d %d\n",a,b,c,d); goto A; } } A:continue; } return 0; }
二分解法（O（n^2 logn））
待补
问题 H: 交换瓶子
#include<bits/stdc++.h> using namespace std; const int N=10010; int a[N],n,t; int main(){ while(cin>>n){ for(int i=1;i<=n;i++) cin>>a[i]; int ans=0; for(int i=1;i<=n;i++) if(a[i]!=i){ for(int j=i+1;j<=n;j++) if(a[j]==i){ t=a[i]; a[i]=a[j]; a[j]=t; } ans++; } cout<<ans<<endl; } return 0; }
