| A | B | C | D | Sum | Rank |
|---|---|---|---|---|---|
| 10 | - | 75 | 20 | 105 | 16/24 |
A. 染色(color)
考虑奇偶性染色，于是就满足了所有奇质数的限制。但是由于有 \(2\) 的存在，所以需要每四个染一个色。考虑 \(1,3,6,8\) 每两个数之差都是质数，因此 \(n\ge8\) 时答案不可能小于 \(4\)。\(n<8\) 时打表打出来即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int ans[9][9]={{},
{1,1},
{1,1,1},
{2,1,1,2},
{2,1,1,2,2},
{3,1,1,2,2,3},
{3,1,1,2,2,3,3},
{4,1,1,2,2,3,3,4}};
int n;
int main(){freopen("color.in","r",stdin);freopen("color.out","w",stdout);ios::sync_with_stdio(0),cin.tie(0);cin>>n;if(n<=7){cout<<ans[n][0]<<'\n';for(int i=1;i<=n;i++){cout<<ans[n][i]<<' ';}}else{cout<<4<<'\n';for(int i=1;i<=n;i++){cout<<(i+3)%4+1<<' ';}}return 0;
}
}
int main(){return asbt::main();}
B. 序列(array)
C. 树上询问(query)
只考虑 \(u\to\operatorname{lca}(u,v)\) 的部分，另一部分类似。
答案要求这条路径上 \(dep_u-dep_x=x\) 的 \(x\) 的数量，也就是 \(x+dep_x=dep_u\)。考虑差分，用 \(u\) 的根链减去 \(fa_{\operatorname{lca}(u,v)}\) 的根链即可，用主席树维护就好了。时间复杂度 \(O(n\log n)\)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pb push_back
using namespace std;
namespace asbt{
const int maxn=3e5+5;
int n,m,dep[maxn],fa[maxn];
vector<int> e[maxn];
namespace LCA{int cnt,dfn[maxn],oula[maxn<<1],idx[maxn<<1];il void dfs(int u,int fth){dfn[u]=++cnt,oula[cnt]=cnt;idx[cnt]=u,fa[u]=fth;dep[u]=dep[fth]+1;for(int v:e[u]){if(v==fth){continue;}dfs(v,u);oula[++cnt]=dfn[u];}}struct{int Log[maxn<<1],st[maxn<<1][22];il void init(){for(int i=2;i<=cnt;i++){Log[i]=Log[i>>1]+1;}for(int i=1;i<=cnt;i++){st[i][0]=oula[i];}for(int j=1;j<=Log[cnt];j++){for(int i=1;i+(1<<j)-1<=cnt;i++){st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);}}}il int query(int l,int r){int p=Log[r-l+1];return min(st[l][p],st[r-(1<<p)+1][p]);}}ST;il void init(){dfs(1,0),ST.init();}il int lca(int u,int v){if(dfn[u]>dfn[v]){swap(u,v);}return idx[ST.query(dfn[u],dfn[v])];}il int dis(int u,int v){return dep[u]+dep[v]-dep[lca(u,v)]*2;}
}
using LCA::lca;
using LCA::dis;
struct{int tot,rt[maxn],ls[maxn*24],rs[maxn*24],sum[maxn*24];il void pushup(int id){sum[id]=sum[ls[id]]+sum[rs[id]];}il void insert(int &p,int q,int l,int r,int x){if(!p){p=++tot;}if(l==r){sum[p]=sum[q]+1;return ;}int mid=(l+r)>>1;if(x<=mid){rs[p]=rs[q];insert(ls[p],ls[q],l,mid,x);}else{ls[p]=ls[q];insert(rs[p],rs[q],mid+1,r,x);}pushup(p);}il int query(int id,int l,int r,int x){if(!id){return 0;}if(l==r){return sum[id];}int mid=(l+r)>>1;return x<=mid?query(ls[id],l,mid,x):query(rs[id],mid+1,r,x);}il void insert(int u,int x){insert(rt[u],rt[fa[u]],-6e5,6e5,x);}il int query(int u,int x){return query(rt[u],-6e5,6e5,x);}
}S1,S2;
il void dfs(int u,int fa){S1.insert(u,u+dep[u]);S2.insert(u,u-dep[u]);for(int v:e[u]){if(v==fa){continue;}dfs(v,u);}
}
int main(){freopen("query.in","r",stdin);freopen("query.out","w",stdout);ios::sync_with_stdio(0),cin.tie(0);cin>>n>>m;for(int i=1,u,v;i<n;i++){cin>>u>>v;e[u].pb(v),e[v].pb(u);}LCA::init(),dfs(1,0);while(m--){int u,v;cin>>u>>v;int w=lca(u,v),k=dis(u,v)-dep[v];cout<<S1.query(u,dep[u])-S1.query(fa[w],dep[u])+S2.query(v,k)-S2.query(w,k)<<'\n';}return 0;
}
}
int main(){return asbt::main();}