2020-2021:teams:legal_string:组队训练比赛记录:contest3
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
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}$。 | 数据范围： $T≤10000,2≤m,n≤1000$，并保证总共的 $n×m$ 不超过 $10^{6}$。 | ||
| - | ===== 题解 ===== | + | ==== 题解 ==== |
| 一道恶心人的搜索/大模拟题。 | 一道恶心人的搜索/大模拟题。 | ||
| 行 228: | 行 228: | ||
| _for(i,0,min(n,k)) | _for(i,0,min(n,k)) | ||
| ans+=max(0,a[i]-b[i])*2; | 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); | enter(ans); | ||
| return 0; | return 0; | ||
2020-2021/teams/legal_string/组队训练比赛记录/contest3.1626589688.txt.gz · 最后更改: 2021/07/18 14:28 由 王智彪
