开题顺序 3-2-1-4，感觉这套题挺草的。
T1 染色(color)
将限制看成边。
考虑质数集中只有一个偶质数 \(2\)，只考虑这条限制，对 \(i\to i+2\) 连边，发现是两条不相交的链，一条上的数都是奇数，另一条则都是偶数。对于一条链只需要使用两种颜色。
然后其他的质数都是奇数，则其他限制一定是从一条链指向另一条链，则只要一条链颜色集为 \(\{1,3\}\)，另一条为 \(\{2,4\}\)，就永远不会出现冲突。
发现 \(n\leq 6\) 最优答案 \(<4\)，特殊处理即可；\(n>6\) 直接输出 \((i-1)\bmod 4+1\)。
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=1e4+10;
int n;
int main()
{
freopen("color.in","r",stdin);
freopen("color.out","w",stdout);
cin.tie(0),cout.tie(0);
ios::sync_with_stdio(0);
cin>>n;
if(n<=6)
{
if(n==1) cout<<1<<endl<<"1"<<endl;
if(n==2) cout<<1<<endl<<"1 1"<<endl;
if(n==3) cout<<2<<endl<<"1 1 2"<<endl;
if(n==4) cout<<2<<endl<<"1 1 2 2"<<endl;
if(n==5) cout<<3<<endl<<"1 1 2 2 3"<<endl;
if(n==6) cout<<3<<endl<<"1 1 2 2 3 3"<<endl;
}
else
{
cout<<4<<endl;
for(register int i=1;i<=n;++i)
cout<<(i-1)%4+1<<' ';
cout<<endl;
}
return 0;
}
开题时一下就注意到只有一个偶质数，但没想到解法，后面写完 T2 突然想到了。
T2 序列(array)
考虑 \(k=0\)。
此时肯定是优先使得小的 \(a_i\) 对应的 \(b_i\) 尽可能大。于是乎先将 \(a\) 升序排序，从小到大枚举，每次使 \(b_i\gets min(n,\lfloor\dfrac{D}{a_i}\rfloor),D\gets D-a_ib_i\)。记 \(f(n,D)\) 为 \(b_i\leq n,\sum\limits_{i=1}^{n} a_ib_i\leq D\) 时最大的答案。
当 \(k\not=0\)，令 \(\min\limits_{i=1}^{m} b_i=x,S=\sum\limits_{i=1}^{m} a_i\)，也就是说先让每个 \(b_i=x\)。这种情况下贡献为 \(xm+kx+f(n-x,D-xS)\)。
感性理解发现是单峰函数，三分求解，\(x\) 取值范围 \([0,min(n,\lfloor\dfrac{D}{S}\rfloor)]\)。
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=2e5+10;
int T,n,m,k,a[MAXN],sum;
long long d;
inline long long f(long long x)
{
long long D=d-x*sum,ans=x*(k+m);
for(register int i=1;i<=m;++i)
{
long long K=min(D/a[i],1ll*n-x);
ans+=K,D-=K*a[i];if(!K) break;
}
return ans;
}
int main()
{
cin.tie(0),cout.tie(0);
ios::sync_with_stdio(0);
cin>>T;
while(T--)
{
cin>>n>>m>>k>>d;sum=0;
for(register int i=1;i<=m;++i)
cin>>a[i],sum+=a[i];
sort(a+1,a+1+m);
int l=0,r=min(1ll*n,d/sum);long long ans=0;
while(l<r)
{
int lmid=l+(r-l)/3,rmid=r-(r-l)/3;
ans=max(ans,max(f(lmid),f(rmid)));
(f(lmid)<f(rmid))?l=lmid+1:r=rmid-1;
}
cout<<f(l)<<endl;
}
return 0;
}
赛时写了二分，但函数值不一定不等，所以寄了。幸好加了特判暴力，只挂了 5pts。
T3 树上询问(query)
感觉挺一眼的，5k 说应该放 T1，臣附议。
记 \(L=lca(l,r)\)，典的不能再典的套路将路径拆成 \(l\to L,L\to r\) 两部分。
第一部分 \(x\) 满足条件等价于 \(dep_{l}-dep_{x}=x\)；第二部分 \(x\) 满足条件等价于 \((dep_{l}-dep_{L})+(dep_{x}-dep_{L})=x\)。与 \(x\) 相关的值不变，故移到一边，变为 \(dep_{l}=x+dep_{x}\) 和 \(dep_{l}-2dep_{L}=x-dep_{x}\)。查询变为路径上等于某个值的数的个数，可以离线树上前缀和或在线树上主席树。
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int MAXN=3e5+10,MAXT=6.5e6+10;
int n,m,fa[MAXN],f[MAXN][20],dep[MAXN];
vector <int> v[MAXN];
struct tree
{
int root[MAXN],cnt,t[MAXT],ls[MAXT],rs[MAXT],L,R;
inline void push_up(int p){t[p]=t[ls[p]]+t[rs[p]];return ;}
void change(int l,int r,int p,int q,int x)
{
if(l==r){t[q]=t[p]+1;return ;}
int mid=(l+r)>>1;ls[q]=ls[p],rs[q]=rs[p];
if(x<=mid) change(l,mid,ls[p],ls[q]=++cnt,x);
else change(mid+1,r,rs[p],rs[q]=++cnt,x);
push_up(q);return ;
}
int query(int l,int r,int p,int x)
{
if(x<l||x>r) return 0;
if(l==r) return t[p];
int mid=(l+r)>>1;
if(x<=mid) return query(l,mid,ls[p],x);
else return query(mid+1,r,rs[p],x);
}
inline void upd(int x,int z)
{
root[x]=++cnt;
change(L,R,root[fa[x]],root[x],z);
return ;
}
inline int Q(int x,int y,int z)
{return query(L,R,root[x],z)-query(L,R,root[y],z);}
}a,b;
void dfs(int x)
{
dep[x]=dep[fa[x]]+1,f[x][0]=fa[x];
for(register int i=1;i<=__lg(dep[x]);++i)
f[x][i]=f[f[x][i-1]][i-1];
a.upd(x,dep[x]+x),b.upd(x,x-dep[x]);
for(int y:v[x]) if(y!=fa[x]) fa[y]=x,dfs(y);
return ;
}
inline int lca(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
while(dep[x]>dep[y]) x=f[x][__lg(dep[x]-dep[y])];
if(x==y) return x;
for(register int i=__lg(dep[x]);i>=0;--i)
if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
return f[x][0];
}
int main()
{
freopen("query.in","r",stdin);
freopen("query.out","w",stdout);
cin.tie(0),cout.tie(0);
ios::sync_with_stdio(0);
cin>>n>>m;
a.L=2,a.R=n<<1,b.L=1-n,b.R=n-1;
for(register int i=1;i<n;++i)
{
int x,y;cin>>x>>y;
v[x].push_back(y),v[y].push_back(x);
}
dfs(1);
for(register int i=1;i<=m;++i)
{
int l,r,L,ans=0;cin>>l>>r;L=lca(l,r);
ans+=a.Q(l,fa[L],dep[l]);
ans+=b.Q(r,L,dep[l]-(dep[L]<<1));
cout<<ans<<endl;
}
return 0;
}
主席树多个 \(\log\)，好像有点傻。
T4 网络(network)
感觉这题是唯一一道有意义的难点的题，还挺神的，但题解还挺烂的，看了 Chen_jr 学长的题解，膜拜。
将每次操作抽象出来，就是限制 \(x,y\) 不能同时带电。
发现仅要求 \(\ge\lfloor\dfrac{n}{2}\rfloor\) 根电线有电，考虑两两分组，定义一个二元组 \((x,y)\)，这两个点中只有任意一个点带电。初始时随意的两两配对。
考虑一组操作 \(x_i,y_i\)，假设现在情况是 \((x_i,p_{x_i}),(y_i,p_{y_i})\)，我们要重新配对为 \((x_i,y_i),(p_{x_i},p_{y_i})\)，这样肯定是可以符合定义的。
最后对于每一组中任意选定一个点带电，答案一定满足条件。
考虑如何输出方案，我们从后往前处理，相当于与原来相反。即对于一组操作 \(x_i,y_i\)，现在情况是 \((x_i,y_i),(p_{x_i},p_{y_i})\)，我们要重新配对为 \((x_i,p_{x_i}),(y_i,p_{y_i})\)。我们知道 \(x_i,y_i\) 不能同时带电，但是其中任意一个点都可能带电，这满足我们二元组的定义。所以如果 \(y_i\) 带电这条边就是 \(1\)，否则是 \(0\)。
然后发现尽管进行这次操作后我们确定了带电的是哪个点，但是在这次操作前，\(x_i,y_i\) 这两个点中，原来是哪个点带电都可以。所以我们重新配对为 \((x_i,p_{x_i}),(y_i,p_{y_i})\) 时，如果 \(p_{x_i}\) 带电，那么带电的就是 \(y_i\)，否则是 \(x_i\)。这样倒推回去也是随时符合定义。
//这题写了点注释
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=5e5+10,MAXM=5e6+10;
int n,m,x[MAXM],y[MAXM],p[MAXN],ans[MAXM];
int opx[MAXM],opy[MAXM];bool b[MAXN];
int main()
{
#ifdef ONLINE_JUDGE
freopen("network.in","r",stdin);
freopen("network.out","w",stdout);
cin.tie(0),cout.tie(0);
ios::sync_with_stdio(0);
#endif
cin>>n>>m;
for(register int i=1;i<=n;++i)
{
if(i&1) p[i]=(i+1<=n)?i+1:0;
else p[i]=(i-1);
}
if(n&1) p[0]=n;//n 为奇数就放个 0 进去
for(register int i=1;i<=m;++i)
{
cin>>x[i]>>y[i];
//opx[i] 指在进行第 i 个操作前的 p[x]，opy[i] 同理
opx[i]=p[x[i]],opy[i]=p[y[i]];
p[x[i]]=y[i],p[y[i]]=x[i];
p[opx[i]]=opy[i],p[opy[i]]=opx[i];
}
//随意钦定，这里判断大于可以保证只选一个点
for(register int i=1;i<=n;++i) if(i>p[i]) b[i]=true;
for(register int i=m;i;--i)
{
if(b[y[i]]) ans[i]=1;
if(!b[opx[i]]) b[x[i]]=true,b[y[i]]=false;
if(!b[opy[i]]) b[y[i]]=true,b[x[i]]=false;
p[x[i]]=opx[i],p[y[i]]=opy[i];
p[opx[i]]=x[i],p[opy[i]]=y[i];
}
cout<<"YES"<<endl;
for(register int i=1;i<=m;++i) cout<<ans[i];
cout<<endl;return 0;
}
考场写了个很奇怪的东西，暴力分都没拿到。话说这题应该很难场切吧。