A、试题类型：
经典数字问题。
B、算法模型：
格雷码。
C、试题说明：
要求n位的格雷码中k（k从0开始）二进制串，可以使用分治思想递归求解。
#include <iostream>
using namespace std;
typedef unsigned long long ULL;
string dfs(int n, ULL k)
{
if(n == 0)
return "";
//1ull表示无符号长整型1
if(k < (1ull << n - 1))
return "0" + dfs(n - 1, k);
ULL t = (1ull << n) - 1;
//当n=64时，2的64次幂ULL也会溢出
//单独判断处理即可
if(n == 64)
t = -1;
return "1" + dfs(n - 1, t - k);
}
int main()
{
int n;
ULL k;
cin >> n >> k;
cout << dfs(n, k) << endl;
return 0;
}
A、试题类型：
生活与结构。
B、算法模型：
树。
C、试题说明：
暴力->链->树（不要拿到题就想正解！先想暴力对出正解有很大的帮助）。
#include<bits/stdc++.h>
#define ll long long
#define mm 500005
using namespace std;
int n,tot,top;
int fa[mm],fi[mm],nxt[mm],to[mm],c[mm];
char s[mm];
ll ans,lit[mm],sum[mm];
void lian(int u,int v)
{
nxt[++tot]=fi[u];
fi[u]=tot;
to[tot]=v;
}
void Dfs(int x)
{
int t=0;
if(s[x]==')')
{
if(top)
{
t=c[top];
lit[x]=lit[fa[t]]+1;
top--;
}
}
else if(s[x]=='(')
c[++top]=x;
sum[x]=sum[fa[x]]+lit[x];
for(int i=fi[x];i;i=nxt[i])
Dfs(to[i]);
if(t)
c[++top]=t;
else if(top)
top--;
return;
}
int main()
{
scanf("%d",&n);
scanf("%s",s+1);
for(int i=2;i<=n;i++)
{
scanf("%d",&fa[i]);
lian(fa[i],i);
}
Dfs(1);
for(int i=1;i<=n;i++)
ans^=sum[i]*(ll)i;
printf("%lld\n",ans);
return 0;
}
A、试题类型：
数据结 + 算法：混合知识点。
B、算法模型：
贪心 + 树、DFS。
C、试题说明：
贪心：枚举每个数，将它们分别移动到尽可能小的节点上面去。
考虑把一个数字送到另一个数字上，对于一个点一共有三种限制：
对于起始点，选中的边必须先于其它所有边删掉；
对于中转点，选中的两条边必须顺序删掉；
对于结束点，选中的边必须在最后删掉。
将删的边的顺序排成一排，可以发现可以用双向链表来维护。给每个节点u都建立一个双向链表。
计算答案的过程中，一定有一些是连不到一起的，这种情况把它们看成一堆链表就可以了。
两次 DFS应用：枚举每个数字，第一次 DFS 找出它能够到达的最小的节点，第二次 DFS 更新链表。
#include <cstdio>
#include <algorithm>
using namespace std;
const int Maxn = 2000;
struct Edge
{
int to;
Edge *nxt;
};
Edge pool[Maxn * 2 + 5];
Edge *G[Maxn + 5], *ecnt;
inline void addedge(int u, int v)
{
Edge *p = ++ecnt;
p->to = v, p->nxt = G[u];
G[u] = p;
}
int N, num[Maxn + 5];
int pre[Maxn + 5][Maxn + 5], nxt[Maxn + 5][Maxn + 5];//链表的前后指针
int head[Maxn + 5][Maxn + 5], tail[Maxn + 5][Maxn + 5];//链表的头节点和尾节点
int len[Maxn + 5][Maxn + 5];//链表的大小
int deg[Maxn + 5];
inline void clear()
{
ecnt = &pool[0];
for(int i = 1; i <= N; i++)
G[i] = NULL;
for(int i = 1; i <= N + 1; i++)
for(int j = 1; j <= N + 1; j++)
len[i][j] = pre[i][j] = nxt[i][j] = head[i][j] = tail[i][j] = 0;
for(int i = 1; i <= N; i++)
deg[i] = 0;
}
int minp;
void DFS1(int u, int fa)
{//找到对应的最小的节点
int st = head[u][fa], ed = tail[u][fa];
if(fa == N + 1)
{//这是起点
for(Edge *p = G[u]; p != NULL; p = p->nxt)
{
//枚举这个点上的第一条应该删掉的边
int v = p->to;
int t1 = head[u][v], t2 = tail[u][v];
if(t1 != v || (pre[u][fa] == t2 && len[u][t1] < deg[u]))
continue;
//若这个点 v 已经有了一个起点且并不是它自己
//或者，这个点的链表形成了一个环但总长度无法将所有的边连接在一起
//那么这条边就不能够被第一个选中
DFS1(v, u);
}
}
else
{
if(fa == ed)
{//如果 u 后面并没有选到一条边，那么枚举一个点
if(pre[u][N + 1] == 0 && (nxt[u][N + 1] != st
|| len[u][st] == deg[u])) minp = min(minp, u);
//当 u 能被当做结束点的时候
//首先，这个点的最后一条没有删的边没有指定
//其次，如果这个点的链表的开头会连上结尾，那么长度必须等于 u 的出度
//否则长度随意
for(Edge *p = G[u]; p != NULL; p = p->nxt)
{
int v = p->to;
int t1 = head[u][v], t2 = tail[u][v];
if(st == t1 || t1 != v || nxt[u][N + 1] == v)
continue;
//若这两条边 (u, fa) 和 (u, v) 已经在同一个链表上面
//或者，这条边不是一条开始边，即它之前还有其它的边要被删掉
//或者这条边就是一条开始边
//那么 (u, v) 就不能够接在 (u, fa) 后面
if(nxt[u][N + 1] == st && pre[u][N + 1] == t2
&& len[u][st] + len[u][t1] < deg[u]) continue;
//若边 (u, v) 和边 (u, fa) 为应该最先删和最后删的边的尾部和头部
//那么它们的长度加起来必须等于这个点的度数
//否则就是提前成了一个环，是不合法的状态
DFS1(v, u);
}
}
else
DFS1(nxt[u][fa], u);//否则只能够按照之前已经确定了的路径找
}
}
inline void merge(int u, int st, int ed)
{
int t1 = head[u][st], t2 = tail[u][ed];
nxt[u][st] = ed, pre[u][ed] = st;
for(int i = t1; i != 0 && i != N + 1; i = nxt[u][i])
head[u][i] = t1, tail[u][i] = t2;
len[u][t1] += len[u][ed];
}//将两个链表连在一起
bool DFS2(int u, int fa)
{//更新链表
//当这个函数返回 true 时则表示找到了路径
if(u == minp)
{//找到了这个数的结束点
pre[u][N + 1] = fa, nxt[u][fa] = N + 1;
//将它设为最后一条边，并设为最后删掉的边
//注意：用 N + 1 来标识最后一条边
return true;
}
int st = head[u][fa], ed = tail[u][fa];
if(fa == N + 1)
{
for(Edge *p = G[u]; p != NULL; p = p->nxt) {
int v = p->to;
int t1 = head[u][v], t2 = tail[u][v];
if(t1 != v || (pre[u][N + 1] == t2 && len[u][t1] < deg[u]))
continue;//参照 DFS1 中对应位置上的注释
if(DFS2(v, u))
{//找出正确的路径了
nxt[u][N + 1] = v, pre[u][v] = N + 1;
//将 u 标记为起始点并加入链表
return true;
}
}
}
else
{//中转点
if(fa == ed)
{//如果 u 后面并没有选到一条边，那么枚举一个点
for(Edge *p = G[u]; p != NULL; p = p->nxt)
{
int v = p->to;
int t1 = head[u][v], t2 = tail[u][v];
if(st == t1 || t1 != v || nxt[u][N + 1] == v)
continue;
if(nxt[u][N + 1] == st && pre[u][N + 1] == t2
&& len[u][st] + len[u][t1] < deg[u])
continue;
//参考 DFS1 中的对应位置注释
if(DFS2(v, u))
{
merge(u, fa, v);//这时应该将两个链表连到一起了
return true;
}
}
}
else
DFS2(nxt[u][fa], u);//按照既定路径找下去
}
return false;
}
int main()
{
#ifdef LOACL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
int _;
scanf("%d", &_);
while(_--)
{
scanf("%d", &N);
clear();
for(int i = 1; i <= N; i++)
scanf("%d", &num[i]);
for(int i = 1; i < N; i++)
{
int u, v;
scanf("%d %d", &u, &v);
addedge(u, v), addedge(v, u);
++deg[u], ++deg[v];
pre[u][v] = pre[v][u] = nxt[u][v] = nxt[v][u] = 0;
head[u][v] = tail[u][v] = v, head[v][u] = tail[v][u] = u;
len[u][v] = len[v][u] = 1;
}
if(N == 1)
{
puts("1");
continue;
}
for(int i = 1; i <= N; i++)
{
minp = N + 1;
DFS1(num[i], N + 1);
DFS2(num[i], N + 1);
printf("%d%c", minp, (i == N) ? '\n' : ' ');
}
}
return 0;
}
A、试题类型：
基本算法。
B、算法模型：
DP算法。
C、试题说明：
优化dp,发现n是优化不掉的，并且只需要k>j/2就可以了，那么其实可以将j和k压为一维dp，将式子化一下，得到：k-j/2>0
f[i][j]就可以从递推。
f[i][j]=f[i][j-1]
如果选a[i][l]，f[i][j]+=f[i-1][j+1]*a[i][l]
如果不选a[i][l]，f[i][j]+=f[i-1][j-1]*(sum[i]-a[i][l])
最后要减去的答案就是那些f[n][i](i<0)
#include<cstdio>
#include<cstring>
#include<algorithm>
#define I int
#define ll long long
#define F(i,a,b) for(I i=a;i<=b;i++)
#define Fd(i,a,b) for(I i=a;i>=b;i--)
#define mem(a,b) memset(a,b,sizeof(a))
#define N 110
#define M 998244353
using namespace std;
I n,m,x;
ll a[N][2010],f[N][N*3],ans=1,s[N];
void rd(I &x)
{
x=0;char ch=getchar();
while(ch<'0'||ch>'9')
ch=getchar();
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
}
void inc(ll &x,ll y)
{
x+=y;x-=(x/M)*M;
}
I main()
{
freopen("meal.in","r",stdin);
freopen("meal.out","w",stdout);
rd(n),rd(m);
F(i,1,n)
{
F(j,1,m)
{
rd(x);a[i][j]=x;
// s[i]+=a[i][j];
inc(s[i],a[i][j]);
}
ans=(ans*s[i]+ans)%M;
}
--ans;
F(l,1,m)
{
mem(f,0);
F(i,1,n) f[i][N]=1;
f[1][N+1]=s[1]-a[1][l],f[1][N-1]=a[1][l];
F(i,2,n)
{
F(j,-i,i)
{
f[i][N+j]=f[i-1][N+j];
inc(f[i][N+j],f[i-1][N+j+1]*a[i][l]);
inc(f[i][N+j],f[i-1][N+j-1]*(s[i]-a[i][l]));
}
}
F(i,N-n,N-1) inc(ans,-f[n][i]+M);
}
printf("%lld\n",ans);
return 0;
}
A、试题类型：
基本数据结构。
B、算法模型：
dp+单调队列优化。
C、试题说明：
注意要高精度，通过观察发现答案最多有34位，可以用两个变量模拟即可。
注意当数据类型为1时，模2^30较慢，可以改为&（2^30 -1）。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define I int
#define ll long long
#define F(i,a,b) for(I i=a;i<=b;++i)
#define Fd(i,a,b) for(I i=a;i>=b;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#define N 40000002
#define M 1000000000
#define s2 1000000000000000000
#define s1 1000000000
using namespace std;
I n,m,type,f[N],q[N],x,y,z,b1,b2,st,l,r,las=0;
ll a[N],p,ans1,ans2;
/*I rd(I &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();}
}*/
template<class T>void rd(T &x)
{
x=0;int f=0;char ch=getchar();
while(ch<'0'||ch>'9')
{
f|=(ch=='-');
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);ch=getchar();
}
x=f?-x:x;
return;
}
I main()
{
freopen("partition.in","r",stdin);
freopen("partition.out","w",stdout);
rd(n),rd(type);
if(type)
{
rd(x),rd(y),rd(z),rd(b1),rd(b2),rd(m);
a[1]=b1,a[2]=b2;
st=1073741824;
F(i,3,n) a[i]=(1LL*x*a[i-1]+1LL*y*a[i-2]+z)&(st-1);
for(int i=las=1;i<=m;++i)
{
rd(st),rd(l),rd(r);
for(int j=las;j<=st;++j) a[j]=a[j-1]+a[j]%(r-l+1)+l;
las=st+1;
}
}
else F(i,1,n)
{
rd(x);a[i]=x+a[i-1];
}
q[1]=0;l=r=1;
for(register int i=1;i<=n;++i)
{
while(l<r&&a[i]>=(a[q[l+1]]<<1)-a[f[q[l+1]]])
++l;
f[i]=q[l];
while(l<=r&&(a[i]<<1)-a[f[i]]<=(a[q[r]]<<1)-a[f[q[r]]]) --r;
q[++r]=i;
}
for(register int i=n;i;i=f[i])
{
p=a[i]-a[f[i]];
ll x=p/s1,y=p%s1;p=x*y<<1;
ans1+=x*x+p/s1,ans2+=y*y+(p%s1)*s1;
ans1+=ans2/s2,ans2%=s2;
/*t[0]=0,p=a[i]-a[f[i]];
mem(t2,0);
while(p){t[++t[0]]=p%M;p/=M;}
F(j,1,t[0]){
F(k,1,t[0]) t2[j+k-1]+=t[j]*t[k];
}
while(t2[t2[0]+1]){
I len=++t2[0];
t2[len+1]+=t2[len]/M;
t2[len]%=M;
}
F(j,1,t2[0]){
ans[j]+=t2[j];
ans[j+1]+=ans[j]/M;
ans[j]%=M;
}
while(ans[ans[0]+1]) ans[0]++;*/
}
/*printf("%lld",ans[ans[0]]);
Fd(i,ans[0]-1,1) printf("%08lld",ans[i]);*/
if(ans1)
printf("%lld%018lld\n",ans1,ans2);
else
printf("%lld\n",ans2);
return 0;
}
A、试题类型：
典型数据结构。
B、算法模型：
树。
C、试题说明：
树的重心一定在根节点的重链上，所以直接倍增跳重链，当上面的节点数小于等于total除以二就可以跳（这是重儿子的定义）。最后再判断一下跳到的点的父亲是否合法即可。
对于删除的边（记为x,y），深度大的点（记为y）可以直接按照普通找重心的方法找，而对于其余部分的重心可以从根节点同样开始跳重链，但保证不跳进删除的边深度较大的点所在的子树(y的子树内)，这个可以用dfs序实现，而当跳到了x这个点时，那么就跳它的次重儿子再继续跳重儿子即可。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define I int
#define ll long long
#define F(i,a,b) for(I i=a;i<=b;i++)
#define Fd(i,a,b) for(I i=a;i>=b;i--)
#define mem(a,b) memset(a,b,sizeof(a))
#define N 300010
using namespace std;
I T,n,x[N],y[N],t[N*2],nx[N*2],l[N],sz[N],f[N],cs[N],top[N],st[N],ed[N],cnt,tot;
I s[N][20];
ll ans;
void rd(I &x)
{
x=0;char ch=getchar();
while(ch<'0'||ch>'9')
ch=getchar();
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';ch=getchar();
}
}
void add(I x,I y)
{
t[++tot]=y;nx[tot]=l[x];l[x]=tot;
}
void dg(I x,I y)
{
s[x][0]=-1;sz[x]=1;st[x]=++cnt;I z;
for(I k=l[x];k;k=nx[k])
if(t[k]!=y)
{
f[z=t[k]]=x;
dg(z,x);
sz[x]+=sz[z];
if(s[x][0]==-1||sz[z]>sz[s[x][0]])
{
if(s[x][0]!=-1)
cs[x]=s[x][0];
s[x][0]=z;
}
else if(sz[z]>sz[cs[x]])
cs[x]=z;
}
ed[x]=++cnt;
}
void work(I x)
{
Fd(i,19,0) if(tot-sz[s[x][i]]<=tot/2) x=s[x][i];
ans+=x+f[x]*(sz[x]==tot/2);
}
void jump(I x,I y)
{
Fd(i,19,0){
if(s[x][i]<1||st[s[x][i]]>=st[y]&&st[s[x][i]]<=ed[y])
continue;
if(st[y]>st[s[x][i]]&&ed[y]<ed[s[x][i]])
{
if(n-sz[s[x][i]]<=tot/2)
x=s[x][i];
}
else{if(tot-sz[s[x][i]]<=tot/2) x=s[x][i];}
}
if(tot-sz[cs[x]]<=tot/2)
{
work(cs[x]);
return;
}
if(st[y]>st[x]&&ed[y]<ed[x])
{
ans+=x*(n-sz[x]<=tot/2)+f[x]*(sz[x]-sz[y]<=tot/2);
}
else
{
ans+=x*(tot-sz[x]<=tot/2)+f[x]*(sz[x]<=tot/2);
}
}
I main()
{
freopen("centroid.in","r",stdin);
freopen("centroid.out","w",stdout);
rd(T);
while(T--)
{
rd(n);
tot=ans=cnt=0;
mem(l,0);
mem(nx,0);
mem(s,0);//重儿子倍增数组
mem(cs,0);//次重儿子
F(i,1,n-1)
{
rd(x[i]),rd(y[i]);
add(x[i],y[i]);add(y[i],x[i]);
}
dg(1,0);
F(j,1,19)
{
F(i,1,n) if(s[i][j-1]!=-1) s[i][j]=s[s[i][j-1]][j-1];
}
//预处理
F(i,1,n-1)
{//枚举边
if(st[x[i]]>st[y[i]]) swap(x[i],y[i]);
tot=sz[y[i]];
work(y[i]);
tot=n-sz[y[i]];
jump(1,y[i]);
}
printf("%lld\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、微信公众号：
添加微信，获取资料。
关注公众号，获取动态。
