【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[][];
int main()
{
int i,j,n;
f[][]=;
for(i=;i<=;i++)
for(j=;j<=i;j++)
f[i][j]=f[i-][j]+f[i-][j-];
while(~scanf("%d",&n)){
for(i=;i<=n;i++){
printf("%lld",f[i][]);
for(j=;j<=i;j++)
printf(" %lld",f[i][j]);
printf("\n");
}
printf("\n");
}
return ;
}
【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[];
int main()
{
int n,i,j,ans,temp;
s[]=;s[]=;s[]=;
for(i=;i<=;i++)
{
s[i]=s[i-]+s[i-];
}
while(cin>>n){
cout<<s[n]<<endl;
}
return ;
}
——————————-上面的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-;
int N,K;
struct in
{
double x,y;
double res;
bool friend operator <(in a,in b){
return a.res>b.res;
}
}a[];
bool check(double Mid)
{
for(int i=;i<=N;i++) a[i].res=a[i].x-Mid*a[i].y;
sort(a+,a+N+);
double tx=;
for(int i=;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=;i<=N;i++) scanf("%lf",&a[i].x),a[i].x*=100.0;
for(int i=;i<=N;i++) scanf("%lf",&a[i].y);
double L=,R=,Mid,ans=;
while(R-L>eps){
Mid=(L+R)/;
if(check(Mid)) ans=Mid,L=Mid+eps;
else R=Mid-eps;
}
printf("%.0lf\n",ans);
}
return ;
}
【D：HihoCoder 1504 骑士游历】
基础的矩阵乘法。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=;
#define ll long long
const int Mod=1e9+;
int x[]={,,-,-,,,-,-};
int y[]={,-,,-,,-,,-};
struct mat
{
ll M[maxn][maxn];
mat() { memset(M,,sizeof(M)); }
mat friend operator *(mat a,mat b)
{
mat res;
for(int k=;k<=;k++)
for(int i=;i<=;i++)
for(int j=;j<=;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=;i<=;i++) res.M[i][i]=;
while(x){
if(x&) res=a*res; a=a*a; x/=;
} return res;
}
}; mat base;
void prepare()
{
for(int i=;i<=;i++)
for(int j=;j<=;j++)
for(int k=;k<;k++)
if(i+x[k]>=&&i+x[k]<=&&j+y[k]>=&&j+y[k]<=)
base.M[(i-)*+j][(i+x[k]-)*+j+y[k]]=;
}
int main()
{
int N,R,C,ans=;
scanf("%d%d%d",&N,&R,&C);
prepare();
base=base^N;
for(int i=;i<=;i++) ans=(ans+base.M[(R-)*+C][i])%Mod;
printf("%d\n",ans);
return ;
}
【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[][][];
bitset<>s[];
int a[],N;
int read()
{
char c=getchar(); int res;
while(c>''||c<'') c=getchar();
for(res=;c>=''&&c<='';c=getchar()) res=(res<<)+(res<<)+c-'';
return res;
}
void solve(int x,int y,int z)
{
for(int i=;i<=;i++) s[i].reset();
s[][]=;
for(int i=;i<=N;i++){
if(i==x||i==y||i==z||a[i]>) continue;
for(int j=;j>=;j--) s[j]|=s[j-]<<a[i];
}
if(s[][]==) 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=;i<=N;i++)
a[i]=read(); for(int i=;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[];
x[]=read(); x[]=read(); x[]=read();
sort(x,x+);
if(ans[x[]][x[]][x[]]) puts("Yes");
else puts("No");
}
}
return ;
}
总结：提交前，一定要分析的东西，数据范围；算法效率是否妥当。
然后，多刷题，如果可以在HDU上面刷500题，或者BZOJ上面刷100道题，稳稳地拿省一（对弱省来说）。
当然，要学会挑战难题，突破自己。
