福建建设资格执业注册管理中心网站,无锡微网站制作,情留 蚊子 pj wordpress,长沙seo优化公司哪家好B. Sliding Window Sort 2 被题目名里的滑动窗口误导了#xff0c;于是卡 B 40min /fn Description 给定长度为 \(n\) 的排列 \(P\) 和一个整数 \(K\)。一次操作定义为选择一个长度为 \(K\) 的区间#xff0c;对原排列的这段区间升序排序#xff0c;其余位置不变。 你要执行… 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-K1,K]\) 时\(x\) 可以取得下界 \(n-K1\)。也就是说如果一个操作改变了 \(n-K1\) 左侧的位置这个操作不如最后一个区间优它一定不是答案。但直接操作最后一个区间并不一定是最优的。如果最后一个区间后面的部分有一些很小的数把操作区间左移避开它们或许更优。 将操作区间左移至 \([L,R]\)要使答案不变劣应当保证 \(n-K1\) 前面的部分都不变即 \([L,n-K]\) 的值单调递增且均小于后面。在满足条件的情况下显然 \(L\) 变小答案不会变劣因此我们只需找到最小满足条件的 \(L\)。 对于“全部小于后面”的条件因为单调递增只需满足 \(P_{n-K}\) 小于后面的最小值可以得出 \(L\) 的上界。而通过“单调递增”的条件可以得出 \(L\) 的下界我们在 \(L\) 存在(上界不小于下界)的情况下取最小的 \(L\)不存在就取 \(n-K1\) 作为区间左端点进行操作即可。 Solution 2 这人被题目名误导弄出来的赛时做法给大家看个乐子。 我们希望第一个被改变的位置尽可能靠后。因此类似于滑动窗口从左到右枚举操作区间用 set 维护当前区间排序后的结果。然后我们一位一位把 set 里的值和原序列匹配找到第一个被改变的位置和它被改成的值更新答案。 这样做时间复杂度不对但是我们发现如果 \([L,R]\) 有一段前缀排序后不动那 \([L1,R1]\) 的这段前缀(长度减了 \(1\))排序后要么还是这段不动要么后面来了个很小的数让不动的区间变短了。总之不会让不动的位置更靠后。 所以每次匹配完把不动的前缀跳过去不枚举即可一共匹配了 \(n\) 次时间复杂度 \(O(n\log n)\)。 代码是 Solution 2。 const int N2e55,inf1e9;
int n,k;
int a[N],flag[N];
int main()
{nread(),kread();for(int i1;in;i) a[i]read();setint s;for(int i1;ik;i) s.insert(a[i]);int mx0,ans0;for(int st1;stn-k1;st){if(st!1) s.insert(a[stk-1]),s.erase(a[st-1]);if(flag[st]) continue;auto its.begin(); int len0;for(int jst;jstk-1;j){if((*it)!a[j]) {lenj;break;}it;}if(!len) mxinf,ansst;for(int ist1;ilen;i) flag[i]1;if(lenmx) mxlen,ansst;}sort(aans,aansk);for(int i1;in;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 N2e55,inf2e9;
int n,m;
struct node{int u,v,w;}E[N];
bool cmp(node x,node y) {return x.wy.w;}
struct edge{int to,w;};
vectoredge e[N];
bool cmp1(edge x,edge y) {return x.wy.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 vi.to;if(col[v]-1) col[v]col[u]^1,dfs(v);}
}
int main()
{nread(),mread();for(int i1;im;i) E[i]{read(),read(),read()};sort(E1,Em1,cmp);for(int i1;in;i) fa[i]i,col[i]-1;for(int i1;im;i){int uE[i].u,vE[i].v,wE[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 i1;in;i) if(find(i)i) col[i]0,dfs(i);int ansinf;for(int i1;im;i){if(flag[i]) if(col[E[i].u]col[E[i].v]) ansmin(ans,E[i].w);}for(int i1;in;i) sort(e[i].begin(),e[i].end(),cmp1);for(int i1;in;i)if(e[i].size()1) ansmin(ans,e[i][0].we[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_iC_i\) 的询问可以直接比较 \(B_i\) 和 \(D_i\) 的大小\(B_iD_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_i1,C_i\gets C_i1\)并在缩点后的图上重新建图重复以上步骤。如果一直重复到 \(A_iB_i\) 或 \(C_iD_i\) 它们都只能相等判断哪个区间还剩下一段如果是前面的区间剩一段就无解。否则这个限制已经满足。 如果重复完了上述步骤中途没有被判无解就是有解。 每次重复该过程都会让当前未满足限制的 \(A_i\gets A_i1\)至多重复 \(n\) 次。每次跑一个 tarjan复杂度 \(O(nm)\)。总复杂度 \(O(n^2nm)\)。 代码为了好写用并查集维护了哪些点值相等但这不是复杂度瓶颈。 const int N2005;
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[N1];
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;
stackint Q;
bool flag;
void tarjan(int u)
{dfn[u]low[u]tot,in[u]1; Q.push(u);for(int ihead[u];i;ie[i].nxt){int ve[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 tQ.top(); if(t!u) flag1;merge(t,u),in[t]0,Q.pop();if(tu) break;}}
}
il void clear()
{memset(head,0,sizeof(head)),cnt0;memset(dfn,0,sizeof(dfn)),memset(low,0,sizeof(low)),tot0;
}
struct node{int a,b,c,d;} q[N];
int main()
{nread(),mread();for(int i1;im;i) q[i]{read(),read(),read(),read()};for(int i1;in;i) fa[i]i;for(int w1;wn;w){clear();for(int i1;im;i){while(find(q[i].a)find(q[i].c)q[i].aq[i].bq[i].cq[i].d)q[i].a,q[i].c;if(q[i].cq[i].d) {printf(No\n);return 0;}if(q[i].aq[i].b) add(find(q[i].a),find(q[i].c));}flag0;for(int i1;in;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\) 恰好在删的过程中作为完整的连通块出现的概率。根据期望的线性性我们考虑每棵子树对答案的贡献。对于一个 \(sizeK\) 的子树 \(T\)它一定要在 \(T\) 形态下被操作一次对答案的期望产生 \(1\times p(T)\) 的贡献。而经过这次操作后\(T\) 就不再是 \(T\)它变成了若干棵别的子树这部分的贡献已经被它变成的新子树统计了。也就是说每个 \(T\) 对期望次数的贡献是 \(p(T)\)。答案的总期望为 \(\sum\limits_{size_TK} p(T)\)。 问题瓶颈变成怎么求 \(p(T)\)。我们设 \(size_Tn\)与 \(T\) 里的点有边直接相连且不属于 \(T\) 的点有 \(m\) 个。即\(T\) 向子树外有 \(m\) 条直接连边。 那么根据 \(T\) 独立存在的条件我们知道\(T\) 内的 \(n\) 个点都还没被操作且与 \(T\) 相连的这 \(m\) 个点都被操作过了。回到一开始把操作转化成的排列上述条件等价于某 \(m\) 个点在排列上的位置均在某 \(n\) 个点前面。不难得出这个的概率为 \(\dfrac{n!m!}{(nm)!}\)。 剩下的最后一个问题是如何对 \(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 N105,mod998244353;
int n,K;
int f[N][N][N];
struct edge{int nxt,to;}e[N1];
int head[N],cnt;
il void add(int u,int v) {e[cnt]{head[u],v};head[u]cnt;}
int siz[N],jc[N1],inv[N1];
il int qpow(int n,int kmod-2)
{int res1;for(;k;nn*n%mod,k1) if(k1) resres*n%mod;return res;
}
il void init(int n)
{jc[0]inv[0]1;for(int i1;in;i) jc[i]jc[i-1]*i%mod;inv[n]qpow(jc[n]);for(int in-1;i;i--) inv[i]inv[i1]*(i1)%mod;
}
int tmp[N][N];
void dfs(int u,int fa)
{f[u][1][0]1,siz[u]1;for(int ihead[u];i;ie[i].nxt){int ve[i].to; if(vfa) continue;dfs(v,u);memset(tmp,0,sizeof(tmp));f[v][0][1]1;for(int j0;jsiz[u];j)for(int k0;ksiz[u];k)for(int s0;ssiz[v];s)for(int t0;tsiz[v];t)tmp[js][kt](tmp[js][kt]f[u][j][k]*f[v][s][t]%mod)%mod;siz[u]siz[v];for(int j0;jsiz[u];j)for(int k0;ksiz[u];k) f[u][j][k]tmp[j][k];}
}
signed main()
{nread(),Kread();init(2*n);for(int i1;in;i){int uread(),vread();add(u,v),add(v,u);}dfs(1,0);int ans0;for(int i1;in;i)for(int jK1;jsiz[i];j)for(int k0;ksiz[i];k){int rlk(i!1);ans(ansf[i][j][k]*jc[j]%mod*jc[rl]%mod*inv[jrl]%mod)%mod;}printf(%lld\n,ans);return 0;
}
