8.24 CSP 模拟 29
I Want to Break Free - Queen
I want to break free
I want to break free
I want to break free from your lies
You're so self satisfied I don't need you
I've got to break free
God knows, God knows I want to break free
I've fallen in love
I've fallen in love for the first time
And this time I know it's for real
I've fallen in love yeah
God knows God knows I've fallen in love
It's strange but it's true
I can't get over the way you love me like you do
But I have to be sure
When I walk out that door
Oh how I want to be free baby
Oh how I want to be free
Oh how I want to break free
But life still goes on
I can't get used to living without living without
Living without you by my side
I don't want to live alone hey
God knows got to make it on my own
So baby can't you see
I've got to break free
I've got to break free
I want to break free yeah
I want, I want, I want, I want to break free
\(\text{ZZ_zuozhe round}\)
T1 树篱之途
原题:CodeForces-685B Kay and Snowflake *1900
判定重心方法是 \(ct=\operatorname{argmin}_{u\in \mathrm{subtree}(rt)} \{\max(\max_{v\in \mathrm{son}(u)}\{siz_v\},siz_{rt}-siz_u)\}\)。
对于节点 \(u\),若已知其儿子 \(v\) 的重心 \(ct\),那么 \(u\) 的重心 \(ct'\) 如果在 \(v\) 子树中则一定在 \((u,ct)\) 路径上,因此可以暴力与 \(ct\) 的父亲比较谁更优,若父亲更优向上跳,否则停止。这样找到每棵子树最优的,再取最优即可。
注意比较过程应当与父亲比较而不是与当前重心比较。
点击查看代码
int n;
struct edge{
int to,nxt;
}e[maxn];
int head[maxn],cnt;
inline void add_edge(int u,int v){
e[++cnt].to=v,e[cnt].nxt=head[u],head[u]=cnt;
}
int fa[maxn],siz[maxn],mxsiz[maxn],ct[maxn];
void dfs(int u,int f){
fa[u]=f,siz[u]=1,mxsiz[u]=0;
for(int i=head[u],v;i;i=e[i].nxt){
v=e[i].to;
dfs(v,u);
siz[u]+=siz[v],mxsiz[u]=max(mxsiz[u],siz[v]);
}
ct[u]=u;
for(int i=head[u],v;i;i=e[i].nxt){
v=e[i].to;
int x=ct[v];
while(x!=u){
if(max(mxsiz[fa[x]],siz[u]-siz[fa[x]])<max(mxsiz[x],siz[u]-siz[x])) x=fa[x];
else break;
}
if(max(mxsiz[x],siz[u]-siz[x])<max(mxsiz[ct[u]],siz[u]-siz[ct[u]])) ct[u]=x;
}
}
int main(){
freopen("cent.in","r",stdin);
freopen("cent.out","w",stdout);
n=read();
for(int u,v=2;v<=n;++v){
u=read();
add_edge(u,v);
}
dfs(1,0);
for(int i=1;i<=n;++i) printf("%d\n",ct[i]);
return 0;
}
T2 坍缩
原题:CodeForces-1080E Sonya and Matrix Beauty *2400
考虑固定列 \([l,r]\),那么一行可以重排成回文当且仅当其出现次数为奇数的
字符不超过一种,可以使用 \(\bigoplus 2^c\) 异或哈希判断。
之后要求两行重排相等,也就是字符可重集完全相同,这部分可以使用 \(\sum base^c\) 哈希判断。之后求回文使用 Manacher,时间复杂度 \(O(n^3)\)。
点击查看代码
int n,m;
int pw[26];
char s[255][255];
int sum[255][255],xorsum[255][255];
int ch[255],now[505],D[505];
int ans;
inline void check(int u,int d){
if(u>d) return;
int len=2*(d-u+1)+1;
now[1]=mod+1;
for(int i=u;i<=d;++i) now[2*(i-u+1)]=ch[i],now[2*(i-u+1)+1]=mod+1;
for(int i=1,l,r=-1;i<=len;++i){
int j=(l+r)-i,k;
if(i>r) k=0;
else k=min(D[j],r-i+1);
while(i+k<=len&&i-k>=1&&now[i-k]==now[i+k]) ++k;
D[i]=k;
ans+=D[i]/2;
if(i+k-1>r) l=i-k+1,r=i+k-1;
}
}
int main(){
freopen("pal.in","r",stdin);
freopen("pal.out","w",stdout);
pw[0]=1;
for(int i=1;i<26;++i) pw[i]=1ll*pw[i-1]*base%mod;
n=read(),m=read();
for(int i=1;i<=n;++i){
scanf("%s",s[i]+1);
for(int j=1;j<=m;++j){
sum[i][j]=(sum[i][j-1]+pw[s[i][j]-'a'])%mod;
xorsum[i][j]=xorsum[i][j-1]^(1<<(s[i][j]-'a'));
}
}
for(int l=1;l<=m;++l){
for(int r=l;r<=m;++r){
int last=0;
for(int i=1;i<=n;++i){
int range_sum=(sum[i][r]-sum[i][l-1]+mod)%mod,range_xor=xorsum[i][r]^xorsum[i][l-1];
if(__builtin_popcount(range_xor)>1){
check(last+1,i-1);
last=i;
continue;
}
ch[i]=range_sum;
}
check(last+1,n);
}
}
printf("%d\n",ans);
return 0;
}
T3 诡意行商
原题:CodeForces-1023F Mobile Phone Network *2600
把 \(k\) 条边边权设为 \(0\),求出最小生成树,非树边 \((u,v)\) 会使得树上 \((u,v)\) 路径上所有边边权不得超过非树边边权,因此树剖区间取 \(\min\),从大到小排序变为区间覆盖。
点击查看代码
int n,k,m;
struct edge{
int u,v,w;
bool mark;
edge()=default;
edge(int u_,int v_,int w_,bool mark_):u(u_),v(v_),w(w_),mark(mark_){}
bool operator<(const edge &rhs)const{
return w<rhs.w;
}
}e[maxn<<1];
int bel[maxn];
int find(int x){
if(x==bel[x]) return x;
else return bel[x]=find(bel[x]);
}
vector<int> E[maxn];
inline void Kruskal(){
for(int i=1;i<=n;++i) bel[i]=i;
sort(e+1,e+k+m+1);
for(int i=1,u,v;i<=k+m;++i){
u=e[i].u,v=e[i].v;
int fu=find(u),fv=find(v);
if(fu==fv) continue;
bel[fv]=fu;
E[u].push_back(v),E[v].push_back(u);
e[i].mark=true;
}
}
int fa[maxn],dep[maxn],siz[maxn],son[maxn];
int top[maxn],dfn[maxn],dfncnt;
void dfs1(int u,int f,int d){
fa[u]=f,dep[u]=d,siz[u]=1;
int maxson=-1;
for(int v:E[u]){
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,dfn[u]=++dfncnt;
if(!son[u]) return;
dfs2(son[u],t);
for(int v:E[u]){
if(v==fa[u]||v==son[u]) continue;
dfs2(v,v);
}
}
int val[maxn];
struct SegmentTree{
#define mid ((l+r)>>1)
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
int tag[maxn<<2];
void build(int rt,int l,int r){
if(l==r) return tag[rt]=inf,void();
build(lson),build(rson);
}
inline void push_down(int rt){
if(tag[rt]){
tag[rt<<1]=tag[rt<<1|1]=tag[rt];
tag[rt]=0;
}
}
void update(int rt,int l,int r,int pl,int pr,int k){
if(pl<=l&&r<=pr) return tag[rt]=k,void();
push_down(rt);
if(pl<=mid) update(lson,pl,pr,k);
if(pr>mid) update(rson,pl,pr,k);
}
void dfs(int rt,int l,int r){
if(l==r) return val[l]=tag[rt],void();
push_down(rt);
dfs(lson),dfs(rson);
}
#undef mid
#undef lson
#undef rson
}S;
inline void update(int u,int v,int w){
while(top[u]!=top[v]){
if(dep[top[u]]>dep[top[v]]) swap(u,v);
S.update(1,1,n,dfn[top[v]],dfn[v],w);
v=fa[top[v]];
}
if(dep[u]>dep[v]) swap(u,v);
if(u!=v) S.update(1,1,n,dfn[u]+1,dfn[v],w);
}
ll ans;
int main(){
freopen("trade.in","r",stdin);
freopen("trade.out","w",stdout);
n=read(),k=read(),m=read();
for(int i=1,u,v;i<=k;++i){
u=read(),v=read();
e[i]=edge(u,v,0,false);
}
for(int i=1,u,v,w;i<=m;++i){
u=read(),v=read(),w=read();
e[k+i]=edge(u,v,w,false);
}
Kruskal();
dfs1(1,0,0);
dfs2(1,1);
S.build(1,1,n);
for(int i=k+m;i>k;--i){
if(e[i].mark) continue;
update(e[i].u,e[i].v,e[i].w);
}
S.dfs(1,1,n);
for(int i=1;i<=k;++i){
int now=max(dfn[e[i].u],dfn[e[i].v]);
if(val[now]==inf) return printf("-1\n"),0;
ans+=val[now];
}
printf("%lld\n",ans);
return 0;
}
T4 越过群山
考虑行 \(x<y<z\),列 \(l<r\),那么有三种移动方式:
-
\((x,l)\to (x,r)\to (z,r)\),代价 \((r-l)a_x+(z-x)b_r\)。
-
\((x,l)\to (z,l)\to (z,r)\),代价 \((r-l)a_z+(z-x)b_l\)。
-
\((x,l)\to (y,l)\to (y,z)\to (z,r)\),代价 \((r-l)a_y+(y-x)b_l+(z-y)b_r\)。
经过 \(y\) 的条件时后者小于前面两个式子,移项整理得到:
\[\dfrac{a_y-a_x}{y-x}<\dfrac{b_r-b_l}{r-l}<\dfrac{a_z-a_y}{z-y} \]因此对 \(a\) 维护一下下凸壳,\(b\) 同理。
现在就只考虑是向下或向右了,把前两个式子比较,有:
\[(r-l)a_x+(z-x)b_r<(r-l)a_z+(z-x)b_l\Rightarrow \dfrac{b_r-b_l}{r-l}<\dfrac{a_z-a_x}{z-x} \]因此每次会选择沿斜率较小的方向移动,维护两个指针分别在两个凸包上移动即可。
点击查看代码
int n,m;
int a[maxn],b[maxn];
inline bool check_slope_a(int x,int y,int z){
ll lhs=1ll*(a[y]-a[x])*(z-y),rhs=1ll*(a[z]-a[y])*(y-x);
return lhs>=rhs;
}
inline bool check_slope_b(int x,int y,int z){
ll lhs=1ll*(b[y]-b[x])*(z-y),rhs=1ll*(b[z]-b[y])*(y-x);
return lhs>=rhs;
}
inline bool check_slope_ab(int x,int y,int l,int r){
ll lhs=1ll*(a[y]-a[x])*(r-l),rhs=1ll*(b[r]-b[l])*(y-x);
return lhs<rhs;
}
int sta[maxn],topa;
int stb[maxn],topb;
ll ans;
int main(){
freopen("grid.in","r",stdin);
freopen("grid.out","w",stdout);
n=read(),m=read();
for(int i=1;i<=n;++i) a[i]=read();
for(int i=1;i<=m;++i) b[i]=read();
sta[++topa]=1;
for(int i=2;i<=n;++i){
while(topa>1&&check_slope_a(sta[topa-1],sta[topa],i)) --topa;
sta[++topa]=i;
}
stb[++topb]=1;
for(int i=2;i<=m;++i){
while(topb>1&&check_slope_b(stb[topb-1],stb[topb],i)) --topb;
stb[++topb]=i;
}
int i=1,j=1;
while(i<topa||j<topb){
if(i==topa){
ans+=1ll*(stb[j+1]-stb[j])*a[sta[i]];
++j;
}
else if(j==topb){
ans+=1ll*(sta[i+1]-sta[i])*b[stb[j]];
++i;
}
else{
if(check_slope_ab(sta[i],sta[i+1],stb[j],stb[j+1])){
ans+=1ll*(sta[i+1]-sta[i])*b[stb[j]];
++i;
}
else{
ans+=1ll*(stb[j+1]-stb[j])*a[sta[i]];
++j;
}
}
}
printf("%lld\n",ans);
return 0;
}
反思
T1 想到一个 \(O(n\log n)\) 的做法,经过卡常喜提 \(0\) 分。
T4 应当尝试去列式思考什么情况下会走一段路径。
开题顺序还行。
标签:考后,int,siz,free,break,maxn,want,CSP,模拟 From: https://www.cnblogs.com/SoyTony/p/Simulation_Problems_of_CSP-S_in_August_9.html