关键词：
北京中关村；海淀黄庄；北京大学；清华大学。少儿编程；中小学编程；信息学竞赛；计算机竞赛；NOIP竞赛；CSP-J/S竞赛；NOI竞赛。2005年、提高组、复赛，第11届。
A、试题类型：
数学算法。
B、算法模型：
STL深入。
C、试题说明：
sort是个不稳定的排序。
stable_sort是稳定的排序。
#include <bits/stdc++.h>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
struct node
{
char name[1000];
int average;
int class_grade;
bool student_leader;
bool student_west;
int paper;
int scholarship;
} p[105];
ll n, sum;
inline bool cmp(node a, node b)
{
return a.scholarship > b.scholarship;
}
int main()
{
cin >> n;
for (int i = 0; i < n; ++i)
{
cin >> p[i].name;
cin >> p[i].average;
cin >> p[i].class_grade;
string str;
cin >> str;
if (str[0] == 'Y')
{
p[i].student_leader = true;
}
else
{
p[i].student_leader = false;
}
cin >> str;
if (str[0] == 'Y')
{
p[i].student_west = true;
}
else
{
p[i].student_west = false;
}
cin >> p[i].paper;
if (p[i].average > 80 && p[i].paper >= 1)
{
p[i].scholarship += 8000;
}
if (p[i].average > 85 && p[i].class_grade > 80)
{
p[i].scholarship += 4000;
}
if (p[i].average > 90)
{
p[i].scholarship += 2000;
}
if (p[i].average > 85 && p[i].student_west)
{
p[i].scholarship += 1000;
}
if (p[i].class_grade > 80 && p[i].student_leader)
{
p[i].scholarship += 850;
}
sum += p[i].scholarship;
}
stable_sort(p, p + n, cmp);
cout << p[0].name << endl;
cout << p[0].scholarship << endl;
cout << sum << endl;
return 0;
}
A、试题类型：
空间想象。
B、算法模型：
离散化与动态规划应用。
C、试题说明：
基本思路：
对石头坐标排序；离散化并对石头对应位置打标记；
详细解释：
对石头坐标排序；题目没说读入时是有序的，所以要先排序，便于离散化。注意：读入
是直接保存坐标。离散化并对石头对应位置打标记。
为什么要离散化？
因为木桥的长度太大，没法用它去建立数组（就是dp要用），所以需要离散化。
怎么离散化？
当相邻的两块石头之间的距离过大时，有些距离是多余的，也就是说需要将这一段距离减掉。
距离有多长呢？2520
是1到10这10个数的最小公倍数。
跳的范围就是1到10的子区间，所以任意挑一个跳的距离，就可以一个石子不占的跳过去，并且对后面不会产生影响，所以这就是无用距离，减去即可。
注意，如果差距正好是2520的整数倍，那就要少减去一个2520，为了防止两块石头重叠。
打标记：
在另一个数组stone[]对应的处理后的坐标位置设置为1，代表有一个石头。
动态规划：
用f[i]表示到达i位置时，所要踩到的石头的最小数。
只需要枚举跳的范围。
状态转移方程应用。
#include<bits/stdc++.h>
using namespace std;
int minn,maxx,m,l,i,j,f[300000],a[1000],sum,k=0;
bool stone[300000];
int main()
{
scanf("%d%d%d%d",&l,&minn,&maxx,&m);
for (i=1;i<=m;++i)
{
scanf("%d",&a[i]);
}
sort(a+1,a+m+1);
for (i=1;i<=m;++i)
{
if (a[i]-a[i-1]>2520)
{
k+=(a[i]-a[i-1])/2520;
if((a[i]-a[i-1])%2520==0)
{
k--;
}
}
stone[a[i]-k*2520]=1;
}
memset(f,0x3f,sizeof(f));
f[0]=0;
for (i=1;i<=252000;++i)
{
for (j=maxx;j>=minn;--j)
{
if (i-j>=0)
{
f[i]=min(f[i-j]+stone[i],f[i]);
}
}
}
printf("%d",f[252000]);
return 0;
}
A、试题类型：
基本算法。
B、算法模型：
朴素算法。
C、试题说明：
首先，判断无解的情况：它相邻的不与它相邻。
然后，构造出合法的数列，因为第一位左边有两种选择，且构造出的环不等价，所以要做两次。
然后，考虑对于构造出的数列(断环为链)，如何计算它与原数列的差别，即答案。
这是这道题最难的地方：如何 O(n)O(n) 的求出两个环的不同之处。
朴素算法：O(n2)O(n2)，显然无法接受。
因为环无论怎么旋转，两个人的相对位置是不会变的，于是，可以对于每一个位置求出的数列与原数列的差 x，表示数列要旋转 x 个位置，此位置才会与原数列重合。
然后条统计出每个 x 出现的次数，n−max(x)n−max(x) 就是答案。
#include <bits/stdc++.h>
using namespace std;
#define db double
#define ll long long
#define RG register
inline int gi()
{
RG int ret; RG bool flag; RG char ch;
ret=0, flag=true, ch=getchar();
while (ch < '0' || ch > '9')
ch == '-' ? flag=false : 0, ch=getchar();
while (ch >= '0' && ch <= '9')
ret=(ret<<3)+(ret<<1)+ch-'0', ch=getchar();
return flag ? ret : -ret;
}
const db pi = acos(-1.0);
const int N = 5e4+5, inf = 1<<30;
int n,ans,f[N],s[N],pos[N],cnt[N];
bool vis[N];
inline void cal()
{
RG int i;
for (i=1; i<=n; ++i)
cnt[(pos[i]-i+n)%n]++;
for (i=0; i<n; ++i)
ans=max(ans,cnt[i]), cnt[i]=0;
}
inline void dfs(RG int o,RG int dep)
{
pos[dep]=o;
if (dep == n)
return cal();
if (!vis[f[o]])
vis[f[o]]=true, dfs(f[o],dep+1), vis[f[o]]=false;
if (!vis[s[o]])
vis[s[o]]=true, dfs(s[o],dep+1), vis[s[o]]=false;
}
int main()
{
freopen("fire.in","r",stdin);
freopen("fire.out","w",stdout);
RG int i;
n=gi();
for (i=1; i<=n; ++i)
f[i]=gi(), s[i]=gi();
for (i=1; i<=n; ++i)
if ((f[f[i]] != i && s[f[i]] != i) || (f[s[i]] != i && s[s[i]] != i))
return puts("-1"), 0;
vis[1]=true;
dfs(1,1);
printf("%d\n",n-ans);
return 0;
}
A、试题类型：
经典表达式。
B、算法模型：
输入少得分就可以。
C、试题说明：
输入有空格 还要考虑括号不匹配的情况。
此题的做法是将字母a设为1，2，3，4，5算出原式的值。
然后在将下面的表达式用a的1，2，3，4，5算出进行比较。
这样就变成了一般的表达式求值题。
由于算出数据可能很大 把算出的值每一步都取模。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
//小于 -->计算 大于-->入栈
char r[9][9] = {
{' ','+','-','*','/','(',')','^','='},
{'+','>','>','<','<','<','>','<','>'},
{'-','>','>','<','<','<','>','<','>'},
{'*','>','>','>','>','<','>','<','>'},
{'/','>','>','>','>','<','>','<','>'},
{'(','<','<','<','<','<','=','<',' '},
{')','>','>','>','>',' ','>','>','>'},
{'^','>','>','>','>','<','>','>','>'},
{'=','<','<','<','<','<',' ','<','='},
};
char ss(char x,char y)
{
int a,b;
switch(x)
{
case '+':
a=1;
break;
case '-':
a=2;
break;
case '*':
a=3;
break;
case '/':
a=4;
break;
case '(':
a=5;
break;
case ')':
a=6;
break;
case '^':
a=7;
break;
case '=':
a=8;
break;
}
switch(y)
{
case '+':
b=1;
break;
case '-':
b=2;
break;
case '*':
b=3;
break;
case '/':
b=4;
break;
case '(':
b=5;
break;
case ')':
b=6;
break;
case '^':
b=7;
break;
case '=':
b=8;
break;
}
return r[a][b];
}
int ct(int x,int y,char ch)
{
switch(ch)
{
case '+':
return (x+y)%10007;
break;
case '-':
return (x-y)%10007;
break;
case '*':
return (x*y)%10007;
break;
case '/':
return (x/y)%10007;
break;
case '^':
if(x==0) return 0;
if(y==0) return 1;
int c=1;
for(int i=1;i<=y;i++){
c*=x;
c%=10007;
//由于乘方可能很大 所以每部都求余 不能使用pow了
}
return c;
break;
}
}
int opd[100],topd,topr=1,a,b,c;
char opr[100],ch,cch;
char s[55];
int ans[10];
int deal(int i)
{//因为要处理多次 将过程化为函数 i即a的值
int t=0;
topr=1,topd=0;
opr[1]='=';
ch=s[t++];
int flag=0;
while(!(ch=='='&&opr[topr]=='='))
{
if(ch>='0'&&ch<='9'&&flag==0)
{
opd[++topd]=ch-48;
ch=s[t++];
flag=1;
}
while(ch>='0'&&ch<='9'&&flag==1)
{
int x=opd[topd--];
x=x*10+ch-48;
opd[++topd]=x;
ch=s[t++];
}
flag=0;
if(ch=='a')
{
opd[++topd]=i;
ch=s[t++];
}
//这里加一个判断 如果不加 输入单个数字的时候会卡死（等号不进行判断）：
if(ch=='='&&opr[topr]=='=')
return opd[1];
else if(!(ch>='0'&&ch<='9'))
switch(ss(opr[topr],ch))
{
case '<':
opr[++topr]=ch;
ch=s[t++];
break;
case '>':
a=opd[topd--];
b=opd[topd--];
cch=opr[topr--];
c=ct(b,a,cch);
opd[++topd]=c;
break;
case '=':
topr--;
ch=s[t++];
break;
}
}
return opd[1];
}
char temp[55];
void makeinput()
{//此函数是为了读入 过滤其空格
gets(temp);
int p=0;
int len=strlen(temp);
for(int i=0;i<len;i++)
{
if(temp[i]==' ') continue;
s[p++]=temp[i];
}
s[p]='=';
s[p+1]='\0';
}
int main()
{
//freopen("equal8.in","r",stdin);
//freopen("answer.txt","w",stdout);
makeinput();
for(int i=1;i<=5;i++)
{
ans[i]=deal(i);
}
int n;
int pd=0;
scanf("%d",&n);
getchar();//这里的getchar很重要
for(int i=1;i<=n;i++)
{
pd=0;
makeinput();
for(int j=1;j<=5;j++)
{
int k=deal(j);
//cout<<k<<endl;
if(k!=ans[j])
{
pd=1;
break;
}
}
if(pd==1)
continue;
else if(pd==0){
printf("%c",i+64);
}
}
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、微信公众号：
添加微信，获取资料。
关注公众号，获取动态。
