差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:jxm2001:contest:cf_698_div._1 [2021/01/29 09:34]
jxm2001 创建
+++ 2020-2021:teams:legal_string:jxm2001:contest:cf_698_div._1 [2021/01/30 21:25] (当前版本)
jxm2001
@@ 行 1: / 行 1: @@
-====== Codeforces Round #666 (Div. 1) ======
+====== Codeforces Round #698 (Div. 1) ======
-[[http://codeforces.com/contest/1396|比赛链接]]
+[[https://codeforces.com/contest/1477|比赛链接]]
 ===== A. Nezzar and Board =====
@@ 行 7: / 行 7: @@
 ==== 题意 ====
-给定 $n$ 个不同的 $x_i$，每次可以选取一对 $x,y$，得到 $2x-y$(注意该操作不会删去原有的 $x,y$)。
+给定 $n$ 个不同的 $x_i$，每次可以选取一对 $x,y$，得到 $2x-y$。(注意该操作不会删去原有的 $x,y$)
 问是否能经过有限次操作得到 $k$。
@@ 行 13: / 行 13: @@
 ==== 题解 ====
+不妨设 $b=\min(x_i)$，记 $a_i=x_i-b,k'=k-b$，于是有 $2x_i-x_j=2a_i-2b-a_j+b=(2a_i-a_j)-b$。
+如果用 $a_i$ 替代 $x_i$，$k'$ 替代 $k$，则所有结果相当于都平移了 $b$，对答案不影响。于是不妨设序列为 $0,a_2,a_3\cdots a_n$。
+首先对于 $0,a$，有 $2a-0=2a,2*(2a)-a=3a,2*(3a)-(2a)=4a$，于是可以得到所有 $a$ 的倍数。
+然后假设 $n=t$ 时 $g_t$ 一定可以得到，于是能得到 $k$ 当且仅当 $g_t=\text{gcd}(a_2,a_3\cdots a_t)\mid k$ 。
+$n=2$ 时相当于 $0,a$ 的情况，显然成立。
+$n=t+1$ 时，根据裴蜀定理，知存在 $x,y$ 满足
+$$
+x*g_t-y*a_{t+1}=\text{gcd}(g_t,a_{t+1})=g_{t+1}
+$$
+根据归纳假设，可以得到 $g_t$。如果 $x=2x'$，则先得到 $x'*g_t$ 和 $y*a_{t+1}$，于是 $g_{t+1}=2x'g_t-y*a_{t+1}$。
+同理 $y$ 为偶数时也能得到 $g_{t+1}$。下证一定存在 $x,y$ 满足至少有一个偶数。
+假设得到的一组 $x,y$ 为全为奇数，则记 $c=\frac {g_t}{g_{t+1}},d=\frac {a_{t+1}}{g_{t+1}}$，于是有
+$$
+=x*c-y*d=(x+d)*c-(y+c)*d
+$$
+因为 $(c,d)=1$，所以  $c,d$ 中至少一个奇数，于是 $x+d,y+c$ 中至少一个偶数，证毕。
 ===== D. Nezzar and Hidden Permutations =====
@@ 行 19: / 行 45: @@
 ==== 题意 ====
+给定两个 $1\sim n$ 的排列 $p,q$ 和 $m$ 个限制。限制 $(l_i,r_i)$ 要求 $(p_{l_i}-q_{l_i}\ge 0)=(p_{r_i}-q_{r_i}\ge 0)$。
+要求在满足所有限制的前提下使得满足 $p_i\neq q_i$ 的 $i$ 最多，输出此时的排列 $p,q$。
 ==== 题解 ====
+对原题进行转化，等价于对点 $1\sim n$，每个点有两个权值 $p_i,q_i$。
+同时每个限制条件对 $l_i,r_i$ 连一条边，于是只要有连边的点之间满足之前的限制条件即可。
+对点 $i$，与该点有连边的点要么 $\max(p_j,q_j)\le \min(p_i,q_i)$，要么 $\min(p_j,q_j)\ge \max(p_i,q_i)$。
+于是 $\deg(i)\le \min(p_i,q_i)+n-1-\max(p_i,q_i)\le n-1$，取等号条件为 $p_i=q_i$。
+于是对所有度数为 $n-1$ 的点，依次将 $1,2\cdots k_0$ 分配给这些点，这些点对其他点的限制被消除，直接将这些点删去。
+下面证明余下点均可满足 $p_i\neq q_i$。
+考虑该图的补图，易知只要使得补图中所有没有连边的点满足之前的限制条件即可。
+同时由于删去点后原图中不存在度数为 $n-1$，于是补图不存在孤立点。
+首先考虑菊花图的情况，令中心点为 $(k_0+1,k_1)$，其他点依次为 $(k_0+2,k_0+1),(k_0+3,k_0+2)\cdots (k_1,k_1-1)$。
+由于菊花图的限制仅存在于两两非中心点之间，是该菊花图满足限制且每个点 $p\neq q$。
+将原图划分为若干个菊花图，且每个菊花图至少有两个点，将 $(k_0+1,k_1)$ 分配给第一个菊花图，$(k_1+1,k_2)$ 分配给第二个菊花图...
+于是每个菊花图内部满足限制，每个菊花图之间也满足限制。
+接下来问题转化为怎么将补图划分为若干个菊花图，且每个菊花图至少有两个点。
+一个经典算法为将补图先划分为若干连通块，每个连通块任意得到一个生成树。
+接下来对每个生成树，取该树的任意叶子，找到与该叶子结点相邻的结点 $u$ 作为菊花图的中心。
+对所有与 $u$ 相邻的结点，如果该点是叶子结点，则将该结点加入菊花图。否则删去该结点与 $u$ 的连边。
+最后将得到的菊花图从点集中删去，直到点集中没有剩余结点，则算法结束。时间复杂度 $O((n+m)\log n)$。
 <hidden 查看代码>
 <code cpp>
+typedef set<int>::iterator iter;
+const int MAXN=5e5+5;
+struct Node{
+	int idx,deg;
+	bool operator < (const Node &b)const{
+		if(deg!=b.deg)
+		return deg<b.deg;
+		else
+		return idx<b.idx;
+	}
+};
+struct star{
+	int root;
+	vector<int> son;
+};
+int deg[MAXN],idx1[MAXN],idx2[MAXN];
+set<int> g0[MAXN],g[MAXN],node0;
+set<Node> node;
+vector<star> stars;
+void dfs(int u){
+	node0.erase(u);
+	int pos=0;
+	while(true){
+		iter it=node0.upper_bound(pos);
+		if(it==node0.end())
+		break;
+		pos=*it;
+		if(g0[u].find(pos)==g0[u].end()){
+			g[u].insert(pos);
+			g[pos].insert(u);
+			dfs(pos);
+		}
+	}
+}
+int main()
+{
+	int T=read_int();
+	while(T--){
+		int n=read_int(),m=read_int();
+		_rep(i,1,n){
+			g0[i].clear();
+			g[i].clear();
+			node0.insert(i);
+		}
+		stars.clear();
+		while(m--){
+			int u=read_int(),v=read_int();
+			g0[u].insert(v);
+			g0[v].insert(u);
+		}
+		while(!node0.empty())
+		dfs(*node0.begin());
+		int pos1=1,pos2=1;
+		_rep(i,1,n){
+			deg[i]=g[i].size();
+			if(!deg[i]){
+				idx1[i]=pos1++;
+				idx2[i]=pos2++;
+			}
+			else
+			node.insert(Node{i,deg[i]});
+		}
+		while(!node.empty()){
+			int leaf=node.begin()->idx,u=*g[leaf].begin();
+			node.erase(Node{u,deg[u]});
+			vector<int> son;
+			for(iter it=g[u].begin();it!=g[u].end();++it){
+				int v=*it;
+				if(deg[v]==1){
+					son.push_back(v);
+					node.erase(Node{v,deg[v]});
+				}
+				else{
+					g[v].erase(u);
+					node.erase(Node{v,deg[v]--});
+					node.insert(Node{v,deg[v]});
+				}
+			}
+			stars.push_back(star{u,son});
+		}
+		_for(i,0,stars.size()){
+			idx1[stars[i].root]=pos1++;
+			_for(j,0,stars[i].son.size()){
+				idx1[stars[i].son[j]]=pos1++;
+				idx2[stars[i].son[j]]=pos2++;
+			}
+			idx2[stars[i].root]=pos2++;
+		}
+		_rep(i,1,n)
+		space(idx1[i]);
+		puts("");
+		_rep(i,1,n)
+		space(idx2[i]);
+		puts("");
+	}
+	return 0;
+}
 </code>
 </hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具