关键词：
北京中关村；海淀黄庄；北京大学；清华大学。少儿编程；中小学编程；信息学竞赛；计算机竞赛；NOIP竞赛；CSP-J/S竞赛；NOI竞赛。2004年、提高组、复赛，第10届。
A、试题类型：
送分题。
B、算法模型：
模拟问题。
C、试题说明：
无。
#include<cstdio>
using namespace std;
int main()
{
//freopen("1.in","r",stdin);
int i,j,k,x=0,y=0;
for(i=1;i<=12;i++)
{
scanf("%d",&j);
x+=300;
if(x<j){printf("-%d\n",i);return 0;}
x-=j;k=x%100;y+=x-k;x=k;
}
printf("%d\n",x+y*120/100);
return 0;
}
A、试题类型：
基本算法。
B、算法模型：
贪心+堆应用。
C、试题说明：
贪心策略：每次都取出最小的两堆果子来合并，直到最后只剩一堆。
最小的两堆果子用堆来维护。
时间复杂度是O（n * log n）。
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 10005
using namespace std;
priority_queue<int>q;
int main()
{
int n,i,x,t,ans=0;
scanf("%d",&n);
for(i=1;i<=n;++i)
{
scanf("%d",&x);
q.push(-x);
}
while(--n)
{
t=0;
t-=q.top();q.pop();
t-=q.top();q.pop();
ans+=t;
q.push(-t);
}
printf("%d",ans);
return 0;
}
A、试题类型：
空间想象题。
B、算法模型：
多数组连用。
C、试题说明：
求出先上升后递减的子序列，要求到达最长。
求出先上升到这个点，再下降的子序。 求出所有点的情况，比较哪个点的长度最长。
写代码时枚举所有的点，求子序时会经过该点两次，长度要减掉1。
#include<iostream>
using namespace std;
int n;
int a[105];
int dp1[105],dp2[105];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<=n;i++)
{
dp1[i] = 1;
for(int j=1;j<i;j++)
{
if(a[i] > a[j])
{
dp1[i] = max(dp1[i],dp1[j]+1);
}
}
}
for(int i=n;i>=1;i--)
{
dp2[i] = 1;
for(int j=i+1;j<=n;j++)
{
if(a[i] > a[j])
{
dp2[i] = max(dp2[i],dp2[j]+1);
}
}
}
int ans =0;
for(int i=1;i<=n;i++)
{
ans = max(ans,dp1[i]+dp2[i]-1);
}
cout<<n-ans;
return 0;
}
A、试题类型：
逻辑推导。
B、算法模型：
传送门。
C、试题说明：
首先判断可行性。如果最高位的两个数加起来大于N 则回溯。注意进位的情况。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int N=30;
char s1[N],s2[N],s3[N];int a[N],b[N],c[N];
int n;bool v[N];int t,p[N],num[N];
bool gj()
{
int x=0;
for(int i=n;i;i--)
{
int A=num[a[i]],B=num[b[i]],C=num[c[i]];
if((A+B+x)%n!=C)return 0;
x=(A+B+x)/n;
}
return 1;
}
void w(int x)
{
if(!v[x])
{
v[x]=1;
p[++t]=x;
}
}
bool jz()
{
if(num[a[1]]+num[b[1]]>=n)
return 1;
for(int i=n;i;i--)
{
int A=num[a[i]],B=num[b[i]],C=num[c[i]];
if(A==-1||B==-1||C==-1)continue;
if((A+B)%n-C&&(A+B+1)%n-C)return 1;
}
return 0;
}
void dfs(int now)
{
if(jz())
return;
if(now==n+1)
{
if(gj())
{
for(int i=1;i<=n;i++)printf("%d ",num[i]);puts("");
exit(0);
}
return ;
}
for(int i=n-1;i>=0;i--)
{
if(!v[i])
{
num[p[now]]=i;//现将低位填了，以便jz。
v[i]=1;
dfs(now+1);
v[i]=0;
num[p[now]]=-1;
}
}
}
int main()
{
scanf("%d",&n);t=0;memset(v,false,sizeof(v));memset(num,-1,sizeof(num));
scanf("%s%s%s",s1+1,s2+1,s3+1);
for(int i=1;i<=n;i++)
{
a[i]=s1[i]-'A'+1;
b[i]=s2[i]-'A'+1;
c[i]=s3[i]-'A'+1;
}
for(int i=n;i;i--)//这样for是有意义的，否则会超时。
{
w(a[i]);w(b[i]);w(c[i]);
}
memset(v,false,sizeof(v));
dfs(1);
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、微信公众号：
添加微信，获取资料。
关注公众号，获取动态。
