关键词：
北京中关村；海淀黄庄；北京大学；清华大学。少儿编程；中小学编程；信息学竞赛；计算机竞赛；NOIP竞赛；CSP-J/S竞赛；NOI竞赛。2003年、提高组、复赛，第9届。
A、试题类型：
图论应用。
B、算法模型：
队列，朴素拓扑排序。
C、试题说明：
从输入点开始传递C值，如果C为正则可以传递。注意到只有当一个结点的所有入度全部传递完成之后这个结点才可以进行传递，而且结点传递之前需要检查C的正负。
用一个队列维护入度已经求完的结点，考虑完成后出队，对于考虑结点而言，对所有出度的in减1，同时判断是否可以入队。
与朴素的拓扑排序有些类似。
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
const int maxn = 300;
struct Edge
{
int v,w;
};
vector<Edge> edges;
queue<int> q;
vector<int> G[maxn];
int in[maxn],out[maxn];
int c[maxn],u[maxn];
int n,m;
inline void AddEdge(int u,int v,int w)
{
edges.push_back((Edge){v,w});
int d=edges.size();
G[u].push_back(d-1);
out[u]++; in[v]++;
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=0;i<n;i++)
{ //标号从0开始
cin>>c[i]>>u[i];
if(c[i]>0) q.push(i);
if(c[i]==0) c[i]-=u[i]; //先减上
}
for(int i=0;i<m;i++)
{
int u,v,w; cin>>u>>v>>w;
u--; v--;
AddEdge(u,v,w);
}
//q为考虑队列 用队列中所有入点已经求完的点更新相连的点
while(!q.empty())
{
int u=q.front();q.pop();
if(c[u]>0)
{ //只有当c>0时才能继续向后传递
for(int i=0;i<G[u].size();i++)
{
int v=edges[G[u][i]].v,w=edges[G[u][i]].w;
c[v]+= w*c[u];
if(!(--in[v])) q.push(v); //in==0但c不确定
}
}
}
bool f=true;
for(int i=0;i<n;i++) if(!out[i] && c[i]>0)
{ //考虑输出点
cout<<i+1<<" "<<c[i]<<"\n"; //标号
f=false;
}
if(f)
cout<<"NULL";
return 0;
}
A、试题类型：
逻辑推理。
B、算法模型：
典型时间复杂度。
C、试题说明：
时间复杂度是O(m*p*2^n),若取 m,n,p最大，则就有了 2097152000，会超时，但幸运的是 该题实际数据范围 n<=8,m<=10,p<=10;
考场上能拿分就拿分，不要牛逼自大。
#include<iostream>
#include<string.h>
#include<fstream>
using namespace std;
int n,m,p,guilty=0;
string tool[5];
bool real[22]={0};
struct
{
string name;
string say[101];
int n;
}a[22];
void Init()
{
cin>>n>>m>>p;
tool[0]="I am guilty.";
tool[1]="I am not guilty.";
tool[2]="is guilty.";
tool[3]="is not guilty.";
tool[4]="Today is";
m=n-m;
for(int i=1;i<=n;++i)
cin>>a[i].name,a[i].n=0;
string sa,na;
getline(cin,sa,'\n');
for(int i=1;i<=p;++i)
{
getline(cin,sa,'\n');
na=sa;
int l=0;
while(sa[l]!=':') l++;
na.erase(l,sa.size()-l);
sa.erase(0,l+2);
for(int j=1;j<=n;++j)
if(a[j].name==na)
{
a[j].n++;
a[j].say[a[j].n]=sa;
break;
}
}
}
int check()
{
string day="0";
for(int i=1;i<=n;++i)
{
if(real[i])
{
for(int j=1;j<=a[i].n;++j)
{
string say=a[i].say[j];
if(say.size()<11)
continue;
if(say==tool[0]&&guilty!=i)
return 0;
if(say==tool[1]&&guilty==i)
return 0;
if(say==tool[0]||say==tool[1])
continue;
string s=say;
int k=say.size()-1,l=tool[2].size()-1;
while(say[k]==tool[2][l]&&l>=0)
{
--k;
--l;
}
if(l<0)
{
s.erase(k,s.size()-k);
if(s!=a[guilty].name)
return 0;
}
k=say.size()-1,l=tool[3].size()-1;
while(say[k]==tool[3][l]&&l>=0)
{
--k;
--l;
}
if(l<0)
{
s.erase(k,s.size()-k);
if(s==a[guilty].name)
return 0;
}
s=say;
s.erase(8,s.size()-8);
if(s==tool[4])
{
say.erase(0,9);
if(day!="0"&&day!=say)
return 0;
day=say;
}
}
}
else if(!real[i])
{
for(int j=1;j<=a[i].n;++j)
{
string say=a[i].say[j];
if(say.size()<11)
continue;
if(say==tool[0]&&guilty==i)
return 0;
if(say==tool[1]&&guilty!=i)
return 0;
if(say==tool[0]||say==tool[1])
continue;
string s=say;
int k=say.size()-1,l=tool[2].size()-1;
while(say[k]==tool[2][l]&&l>=0)
{
--k;--l;
}
if(l<0)
{
s.erase(k,s.size()-k);
if(s==a[guilty].name)
return 0;
}
k=say.size()-1,l=tool[3].size()-1;
while(say[k]==tool[3][l]&&l>=0)
{
--k;
--l;
}
if(l<0)
{
s.erase(k,s.size()-k);
if(s!=a[guilty].name)
return 0;
}
s=say;
s.erase(8,s.size()-8);
if(s==tool[4])
{
say.erase(0,9);
if(day==say)
return 0;
}
}
}
return 1;
}
}
int Dfs(int d,int tot)
{
if(d>n||tot>m||n-d<m-tot)
return 0;
if(tot==m&&d==n)
{
if(check())
return 1;
return 0;
}
if(Dfs(d+1,tot))
return 1;
real[d+1]=1;
if(Dfs(d+1,tot+1))
return 1;
real[d+1]=0;
return 0;
}
int main()
{
Init();
int ans=0,sum=0;
for(int i=1;i<=n;++i)
{
guilty=i;
if(Dfs(0,0))
{sum++;ans=i;}
}
if(sum==0)
{
cout<<"Impossible"<<endl;return 0;
}
if(sum>=2)
{
cout<<"Cannot Determine"<<endl;return 0;
}
cout<<a[ans].name<<endl;
return 0;
}
A、试题类型：
基本数据结构。
B、算法模型：
中序遍历。
C、试题说明：
中序遍历的应用
#include <bits/stdc++.h>
using namespace std;
const int Max=35;
int n,m;
int f[Max][Max],root[Max][Max],num[Max];
inline void print(int l,int r)
{
cout<<root[l][r]<<" ";
if(root[l][r]>l) print(l,root[l][r]-1);
if(root[l][r]<r) print(root[l][r]+1,r);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&num[i]);
f[i][i]=num[i],root[i][i]=i,f[i][i-1]=f[i+1][i]=1;
}
for(int i=n;i>=1;i--)
for(int j=i+1;j<=n;j++)
for(int k=i;k<=j;k++)
{
if(f[i][k-1]*f[k+1][j]+f[k][k] <= f[i][j]) continue;
f[i][j]=max(f[i][j],f[i][k-1]*f[k+1][j]+f[k][k]);
root[i][j]=k;
}
cout<<f[1][n]<<"\n";
print(1,n);
return 0;
}
A、试题类型：
医学类问题。
B、算法模型：
STL与算法应用。
C、试题说明：
现实生活与逻辑的结合。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define maxn 305
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;
}
int n,p,m,a[maxn][maxn],b[maxn][maxn],fa[maxn],dep[maxn],num[maxn],sum[maxn],maxx;
bool f[maxn];
bool find(int x)
{
if(x==1) return false;
if(f[x]) return true;
return find(fa[x]);
}
void build_tree(int x,int depth)
{
dep[x]=depth;
num[depth]++;
m=max(m,depth);
b[depth][num[depth]]=x;
sum[x]=1;
for(int i=1;i<=a[x][0];i++)
if(fa[x]!=a[x][i])
{
fa[a[x][i]]=x;
build_tree(a[x][i],depth+1);
sum[x]+=sum[a[x][i]];
}
}
void dfs(int depth,int ans)
{
if(depth==m+1)
return;
int x;
for(int i=1;i<=num[depth];i++)
{
x=b[depth][i];
if(find(x)) continue;
f[x]=true;
maxx=max(maxx,ans+sum[x]);
dfs(depth+1,ans+sum[x]);
f[x]=false;
}
}
int main(){
//freopen("epidemic.in","r",stdin);
//freopen("epidemic.out","w",stdout);
n=read(),p=read();
for(int i=1;i<=p;i++)
{
int x=read(),y=read();
a[x][++a[x][0]]=y;
a[y][++a[y][0]]=x;
}
build_tree(1,1);
dfs(2,0);
printf("%d",n-maxx);
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、微信公众号：
添加微信，获取资料。
关注公众号，获取动态。
