CVBB ACM Team

到此差别页面的链接

--- 2020-2021:teams:legal_string:组队训练比赛记录:contest6 [2021/07/28 11:03]
lgwza [补题情况]
+++ 2020-2021:teams:legal_string:组队训练比赛记录:contest6 [2021/08/11 20:47] (当前版本)
jxm2001
@@ 行 4: / 行 4: @@
 ^  题目  ^  蒋贤蒙  ^  王赵安  ^  王智彪  ^
-|  A  |  0  |  0  |  0  |
+|  A  |  2  |  1  |  0  |
 |  B  |  1  |  2  |  2  |
 |  C  |  1  |  1  |  2  |
-|  D  |  0  |  0  |  0  |
+|  D  |  2  |  0  |  0  |
 |  E  |  2  |  0  |  2  |
 |  F  |  2  |  0  |  1  |
-|  G  |  2  |  0  |  0  |
+|  G  |  2  |  1  |  0  |
 |  H  |  0  |  0  |  0  |
 |  I  |  2  |  0  |  1  |
@@ 行 16: / 行 16: @@
 ====== 题解 ======
+===== A. Guess and lies =====
+==== 题意 ====
+一开始有一个数 $x\in [1,n]$，只有 $A$ 知道，$B$ 不知道。
+$B$ 每次可以给定一个 $y$，询问 $y\le x$ 是否成立。$A$ 至多可以说一次谎，$A$ 想要最大化询问次数，$B$ 想要最小化询问次数。
+假定 $B$ 第一次问的数为 $i$ 且 $A$ 回答 $i\le x$ 成立，问还需要询问多少次。
+==== 题解 ====
+假定 $B$ 询问的数为 $y$，如果 $A$ 回答 $i\le x$ 成立，则将 $[1,y)$ 的说谎次数 $+1$，否则将 $[y,n]$ 的说谎次数 $+1$。
+易知最后只剩下一个说谎次数不超过 $1$ 的数就是答案。于是 $B$ 相当于每个把 $[1,n]$ 分成两段，而 $A$ 需要选择一段 $+1$。
+不妨在每次操作后删去大于 $1$ 的值，于是不难发现剩下的序列一定满足 $11100011$ 的形式。
+假定当前序列开头有连续 $a$ 个 $1$，中间有连续 $b$ 个 $0$，最后有连续 $c$ 个 $1$。设 $\text{dp}(a,b,c)$ 表示当前局面剩下的操作次数。
+不难发现可以枚举分割的位置，然后计算答案，时间复杂度 $O\left(n^4\right)$。
+另外还有一个性质，设 $f(a,b,c,k)$ 表示当前局面如果决策位置为 $k$ 则接下来还需要操作的次数，不难发现 $f(a,b,c,k)$ 为单峰函数。
+同时，设当前局面的最优决策位置为 $p(a,b,c)$，有 $c_1\le c_2\to p(a,b,c_1)\le p(a,b,c_2)$。
+于是考虑决策单调性，可以做到 $O\left(n^3\right)$，但还是不能通过本题数据范围。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=505;
+int dp[MAXN][MAXN][MAXN];
+int pos[MAXN][MAXN][MAXN];
+int cal(int a,int b,int c,int p){
+	if(p<=a)
+	return max(dp[a-p][b][c],dp[p+b][0][0]);
+	else if(p<=a+b){
+		int l=p-a,r=a+b-p;
+		return max(dp[a][l][r],dp[l][r][c]);
+	}
+	else{
+		int l=p-a-b,r=a+b+c-p;
+		return max(dp[a][b][l],dp[b+r][0][0]);
+	}
+}
+int main(){
+	int n=read_int();
+	pos[1][0][0]=pos[0][1][0]=pos[0][0][1]=1;
+	_rep(s,2,n){
+		for(int a=s;a>=0;a--)_rep(b,0,s-a){
+			int c=s-a-b;
+			int &p=pos[a][b][c];
+			if(c==0)
+			p=1;
+			else
+			p=pos[a][b][c-1];
+			while(p<s-1){
+				if(cal(a,b,c,p)>=cal(a,b,c,p+1))
+				p++;
+				else
+				break;
+			}
+			dp[a][b][c]=cal(a,b,c,p)+1;
+		}
+	}
+	_for(i,0,n)
+	space(dp[i][n-i][0]);
+	return 0;
+}
+</code>
+</hidden>
+不难发现 $B$ 询问的次数最多 $O\left(\log n\right)$ 次，于是交换 $\text{dp}$ 的值域和第三维。
+设 $\text{dp}(i,a,b)$ 表示 $i$ 次操作能处理的局面 $(a,b,c)$ 中 $c$ 的最大值，如果 $\text{dp}(i,a,b)=-1$ 表示 $i$ 次操作不能处理局面 $(a,b,0)$。
+关于状态转移也比较复杂，要分三种情况。
+如果 $k\in [1,a]$，则 $(a,b,c)\to (k+b,0,0),(a-k,b,c)$，此时要保证 $\text{dp}(i-1,k+b,0)\ge 0$ 才算合法，否则 $B$ 就不能 $i$ 步走完。
+合法情况下有 $\text{dp}(i,a,b)\gets \text{dp}(i-1,a-k,b)$。不难发现，$\text{dp}(i-1,a-k,b)$ 随 $k$ 增加递减，于是取合法情况的分界点即可。
+如果 $k\in (a,a+b]$，则 $(a,b,c)\to (a,k-a,a+b-k),(k-a,a+b-k,c)$，此时要保证 $\text{dp}(i-1,a,k-a)\ge a+b-k$ 才算合法。
+合法情况下有 $\text{dp}(i,a,b)\gets \text{dp}(i-1,k-a,a+b-k)$。同样 $\text{dp}(i-1,k-a,a+b-k)$ 也随 $k$ 增加递减。
+最后 $k\in (a+b,a+b+c]$，不妨记 $k'=k-a-b$，则 $(a,b,c)\to (b,0,c-k'),(a,b,k')$。
+此时要保证 $\text{dp}(i-1,b,0),\text{dp}(i-1,a,b)\ge 0$ 才算合法，不难发现，此时 $c=c-k'+k'=\text{dp}(i-1,b,0)+\text{dp}(i-1,a,b)$。
+同时 $p(i,a,b)$ 表示当前状态最优决策位置，关于 $a$ 貌似具有不严格单峰性，根据打表结果有 $p(i,a,b)\ge p(i,a-1,b)-1$。
+于是可以 $O(n^2\log n)$ 通过此题。
+<hidden 查看代码>
+<code cpp>
+const int MAXV=20,MAXN=2005;
+int dp[MAXV][MAXN][MAXN];
+bool check(int i,int a,int b,int p){
+	if(p<=a)
+	return dp[i-1][p+b][0]>=0;
+	else
+	return dp[i-1][a][p-a]>=a+b-p;
+}
+int main(){
+	int n=read_int();
+	mem(dp,-1);
+	dp[0][0][0]=1;
+	dp[0][1][0]=dp[0][0][1]=0;
+	_for(i,1,MAXV){
+		_rep(b,0,n)for(int a=0,p=0;a<=n-b;a++){
+			while(p<a+b&&check(i,a,b,p))p++;
+			while(p&&!check(i,a,b,p))p--;
+			dp[i][a][b]=(p<=a)?dp[i-1][a-p][b]:dp[i-1][p-a][a+b-p];
+			if(dp[i-1][a][b]>=0&&dp[i-1][b][0]>=0)
+			dp[i][a][b]=max(dp[i][a][b],dp[i-1][a][b]+dp[i-1][b][0]);
+		}
+	}
+	_for(i,0,n){
+		_for(j,0,MAXV){
+			if(dp[j][i][n-i]>=0){
+				space(j);
+				break;
+			}
+		}
+	}
+	return 0;
+}
+</code>
+</hidden>
+===== D. Count =====
+==== 题意 ====
+给定一个 $n\times n$ 的网格图，有 $k$ 个格子不能选，分别为 $(r_1,c_1),(r_2,c_2)\cdots (r_k,c_k)$。
+在此基础上选择 $m$ 个格子，满足每行每列至少选中一个格子，$r=c$ 和 $r+c=n+1$ 的对角线上至少选中一个格子。
+==== 题解 ====
+考虑容斥，首先枚举 $k$ 个不能选的格子的子集，强制选中这些格子，设共选了 $c$ 个格子。
+进一步容斥计算在强制选中这些格子对应的方案数，考虑是否禁止对角线、是否禁止某行某列。
+设 $\text{dp}(i,j,k)$ 表示强制只选 $i$ 行，只选 $j$ 列，且这些位置中有 $k$ 个位置因为强制不选对角线被禁止的方案数。
+于是状态 $(i,j,k)$ 对应的方案数为 ${i\times j-k-c \choose m-c}\text{dp}(i,j,k)$。接下来考虑如何计算  $\text{dp}(i,j,k)$。
+事实上，只有形如第 $i$ 行、第 $i$ 列、第 $n+1-i$ 行、第 $n+1-i$ 列这样的四元组会对 $k$ 产生影响。
+于是可以将每个四元组看成一个物品，$O(2^4)$ 枚举这四元组每个元素的选择情况计算对 $k$ 的影响，然后三维背包合并所有四元组贡献。
+由于 $(i,j,k)$ 的每个维度上界都是 $O(n)$，所以总时间复杂 $O\left(2^kn^4\right)$。实际上还是比较卡的，但题目数据比较友好。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=35,MAXV=MAXN*MAXN,mod=1e4+7;
+int dp[MAXN][MAXN][MAXN<<1],temp[MAXN][MAXN][MAXN<<1];
+int sr[MAXN],sc[MAXN],node[MAXN][2],frac[MAXV],invf[MAXV];
+int quick_pow(int n,int k){
+	int ans=1;
+	while(k){
+		if(k&1)ans=ans*n%mod;
+		n=n*n%mod;
+		k>>=1;
+	}
+	return ans;
+}
+int C(int n,int m){
+	return frac[n]*invf[m]%mod*invf[n-m]%mod;
+}
+int solve(int n,int _k,int _c,int _s){
+	int tf1=2,tf2=2,cnt=0;
+	mem(sr,0);mem(sc,0);
+	_for(i,0,_k){
+		if(_s&(1<<i)){
+			sr[node[i][0]]=1,sc[node[i][1]]=1;
+			if(node[i][0]==node[i][1])
+			tf1=1;
+			if(node[i][0]+node[i][1]==n+1)
+			tf2=1;
+			cnt++;
+		}
+	}
+	int ans=0;
+	_for(f1,0,tf1)_for(f2,0,tf2){
+		mem(dp,0);
+		dp[0][0][0]=1;
+		int mr=0,mc=0,mk=0;
+		for(int p1=1,p2=n;p1<=p2;p1++,p2--){
+			mem(temp,0);
+			if(p1!=p2){
+				mr+=2,mc+=2,mk+=4;
+				_for(r1,sr[p1],2)_for(r2,sr[p2],2)
+				_for(c1,sc[p1],2)_for(c2,sc[p2],2){
+					int dr=r1+r2,dc=c1+c2;
+					int dk=(r1&c1&f1)+(r2&c2&f1)+(r1&c2&f2)+(r2&c1&f2);
+					_rep(i,dr,mr)_rep(j,dc,mc)_rep(k,dk,mk)
+					temp[i][j][k]+=dp[i-dr][j-dc][k-dk];
+				}
+			}
+			else{
+				mr++,mc++,mk++;
+				_for(dr,sr[p1],2)_for(dc,sc[p1],2){
+					int dk=dr&dc&(f1|f2);
+					_rep(i,dr,mr)_rep(j,dc,mc)_rep(k,dk,mk)
+					temp[i][j][k]+=dp[i-dr][j-dc][k-dk];
+				}
+			}
+			_rep(i,0,mr)_rep(j,0,mc)_rep(k,0,mk)
+			dp[i][j][k]=temp[i][j][k]%mod;
+		}
+		_for(i,0,MAXN)_for(j,0,MAXN)_for(k,0,MAXN<<1){
+			int tot=i*j-k;
+			if(tot>=_c){
+				int s=C(tot-cnt,_c-cnt)*dp[i][j][k]%mod;
+				int sg=(n-i)+(n-j)+f1+f2+cnt;
+				if(sg&1)
+				ans=(ans-s)%mod;
+				else
+				ans=(ans+s)%mod;
+			}
+		}
+	}
+	return (ans+mod)%mod;
+}
+int main()
+{
+	int n=read_int(),k=read_int(),c=read_int();
+	_for(i,0,k)
+	node[i][0]=read_int(),node[i][1]=read_int();
+	frac[0]=1;
+	_for(i,1,MAXV)
+	frac[i]=frac[i-1]*i%mod;
+	invf[MAXV-1]=quick_pow(frac[MAXV-1],mod-2);
+	for(int i=MAXV-1;i;i--)
+	invf[i-1]=invf[i]*i%mod;
+	int ans=0;
+	_for(i,0,1<<k)
+	ans=(ans+solve(n,k,c,i))%mod;
+	enter(ans);
+	return 0;
+}
+</code>
+</hidden>
 ===== G. Yu Ling(Ling YueZheng) and Colorful Tree =====
@@ 行 296: / 行 543: @@
 jxm：找操作中的不变量可能是解题的一种思路，比如这场的 $B$ 或者博弈论题。 $A$ 据说是 $\text{dp}$ 优化题，但没看懂题解，先咕了。
+update：补完A了，感觉性质比较玄学。

CVBB ACM Team

用户工具

站点工具

页面工具