关键词：
北京中关村；海淀黄庄；北京大学；清华大学。少儿编程；中小学编程；信息学竞赛；计算机竞赛；NOIP竞赛；CSP-J/S竞赛；NOI竞赛。2002年、提高组、复赛，第8届。
A、试题类型：
基本算法考察。
B、算法模型：
贪心算法。
C、试题说明：
先将所有的牌都统计起来再判断每一堆牌到底要几张牌（就是求平均数）。
从第一组开始只要这一组的牌数不等于这个平均数。
就可以将这一堆牌减去平均数。
不论正负，正负不影响最优解。
将差值移交给下一组处理，同时步数加一。
最后将步数输出就是答案。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,card[105],ave,step;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d",&card[i]),ave+=card[i];
ave=ave/n;
for(int i=1;i<=n;++i)
{
if(ave==card[i]) continue;
card[i+1]+=card[i]-ave,step++;
}
printf("%d\n",step);
return 0;
}
A、试题类型：
搜索问题。
B、算法模型：
BFS。
C、试题说明：
隐式图搜索，注意的是转移的时候状态u中可能有多处与A$匹配，也就是一个A$可以拓展多个点。
#include<iostream>
#include<fstream>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<map>
using namespace std;
const int maxn = 1000+10;
struct Node
{
string s;
int d;
};
string block[maxn];
map<string,int> X;
string a[7],b[7];
string A,B;
int n=0;
int pos[maxn];
void make_pos(string s,string t)
{
pos[0]=1; int lens=s.size(),lent=t.size();
for(int i=0;i<=lens-lent;i++)
if(s.substr(i,lent)==t)
pos[pos[0]++]=i;
}
void bfs()
{
queue<Node> q;
q.push((Node){A,0});
X[A]=1;
while(!q.empty())
{
Node u=q.front(); q.pop();
if(u.s==B) { cout<<u.d; return ;
}
for(int r=0;r<n;r++)
{
make_pos(u.s,a[r]);
for(int i=1;i<pos[0];i++)
{
string s=u.s;
s.replace(pos[i],a[r].size(),b[r]);
if(!X.count(s) && u.d+1<=10)
{
X[s]=1;
q.push((Node){s,u.d+1});
}
}
}
}
cout<<"NO ANSWER!";
}
int main()
{
ios::sync_with_stdio(false);
freopen("NOIPG2.in","r",stdin);
freopen("NOIPG2.out","w",stdout);
cin>>A>>B;
while(cin>>a[n]>>b[n])
n++;
bfs();
return 0;
}
A、试题类型：
送分问题。
B、算法模型：
物理问题。
C、试题说明：
物理与逻辑的结合。
#include<bits/stdc++.h>
using namespace std;
double h,s,v,l,k;
int n;
double t1,t2;
int s1,s2;
int main()
{
cin>>h>>s>>v>>l>>k>>n;
t1=sqrt((h-k)/5);
t2=sqrt(h/5);
s1=s-t1*v+l;
s2=s-t2*v;
s1=min(s1,n);//边界
s2=max(s2,0);//边界
printf("%d",s1-s2);
return 0;
}
A、试题类型：
空间几何。
B、算法模型：
搜索。剪枝方法应用。
C、试题说明：
将读入的坐标按x和y从小到大排序，然后搜索将连续的i个点分在一起，期间判断问题是否可行，以及进行各种小优化。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0' || ch>'9')
{
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
struct point
{
int x,y;
}a[60];
int cmp(point a,point b)
{
if(a.x==b.x)
return a.y<b.y;
return a.x<b.x;
}
struct block
{
int x1,y1,x2,y2;
}b[5];
int n,k;
int ans=1e9;
void DFS(int pos,int cnt,int smm)
{
if(pos>n)
{
ans=min(ans,smm);
return;
}
if(cnt>k)
return;
int i,j;
b[cnt].x1=a[pos].x;
b[cnt].x2=a[pos].x;
b[cnt].y1=a[pos].y;
b[cnt].y2=a[pos].y;
for(i=pos;i<=n;i++)
{
b[cnt].y2=max(b[cnt].y2,a[i].y);
b[cnt].x2=max(b[cnt].x2,a[i].x);
b[cnt].x1=min(b[cnt].x1,a[i].x);
b[cnt].y1=min(b[cnt].y1,a[i].y);
for(j=1;j<cnt;j++)
{
if(b[cnt].x1<=b[j].x2 && b[cnt].y1<=b[j].y2)
return;
}
if(i<n && cnt==k)
continue;
DFS(i+1,cnt+1,smm+(b[cnt].x2-b[cnt].x1)*(b[cnt].y2-b[cnt].y1));
}
return;
}
int main()
{
n=read();k=read();
int i,j;
for(i=1;i<=n;i++)
{
a[i].y=read();a[i].x=read();
}
sort(a+1,a+n+1,cmp);
memset(b,-1,sizeof b);
DFS(1,1,0);
printf("%d\n",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、微信公众号：
添加微信，获取资料。
关注公众号，获取动态。
