A、试题类型：
送分题。
B、算法模型：
二维数组。
C、试题说明：
手动模拟，该题逻辑简单，就是二维数组 + if else 语句。
#include <stdio.h>
#include <string.h>
int a[100][100];
int main()
{
int n;
int i,j;
int k;
int before_row,before_col;
scanf("%d",&n);
memset(a,0,sizeof(0));
a[1][(1+n)/2]=1;//安排数据1
before_row=1;
before_col=(1+n)/2;
for(i=2;i<=n*n;i++)
{
if(before_row==1&&before_col!=n)
{
a[n][before_col+1]=i;
before_row=n;
before_col++;
}
else if(before_col==n&&before_row!=1)
{
a[before_row-1][1]=i;
before_row--;
before_col=1;
}
else if(before_row==1&&before_col==n)
{
a[before_row+1][before_col]=i;
before_row++;
}
else if(before_row!=1&&before_col!=n)
{
if(a[before_row-1][before_col+1]==0)
{
a[before_row-1][before_col+1]=i;
before_row--;
before_col++;
}
else
{
a[before_row+1][before_col]=i;
before_row++;
}
}
}
for(i=1;i<=n;i++)
{
printf("%d",a[i][1]);//此处写成a[i][j]，查了半天。
for(j=2;j<=n;j++)
{
printf(" %d",a[i][j]);
}
printf("\n");
}
return 0;
}
A、试题类型：
基本算法。
B、算法模型：
暴力排序。
C、试题说明：
大暴力其实就能过80分。
用输入输出优化和register再用一个Max来记录。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std;
const int N=200005;
int n,k=1,head[N],ss,rd[N],ans=0x7f7f7f,temp=0;//注意ans初始值
bool vis[N];
struct node
{
int to,next;
}edge[N*2];
void add(int u,int v)
{
edge[++k].to=v;
edge[k].next=head[u];
head[u]=k;
}
void topsort()
{
queue<int>q;
for(int i=1;i<=n;i++)
if(rd[i]==0)
{
q.push(i);
vis[i]=true;
}
while(!q.empty())
{
int x=q.front();q.pop();
for(int i=head[x];i;i=edge[i].next)
{
rd[edge[i].to]--;//入度--
if(rd[edge[i].to]==0)
{
vis[edge[i].to]=true;//删点
q.push(edge[i].to);
}
}
}
}
void dfs(int s)//找环
{
for(int i=head[s];i;i=edge[i].next)
{
if(!vis[edge[i].to])
{
temp++;//找到环中一个点
vis[edge[i].to]=true;
dfs(edge[i].to);
}
}
}
int main()
{
scanf("%d",&n);
for(int u=1;u<=n;u++)
{
int v;
scanf("%d",&v);
add(u,v);rd[v]++;//入度++
}
topsort();
for(int i=1;i<=n;i++)
{
if(!vis[i])
temp=0,dfs(i),ans=min(temp,ans);//找最小环
}
printf("%d",ans);
}
A、试题类型：
基本生活问题。
B、算法模型：
剪枝。
C、试题说明：
考虑没有顺子的情况，那么就可以贪心的进行出牌，出牌优先级为顺子>四带二>四带一>三带二>三带一>对子>单牌。
出一次优先级大的组合一定有多个优先级小的组合组成的，所以贪心一定是是对的。
有了顺子后，就不能证明贪心是对的，就直接搜索顺子是哪些，然后更新答案，必要的剪枝是肯定要加的。
#include <bits/stdc++.h>
using namespace std;
const int card[5]={0,5,3,2};
const int Max=16;
int n,m,ans,x,y,t;
int a[Max],sum[Max];
inline int calc()
{
int tot=0;
memset(sum,0,sizeof(sum));
for(int i=0;i<=14;i++)
if(i^1)
sum[a[i]]++;
while(sum[4]&&sum[2]>=2)
tot++,sum[4]--,sum[2]-=2;
while(sum[4]&&sum[1]>=2)
tot++,sum[4]--,sum[1]-=2;
while(sum[3]&&sum[2])
tot++,sum[3]--,sum[2]--;
while(sum[3]&&sum[1])
tot++,sum[3]--,sum[1]--;
return tot+sum[1]+sum[2]+sum[3]+sum[4];
}
inline void dfs(int step)
{
if(step>=ans)
return;
ans=min(ans,step+calc());
for(int same=3;same;same--)
for(int i=3;i<=13;i++)
{
int j=i;
while(a[j]>=same&&j<=14)
j++;j--;
if(j-i+1<card[same])
continue;
for(int k=i;k<=i+card[same]-2;k++)
a[k]-=same;
for(int k=i+card[same]-1;k<=j;k++)
a[k]-=same,dfs(step+1);
for(int k=i;k<=j;k++)
a[k]+=same;
}
}
int main()
{
scanf("%d%d",&t,&n);
while(t--)
{
memset(a,0,sizeof(a)),ans=n;
for(int i=1;i<=n;i++)
scanf("%d%d",&x,&y),x=x==1?14:x ,a[x]++;
dfs(0),printf("%d\n",ans);
}
return 0;
}
A、试题类型：
最小最大值问题。
B、算法模型：
二份查找。
C、试题说明：
一般求最小值最大或最大值最小的问题，要用二分的方法。
二分答案，检查一下能不能让所有的跳跃距离都大于mid。如果可以，下一步在[mid+1, r]中再二分，反之在[l,mid-1]中二分。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int L,m,n;
int a[50010];
int check(int x)
{
int ans = 0;
int last = 0;//上一块石头距起点的位置
for(int i = 1; i <= n; i++)
{
if(a[i] - last < x)//如果这两块石头相距小于当前值，
ans++;//就要把这块石头移走
else
last = a[i];
}
if(ans > m)
return 0;//移走的数目多于m，说明答案取大了
else
return 1;//反之答案取小了
}
int main()
{
scanf("%d%d%d", &L, &n, &m);
for(int i = 1; i <= n; i++)
scanf("%d", &a[i]);
n++;
a[n] = L;
int l = 0, r = L;
while(l <= r)
{
int mid = (l + r) / 2;
if(check(mid))
l = mid + 1;
else
r = mid - 1;
}
printf("%d", r);
return 0;
}
A、试题类型：
字符串问题。
B、算法模型：
方程和优化。
C、试题说明：
注意优化。
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <cstring>
#include <string>
using namespace std;
int i,j,k,l,m,n,la,lb,ll,ans,pd;
int f[2][1005][405];//!!!!!!!!!!!!!!!!!!!!+取模
char a[1005],b[205];
int main()
{
scanf("%d%d%d\n",&la,&lb,&ll);
gets(a+1);
gets(b+1);
l=0;
for(i=0;i<=la;i++)
f[0][i][0]=1;
for(k=1;k<=ll;k++)
{
l^=1;
for(i=0;i<=la;i++)
f[l][i][k-1]=0;
for(j=k;j<=lb;j++)
for(i=j;i<=la;i++)
{
if (a[i]==b[j])
{
f[l][i][j]=(f[l][i-1][j-1]+f[l][i-1][j])%1000000007;
f[l][i][j]=(f[l][i][j]+f[l^1][i-1][j-1])%1000000007;
if (i>=2)
f[l][i][j]=(f[l][i][j]-f[l][i-2][j-1]+1000000007)%1000000007;
}
else
f[l][i][j]=f[l][i-1][j];
}
}
printf("%d\n",f[l][la][lb]);
return 0;
}
A、试题类型：
典型数据结构。
B、算法模型：
树的问题。
C、试题说明：
题目：给定一棵带权树与m条路径，你可以使一条树上的边的权值变为0，问你m条路径的长度的最大值最小是多少。
最大值最小问题，非常显然是二分方法。
#include<iostream>
#include<cstdio>
#include<cstring>
#define N 300010
using namespace std;
int n,m,x,y,z,MAX,l,r,mid,ans;
int a[N],b[N],lca[N],len[N],cf[N];
int f[N][21],dfn[N],dfn_tot,dep[N],dis[N],va[N],father[N];
int head[N],next[N*2],e[N*2],v[N*2],tot;//链式前向星
inline void read(int &x)//快读加速
{
x=0;
char c=getchar();
while (c<'0'||c>'9')
c=getchar();
while (c>='0'&&c<='9')
x=x*10+c-'0',c=getchar();
}
inline int add(int x,int y,int z)
{
e[++tot]=y,v[tot]=z,next[tot]=head[x],head[x]=tot;
}//链式前向星
inline void dfs(int x,int fa)//LCA递归预处理
{
dfn[++dfn_tot]=x/*dfs序*/,father[x]=fa,dep[x]=dep[fa]+1;
for (register int i=0;i<20;i++)
f[x][i+1]=f[f[x][i]][i];
for (register int i=head[x];i;i=next[i])
if (e[i]!=fa)
dis[e[i]]=dis[x]+v[i]/*dis数组更新*/,f[e[i]][0]=x,va[e[i]]=v[i],dfs(e[i],x);
}
int LCA(int x,int y)//求LCA
{
if (dep[x]<dep[y])
swap(x,y);
for (register int i=20;i>=0;i--)
{
if (dep[f[x][i]]>=dep[y])
x=f[x][i];
if (x==y)
return x;
}
for (register int i=20;i>=0;i--)
if (f[x][i]&&f[y][i]&&f[x][i]!=f[y][i])
x=f[x][i],y=f[y][i];
return f[x][0];
}
inline int check(int mid)//二分判断函数
{
memset(cf,0,sizeof(cf));
int k=0;
for (register int i = 1;i <= m; ++i)
if (len[i]>mid)
cf[a[i]]++,cf[b[i]]++,cf[lca[i]]-=2,k++;//树上差分
for (register int i=n;i;i--)//树上差分dfs序优化
cf[father[dfn[i]]]+=cf[dfn[i]];
for (register int i=1;i<=n;i++)//枚举边判断
if (cf[i]==k&&MAX-va[i]<=mid) return 1;
return 0;
}
int main()
{
freopen("transport.in","r",stdin);
freopen("transport.out","w",stdout);
read(n), read(m);
for (register int i=1;i<n;i++)
read(x),read(y),read(z),add(x,y,z),add(y,x,z);
dfs(1,0);
for (register int i=1;i<=m;i++)
{
read(a[i]),read(b[i]);
lca[i]=LCA(a[i],b[i]),len[i]=dis[a[i]]+dis[b[i]]-2*dis[lca[i]]/*计算距离*/,MAX=max(MAX,len[i])/*求最大距离*/;
}
r=MAX;//二分
while (l<=r)
{
if (check(mid=l+r>>1))
r=mid-1,ans=mid;
else
l=mid+1;
}
printf("%d",ans);
}
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、微信公众号：
添加微信，获取资料。
关注公众号，获取动态。
