A、试题类型：
经典数学问题。
B、算法模型：
快速幂。
C、试题说明：
无。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long read()
{
long long res=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
res=res*10+(ch-'0');
ch=getchar();
}
return res*f;
}
long long mod;
long long n,m,k,x;
long long ksm(long long d,long long z)
{
d%=mod;
if(z==0)
return 1ll;
if(z%2)
{
return (ksm(d,z/2)%mod*(ksm(d,z/2)%mod*d%mod)%mod)%mod;
}
else return (ksm(d,z/2)%mod*ksm(d,z/2)%mod)%mod;
}
int main()
{
mod=read();
m=read();
k=read();
x=read();
cout<<(x+m*ksm(10,k)%mod)%mod;
return 0;
}
A、试题类型：
复杂结构。
B、算法模型：
树状数组。
C、试题说明：
逆序对方法。树状数组应用。
#include<cstdio>
#include"algorithm"
#include<iostream>
#define MOD 99999997
#define M 1000010
using namespace std;
struct node
{
int s;int id;
};
node t1[M],t2[M];
int n,a[M],t[M],cnt;
int read()
{
int x=0,f=1;char c=getchar();
while(c>'9'||c<'0') c=getchar();
while(c>='0'&&c<='9') {x=10*x+c-'0';c=getchar();}
return x*f;
}
bool cmp(const node&a,const node&b)
{
return a.s<b.s;
}
int lowbit(int x)
{
return x&(-x);
}
void add(int x)
{
while(x<=n)
{
t[x]++;
x+=lowbit(x);
}
}
int query(int x)
{
int sum=0;
while(x)
{
sum+=t[x];
x-=lowbit(x);
}
return sum;
}
int main()
{
n=read();
for(int i=1;i<=n;i++)
t1[i].s=read(),t1[i].id=i;
for(int i=1;i<=n;i++)
t2[i].s=read(),t2[i].id=i;
sort(t1+1,t1+1+n,cmp);
sort(t2+1,t2+1+n,cmp);
for(int i=1;i<=n;i++)
a[t1[i].id]=t2[i].id;
for(int i=1;i<=n;i++)
{
add(a[i]);
cnt+=i-query(a[i]);
cnt%=MOD;
}
printf("%d\n",cnt);
return 0;
}
A、试题类型：
经典数据结构。
B、算法模型：
最大生成树，要经过的边一定在这棵树，LCA处理。
C、试题说明：
无。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn = 10005, maxm = 50005, inf = 0x3f3f3f3f;
struct edge
{
int a, b, w;
bool operator <(const edge& b) const
{
return w>b.w;
}
}e[maxm];
int fir[maxn], ne[maxn*2], to[maxn*2], w[maxn*2], np;
void add(int x, int y, int z)
{
ne[++np] = fir[x];
fir[x] = np;
to[np] = y;
w[np] = z;
}
int fa[maxn];
int find(int x)
{
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
int n, m;
void kruskal()
{
sort(e, e+m);
for(int i=0; i<m; i++)
{
int u = e[i].a, v = e[i].b;
if(find(u) == find(v))
continue;
fa[find(u)] = find(v);
add(u, v, e[i].w);
add(v, u, e[i].w);
}
}
int f[maxn][20], dist[maxn][20];
int dep[maxn];
void dfs(int u, int F, int depth, int wf)
{
dep[u] = depth;
f[u][0] = F; dist[u][0] = wf;
for(int i=1; i<=18; i++)
f[u][i] = f[f[u][i-1]][i-1],
dist[u][i] = min( dist[u][i-1], dist[f[u][i-1]][i-1]);
for(int i=fir[u]; i; i=ne[i])
if(to[i] != F)
dfs(to[i], u, depth+1, w[i]);
}
int LCA(int x, int y)
{
if(find(x) != find(y)) return -1;
if(dep[x]<dep[y])
swap(x, y);
int ans = inf;
for(int i=18; i>=0; i--)
if((dep[x]-dep[y])&(1<<i))
{
ans = min(ans, dist[x][i]);
x = f[x][i];
}
if(x == y)
return ans;
for(int i=18; i>=0; i--)
if(f[x][i] != f[y][i])
{
ans = min(ans, min(dist[x][i], dist[y][i]));
x = f[x][i];
y = f[y][i];
}
return min(ans, min(dist[x][0], dist[y][0]));
}
int main()
{
scanf("%d%d", &n, &m);
for(int i=1; i<=n; i++)
fa[i] = i;
for(int i=0, x, y, z; i<m ;i++)
{
scanf("%d%d%d", &x, &y, &z);
e[i]=(edge){x, y, z};
}
kruskal();
for(int i=1; i<=n; i++)
if(!dep[i])
dfs(i, 0, 1, inf);
int q;
scanf("%d", &q);
while(q--)
{
int x, y;
scanf("%d%d", &x, &y);
printf("%d\n", LCA(x, y));
}
return 0;
}
A、试题类型：
算法问题。
B、算法模型：
暴力与二分选择。
C、试题说明：
暴力：直接枚举左端点和右端点，计算左端点和右端点之间需要填多少积木，如果小于等于m就选择右端点++，否则就左端点++。
正解，可以想到积木最后的形状一定有一部分是类似金字塔形状的，二分高度，判断所用积木块是否超过m。
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long ll;
int h[100001],Max=0;
long long bb[100001];int n,m;
int L[100001],R[100001];
bool check(int x)
{
int l=n,r=1;
for(int i=n;i>=1;i--){while(h[l]<x-(i-l)&&l>=1)l--;L[i]=l;}
for(int i=1;i<=n;i++){while(h[r]<x-(r-i)&&r<=n)r++;R[i]=r;}
for(int i=1;i<=n;i++)
{
if(R[i]==n+1||L[i]==0)continue;
int a=x-(i-L[i]),b=x-(R[i]-i);
ll y=(ll)x*(ll)x-(ll)(b+1)*(ll)b/2ll-(ll)(a+1)*(ll)a/2ll;
if(y-(ll)(bb[R[i]-1]-bb[L[i]])<=(ll)m)return true;
}
return false;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&h[i]);Max=max(Max,h[i]);bb[i]=bb[i-1]+(ll)h[i];
}
int l=Max+1,r=(int)(sqrt(m)+1.00)+Max+1;
while(l<r)
{
int mid=(l+r)/2;
if(check(mid))l=mid+1;
else r=mid;
}
cout<<l-1;
return 0;
```
}
A、试题类型：
算法推理。
B、算法模型：
贪心。
C、试题说明：
无。
#include <iostream>
using namespace std;
const int N = 100005;
int n, h[N], ans, cnt, pre = -1;
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i++)
scanf("%d", &h[i]);
if(n == 1)
return puts("1"), 0;
if(n == 2)
return puts(h[1] == h[2] ? "1" : "2"), 0;
int now = 1;
while(now < n && h[now] == h[now+1])
now++;
cnt += 2;
pre = h[now+1] > h[now];
for(int i = now+2; i <= n; i++)
{
if(h[i] == h[i-1]) continue;
cnt += ((h[i] > h[i-1]) != pre);
pre = h[i] > h[i-1];
}
printf("%dn", cnt);
return 0;
}
A、试题类型：
基本算法。
B、算法模型：
搜索、暴力搜索、bfs、剪枝叶。
C、试题说明：
无。
#include<bits/stdc++.h>
#define in read()
#define re register
using namespace std;
inline int read()
{
char ch;int f=1,res=0;
while((ch=getchar())<'0'||ch>'9')
if(ch=='-')
f=-1;
while(ch>='0'&&ch<='9')
{
res=(res<<1)+(res<<3)+(ch^48);
ch=getchar();
}
return f==1?res:-res;
}
const int N=35;
int n,m,q;
int a[N][N];
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int f[N][N];
const int M=4009;
int nxt[M<<4],head[M],to[M<<4],w[M<<4],ecnt=0;
int dis[M<<2];
inline void add(int x,int y,int z)
{
// printf("u=%d v=%d val=%d\n",x,y,z);
nxt[++ecnt]=head[x];head[x]=ecnt;to[ecnt]=y;w[ecnt]=z;
}
inline int get_num(int x,int y)
{
y--;
return (x-1)*m+y<<2;
}
#define mp make_pair
void BFS(int ex,int ey,int px,int py,int d)
{
// printf("px=%d py=%d ex=%d ey=%d\n",px,py,ex,ey);
memset(f,-1,sizeof(f));
f[ex][ey]=0;
f[px][py]=1;
queue<pair<int,int> > q;
q.push(mp(ex,ey));
while(!q.empty())
{//预处理出来空格位置到其它位置的最短步数
int x=q.front().first,y=q.front().second;q.pop();
for(re int i=0;i<4;++i)
{
int xx=x+dx[i];
int yy=y+dy[i];
if(f[xx][yy]!=-1) continue;
if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&a[xx][yy])
{
f[xx][yy]=f[x][y]+1;
q.push(mp(xx,yy));
}
}
}
if(d==-1) return;
int num=get_num(px,py);
// printf("px=%d py=%d num=%d\n",px,py,num);
for(re int i=0;i<4;++i)
{//状态转移
int x=px+dx[i];
int y=py+dy[i];
// x>=1&&x<=n&&y>=1&&y<=m&&
if(f[x][y]>0)
add(num+d,num+i,f[x][y]);
}
add(num+d,get_num(ex,ey)+(d+2)%4,1);
}
int INF;
bool vis[M<<2];
void spfa(int sx,int sy)
{
queue<int> q;
memset(vis,0,sizeof(vis));
memset(dis,127/3,sizeof(dis));
INF=dis[0];
for(re int i=0;i<4;++i)
{
int x=sx+dx[i];
int y=sy+dy[i];
if(x>=1&&x<=n&&y>=1&&y<=m&&f[x][y]!=-1)
{
int num=get_num(sx,sy)+i;
dis[num]=f[x][y];
q.push(num);
// printf("tmp=%d dis=%d\n",num,dis[num]);
}
}
while(!q.empty())
{
int u=q.front();q.pop();
vis[u]=0;
for(re int e=head[u];e;e=nxt[e])
{
int v=to[e];
if(dis[v]>dis[u]+w[e])
{
dis[v]=dis[u]+w[e];
if(vis[v]) continue;
vis[v]=1;
q.push(v);
}
}
}
}
int main()
{
n=in;m=in;q=in;
for(re int i=1;i<=n;++i)
for(re int j=1;j<=m;++j)
a[i][j]=in;
for(re int i=1;i<=n;++i)
for(re int j=1;j<=m;++j)if(a[i][j])
{
if(a[i-1][j])BFS(i-1,j,i,j,0);
if(a[i][j+1])BFS(i,j+1,i,j,1);
if(a[i+1][j])BFS(i+1,j,i,j,2);
if(a[i][j-1])BFS(i,j-1,i,j,3);
}
for(re int i=1;i<=q;++i)
{
int ex=in,ey=in,sx=in,sy=in,tx=in,ty=in;
if(sx==tx&&sy==ty){printf("0\n");continue;}
BFS(ex,ey,sx,sy,-1);
spfa(sx,sy);
int ans=INF;
for(re int j=0;j<4;++j)
ans=min(ans,dis[get_num(tx,ty)+j]);
if(ans>=INF) printf("-1\n");
else printf("%d\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、微信公众号：
添加微信，获取资料。
关注公众号，获取动态。
