关键词：
北京中关村；海淀黄庄；北京大学；清华大学。少儿编程；中小学编程；信息学竞赛；计算机竞赛；NOIP竞赛；CSP-J/S竞赛；NOI竞赛。2001年、提高组、复赛，第7届。
A、试题类型：
方程问题。
B、算法模型：
推理证明。
C、试题说明：
方程f(x)=0，若存在2个数x1和x2，且x1 < x2，f(x1)*f(x2) < 0，则在(x1，x2)之间一定有一个根。
#include<iostream>
#include<cmath>
#include<iomanip>
using namespace std;
int main()
{
double a,b,c,d;
cin>>a>>b>>c>>d;
if(a<0)
{
a=-a;
b=-b;
c=-c;
d=-d;
}
double x1=(-2*b-sqrt(4*b*b-12*a*c))/(6*a);
double x2=(-2*b+sqrt(4*b*b-12*a*c))/(6*a);
double mid=(-100+x1)/2;
double low=-100,high=x1;
while(abs(a*mid*mid*mid+b*mid*mid+c*mid+d)>=0.001)
{
if((a*mid*mid*mid+b*mid*mid+c*mid+d)<0)
{
low=mid;
mid=(low+high)/2;
}
else
{
high=mid;
mid=(low+high)/2;
}
}
cout<<fixed<<setprecision(2)<<mid<<" ";
mid=(x1+x2)/2;
low=x1,high=x2;
while(abs(a*mid*mid*mid+b*mid*mid+c*mid+d)>=0.001)
{
if((a*mid*mid*mid+b*mid*mid+c*mid+d)>0)
{
low=mid;
mid=(low+high)/2;
}
else
{
high=mid;
mid=(low+high)/2;
}
}
cout<<fixed<<setprecision(2)<<mid<<" ";
mid=(x2+100)/2;
low=x2,high=100;
while(abs(a*mid*mid*mid+b*mid*mid+c*mid+d)>=0.001)
{
if((a*mid*mid*mid+b*mid*mid+c*mid+d)<0)
{
low=mid;
mid=(low+high)/2;
}
else
{
high=mid;
mid=(low+high)/2;
}
}
cout<<fixed<<setprecision(2)<<mid;
}
A、试题类型：
方程推导问题。
B、算法模型：
推导分类。
C、试题说明：
f(1,b)+f(2,b)+..f(a-1,b) =g(a-1,b)
推导得到：
g(a,b)=f(1,b)+...f(i,b)＋f(a,b)=g(a-1,b)+g(a,b-a)(1<=i<=a-1)
当b<a时，根据g(a,b)的含义，g(a,b-a)无意义。
当a=1时，显然 g(1,b)=1.
于是，根据新模型求解得到下列递推公式：
g (a,b)= g (a-1,b） b<a
g (a-1,b)+g(a,b-a) b>=a.
g(1,b)=1.
最后g (k,n-k)即为所求。
#include<iostream>
#include<cstring>
using namespace std;
int g[7][201];
int main()
{
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
int n,k,i,j;
while(cin>>n>>k)
{
memset(g,0,sizeof(g));
for(j=0;j<=n;j++)
g[1][j]=1;
for(i=2;i<=k;i++)
for(j=0;j<=n-k;j++)
if(j>=i)
g[i][j]=g[i-1][j]+g[i][j-i];
else
g[i][j]=g[i-1][j];
cout<<g[k][n-k]<<endl;
}
return 0;
}
A、试题类型：
动态规划。
B、算法模型：
STL。
C、试题说明：
字符串应用。
#include<bits/stdc++.h>
using namespace std;
string s;
string a[10];
int sum[210][210];
int f[210][210];
int n,m;
int p,k;
bool check(int l,int r)
{
string x=s.substr(l,r-l+1);
for(int i=1;i<=n;i++)
{
if(x.find(a[i])==0) return true;
}
return false;
}
void work()
{
//f[i][j]的意思是前i个字母分成j份所形成的单词数；
for(int i=1;i<=k;i++)
{
f[i][i]=f[i-1][i-1]+sum[i][i];
}
for(int i=1;i<=m;i++)
{
f[i][1]=sum[1][i];
}
for(int i=1;i<=m;i++)
{
for(int j=1;j<=k&&j<i;j++)
{
for(int l=j;l<i;l++)
{
f[i][j]=max(f[i][j],f[l][j-1]+sum[l+1][i]);//动态规划的核心;
}
}
}
cout<<f[m][k]<<endl;
}
int main()
{
cin>>p>>k;
s="0";
string str;
for(int i=1;i<=p;i++)
{
cin>>str;
s+=str;
}
cin>>n;
m=s.length()-1;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=m;i>=1;i--)
{
for(int j=i;j>=1;j--)
{
sum[j][i]=sum[j+1][i];
if(check(j,i)) sum[j][i]++;//预处理，因为每一份的第一个字母只能出现在一个单词里面，
//从后往前的时候判断以每个字母为首的部分到后面的单词数，以这个字母为首可以构成单词那么sum[j][i]=sum[j+1][i]+1;
//否则sum[j][i]=sum[j+1][i];这里处理完了以后，就能确定任意部分之间的单词数
}
}
work();
return 0;
}
A、试题类型：
最短路径问题。
B、算法模型：
列方程推导。
C、试题说明：
无。
#include<bits/stdc++.h>
#define maxn 401
#define maxm 160001
#define bh(x,y) ((x-1)*4+y)//将第x个城市的第y个机场直接用四进制的方法转换成十进制（其实就是强制编号）
using namespace std;
int n,s,t,a,b;
struct zj
{
int x,y;
};
zj f[maxn][4];//存边，变量实在太多了，只好用f，一不小心重名了调死我了
int c[maxn];
int head[maxn],k,nex[maxm],to[maxm];
double v[maxm];
double d[maxm];
void add(int x,int y,double z)
{//链式前向星
to[k]=y;
v[k]=z;
nex[k]=head[x];
head[x]=k++;
}
int main()
{
cin>>n;
while(n--)
{
k=0;
memset(head,-1,sizeof(head));
//链表清空
cin>>s>>t>>a>>b;
for(int i=1;i<=s;i++)
{
double x1,y1,x2,y2,x3,y3,maxx=0;
int x,y;
for(int j=0;j<3;j++)
cin>>f[i][j].x>>f[i][j].y;
cin>>c[i];
/*****************求第四条边****************/
for(int j=0;j<3-1;j++)
{
for(int l=j+1;l<3;l++)
{
x=f[i][j].x-f[i][l].x;
y=f[i][j].y-f[i][l].y;
if(sqrt(double(x*x)+double(y*y))>maxx)
{//找距离最长的两个点
x1=f[i][j].x;
y1=f[i][j].y;
x2=f[i][l].x;
y2=f[i][l].y;
x3=f[i][3-j-l].x;
y3=f[i][3-j-l].y;
maxx=sqrt(double(x*x)+double(y*y));
}
}
}
f[i][3].x=x1+x2-x3;
f[i][3].y=y1+y2-y3;//套公式
/**************************************************/
}
/*****************建边******************************************************/
for(int i=1;i<=s;i++)
{
for(int ii=1;ii<=s;ii++)
{
for(int j=0;j<4;j++)
{
for(int jj=0;jj<4;jj++)
{
if(i==ii&&j==jj)
continue;
double p=sqrt(double((f[i][j].x-f[ii][jj].x)*(f[i][j].x-f[ii][jj].x)+(f[i][j].y-f[ii][jj].y)*(f[i][j].y-f[ii][jj].y)));
if(i!=ii)
add(bh(i,j),bh(ii,jj),p*t);
else
add(bh(i,j),bh(ii,jj),p*c[i]);
}
}
}
}
/**************初始化*********************************************************/
queue<int> q;
for(int i=0;i<s*4;i++)
d[i]=0x3fffffff;
for(int i=0;i<4;i++)
{
q.push(bh(a,i));
d[bh(a,i)]=0;
}
/*************SPFA**********************************************************/
while(!q.empty())
{
int x=q.front();
q.pop();
for(int pos=head[x];pos!=-1;pos=nex[pos])
{
if(d[to[pos]]>d[x]+v[pos])
{
d[to[pos]]=d[x]+v[pos];
q.push(to[pos]);
}
}
}
/****************找答案*******************************************************/
double ans=0x3fffffff;
for(int i=0;i<4;i++)
if(d[bh(b,i)]<ans)
ans=d[bh(b,i)];
printf("%0.1lf",ans);
}
return 0;
}
IT航班支持----中小学编程比赛汇总：
第一部分：国内比赛(IT航班支持)
1、软件能力认证(CSP-JS)
2、全国青少年信息学奥林匹克联赛(NOIP)
3、全国青少年信息学奥林匹克竞赛(NOI)
4、中国青少年………………………
5、………………………创新挑战赛
6、全国青少年………………………
7、………………………
8、 恩欧希教育信息化发明创新奖
9、世界机器人大赛(WRC)
10、………………………大赛
11、少………………………智能教育成果展示大赛
12、“明天小小科学家”奖励活动
13、………………………
14、………………………
15、国际信息学………………………
16、………………………
第二部分：国际比赛(IT航班支持)
17、………………………
18、国际………………………
19、………………………
20、美国信息学………………………
21、加拿大………………………
22、官方邀请赛 (CCO)
23、国际计算思维………………………
24、美国计算机………………………
25、澳大利亚………………………
第三部分：企业比赛(IT航班支持)
26、微软MTA
27、………………………挑战赛
28、………………………科学奖
29、………………………学奖
30、………………………创新挑战赛
31、………………………挑战赛
32、………………………芯计算机表演赛
33、………………………大赛
第四部分：Scratch相关竞赛(IT航班支持)
34、全国中小学生电脑制作大赛
35、………………………
36、………………………
37、………………………
第五部分：其它(IT航班支持)
38、NOI夏令营
39、NOI冬令营(NOIWC)
40、全国青少年………………………
41、国际青少年………………………
联系方式：
A、官方网址：
B、微信公众号：
添加微信，获取资料。
关注公众号，获取动态。
