【A：HDU2032 杨辉三角】：
简单的递推，或者是基础的DP；
但是只有杨润东一个人1A，整体准确率只有8/37，具体原因不详。
经验：提交前一定要试一下比较特殊的数据或者最大的数据。其次，为了保险，一定要严格按照格式来输出。
最后，数组最好定义为全局变量，i，j等定义为局部变量。
#include<cstdio> #include<cstdlib> #include<iostream> #include<memory.h> #include<algorithm> using namespace std; long long f[40][40]; int main() { int i,j,n; f[1][1]=1; for(i=2;i<=30;i++) for(j=1;j<=i;j++) f[i][j]=f[i-1][j]+f[i-1][j-1]; while(~scanf("%d",&n)){ for(i=1;i<=n;i++){ printf("%lld",f[i][1]); for(j=2;j<=i;j++) printf(" %lld",f[i][j]); printf(" "); } printf(" "); } return 0; }
【B：HDU2046 骨牌铺方格】：
我们可以得到方程F[i]=F[i-1]+F[i-2]，其实就是斐波拉契数列，注意要使用long long。
经验：此题的N较小，N较大时需要用“矩阵乘法”来做。
#include<cstdio> #include<cstdlib> #include<iostream> #include<memory.h> #include<algorithm> #include<cmath> using namespace std; int a,b; long long s[60]; int main() { int n,i,j,ans,temp; s[1]=1;s[2]=2;s[3]=3; for(i=4;i<=51;i++) { s[i]=s[i-1]+s[i-2]; } while(cin>>n){ cout<<s[n]<<endl; } return 0; }
-------------------------------上面的noip第一题水平，以下是noip第二题水平------------------------------------
【C：POJ2976 Dropping tests】
题意：有几门成绩，现在要求选N-K门，使得平均成绩最高，求最高平均成绩。
思路：01分数规划：贪心+二分，我们二分最高平均成绩ans，然后排序，得到前N-K名，看他们的平均成绩是否大于等于ans。
具体实现：a/b>=ans，a-b*ans排序，越大的价值越高。证明：这里涉及一个式子：若a/b=c/d，则a/b=c/d=(a+c)/(b+d)，所以分子之和/分母之和>=ans，那么a/b>=ans的程度越大越好，所以根据a-b*ans排序。
详细的证明还请自己百度。
#include<cstdio> #include<cstdlib> #include<iostream> #include<cstring> #include<algorithm> using namespace std; const double eps=1e-6; int N,K; struct in { double x,y; double res; bool friend operator <(in a,in b){ return a.res>b.res; } }a[1010]; bool check(double Mid) { for(int i=1;i<=N;i++) a[i].res=a[i].x-Mid*a[i].y; sort(a+1,a+N+1); double tx=0; for(int i=1;i<=K;i++) tx+=a[i].res; if(tx>=-eps) return true; return false; } int main() { while(~scanf("%d%d",&N,&K)&&(N||K)){ K=N-K; for(int i=1;i<=N;i++) scanf("%lf",&a[i].x),a[i].x*=100.0; for(int i=1;i<=N;i++) scanf("%lf",&a[i].y); double L=0,R=100,Mid,ans=0; while(R-L>eps){ Mid=(L+R)/2; if(check(Mid)) ans=Mid,L=Mid+eps; else R=Mid-eps; } printf("%.0lf ",ans); } return 0; }
【D：HihoCoder 1504 骑士游历】
基础的矩阵乘法。
#include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> using namespace std; const int maxn=70; #define ll long long const int Mod=1e9+7; int x[8]={2,2,-2,-2,1,1,-1,-1}; int y[8]={1,-1,1,-1,2,-2,2,-2}; struct mat { ll M[maxn][maxn]; mat() { memset(M,0,sizeof(M)); } mat friend operator *(mat a,mat b) { mat res; for(int k=1;k<=64;k++) for(int i=1;i<=64;i++) for(int j=1;j<=64;j++){ res.M[i][j]=(res.M[i][j]+a.M[i][k]*b.M[k][j])%Mod; } return res; } mat friend operator ^(mat a,int x) { mat res; for(int i=1;i<=64;i++) res.M[i][i]=1; while(x){ if(x&1) res=a*res; a=a*a; x/=2; } return res; } }; mat base; void prepare() { for(int i=1;i<=8;i++) for(int j=1;j<=8;j++) for(int k=0;k<8;k++) if(i+x[k]>=1&&i+x[k]<=8&&j+y[k]>=1&&j+y[k]<=8) base.M[(i-1)*8+j][(i+x[k]-1)*8+j+y[k]]=1; } int main() { int N,R,C,ans=0; scanf("%d%d%d",&N,&R,&C); prepare(); base=base^N; for(int i=1;i<=64;i++) ans=(ans+base.M[(R-1)*8+C][i])%Mod; printf("%d ",ans); return 0; }
【HDU 5890：Eighty seven】
题意：N个物品，分别有自己的值，Q个问题，每次问拿走第X个，第Y个和第Z个物品后，是否能在里面找10个物品，使其和为87。
思路：背包问题，DP。
经验：必须要学会使用Bitset。
#include<bitset> #include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> using namespace std; bool ans[55][55][55]; bitset<90>s[20]; int a[60],N; int read() { char c=getchar(); int res; while(c>'9'||c<'0') c=getchar(); for(res=0;c>='0'&&c<='9';c=getchar()) res=(res<<3)+(res<<1)+c-'0'; return res; } void solve(int x,int y,int z) { for(int i=0;i<=11;i++) s[i].reset(); s[0][0]=1; for(int i=1;i<=N;i++){ if(i==x||i==y||i==z||a[i]>87) continue; for(int j=10;j>=1;j--) s[j]|=s[j-1]<<a[i]; } if(s[10][87]==1) ans[x][y][z]=true; else ans[x][y][z]=false; } int main() { int T,Q; T=read(); while(T--){ scanf("%d",&N); for(int i=1;i<=N;i++) a[i]=read(); for(int i=1;i<=N;i++) for(int j=i;j<=N;j++) for(int k=j;k<=N;k++) solve(i,j,k); Q=read(); while(Q--){ int x[3]; x[0]=read(); x[1]=read(); x[2]=read(); sort(x,x+3); if(ans[x[0]][x[1]][x[2]]) puts("Yes"); else puts("No"); } } return 0; }
总结：提交前，一定要分析的东西，数据范围；算法效率是否妥当。
然后，多刷题，如果可以在HDU上面刷500题，或者BZOJ上面刷100道题，稳稳地拿省一（对弱省来说）。
当然，要学会挑战难题，突破自己。