A、试题类型：
基本数据结构。
B、算法模型：
队列问题。
C、试题说明：
将内存看成一个队列（队列内元素先进先出），只不过这个队是个环，最开始的时候，内存为空，对文章的每个单词再内存中遍历，如果找到这个元素，就查看下一个单词，如果没找到这个单词，就把最先入队的（P指着那个位置）单词，出队，然后放入P中。然后P移向下一个位置，当P超出内存的长度的时候，P=1；其实P在这里的作用就是一个分割。
//#include<bits/stdc++.h> //万能头文件
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int main()
{
int ramlen,len,point,ans;
int passage[10001],ram[1001];
while(scanf("%d%d",&ramlen,&len)!=EOF)
{
ans=0;
memset(ram,0,sizeof(ram)); // 因为单词用非负整数表示，所以最初内存中为空，用0表示
for(int i=1;i<=len;i++)
scanf("%d",&passage[i]);
point=1;
for(int i=1;i<=len;i++)
{
int flag=0;
for(int j=1;j<=ramlen;j++)
if(ram[j]==passage[i])
{
flag=1;
break;
} //内存中有这个单词 不再进行查找
if(!flag) //如果没找到，查询次数加1，内存中新增这个单词 ，替换掉point指着的ram
{
ans++;
ram[point]=passage[i];
point++; //替换完成，point指向下一这个单词
if(point==ramlen+1)
point=1;
}
}
cout<<ans<<endl;
}
return 0;
}
A、试题类型：
动态规划。
B、算法模型：
四维动态规划。
C、试题说明：
四维动态规划问题。
很容易想到一种状态。
f[a][b][c][d]=max{f[a−1,b,c,d],f[a,b−1,c,d],f[a,b,c−1,d],f[a,b,c,d−1]}+box[a+2b+3c+4d+1]
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int f[360][43][43][43];
int n , m ;
int b[5] = {0};
int a[1000] ;
void update(int & x , int y)
{
if( y > x)
x = y ;
}
int main()
{
freopen("tortoise.in","r",stdin);
freopen("tortoise.out","w",stdout);
scanf("%d %d\n",&n,&m);
int x ;
for(int i = 1 ; i <= n ; i ++ )
scanf("%d ",&a[i]);scanf("\n");
for(int i = 1 ; i <= m ; i ++ )
scanf("%d ",&x) , b[x] ++ ;
f[1][0][0][0] = a[1] ;
for(int i = 1 ; i <= n ; i ++ )
for(int x = 0 ; x <= b[2] ; x ++ )
for(int y = 0 ; y <= b[3] ; y ++ )
for(int z = 0 ; z <= b[4] ; z ++ )
if(f[i][x][y][z]){
int d = f[i][x][y][z] , g = i - 1 - x * 2 - y * 3 - z * 4 ;
if( x != b[2] ) update( f[i+2][x+1][y][z] , d + a[i+2] );
if( y != b[3] ) update( f[i+3][x][y+1][z] , d + a[i+3] );
if( z != b[4] ) update( f[i+4][x][y][z+1] , d + a[i+4] );
if( g != b[1] ) update( f[i+1][x][y][z] , d + a[i+1] );
}
cout << f[n][b[2]][b[3]][b[4]] << endl ;
return 0 ;
}
A、试题类型：
博弈问题。
B、算法模型：
逻辑推导。
C、试题说明：
无。
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int fa[20005],f[20005];
int n,m,ans;
struct edge
{
int a;
int b;
int c;
};
bool cmp(edge a,edge b)
{//按照怨气值从大到小排序
if(a.c!=b.c)
{
return a.c>b.c;
}
return a.a<b.a;
}
edge e[100005];
void init()
{
for(int i=1;i<=n;i++)
{
fa[i]=i;
}
}
int get(int x)
{
if(fa[x]==x)
{
return x;
}
return fa[x]=get(fa[x]);
}
void merge(int x,int y)
{
x=get(x);
y=get(y);
if(x!=y)
{
fa[y]=x;
}
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=0;i<m;i++)
{
scanf("%d %d %d",&e[i].a,&e[i].b,&e[i].c);
}
init();
sort(e,e+m,cmp);
for(int i=0;i<m;i++)
{
if(get(e[i].a)==get(e[i].b))
{//如果这个矛盾关系的双方已经在同一个集合里了，那么这个怨气值就是答案，并且不用再看后边的循环了。
ans=e[i].c;
break;
}
else
{//否则的话，
if(f[e[i].a])
{//先看f[e[i].a]是不是非0，是的话就是已经有对立集合了，就把f[e[i].a]所在的集合和e[i].b所在的集合合并，
merge(f[e[i].a],e[i].b);
}
else
{//否则就是没有对立集合，就把f[e[i].a]赋值为e[i].b。
f[e[i].a]=e[i].b;
}
if(f[e[i].b])
{//再看f[e[i].b]是不是非0，是的话说明e[i].b有对立集合，就把f[e[i].b]所在的集合和e[i].a所在的集合合并，
merge(f[e[i].b],e[i].a);
}
else
{//否则就是没有对立集合，就把f[e[i].b]赋值为e[i].a。
f[e[i].b]=e[i].a;
}
}
}
printf("%d",ans);
return 0;
}
A、试题类型：
多算法结合。
B、算法模型：
BFS+贪心+区域覆盖。
C、试题说明：
算出第一行每个点能到达的区间，然后就是经典的区间覆盖问题，用贪心解决。
#include <bits/stdc++.h>
using namespace std;
const int fx[5]={0,1,0,-1,0};
const int fy[5]={0,0,1,0,-1};
const int Max=505;
int n,m,head,tail,ans,sum,now=1;
int num[Max][Max],vis[Max][Max],l[Max][Max],r[Max][Max];
struct shu
{
int x,y;
};
shu p[250005];
struct qj
{
int l,r;
};
qj c[Max];
inline int get_int()
{
int x=0,f=1;
char c;
for(c=getchar();(!isdigit(c))&&(c!='-');c=getchar());
if(c=='-')
f=-1,c=getchar();
for(;isdigit(c);c=getchar())
x=(x<<3)+(x<<1)+c-'0';
return x*f;
}
inline bool comp(const qj &a,const qj &b)
{
return a.l!=b.l ? a.l<b.l : a.r<b.r;
}
inline void bfs(int a[Max][Max],int X,int Y,int v,int tag)
{
if(a[X][Y])
return;
head=0,tail=1;
p[1].x=X,p[1].y=Y,a[X][Y]=v;
while(head<tail)
{
head++;
int x=p[head].x,y=p[head].y;
for(int i=1;i<=4;++i)
{
int x1=x+fx[i],y1=y+fy[i];
if(a[x1][y1]||x1<1||x1>n||y1<1||y1>m)
continue;
if(!tag&&num[x1][y1]>=num[x][y])
continue;
if(tag&&num[x1][y1]<=num[x][y])
continue;
tail++,a[x1][y1]=a[x][y];
p[tail].x=x1,p[tail].y=y1;
}
}
}
int main()
{
n=get_int(),m=get_int();
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j) num[i][j]=get_int();
for(int i=1;i<=m;++i)
bfs(vis,1,i,1,0);
for(int i=1;i<=m;++i)
if(!vis[n][i])
sum++;
if(sum)
{
cout<<"0\n"<<sum;
return 0;
}
for(int i=1;i<=m;++i)
if(!l[n][i])
bfs(l,n,i,i,1); //妙啊
for(int i=m;i>=1;--i)
if(!r[n][i])
bfs(r,n,i,i,1); //妙啊
for(int i=1;i<=m;++i)
c[i].l=l[1][i],c[i].r=r[1][i];
sort(c+1,c+m+1,comp);
int to=0;
for(int i=1;i<=m;++i)
{
if(now>=c[i].l)
to=max(to,c[i].r);
else
ans++,now=to+1,to=max(to,c[i].r);
}
if(now-1<m)
ans++;
cout<<"1\n"<<ans;
return 0;
}
IT航班提供：教辅资料、课程视频、课程书籍、竞赛辅导、少儿编程指导、课程采购、加盟、少儿编程资料、少儿编程课程、保送生、特长生、加分、中小学计算机教育、中小学信息学、竞赛、中小学信息学课程、人工智能、中小学编程加盟、少儿编程加盟、品牌加盟、技术加盟、技术指导、课程加盟、师资培训、中小学编程教辅资料、中小学编程教师培训、少儿编程教学书籍、少儿编程视频、教学书籍、教师培训、教学视频、CSP-J/S、中小学信息学课程服务、竞赛指导、课程提供、国内外计算机中小学计算机竞赛、信息学竞赛、信息学课程提供商、信息学奥林匹克。
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、微信公众号：
添加微信，获取资料。
关注公众号，获取动态。
