CVBB ACM Team

到此差别页面的链接

--- 2020-2021:teams:legal_string:组队训练比赛记录:contest16 [2021/08/18 17:08]
jxm2001
+++ 2020-2021:teams:legal_string:组队训练比赛记录:contest16 [2021/08/28 08:50] (当前版本)
jxm2001 [题解]
@@ 行 4: / 行 4: @@
 ^  题目  ^  蒋贤蒙  ^  王赵安  ^  王智彪  ^
-|  A  |  2  |  0  |  0  |
+|  A  |  2  |  2  |  0  |
 |  B  |  0  |  0  |  0  |
-|  C  |  0  |  0  |  0  |
+|  C  |  2  |  2  |  0  |
-|  D  |  2  |  0  |  0  |
+|  D  |  2  |  1  |  0  |
 |  E  |  0  |  0  |  0  |
 |  G  |  2  |  1  |  0  |
-|  I  |  0  |  0  |  0  |
+|  I  |  2  |  1  |  0  |
 |  J  |  2  |  0  |  2  |
-|  K  |  0  |  0  |  0  |
+|  K  |  2  |  1  |  0  |
 ====== 题解 =====
@@ 行 126: / 行 126: @@
 	ans++;
 	enter(dep[0]==0?ans:1);
+	return 0;
+}
+</code>
+</hidden>
+===== C. Dance Party =====
+==== 题意 ====
+给定 $n\times 2$ 的二分图。对左部每个点，仅和右部 $k_i$ 个点不连边。求二分图最大匹配。
+==== 题解 ====
+设 $k=\max_{i=1}^n k_i$。
+先进行预匹配，每个左部点任选一个还未被匹配且有连边的右部点匹配，可以用 $\text{set}$ 维护所有未匹配的右部点，时间复杂度 $O(nk\log n)$。
+接下来剩下的未匹配的点一定不超过 $k$ 个，对每个点考虑匈牙利算法匹配， 总时间复杂度为 $O(km)$。
+$O(m)\sim O(n^2)$，考虑优化。假定现在需要对点 $i$ 进行匈牙利算法，将右部与点 $i$ 不相邻的点染黑，其余右部点染白。
+对除点 $i$ 以外的左部点，仅保留与黑点相关的连边，这样 $O(m)\sim O(nk)$，总时间复杂度 $O\left(nk^2\right)$ 足以通过此题。
+关于算法的正确性，假设在原图上存在一条从 $i$ 出发的增广路，且增广路上除了 $i$ 以外有其他点的失配边指向白点。
+找到增广路上的最后一个白点，直接将 $i$ 的失配边指向该点然后保留原增广路的剩余部分也可以一条增广路。
+同时该增广路上除了 $i$ 其他点的失配边都指向黑点。因此只要原图存在一条从 $i$ 出发的增广路则只保留与黑点相关的连边也可以得到一条增广路。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=3e4+5,MAXK=105;
+struct Edge{
+	int to,next;
+}edge[MAXN*MAXK];
+int head[MAXN],edge_cnt;
+void Insert(int u,int v){
+	edge[++edge_cnt]=Edge{v,head[u]};
+	head[u]=edge_cnt;
+}
+bitset<MAXN> bt[MAXN];
+vector<int> g[MAXN];
+namespace KM{
+	set<int> s;
+	int match[MAXN],vis[MAXN];
+	bool dfs(int u,int k){
+		if(vis[u]==k)
+		return false;
+		vis[u]=k;
+		for(int i=head[u];i;i=edge[i].next){
+			int v=edge[i].to;
+			if(!match[v]||dfs(match[v],k))
+			return match[v]=u,true;
+		}
+		return false;
+	}
+	bool get_pair(int n){
+		_rep(u,1,n)
+		s.insert(u);
+		vector<int> vec;
+		_rep(u,1,n){
+			bool flag=true;
+			for(int v:s){
+				if(!bt[u][v]){
+					match[v]=u;
+					s.erase(v);
+					flag=false;
+					break;
+				}
+			}
+			if(flag)
+			vec.push_back(u);
+		}
+		for(int i:vec){
+			mem(head,0);
+			edge_cnt=0;
+			_rep(u,1,n){
+				for(int v:g[i]){
+					if(!bt[u][v])
+					Insert(u,v);
+				}
+			}
+			_rep(v,1,n){
+				if(!bt[i][v])
+				Insert(i,v);
+			}
+			if(!dfs(i,i))
+			return false;
+		}
+		return true;
+	}
+}
+int ans[MAXN];
+int main()
+{
+	int n=read_int();
+	_rep(u,1,n){
+		int k=read_int();
+		while(k--){
+			int v=read_int();
+			g[u].push_back(v);
+			bt[u][v]=1;
+		}
+	}
+	if(KM::get_pair(n)){
+		_rep(i,1,n)
+		ans[KM::match[i]]=i;
+		_rep(i,1,n)
+		space(ans[i]);
+	}
+	else
+	puts("-1");
 	return 0;
 }
@@ 行 446: / 行 558: @@
 	return 0;
 }
+</code>
+</hidden>
+===== I. War of Inazuma (Hard Version) =====
+==== 题意 ====
+要求给 $n$ 位二进制数染上黑白两色，使得黑白两色的二进制数个数不相等。同时每个二进制数向其他只有一位与自身不同的二进制数连边。
+要求与每个二进制数相邻的同色二进制数不超过 $m=\lceil\sqrt n\rceil$。
+==== 题解 ====
+将二进制数写成一个 $\lceil\frac nm\rceil\times m$ 的矩阵，最后一行不足的位置补 $1$，然后将二进制数分为四类：
+$A.$ 有奇数个 $1$，至少存在一行全为 $1$
+$B.$ 有偶数个 $1$，不存在一行全为 $1$
+$C.$ 有奇数个 $1$，不存在一行全为 $1$
+$D.$ 有偶数个 $1$，至少存在一行全为 $1$
+$A,B$ 染白色，$C,D$ 染黑色。下面证明方案合法：
+只考虑白色的合法性，黑色的合法性是对称的。
+首先 $A$，$B$ 内部不连边，因为内部 $1$ 奇偶性相同所有至少有两个位置不同。
+只有仅一行全 $1$ 的 $A$ 才能和 $B$ 连边，否则至少有两个位置不同。
+对于 $A$ 仅一行全 $1$ 的数 $u$，为了和 $B$ 中的数 $v$ 连边，需要 $v$ 其他行与 $u$ 完全相同，然后 $v$ 在 $u$ 的全 $1$ 行只有一个位置是 $0$。
+由于一行只有 $m$ 个数，于是这样的 $v$ 最多只有 $m$ 个。
+对与 $B$ 中的每个数 $u$，为了和 $A$ 中的数 $v$ 连边，需要 $v$ 其他行与 $u$ 完全相同，然后仅某一行是全 $1$ 行。
+由于只有 $\lceil\frac nm\rceil$ 行，因此这样的 $v$ 最多只有 $\lceil\frac nm\rceil\le m$ 个。
+最后有 $A+C=B+D=2^{n-1},B+C=(2^m-1)^{\lceil\frac nm\rceil}$，于是 $A+B,C+D$ 都是奇数。
+由于 $4\mid A+B+C+D$，于是 $A+B\neq C+D$。
+<hidden 查看代码>
+<code cpp>
+bool check(int n,int m,int v){
+	bool flag_cnt=false;
+	bool flag_one=false;
+	for(int i=0;i<n;i+=m){
+		bool flag_line=true;
+		int r=min(n,i+m);
+		_for(j,i,r){
+			int c=v&1;
+			flag_line&=c;
+			flag_cnt^=c;
+			v>>=1;
+		}
+		flag_one|=flag_line;
+	}
+	return flag_cnt^flag_one;
+}
+int main()
+{
+	int n=read_int(),m=ceil(sqrt(n));
+	_for(i,0,1<<n)
+	putchar('0'+check(n,m,i));
+	return 0;
+}
 </code>
 </hidden>
@@ 行 1218: / 行 1399: @@
 	for(int i=0; i<m; i++) PO.work(po.p[i],i+1);
 	JXM::solve();
+	return 0;
+}
+</code>
+</hidden>
+===== K. Walking =====
+==== 题意 ====
+给定一个 $n\times m$ 的网格和初始点 $(a,b)$，求从初始点出发移动 $t$ 步且始终不出界的情况下的所有走法。
+==== 题解 ====
+显然横轴坐标是独立的，可以分开考虑。
+设 $f(s,n,a)$ 表示从一维坐标轴从 $a$ 点出发走 $s$ 步且始终处于 $[1,n]$ 范围内的情况下的所有走法。于是答案为
+$$
+\sum_{i=0}^t {t\choose i}f(i,n,a)f(t-i,m,b)
+$$
+接下来考虑如何计算 $f(s,n,a)(s\in [0,t])$，$f(s,m,b)$ 的计算方式类同。
+方案一：设 $\text{dp}(i,j)$ 表示走 $i$ 步最后位于 $j$ 点且始终为出界的方案数，不难得到一个 $O(nt)$ 的暴力解法。
+方案二：不难发现，有
+$$
+\begin{equation}\begin{split}
+f(s,n,a)&=\sum_{i=1}^n \text{dp}(s,i) \\
+&=\text{dp}(s-1,1)+\sum_{i=2}^{n-1} (\text{dp}(s-1,i-1)+\text{dp}(s-1,i+1))+\text{dp}(s-1,n)\\
+& =2f(s-1,n,a)-\text{dp}(s-1,1)-\text{dp}(s-1,n)
+\end{split}\end{equation}
+$$
+于是问题转化为计算 $\text{dp}(s,1),\text{dp}(s,n)$。
+对每个移动方案，定义非法序列，每当点进入 $(-\infty,0)$ 时非法序列末尾加上 $L$，每当点进入 $(n,+\infty)$ 时非法序列末尾加上 $R$。
+对于 $\text{dp}(s,1)$，我们需要获得所有非法序列为空串的移动方案。设 $h(a,b,s)$ 表示从 $a$ 移动 $s$ 步到达 $b$ 的方案数。
+显然根据 $a,b,s$ 奇偶性以及预处理组合数可以 $O(1)$ 计算 $h(a,b,s)$。
+然后总移动方案为 $h(a,1,s)$。利用容斥，首先我们减去非法序列为 ''.*L+.*'' 和 ''.*R+.*'' (非法序列均用正则表达式表示)的移动方案。
+设 $l(x)=-x,r(x)=2(n+1)-x$。
+根据简单组合数学知识，不难发现 ''.*L+.*''  代表的方案为 $h(a,l(1),s)$，''.*R+.*''  代表的方案为 $h(a,r(1),s)$。
+接下来我们需要补上减去非法序列为 ''.*L+R+.*'' 和 ''.*R+L+.*'' 的移动方案，分别为 $h(a,r(l(1)),s),h(a,l(r(1)),s)$。
+依此类推，有
+$$
+\text{dp}(s,1)=h(a,1,s)-h(a,l(1),s)-h(a,r(1),s)+h(a,r(l(1)),s)+h(a,l(r(1)),s)-h(a,l(r(l(1))),s)-h(a,r(l(r(1))),s)+\cdots
+$$
+由于 $r(l(x))=2(n+1)+x$，且当 $\text{abs}(a-x)\gt s$ 时一定有 $h(a,x,s)=0$，所以上述容斥最多迭代 $O(\frac sn)$ 次。
+于是方案二的总时间复杂度为 $O\left(\sum_{i=1}^t \frac in\right)\sim O\left(\frac {t^2}n\right)$。
+考虑根号分治，当 $n\lt \sqrt t$ 时采用方案一，否则采用方案二。总时间复杂度 $O(t\sqrt t)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=5e5+5,MAXM=800,mod=998244353;
+int quick_pow(int n,int k){
+    int ans=1;
+    while(k){
+        if(k&1)ans=1LL*ans*n%mod;
+        n=1LL*n*n%mod;
+        k>>=1;
+    }
+    return ans;
+}
+int frac[MAXN],invf[MAXN];
+int C(int n,int m){
+    return 1LL*frac[n]*invf[m]%mod*invf[n-m]%mod;
+}
+void init(){
+	frac[0]=1;
+    _for(i,1,MAXN)frac[i]=1LL*frac[i-1]*i%mod;
+    invf[MAXN-1]=quick_pow(frac[MAXN-1],mod-2);
+    for(int i=MAXN-1;i;i--)
+    invf[i-1]=1LL*invf[i]*i%mod;
+}
+int ans1[MAXN],ans2[MAXN];
+int dp[2][MAXM];
+void solve1(int s,int n,int a,int *ans){
+	int pos=0;
+	mem(dp[pos],0);
+	dp[pos][a]=1;
+	ans[0]=1;
+	_rep(i,1,s){
+		pos=!pos;
+		mem(dp[pos],0);
+		_rep(j,1,n){
+			dp[pos][j]=(dp[!pos][j-1]+dp[!pos][j+1])%mod;
+			ans[i]=(ans[i]+dp[pos][j])%mod;
+		}
+	}
+}
+int cal(int s,int n,int a,int pos){
+	int pos1=pos,pos2=pos,ans=0,d=abs(pos-a);
+	if(d<=s&&(s-d)%2==0)
+	ans=C(s,(s+d)/2);
+	for(int j=1;;j++){
+		if(j&1){
+			pos1=-pos1;
+			pos2=2*(n+1)-pos2;
+		}
+		else{
+			pos1=2*(n+1)-pos1;
+			pos2=-pos2;
+		}
+		int d1=abs(pos1-a),d2=abs(pos2-a),det=0;
+		if(d1>s&&d2>s)break;
+		if(d1<=s&&(s-d1)%2==0)
+		det=(det+C(s,(s+d1)/2));
+		if(d2<=s&&(s-d2)%2==0)
+		det=(det+C(s,(s+d2)/2))%mod;
+		if(j&1)
+		ans=(ans+mod-det)%mod;
+		else
+		ans=(ans+det)%mod;
+	}
+	return ans;
+}
+void solve2(int s,int n,int a,int *ans){
+	ans[0]=1;
+	_rep(i,1,s)
+	ans[i]=(2LL*ans[i-1]+mod-cal(i-1,n,a,1)+mod-cal(i-1,n,a,n))%mod;
+}
+void solve(int s,int n,int a,int *ans){
+	if(1LL*n*n<s)
+	solve1(s,n,a,ans);
+	else
+	solve2(s,n,a,ans);
+}
+int main()
+{
+	init();
+	int t=read_int(),n=read_int(),m=read_int(),a=read_int(),b=read_int();
+	solve(t,n,a,ans1);
+	solve(t,m,b,ans2);
+	int ans=0;
+	_rep(i,0,t)
+	ans=(ans+1LL*C(t,i)*ans1[i]%mod*ans2[t-i])%mod;
+	enter(ans);
 	return 0;
 }
 </code>
 </hidden>

CVBB ACM Team

用户工具

站点工具

页面工具