A、试题类型：
送分题。
B、算法模型：
模拟。
C、试题说明：
条件结构和循环。每次是往顺时针或逆时针来转，仔细观察可以发现，如果方向与左右手相同的话，就是加，不然就是减。
#include<bits/stdc++.h>
#define N 100000
using namespace std;
int n,dir[N+5],tmp,s,m;
int pos;
char name[N+5][15];
int main()
{
freopen("in.txt","r",stdin);
scanf("%d%d\n",&n,&m);
for(int i=0;i<n;i++)
scanf("%d %s\n",&dir[i],name[i]);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&tmp,&s);
if(tmp!=dir[pos])pos=(pos+s)%n;
else pos=(pos-s+n)%n;
}
cout<<name[pos];
return 0;
}
A、试题类型：
基本算法。
B、算法模型：
DFS。
C、试题说明：
dfs序——将求子树的信息（树形）转化为求一段连续区间信息（线形）。
线段树——求区间信息。
树上差分——统计答案。
lca——拆分路径。
树链剖分——求lca。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 300401
using namespace std;
int n,m,fa[N],son[N],deep[N],bl[N],sz,id[N],ans[N];
int in[N],out[N],watch[N];
int front[N],nextt[N*2],to[N*2];
int root[N*3],lc[N*25],rc[N*25],sum[N*25],tot,cnt;
struct node
{
int s,t,lca;
}runner[N];
void add(int u,int v)
{
to[++cnt]=v; nextt[cnt]=front[u]; front[u]=cnt;
}
void dfs1(int now)
{
son[now]++;
for(int i=front[now];i;i=nextt[i])
{
if(to[i]==fa[now])
continue;
deep[to[i]]=deep[now]+1;
fa[to[i]]=now;
dfs1(to[i]);
son[now]+=son[to[i]];
}
}
void dfs2(int now,int chain)
{
id[now]=++sz;
in[now]=sz;
bl[now]=chain;
int y=0;
for(int i=front[now];i;i=nextt[i])
{
if(to[i]==fa[now])
continue;
if(son[to[i]]>son[y])
y=to[i];
}
if(!y)
{
out[now]=sz;
return;
}
dfs2(y,chain);
for(int i=front[now];i;i=nextt[i])
{
if(to[i]==fa[now]||to[i]==y)
continue;
dfs2(to[i],to[i]);
}
out[now]=sz;
}
int getlca(int u,int v)
{
while(bl[u]!=bl[v])
{
if(deep[bl[u]]<deep[bl[v]])
swap(u,v);
u=fa[bl[u]];
}
return deep[u]<deep[v] ? u:v;
}
void change(int & now,int l,int r,int pos,int w)
{
if(!pos)
return;
if(!now)
now=++tot;
sum[now]+=w;
if(l==r)
return;
int mid=l+r>>1;
if(pos<=mid)
change(lc[now],l,mid,pos,w);
else
change(rc[now],mid+1,r,pos,w);
}
int query(int now,int l,int r,int opl,int opr)
{
if(!now)
return 0;
if(l==opl&&r==opr)
return sum[now];
int mid=l+r>>1;
if(opr<=mid)
return query(lc[now],l,mid,opl,opr);
else if(opl>mid)
return query(rc[now],mid+1,r,opl,opr);
else
return query(lc[now],l,mid,opl,mid)+query(rc[now],mid+1,r,mid+1,opr);
}
void clear()
{
tot=0;
memset(lc,0,sizeof(lc));
memset(rc,0,sizeof(rc));
memset(sum,0,sizeof(sum));
memset(root,0,sizeof(root));
}
int main()
{
/*freopen("runninga.in","r",stdin);
freopen("runninga.out","w",stdout);*/
scanf("%d%d",&n,&m);
int u,v;
for(int i=1;i<n;i++)
{
scanf("%d%d",&u,&v);
add(u,v);add(v,u);
}
for(int i=1;i<=n;i++)
scanf("%d",&watch[i]);
for(int i=1;i<=m;i++)
scanf("%d%d",&runner[i].s,&runner[i].t);
dfs1(1);
dfs2(1,0);
for(int i=1;i<=m;i++)
runner[i].lca=getlca(runner[i].s,runner[i].t);
int now;
for(int i=1;i<=m;i++)
{
now=deep[runner[i].s];
change(root[now],1,n,id[runner[i].s],1);
change(root[now],1,n,id[fa[runner[i].lca]],-1);
}
for(int i=1;i<=n;i++)
ans[i]=query(root[deep[i]+watch[i]],1,n,in[i],out[i]);
clear();
for(int i=1;i<=m;i++)
{
now=deep[runner[i].s]-deep[runner[i].lca]*2+n*2;
change(root[now],1,n,id[runner[i].t],1);
change(root[now],1,n,id[runner[i].lca],-1);
}
for(int i=1;i<=n;i++)
ans[i]+=query(root[watch[i]-deep[i]+n*2],1,n,in[i],out[i]);
for(int i=1;i<=n;i++)
printf("%d ",ans[i]);
}
A、试题类型：
动态规划。
B、算法模型：
多方程推导。
C、试题说明：
先用Floyd预处理任意两点x,y之间的最短路d[x][y]。
设f[ i ][ j ][ k ]表示当前是第i天，一共换了j间教室，k=0或1表示第i天是否换了教室
k[i]表示第i天换教室成功的概率。
c[i][0]表示第i天换前的教室，c[i][1]表示第i天换后的教室。
有以下四种情况：
情况一：第i-1天换了教室,第i天未换教室；
情况二：第i-1天换了教室,第i天换了教室；
情况三：第i-1天未换教室,第i天未换教室；
情况一：第i-1天未换教室,第i天换了教室；
初始状态：
f[i][j][k]=inf(极大值）
f[1][0][0]=0; f[1][1][1]=0;
状态转移方程：
f[i][j][0]=min(f[i][j][0],f[i-1][j][1]+k[i-1]*d[c[i-1][1]][c[i][0]]+(1-k[i-1])*d[c[i-1][0]][c[i][0]]);
f[i][j][0]=min(f[i][j][0],f[i-1][j][0]+d[c[i-1][0]][c[i][0]]);
if(j!=0){
f[i][j][1]=min(f[i][j][1],f[i-1][j-1][0]+k[i]*d[c[i-1][0]][c[i][1]]+(1-k[i])*d[c[i-1][0]][c[i][0]]);
f[i][j][1]=min(f[i][j][1],f[i-1][j-1][1]+k[i]*k[i-1]d[c[i-1][1]][c[i][1]]+k[i](1-k[i-1])*d[c[i-1][0]][c[i][1]]+(1-k[i])*k[i-1]d[c[i-1][1]][c[i][0]]+(1-k[i])(1-k[i-1])*d[c[i-1][0]][c[i][0]]);
}
#include<bits/stdc++.h>
using namespace std;
const int N=2005;
const double maxi=800050000;
int n,m,v,e;
int c[N][2];
double k[N];
double d[N][N];
double f[N][N][2];
int read()
{
int sum=0,f=1;
char ch=getchar();
while(ch>'9'||ch<'0')
{
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
sum=(sum<<3)+(sum<<1)+ch-'0';
ch=getchar();
}
return sum*f;
}
int main()
{
// freopen("classroom.in","r",stdin);
// freopen("classroom.out","w",stdout);
n=read();
m=read();
v=read();
e=read();
for(int i=1;i<=n;i++)
c[i][0]=read();
for(int i=1;i<=n;i++)
c[i][1]=read();
for(int i=1;i<=n;i++)
scanf("%lf",&k[i]);
for(int i=1;i<=v;i++)
for(int j=1;j<i;j++)
d[i][j]=d[j][i]=maxi;
int x,y;
double w;
for(int i=1;i<=e;i++)
{
x=read();
y=read();
scanf("%lf",&w);
if(w<d[x][y])
d[x][y]=d[y][x]=w;
}
for(int t=1;t<=v;t++)
for(int i=1;i<=v;i++)
for(int j=1;j<i;j++)
if(d[i][j]>d[i][t]+d[t][j])
d[i][j]=d[j][i]=d[i][t]+d[t][j];
for(int i=1;i<=n;i++)
for(int j=0;j<=m;j++)
f[i][j][0]=f[i][j][1]=maxi;
f[1][0][0]=0;
f[1][1][1]=0;
for(int i=2;i<=n;i++)
for(int j=0;j<=m;j++)
{
f[i][j][0]=min(f[i][j][0],f[i-1][j][1]+k[i-1]*d[c[i-1][1]][c[i][0]]+(1-k[i-1])*d[c[i-1][0]][c[i][0]]);
f[i][j][0]=min(f[i][j][0],f[i-1][j][0]+d[c[i-1][0]][c[i][0]]);
if(j!=0)
{
f[i][j][1]=min(f[i][j][1],f[i-1][j-1][0]+k[i]*d[c[i-1][0]][c[i][1]]+(1-k[i])*d[c[i-1][0]][c[i][0]]);
f[i][j][1]=min(f[i][j][1],f[i-1][j-1][1]+k[i]*k[i-1]*d[c[i-1][1]][c[i][1]]+k[i]*(1-k[i-1])*d[c[i-1][0]][c[i][1]]+(1-k[i])*k[i-1]*d[c[i-1][1]][c[i][0]]+(1-k[i])*(1-k[i-1])*d[c[i-1][0]][c[i][0]]);
}
}
double ans=maxi;
for(int j=0;j<=m;j++)
for(int t=0;t<2;t++)
{
ans=min(ans,f[n][j][t]);
}
printf("%.2lf",ans);
return 0;
}
A、试题类型：
数字问题。
B、算法模型：
组合数。
C、试题说明：
无。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll c[2005][2005],f[2005][2005];
int m,n,k,t;
inline int read()
{
char ch=getchar();
int res=0;
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) res=(res<<3)+(res<<1)+(ch^48),ch=getchar();
return res;
}
inline void init()
{
for(int i=0;i<=2003;i++)
c[i][1]=i,c[i][0]=1;
for(int i=1;i<=2003;i++)
{
for(int j=1;j<=i;j++)
{
c[i][j]=c[i-1][j-1]+c[i-1][j];
c[i][j]%=k;
}
}
for(int i=1;i<=2003;i++)
{
for(int j=1;j<=i;j++)
{
f[i][j]=f[i][j-1]+(c[i][j]%k==0);
}
}
}
int main()
{
t=read(),k=read();
init();
while(t--)
{
n=read(),m=read();
m=min(m,n);
ll ans=0;
for(int i=1;i<=n;i++)
{
int h=min(m,i);
ans+=f[i][h];
}
cout<<ans<<'\n';
}
}
A、试题类型：
基本数据结构。
B、算法模型：
队列。
C、试题说明：
可以用优先队列实现，但是要优化一下。考虑每次取出一个最大值这个操作，堆来维护比较方便，但是每次加上一个似乎不好处理。
考虑增加一个全局变量，表示每个数都需要加上，这样就可以避免对于堆中所有元素增加，而只需把每次新的两个元素减去，再放入堆中即可。
具体做法：系统堆维护，每次取出最大元素，然后加上，得到真实值，算出两个新元素值，加上，两个新元素值减去，丢入堆中。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int Max=7000100;
int n,m,u,v,q,t,h1=1,t1,h2=1,t2,h3=1,t3,sum,x,pre,num;
int ans[Max],q1[Max],q2[Max],q3[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 void print(int x)
{
if(x > 9)
print(x/10);
putchar(x%10+'0');
}
inline bool comp(const int &a,const int &b)
{
return a>b;
}
inline int calc(int x)
{
return x*u/v;
}
inline void solve()
{
for(int i=1;i<=m;i++)
{
num=max(q1[h1],max(q2[h2],q3[h3]));
if(q1[h1]==num)
h1++;
else if(q2[h2]==num)
h2++;
else
h3++;
x=num+sum;sum+=q;
if(!(i%t))
print(x),putchar(' ');
num=calc(x),pre=x-num;
q2[++t2]=num-sum,q3[++t3]=pre-sum;
}
}
signed main()
{
n=get_int(),m=get_int(),q=get_int(),u=get_int(),v=get_int(),t=get_int();
memset(q1,-0x3f3f3f,sizeof(q1)),memset(q2,-0x3f3f3f,sizeof(q2)),memset(q3,-0x3f3f3f,sizeof(q3));
for(int i=1;i<=n;i++)
q1[i]=get_int();
sort(q1+1,q1+n+1,comp);
solve(),putchar('\n');
for(int i=1;i<=n+m;i++)
{
x=max(q1[h1],max(q2[h2],q3[h3]));
if(q1[h1]==x)
h1++;
else if(q2[h2]==x)
h2++;
else
h3++;
if(!(i%t))
print(x+sum),putchar(' ');
}
return 0;
}
A、试题类型：
经典数学问题。
B、算法模型：
抛物线。
C、试题说明：
无。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const double eps=1e-8;
double abs(double x)
{
return x>0?x:-x;
}
bool dy(double a,double b)
{
return abs(a-b)<eps;
}
int n=0,m=0,ans=0;
double x[20],y[20],ax[20],bx[20],tx[20],ty[20];
void dfs(int c,int u,int v)
{
if(u+v>=ans)
return;
if(c>n)
{
ans=u+v;
return;
}
bool bb=0;
for(int i=1;i<=u;i++)
if(dy(ax[i]*x[c]*x[c]+bx[i]*x[c],y[c]))
{
dfs(c+1,u,v);
bb=1;
break;
}
if(!bb)
{
for(int i=1;i<=v;i++)
{
if(dy(x[c],tx[i]))
continue;
double a=(y[c]*tx[i]-ty[i]*x[c])/(x[c]*x[c]*tx[i]-tx[i]*tx[i]*x[c]);
double b=(y[c]-x[c]*x[c]*a)/x[c];
if(a<0)
{
ax[u+1]=a;
bx[u+1]=b;
double q=tx[i],w=ty[i];
for(int j=i;j<v;j++)
{
tx[j]=tx[j+1];
ty[j]=ty[j+1];
}
dfs(c+1,u+1,v-1);
for(int j=v;j>i;j--)
{
tx[j]=tx[j-1];
ty[j]=ty[j-1];
}
tx[i]=q;
ty[i]=w;
}
}
tx[v+1]=x[c];
ty[v+1]=y[c];
dfs(c+1,u,v+1);
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%lf%lf",&x[i],&y[i]);
ans=100;
dfs(1,0,0);
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、微信公众号：
添加微信，获取资料。
关注公众号，获取动态。
