差别

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

--- 2020-2021:teams:legal_string:组队训练比赛记录:contest3 [2021/07/18 14:28]
王智彪
+++ 2020-2021:teams:legal_string:组队训练比赛记录:contest3 [2021/07/18 17:26] (当前版本)
jxm2001
@@ 行 1: / 行 1: @@
-[[https://ac.nowcoder.com/acm/contest/4138|比赛链接]]
+[[https://ac.nowcoder.com/acm/contest/11166|比赛链接]]
 ====== 题解 ======
@@ 行 13: / 行 13: @@
 数据范围： $T≤10000,2≤m,n≤1000$，并保证总共的 $n×m$ 不超过 $10^{6}$。
-===== 题解 =====
+==== 题解 ====
 一道恶心人的搜索/大模拟题。
@@ 行 228: / 行 228: @@
 	_for(i,0,min(n,k))
 	ans+=max(0,a[i]-b[i])*2;
+	enter(ans);
+	return 0;
+}
+</code>
+</hidden>
+===== I. Increasing Subsequence =====
+==== 题意 ====
+给定 $1\sim n$ 的排列，现有两名玩家轮流操作，设当前两名玩家之前选择的位置为 $i,j$。
+当轮到玩家一时，他必须选择 $k\gt i,p_k\gt p_j$。如果存在多个 $k$ 满足条件，则玩家一将等概率选择一个。
+当轮到玩家二时，他必须选择 $k\gt j,p_k\gt p_i$。如果存在多个 $k$ 满足条件，则玩家二将等概率选择一个。
+默认两名玩家初始时 $i=0,j=0,p_0=0$。问两名玩家的期望步数和。
+==== 题解 ====
+设 $\text{dp}(i,j)$ 表示当前必须选择一个 $k\ge i,p_k\gt p_j$ 的局面出现的概率，$\text{cnt}(i,j)$ 表示满足 $k\ge i,p_k\ge j$ 的 $k$ 的个数。
+当前状态有两种情况。如果 $p_i\le p_j$，则必须放弃 $p_i$，此时有 $\text{dp}(i+1,j)\gets \text{dp}(i,j)$。
+如果 $p_i\gt p_j$，则 $p_i$ 是一个合法选择，此时可以考虑强制放弃 $p_i$ 和选择 $p_i$，依次有状态转移
+$$
+\text{dp}(i+1,j)\gets \cfrac {\text{cnt}(i,p_j+1)-1}{\text{cnt}(i,p_j+1)}\times \text{dp}(i,j)\\
+\text{dp}(j+1,i)\gets \cfrac 1{\text{cnt}(i,p_j+1)}\times \text{dp}(i,j)\\
+\text{ans}\gets \cfrac 1{\text{cnt}(i,p_j+1)}\times \text{dp}(i,j)
+$$
+考虑利用二维前缀和预处理 $\text{cnt}$，然后按拓扑序进行状态转移，时间复杂度 $O(n^2)$。初始状态为 $\text{dp}(1,0)=1$。
+<hidden 查看代码>
+<code cpp>
+#include <iostream>
+#include <cstdio>
+#include <cstdlib>
+#include <algorithm>
+#include <string>
+#include <sstream>
+#include <cstring>
+#include <cctype>
+#include <cmath>
+#include <vector>
+#include <bitset>
+#include <set>
+#include <map>
+#include <stack>
+#include <queue>
+#include <ctime>
+#include <cassert>
+#define _for(i,a,b) for(int i=(a);i<(b);++i)
+#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
+#define mem(a,b) memset(a,b,sizeof(a))
+using namespace std;
+typedef long long LL;
+inline int read_int(){
+	int t=0;bool sign=false;char c=getchar();
+	while(!isdigit(c)){sign|=c=='-';c=getchar();}
+	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
+	return sign?-t:t;
+}
+inline LL read_LL(){
+	LL t=0;bool sign=false;char c=getchar();
+	while(!isdigit(c)){sign|=c=='-';c=getchar();}
+	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
+	return sign?-t:t;
+}
+inline char get_char(){
+	char c=getchar();
+	while(c==' '||c=='\n'||c=='\r')c=getchar();
+	return c;
+}
+inline void write(LL x){
+	char c[21],len=0;
+	if(!x)return putchar('0'),void();
+	if(x<0)x=-x,putchar('-');
+	while(x)c[++len]=x%10,x/=10;
+	while(len)putchar(c[len--]+48);
+}
+inline void space(LL x){write(x),putchar(' ');}
+inline void enter(LL x){write(x),putchar('\n');}
+const int MAXN=5e3+5,mod=998244353;
+int p[MAXN],inv[MAXN],cnt[MAXN][MAXN],dp[MAXN][MAXN];
+int main()
+{
+	int n=read_int(),ans=0;
+	_rep(i,1,n){
+		p[i]=read_int();
+		cnt[1][1]++;
+		cnt[1][p[i]+1]--;
+		cnt[i+1][1]--;
+		cnt[i+1][p[i]+1]++;
+	}
+	inv[1]=1;
+	_rep(i,2,n)inv[i]=1LL*(mod-mod/i)*inv[mod%i]%mod;
+	_rep(i,1,n)_rep(j,1,n)
+	cnt[i][j]+=cnt[i-1][j]+cnt[i][j-1]-cnt[i-1][j-1];
+	dp[1][0]=1;
+	_for(k,1,2*n){
+		_rep(i,max(k-n,1),min(n,k)){
+			int j=k-i;
+			dp[i+1][j]=(dp[i+1][j]+dp[i][j])%mod;
+			if(p[i]>p[j]){
+				int t=1LL*dp[i][j]*inv[cnt[i][p[j]+1]]%mod;
+				dp[i+1][j]=(dp[i+1][j]+mod-t)%mod;
+				dp[j+1][i]=(dp[j+1][i]+t)%mod;
+				ans=(ans+t)%mod;
+			}
+		}
+	}
 	enter(ans);
 	return 0;

CVBB ACM Team

用户工具

站点工具

差别

页面工具