B. Sliding Window Sort 2
被题目名里的滑动窗口误导了,于是卡 B 40min /fn
Description
给定长度为 \(n\) 的排列 \(P\) 和一个整数 \(K\)。一次操作定义为选择一个长度为 \(K\) 的区间,对原排列的这段区间升序排序,其余位置不变。
你要执行操作恰好一次,求能得到的字典序最大的排列。
\(1\le K \le N\le 2\times 10^5\)。
Solution 1
题解做法。
观察到由于操作是升序排列,操作之后不会使排列的字典序变得比原来更大。那么如果存在某种操作方式使得这个区间不变,这样做一定是最优的。这种情况等价于找一个长度为 \(K\) 的单调递增区间,而这是容易判断的。
考虑不存在上述区间的情况,即无论如何操作都会使排列的字典序变小。我们显然更希望操作后值被改变的第一个位置尽可能靠右。设这个位置的下标为 \(x\)。
可以发现,当选择区间 \([n-K+1,K]\) 时,\(x\) 可以取得下界 \(n-K+1\)。也就是说,如果一个操作改变了 \(n-K+1\) 左侧的位置,这个操作不如最后一个区间优,它一定不是答案。但直接操作最后一个区间并不一定是最优的。如果最后一个区间后面的部分有一些很小的数,把操作区间左移避开它们或许更优。
将操作区间左移至 \([L,R]\),要使答案不变劣,应当保证 \(n-K+1\) 前面的部分都不变,即 \([L,n-K]\) 的值单调递增且均小于后面。在满足条件的情况下,显然 \(L\) 变小答案不会变劣,因此我们只需找到最小满足条件的 \(L\)。
对于“全部小于后面”的条件,因为单调递增,只需满足 \(P_{n-K}\) 小于后面的最小值,可以得出 \(L\) 的上界。而通过“单调递增”的条件可以得出 \(L\) 的下界,我们在 \(L\) 存在(上界不小于下界)的情况下取最小的 \(L\),不存在就取 \(n-K+1\) 作为区间左端点进行操作即可。
Solution 2
这人被题目名误导弄出来的赛时做法,给大家看个乐子。
我们希望第一个被改变的位置尽可能靠后。因此,类似于滑动窗口,从左到右枚举操作区间,用 set
维护当前区间排序后的结果。然后我们一位一位把 set
里的值和原序列匹配,找到第一个被改变的位置和它被改成的值,更新答案。
这样做时间复杂度不对,但是我们发现:如果 \([L,R]\) 有一段前缀排序后不动,那 \([L+1,R+1]\) 的这段前缀(长度减了 \(1\))排序后要么还是这段不动,要么后面来了个很小的数让不动的区间变短了。总之不会让不动的位置更靠后。
所以每次匹配完把不动的前缀跳过去不枚举即可,一共匹配了 \(n\) 次,时间复杂度 \(O(n\log n)\)。
代码是 Solution 2。
const int N=2e5+5,inf=1e9;
int n,k;
int a[N],flag[N];
int main()
{
n=read(),k=read();
for(int i=1;i<=n;i++) a[i]=read();
set<int> s;
for(int i=1;i<=k;i++) s.insert(a[i]);
int mx=0,ans=0;
for(int st=1;st<=n-k+1;st++)
{
if(st!=1) s.insert(a[st+k-1]),s.erase(a[st-1]);
if(flag[st]) continue;
auto it=s.begin(); int len=0;
for(int j=st;j<=st+k-1;j++)
{
if((*it)!=a[j]) {len=j;break;}
it++;
}
if(!len) mx=inf,ans=st;
for(int i=st+1;i<=len;i++) flag[i]=1;
if(len>mx) mx=len,ans=st;
}
sort(a+ans,a+ans+k);
for(int i=1;i<=n;i++) printf("%d ",a[i]);
printf("\n");
return 0;
}
C. Social Distance on Graph
C < B,简单题。
Description
给一张 \(n\) 个点 \(m\) 条边的无向带权图,你要给每个点染黑色或白色。要求对于任意起点终点同色的简单路径,路径的长度(即边权和)不小于 \(X\)。求 \(X\) 的最大值。
保证图连通、无重边无自环,\(N,M \le 2\times 10^5\),\(1\le W_i\le 10^9\)。
Solution
长度最小的路径肯定是只有一条边的路径,我们希望这样的路径尽量不连接相同颜色的点,并让边权小的优先满足条件。
发现这个本质上是对原图跑最小生成树,跑完的这棵树一定是二分图,且优先令边权小的边满足了条件。对最小生成树黑白染色,判断未被加入的边两个端点颜色是否相同。若相同,则答案对该边权取 \(\min\)。
考虑路径长度不为 \(1\) 的情况,发现最小生成树上路径长度为 \(2\) 的边一定属于同一颜色。对每个点记录与它相连的最小边和次小边,并用它们更新答案。同时你发现这东西是答案上界,最多只有 \(2\times 10^9\),不用开 long long。
const int N=2e5+5,inf=2e9;
int n,m;
struct node{int u,v,w;}E[N];
bool cmp(node x,node y) {return x.w<y.w;}
struct edge{int to,w;};
vector<edge> e[N];
bool cmp1(edge x,edge y) {return x.w<y.w;}
int fa[N];
int find(int x) {return fa[x]==x?x:fa[x]=find(fa[x]);}
int col[N],flag[N];
void dfs(int u)
{
for(auto i:e[u])
{
int v=i.to;
if(col[v]==-1) col[v]=col[u]^1,dfs(v);
}
}
int main()
{
n=read(),m=read();
for(int i=1;i<=m;i++) E[i]={read(),read(),read()};
sort(E+1,E+m+1,cmp);
for(int i=1;i<=n;i++) fa[i]=i,col[i]=-1;
for(int i=1;i<=m;i++)
{
int u=E[i].u,v=E[i].v,w=E[i].w;
if(find(u)==find(v)) {flag[i]=1;continue;}
fa[find(u)]=find(v);
e[u].push_back({v,w}),e[v].push_back({u,w});
}
for(int i=1;i<=n;i++) if(find(i)==i) col[i]=0,dfs(i);
int ans=inf;
for(int i=1;i<=m;i++)
{
if(flag[i]) if(col[E[i].u]==col[E[i].v]) ans=min(ans,E[i].w);
}
for(int i=1;i<=n;i++) sort(e[i].begin(),e[i].end(),cmp1);
for(int i=1;i<=n;i++)
if(e[i].size()>1) ans=min(ans,e[i][0].w+e[i][1].w);
printf("%d\n",ans);
return 0;
}
D. Substring Comparison
Description
构造一个长度为 \(n\) 的整数序列 \(X\),使其满足 \(m\) 条限制。第 \(i\) 条限制形如 \((A_i,B_i,C_i,D_i)\),表示要求 \(X\) 的子段 \([A_i,B_i]\) 字典序小于 \([C_i,D_i]\)。问是否存在满足条件的序列 \(X\)。
\(n,m\le 2000\)。
Solution
对于 \(A_i=C_i\) 的询问,可以直接比较 \(B_i\) 和 \(D_i\) 的大小,\(B_i>D_i\) 则无解,否则这个限制一定满足,可以忽略。因此,我们假设所有询问满足 \(A_i\neq C_i\)。
我们希望每组限制的两个区间在尽量靠前的位置上就开始不一样,因为这样后面的位就都没有大小限制。看到判断若干点之间的大小关系能否满足,考虑建图。
对每组限制连边 \(A_i\to C_i\),表示对于 \(X\) 有限制 \(X_{A_i}\le X_{C_i}\)。那么连出的这个图分两种情况:
- 图里没有环,则直接按拓扑序给 \(X\) 的每个位置赋值即可,答案为
Yes
。 - 图里有环,需要做进一步考虑。
对于在同一个强连通分量内的点,要满足图连边的大小关系,它们的 \(X\) 值必须都相等。因此可以对这个图跑 tarjan 求出强连通分量,并重新依次考虑题目给出的每个限制:
- 如果 \(A_i\) 和 \(C_i\) 不在一个强连通分量,那么它们所在位置的 \(X\) 值不相等,这个字典序的条件已经满足了;
- 否则,代表 \(X_{A_i}\) 和 \(X_{C_i}\) 一定是相等的,需要限制它们下一位的大小关系。我们令 \(A_i\gets A_i+1,C_i\gets C_i+1\),并在缩点后的图上重新建图,重复以上步骤。
- 如果一直重复到 \(A_i=B_i\) 或 \(C_i=D_i\) 它们都只能相等,判断哪个区间还剩下一段,如果是前面的区间剩一段就无解。否则这个限制已经满足。
如果重复完了上述步骤,中途没有被判无解,就是有解。
每次重复该过程都会让当前未满足限制的 \(A_i\gets A_i+1\),至多重复 \(n\) 次。每次跑一个 tarjan,复杂度 \(O(n+m)\)。总复杂度 \(O(n^2+nm)\)。
代码为了好写用并查集维护了哪些点值相等,但这不是复杂度瓶颈。
const int N=2005;
int n,m,fa[N];
int find(int x) {return fa[x]==x?x:fa[x]=find(fa[x]);}
il void merge(int x,int y) {if(find(x)!=find(y)) fa[find(x)]=find(y);}
struct edge{int nxt,to;}e[N<<1];
int head[N],cnt;
il void add(int u,int v) {e[++cnt]={head[u],v};head[u]=cnt;}
int dfn[N],low[N],in[N],tot;
stack<int> Q;
bool flag;
void tarjan(int u)
{
dfn[u]=low[u]=++tot,in[u]=1; Q.push(u);
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
else if(in[v]) low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u])
{
while(!Q.empty())
{
int t=Q.top(); if(t!=u) flag=1;
merge(t,u),in[t]=0,Q.pop();
if(t==u) break;
}
}
}
il void clear()
{
memset(head,0,sizeof(head)),cnt=0;
memset(dfn,0,sizeof(dfn)),memset(low,0,sizeof(low)),tot=0;
}
struct node{int a,b,c,d;} q[N];
int main()
{
n=read(),m=read();
for(int i=1;i<=m;i++) q[i]={read(),read(),read(),read()};
for(int i=1;i<=n;i++) fa[i]=i;
for(int w=1;w<=n;w++)
{
clear();
for(int i=1;i<=m;i++)
{
while(find(q[i].a)==find(q[i].c)&&q[i].a<=q[i].b&&q[i].c<=q[i].d)
q[i].a++,q[i].c++;
if(q[i].c>q[i].d) {printf("No\n");return 0;}
if(q[i].a<=q[i].b) add(find(q[i].a),find(q[i].c));
}
flag=0;
for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
if(!flag) break;
}
printf("Yes\n");
return 0;
}
E. Random Isolation
好厉害的题,不会做。看了官方题解。
Description
给一棵 \(n\) 个节点的树和一个整数 \(K\)。每次操作,等概率随机选一个所在连通块大小大于 \(K\) 的点,并删掉这个点和与之相连的所有边。重复操作直到图上所有连通块大小不超过 \(K\),求期望操作次数,答案对 \(998244353\) 取模。
\(1\le K < N\le 100\)。
Solution
将题目的操作转化为:对于随机的长度为 \(n\) 的排列 \(p\),我们按 \(p_1,p_2,\dots,p_n\) 的顺序依次考虑。若 \(p_i\) 所在连通块的大小大于 \(K\),那么在当前的树上删除 \(p_i\);否则不进行任何操作。求有效操作的期望次数。
考虑为什么这和原问题是等价的。忽略掉所有无效的操作,则当前局面下,所有可以有效操作的点在下一步被选取的概率均相等。而对于这步无效的点显然不会后面删着删着变有效了,所以它在哪里都对期望次数没有影响。
设 \(p(T)\) 表示原树的子树 \(T\) 恰好在删的过程中作为完整的连通块出现的概率。根据期望的线性性,我们考虑每棵子树对答案的贡献。对于一个 \(size>K\) 的子树 \(T\),它一定要在 \(T\) 形态下被操作一次,对答案的期望产生 \(1\times p(T)\) 的贡献。而经过这次操作后,\(T\) 就不再是 \(T\),它变成了若干棵别的子树,这部分的贡献已经被它变成的新子树统计了。也就是说,每个 \(T\) 对期望次数的贡献是 \(p(T)\)。答案的总期望为 \(\sum\limits_{size_T>K} p(T)\)。
问题瓶颈变成怎么求 \(p(T)\)。我们设 \(size_T=n\),与 \(T\) 里的点有边直接相连,且不属于 \(T\) 的点有 \(m\) 个。即,\(T\) 向子树外有 \(m\) 条直接连边。
那么根据 \(T\) 独立存在的条件,我们知道:\(T\) 内的 \(n\) 个点都还没被操作,且与 \(T\) 相连的这 \(m\) 个点都被操作过了。回到一开始把操作转化成的排列,上述条件等价于:某 \(m\) 个点在排列上的位置均在某 \(n\) 个点前面。不难得出这个的概率为 \(\dfrac{n!m!}{(n+m)!}\)。
剩下的最后一个问题是如何对 \(T\) 进行计数。发现 \(T\) 对答案的贡献只与 \(n\) 和 \(m\) 的值有关,考虑基于这点合并统计 \(n\) 和 \(m\) 均相等的子树的数量,可以树形 DP。
令 \(f_{u,i,j}\) 表示以点 \(u\) 为根,点数为 \(i\),且 不包括 \(u\) 的父亲 与之相连的点数为 \(j\) 的连通块个数。这么设是因为把 \(u\) 的父亲也算进去,向上转移又要减掉这部分贡献很麻烦。
树形背包转移即可,式子这里不写了。时间复杂度是 \(O(n^2K^2)\)。
#define int long long
const int N=105,mod=998244353;
int n,K;
int f[N][N][N];
struct edge{int nxt,to;}e[N<<1];
int head[N],cnt;
il void add(int u,int v) {e[++cnt]={head[u],v};head[u]=cnt;}
int siz[N],jc[N<<1],inv[N<<1];
il int qpow(int n,int k=mod-2)
{
int res=1;
for(;k;n=n*n%mod,k>>=1) if(k&1) res=res*n%mod;
return res;
}
il void init(int n)
{
jc[0]=inv[0]=1;
for(int i=1;i<=n;i++) jc[i]=jc[i-1]*i%mod;
inv[n]=qpow(jc[n]);
for(int i=n-1;i;i--) inv[i]=inv[i+1]*(i+1)%mod;
}
int tmp[N][N];
void dfs(int u,int fa)
{
f[u][1][0]=1,siz[u]=1;
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to; if(v==fa) continue;
dfs(v,u);
memset(tmp,0,sizeof(tmp));
f[v][0][1]=1;
for(int j=0;j<=siz[u];j++)
for(int k=0;k<=siz[u];k++)
for(int s=0;s<=siz[v];s++)
for(int t=0;t<=siz[v];t++)
tmp[j+s][k+t]=(tmp[j+s][k+t]+f[u][j][k]*f[v][s][t]%mod)%mod;
siz[u]+=siz[v];
for(int j=0;j<=siz[u];j++)
for(int k=0;k<=siz[u];k++) f[u][j][k]=tmp[j][k];
}
}
signed main()
{
n=read(),K=read();
init(2*n);
for(int i=1;i<n;i++)
{
int u=read(),v=read();
add(u,v),add(v,u);
}
dfs(1,0);
int ans=0;
for(int i=1;i<=n;i++)
for(int j=K+1;j<=siz[i];j++)
for(int k=0;k<=siz[i];k++)
{
int rl=k+(i!=1);
ans=(ans+f[i][j][k]*jc[j]%mod*jc[rl]%mod*inv[j+rl]%mod)%mod;
}
printf("%lld\n",ans);
return 0;
}
- Atcoder Regular Contest 165atcoder regular contest 165 minimization atcoder regular contest atcoder regular contest 166 atcoder regular contest 167 atcoder regular contest sliding atcoder regular contest degree atcoder regular contest 164 atcoder regular contest builder subsegments atcoder regular contest disconnected atcoder regular contest