8.19 CSP 模拟 25
给我一首歌的时间 - 周杰伦
雨淋湿了天空 毁得很讲究
你说你不懂 为何在这时牵手
我晒干了沉默 悔得很冲动
就算这是做错 也只是怕错过
在一起叫梦 分开了叫痛
是不是说 没有做完的梦最痛
迷路的后果 我能承受
这最后的出口 在爱过了才有
能不能给我一首歌的时间
紧紧的把那拥抱变成永远
在我的怀里你不用害怕失眠
哦 如果你想忘记我也能失忆
能不能给我一首歌的时间
把故事听到最后才说再见
你送我的眼泪 让它留在雨天
哦 越过你划的线我定了勇气 的终点
雨淋湿了天空 毁得很讲究
你说你不懂 我为何在这时牵手
我晒干了沉默 悔得很冲动
就算这是做错 也只是怕错过
在一起叫梦 分开了叫痛
是不是说 没有做完的梦最痛
迷路的后果 我能承受
这最后的出口 在爱过了才有
能不能给我一首歌的时间
紧紧的把那拥抱变成永远
在我的怀里你不用害怕失眠
哦 如果你想忘记我也能失忆
能不能给我一首歌的时间
把故事听到最后才说再见
你送我的眼泪 让它留在雨天
哦 越过你划的线我定了勇气 的终点
哦 你说我不该不该
不该在这时候说了我爱你
要怎么证明我没有说谎的力气
哦 请告诉我 暂停算不算放弃
我只有一天的回忆
能不能给我一首歌的时间
紧紧的把那拥抱变成永远
在我的怀里你不用害怕失眠
哦 如果你想忘记我也能失忆
能不能给我一首歌的时间
哦 把故事听到最后才说再见
你送我的眼泪 让它留在雨天
哦 越过你划的线我定了勇气 的终点
你说我不该不该
不该在这时说了爱你
要怎么证明我没力气
告诉我暂停算不算放弃
你说我不该不该
不该在这时才说爱你
要怎么证明我没有力气
我只有一天的回忆
\(\text{happyguy round}\)
去年 CSP 石家庄隔离期间的沈老师信心赛。
原 T4 是另一道 Pjudge 的题。
T1 炒币
原题：AtCoder-ARC128A Gold and Silver
正常 DP 转移是朴素的，但是乘除太大会计算不了，由于只比较大小不求结果，取 \(\ln\) 改成加减计算。
点击查看代码
int n;
int a[maxn];
db f[maxn][2];
int pre[maxn][2];
int st[maxn],top;
int main(){
n=read();
for(int i=1;i<=n;++i) a[i]=read();
for(int i=0;i<=n;++i) f[i][0]=f[i][1]=-1e10;
f[0][0]=0;
for(int i=1;i<=n;++i){
if(f[i-1][0]>f[i-1][1]-log(a[i])) f[i][0]=f[i-1][0],pre[i][0]=0;
else f[i][0]=f[i-1][1]-log(a[i]),pre[i][0]=1;
if(f[i-1][1]>f[i-1][0]+log(a[i])) f[i][1]=f[i-1][1],pre[i][1]=0;
else f[i][1]=f[i-1][0]+log(a[i]),pre[i][1]=1;
}
int now=0;
for(int i=n;i>=1;--i){
st[++top]=pre[i][now];
now^=pre[i][now];
}
for(int i=top;i>=1;--i) printf("%d ",st[i]);
printf("\n");
return 0;
}
T2 凑数
按性价比排序，如果每次增加 \(1\) 不是最劣的，那么只用前两种一定可以凑出 \(n\)。
否则就是形如 \(Ai+Bj+k=n\)，其中 \(A\) 的性价比优于 \(B\)，那么 \(j\in [0,A)\)，同时 \(i\in \left[0,\left\lfloor\frac{n}{A}\right\rfloor\right]\)，可以根号分治，枚举其中一个，最后用 \(1\) 补齐。
点击查看代码
int t;
int n;
pii P[4];
ll ans;
int main(){
t=read();
while(t--){
n=read();
P[1].fir=1,P[2].fir=read(),P[3].fir=read();
P[1].sec=read(),P[2].sec=read(),P[3].sec=read();
sort(P+1,P+4,[&](pii A,pii B){
return 1ll*A.fir*B.sec>1ll*B.fir*A.sec;
});
ans=llinf;
if(P[1].fir==1) ans=1ll*n*P[1].sec;
else if(P[2].fir==1) ans=1ll*(n/P[1].fir)*P[1].sec+1ll*(n%P[1].fir)*P[2].sec;
else{
if(P[1].fir<=31625){
for(int j=0;j<P[1].fir;++j){
if(1ll*j*P[2].fir>n) break;
ll now=1ll*j*P[2].sec+1ll*((n-j*P[2].fir)/P[1].fir)*P[1].sec+1ll*((n-j*P[2].fir)%P[1].fir)*P[3].sec;
ans=min(ans,now);
}
}
else{
for(int i=0;i<=n/P[1].fir;++i){
ll now=1ll*i*P[1].sec+1ll*((n-i*P[1].fir)/P[2].fir)*P[2].sec+1ll*((n-i*P[1].fir)%P[2].fir)*P[3].sec;
ans=min(ans,now);
}
}
}
printf("%lld\n",ans);
}
return 0;
}
T3 同构
原题：CodeForces-698F Coprime Permutation *3000
肯定能意识到如果质因子集合相同的数可以互换，略微打表发现 \(n=3\) 时 \(\{1,3\}\) 可以互换，\(n=7\) 时 \(\{1,5,7\}\) 可以互换，但 \(\{1,3\}\) 不能互换了。
如果能打表打到 \(n=14\)，那么这题应该就做出来了，会发现 \(\{10,14\}\) 也可以互换，但是一个特点是 \(\{10,14\}\) 互换时 \(\{5,7\}\) 也互换了，类似一个整体互换。而这个互换到 \(n=15\) 又不复存在。
可以猜想出两个互换：质因子集合相同的数集，以及倍数个数相同的质数倍数集。
前者证明比较显然，这题是不要知道具体次数的，质因子集合有交无交是判断依据，因此质因子集合相同的能任一互换。
后者证明可以这样考虑，\(p\) 的倍数之间发生的互换属于第一类互换，例如 \(n=52\) 时 \(\{26,52\}\) 可以互换，而两个质因数 \(p_1,p_2\) 倍数集合的的任意两个元素，他们质因子集合的交一定和 \(p_1,p_2\) 无关，而第一类互换和此时的整体互换都保证了除去 \(p_1,p_2\) 的质因子集合相同，那么没有影响。至于和其他不在集合内数，发现质因子集合的交也是和 \(p\) 无关的。
第一类互换每个数一定只在一个集合内出现，第二类也有这样的保证，因为事实上一定有 \(p\ge \sqrt{n}\)，若 \(p<\sqrt{n}\)，那么 \(\left\lfloor\frac{n}{p}\right\rfloor\) 互不相同，也就是每个数只会作为最大质因子的倍数出现。
点击查看代码
int n;
int fact[maxn];
int pr[maxn],mn[maxn];
int cnt1[maxn],cnt2[maxn];
int ans;
inline void solve(){
fact[0]=1;
for(int i=1;i<=n;++i) fact[i]=1ll*fact[i-1]*i%mod;
for(int i=2;i<=n;++i){
if(!mn[i]) pr[++pr[0]]=i,mn[i]=i;
for(int j=1;i*pr[j]<=n&&j<=pr[0];++j){
mn[i*pr[j]]=pr[j];
if(i%pr[j]==0) break;
}
}
for(int i=2;i<=n;++i){
int now=i,S=1,tmp;
while(now!=1){
S*=mn[now],tmp=mn[now],now/=mn[now];
while(mn[now]==tmp) now/=tmp;
}
++cnt1[S];
}
++cnt2[1];
for(int i=2;i<=pr[0];++i) ++cnt2[n/pr[i]];
ans=1;
for(int i=1;i<=n;++i){
ans=1ll*ans*fact[cnt1[i]]%mod*fact[cnt2[i]]%mod;
}
printf("%d\n",ans);
}
int main(){
n=read();
solve();
return 0;
}
原题区别在于限制了一些位置的值。
判断合法就是判断第一类互换质因子集合是否相同，第二类互换最大质因子的倍数个数是否相同、除去最大质因子后质因子集合是否相同以及整体互换是否矛盾。
计算答案可以先求出没有限制的答案，遇到一个限制就计数器作更改。
点击查看代码
int n;
int fact[maxn],inv_fact[maxn];
int p[maxn];
int pr[maxn],mn[maxn],mx[maxn];
int S[maxn];
int cnt1[maxn],cnt2[maxn];
int nxt[maxn];
int ans;
inline void linear_sieve(){
fact[0]=1,inv_fact[0]=1;
for(int i=1;i<=n;++i) fact[i]=1ll*fact[i-1]*i%mod;
inv_fact[n]=q_pow(fact[n],mod-2,mod);
for(int i=n-1;i>=1;--i) inv_fact[i]=1ll*inv_fact[i+1]*(i+1)%mod;
mn[1]=mx[1]=1;
for(int i=2;i<=n;++i){
if(!mn[i]) pr[++pr[0]]=i,mn[i]=i;
for(int j=1;i*pr[j]<=n&&j<=pr[0];++j){
mn[i*pr[j]]=pr[j];
if(i%pr[j]==0) break;
}
}
for(int i=2;i<=n;++i){
int now=i,tmp;
S[i]=1;
while(now!=1){
S[i]*=mn[now],tmp=mn[now],now/=mn[now];
while(mn[now]==tmp) now/=tmp;
}
++cnt1[S[i]];
}
++cnt2[1];
for(int i=1;i<=pr[0];++i){
++cnt2[n/pr[i]];
for(int j=1;pr[i]*j<=n;++j){
mx[pr[i]*j]=max(mx[pr[i]*j],pr[i]);
}
}
}
int main(){
n=read();
for(int i=1;i<=n;++i) p[i]=read();
linear_sieve();
for(int i=1;i<=n;++i){
if(!p[i]) continue;
// 特判 1 的情况
if(i==1&&p[1]==1) --cnt2[1];
else if(i==1){
if(mn[p[i]]!=p[i]||n/p[i]>1) return printf("0\n"),0;
--cnt2[1];
}
else if(p[i]==1){
if(mn[i]!=i||n/i>1) return printf("0\n"),0;
--cnt2[1];
}
else{
// 不合法情况分为 第二类互换不在同一集合，第二类互换除去 p 后 S 集合不同，第二类互换出现矛盾
if(S[i]==S[p[i]]){
if(nxt[mx[i]]&&nxt[mx[i]]!=mx[i]) return printf("0\n"),0;
--cnt1[S[i]];
if(!nxt[mx[i]]) --cnt2[n/mx[i]],nxt[mx[i]]=mx[i];
}
else{
if(n/mx[i]!=n/mx[p[i]]) return printf("0\n"),0;
if(S[i/mx[i]]!=S[p[i]/mx[p[i]]]) return printf("0\n"),0;
if(nxt[mx[p[i]]]&&nxt[mx[p[i]]]!=mx[i]) return printf("0\n"),0;
--cnt1[S[i]];
if(!nxt[mx[p[i]]]) --cnt2[n/mx[i]],nxt[mx[p[i]]]=mx[i];
}
}
}
ans=1;
for(int i=1;i<=n;++i){
ans=1ll*ans*fact[cnt1[i]]%mod*fact[cnt2[i]]%mod;
}
printf("%d\n",ans);
return 0;
}
T4 最近公共祖先
考虑一个节点什么时候一定可以作为 \(u\) 与一个节点的 \(\mathrm{LCA}\)，答案是这个节点有至少两棵子树有黑色节点。
不妨用线段树对 DFS 序维护所有至少两棵子树有黑色节点的节点的权值最大值，再用两个 set 分别维护只有一棵子树或没有子树有黑色节点的节点，子树内节点每次产生贡献时，暴力把修改范围内只有一棵子树或没有子树有黑色节点的从 set 移动到线段树或是另一个 set，均摊 \(O(n)\) 次操作。
现在要思考的是如何不重复的把新的黑色节点 \(u\) 贡献到父亲中。我们实际要找到最深的节点 \(f\) 使得其子树内对父亲产生过贡献，那么 \(u\) 可以产生的贡献是沿到根据路径上节点一直到 \(f\)（\(f\) 的儿子并未对 \(f\) 产生过贡献）。
不妨对每条重链开树状数组，每次跳重链可以先判断这条链上有无要求的 \(f\)，如果有那么在上面二分，单次复杂度 \(O(\log^2 n)\)。修改直接暴力修改，显然这样操作也是均摊 \(O(n)\) 次的。
这样查询答案时，先在线段树查询到根路径上最大值。考虑只有一棵子树有黑色节点的祖先能不能作为 \(\mathrm{LCA}\)，事实上也只有最深的祖先可能有贡献，只需要判断这个祖先的儿子有没有对其产生贡献，依旧使用刚才的树状数组。
时间复杂度 \(O(n\log^2 n)\)。
点击查看代码
int n,m;
int w[maxn];
struct edge{
int to,nxt;
}e[maxn<<1];
int head[maxn],cnt;
inline void add_edge(int u,int v){
e[++cnt].to=v,e[cnt].nxt=head[u],head[u]=cnt;
e[++cnt].to=u,e[cnt].nxt=head[v],head[v]=cnt;
}
int fa[maxn],dep[maxn],siz[maxn],son[maxn];
int top[maxn],ed[maxn],dfn[maxn],dfncnt,id[maxn];
set<int> S0,S1;
void dfs1(int u,int f,int d){
fa[u]=f,dep[u]=d,siz[u]=1;
int maxson=-1;
for(int i=head[u],v;i;i=e[i].nxt){
v=e[i].to;
if(v==f) continue;
dfs1(v,u,d+1);
siz[u]+=siz[v];
if(siz[v]>maxson) son[u]=v,maxson=siz[v];
}
}
void dfs2(int u,int t){
top[u]=t,ed[t]=u,dfn[u]=++dfncnt,id[dfncnt]=u;
S0.insert(dfn[u]);
if(!son[u]) return;
dfs2(son[u],t);
for(int i=head[u],v;i;i=e[i].nxt){
v=e[i].to;
if(v==fa[u]||v==son[u]) continue;
dfs2(v,v);
}
}
struct BinaryIndexTree{
#define lowbit(x) (x&-x)
int siz;
vector<int> sum;
inline void build(int k){
siz=k;
sum.resize(k+1);
}
inline void update(int x){
while(x<=siz){
++sum[x];
x+=lowbit(x);
}
}
inline int query_prefix(int x){
int res=0;
while(x){
res+=sum[x];
x-=lowbit(x);
}
return res;
}
inline int query_range(int l,int r){
return query_prefix(r)-query_prefix(l-1);
}
#undef lowbit
}B[maxn];
struct SegmentTree{
#define mid ((l+r)>>1)
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
int mx[maxn<<2];
inline void push_up(int rt){
mx[rt]=max(mx[rt<<1],mx[rt<<1|1]);
}
void build(int rt,int l,int r){
if(l==r) return mx[rt]=-1,void();
build(lson),build(rson);
push_up(rt);
}
void update(int rt,int l,int r,int p){
if(l==r) return mx[rt]=w[id[p]],void();
if(p<=mid) update(lson,p);
else update(rson,p);
push_up(rt);
}
int query(int rt,int l,int r,int pl,int pr){
if(pl<=l&&r<=pr) return mx[rt];
int res=-1;
if(pl<=mid) res=max(res,query(lson,pl,pr));
if(pr>mid) res=max(res,query(rson,pl,pr));
return res;
}
#undef mid
#undef lson
#undef rson
}S2;
inline void update(int u){
if(!B[0].query_range(dfn[u],dfn[u]+siz[u]-1)){
int x=u;
while(x){
if(B[top[x]].query_range(1,dfn[x]-dfn[top[x]]+1)){
int l=1,r=dfn[x]-dfn[top[x]]+1,f;
while(l<=r){
int mid=(l+r)>>1;
if(B[top[x]].query_range(mid,dfn[x]-dfn[top[x]]+1)) f=id[dfn[top[x]]+mid-1],l=mid+1;
else r=mid-1;
}
set<int>::iterator it=S1.lower_bound(dfn[f]),tmp;
while(it!=S1.end()){
if((*it)>dfn[x]) break;
S2.update(1,1,n,(*it));
tmp=it,++it;
S1.erase(tmp);
}
it=S0.lower_bound(dfn[f]);
while(it!=S0.end()){
if((*it)>dfn[x]) break;
S1.insert((*it));
tmp=it,++it;
S0.erase(tmp);
}
for(int i=dfn[f]+1;i<=dfn[x];++i) B[top[x]].update(i-dfn[top[x]]+1);
break;
}
else{
set<int>::iterator it=S1.lower_bound(dfn[top[x]]),tmp;
while(it!=S1.end()){
if((*it)>dfn[x]) break;
S2.update(1,1,n,(*it));
tmp=it,++it;
S1.erase(tmp);
}
it=S0.lower_bound(dfn[top[x]]);
while(it!=S0.end()){
if((*it)>dfn[x]) break;
S1.insert((*it));
tmp=it,++it;
S0.erase(tmp);
}
for(int i=dfn[top[x]];i<=dfn[x];++i) B[top[x]].update(i-dfn[top[x]]+1);
}
x=fa[top[x]];
}
}
B[0].update(dfn[u]);
S2.update(1,1,n,dfn[u]);
set<int>::iterator it=S0.lower_bound(dfn[u]);
if(it!=S0.end()&&(*it)==dfn[u]) S0.erase(it);
it=S1.lower_bound(dfn[u]);
if(it!=S1.end()&&(*it)==dfn[u]) S1.erase(it);
}
inline int query(int u){
int res=-1;
if(B[0].query_range(dfn[u],dfn[u]+siz[u]-1)) res=w[u];
int x=u;
while(x){
res=max(res,S2.query(1,1,n,dfn[top[x]],dfn[x]));
x=fa[top[x]];
}
x=u;
int tmp;
while(x){
set<int>::iterator it=S1.lower_bound(dfn[top[x]]);
if(it!=S1.end()&&(*it)<=dfn[x]){
it=S1.upper_bound(dfn[x]);
--it;
tmp=((*it)==dfn[x])?tmp:id[(*it)+1];
if(!B[top[tmp]].query_range(dfn[tmp]-dfn[top[tmp]]+1,dfn[tmp]-dfn[top[tmp]]+1)) res=max(res,w[id[(*it)]]);
break;
}
tmp=top[x],x=fa[top[x]];
}
return res;
}
char opt[10];
int main(){
n=read(),m=read();
for(int i=1;i<=n;++i) w[i]=read();
for(int i=1,u,v;i<n;++i){
u=read(),v=read();
add_edge(u,v);
}
dfs1(1,0,0);
dfs2(1,1);
S2.build(1,1,n);
B[0].build(n);
for(int u=1;u<=n;++u){
if(top[u]!=u) continue;
B[u].build(dep[ed[u]]-dep[u]+1);
}
for(int i=1;i<=m;++i){
scanf("%s",opt);
int u=read();
if(opt[0]=='M') update(u);
else printf("%d\n",query(u));
}
return 0;
}
正解是考虑每次对子树取 \(\max\)，暴力枚举祖先 \(f\)，每次把 \(f\) 除去 \(u\) 所在子树的部分取 \(\max\)，如果此时 \(f\) 内已经有黑色节点，那么后续的操作都是重复操作，这样均摊 \(O(n)\) 次操作。
这样只需要区间取 \(\max\) 单点查询，复杂度 \(O(n\log n)\)。