2020-2021:teams:legal_string:组队训练比赛记录:contest3
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:组队训练比赛记录:contest3 [2021/07/18 11:20] jxm2001 |
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|比赛链接]] |
| ====== 题解 ====== | ====== 题解 ====== | ||
| + | |||
| + | ===== E. Escape along Water Pipe ===== | ||
| + | |||
| + | ==== 题意 ==== | ||
| + | |||
| + | 给一张 $n×m$ 的图，起点在 $(1,1)$ 坐标点的上方，终点在 $(n,m)$ 坐标点的下方。每个点有一个水管，其中 $(0,3)$ 是垂直的管，连接两个方向， $4$ 是水平管， $5$ 是竖直管，每个管子可以旋转 $90,180,270$ 度。问向起点灌水，能不能到达终点。 | ||
| + | |||
| + | 如果不能输出 $NO$ 。如果能，输出 $YES$ ，并输出方案，方案输出方式是 到达 $(x,y)$ 输出 $0,x,y$ 。如果需要旋转，请输出 $1,$ 旋转角度 $,$ 点横坐标 $,$ 点纵坐标。要求操作数不能超过 $20mn$ 。 $T$ 组数据。 | ||
| + | |||
| + | 数据范围： $T≤10000,2≤m,n≤1000$，并保证总共的 $n×m$ 不超过 $10^{6}$。 | ||
| + | |||
| + | ==== 题解 ==== | ||
| + | |||
| + | 一道恶心人的搜索/大模拟题。 | ||
| + | |||
| + | 显然需要 $BFS$ 搜一下，并且对于不同的管子，用类似的处理方式。首先是最基础的 $dx,dy$ 数组，表示位移方向。直管、弯管分别连接哪两个方向，要按照题目顺序标识，这样后面好处理。剩下就是标记是否到达，已经到达这个点(包括到达时的方向方向)上一个点的位置。然后就常规的 $BFS$ 搜索一遍，如果存在解，从终点往回找，存起来，最后输出即可，主要是细节很多。复杂度 $O(n×m)$ ，可以通过。 | ||
| + | |||
| + | <hidden 代码> | ||
| + | |||
| + | <code cpp> | ||
| + | |||
| + | #include<bits/stdc++.h> | ||
| + | using namespace std; | ||
| + | |||
| + | int dx[5] = {-1,0,1,0}, dy[5] = {0,1,0,-1}; | ||
| + | int a[1010][1010]; | ||
| + | int wg[4][2] = {{3,0},{0,1},{1,2},{2,3}}; | ||
| + | int zg[2][2] = {{1,3},{0,2}}; | ||
| + | char dp[1010][1010][4]; | ||
| + | int f[1010][1010][4]; | ||
| + | int n,m; | ||
| + | deque<int> q; | ||
| + | vector<int> pans; | ||
| + | const int maxn=1000+5; | ||
| + | |||
| + | bool check(int x,int y) { | ||
| + | return x>0&&x<=n+1&&y>0&&y<=m; | ||
| + | } | ||
| + | |||
| + | void dfs(int x,int y,int fx) { | ||
| + | int from = f[x][y][fx]; | ||
| + | if(!from) return; | ||
| + | int tmp=from; | ||
| + | int lfx=tmp%4; | ||
| + | tmp/=4; | ||
| + | int ly=tmp%maxn; | ||
| + | tmp/=maxn; | ||
| + | int lx=tmp; | ||
| + | dfs(lx,ly,lfx); | ||
| + | if(a[lx][ly]<4) { | ||
| + | for(int i=0; i<4; i++) { | ||
| + | int tmpi=0; | ||
| + | while(tmpi<2&&wg[i][tmpi]!=lfx) tmpi++; | ||
| + | if(tmpi==2) continue; | ||
| + | int llfx=wg[i][1-tmpi]; | ||
| + | int ffx=llfx>1?(llfx-2):(llfx+2); | ||
| + | if(ffx==fx) { | ||
| + | if(a[lx][ly]!=i) { | ||
| + | pans.push_back((i-a[lx][ly]+8)%4*maxn*maxn+lx*maxn+ly); | ||
| + | a[lx][ly]=i; | ||
| + | } | ||
| + | pans.push_back(lx*maxn+ly); | ||
| + | return; | ||
| + | } | ||
| + | } | ||
| + | } else { | ||
| + | for(int i=0; i<2; i++) { | ||
| + | int tmpi=0; | ||
| + | while(tmpi<2&&zg[i][tmpi]!=lfx) tmpi++; | ||
| + | if(tmpi==2) continue; | ||
| + | int llfx=zg[i][1-tmpi]; | ||
| + | int ffx=llfx>1?(llfx-2):(llfx+2); | ||
| + | if(ffx==fx) { | ||
| + | if(a[lx][ly]-4!=i) { | ||
| + | //printf("%d %d %d %d %d\n",maxn*maxn+lx*maxn+ly,lx,ly,a[lx][ly],i); | ||
| + | pans.push_back(maxn*maxn+lx*maxn+ly); | ||
| + | a[lx][ly]=i+4; | ||
| + | } | ||
| + | pans.push_back(lx*maxn+ly); | ||
| + | return; | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | |||
| + | int main() { | ||
| + | int t; | ||
| + | scanf("%d",&t); | ||
| + | while(t--) { | ||
| + | scanf("%d %d",&n,&m); | ||
| + | for(int i=1; i<=n; i++) { | ||
| + | for(int j=1; j<=m; j++) { | ||
| + | scanf("%d",&a[i][j]); | ||
| + | } | ||
| + | } | ||
| + | for(int i=1; i<=n+1; i++) { | ||
| + | for(int j=1; j<=m; j++) { | ||
| + | for(int k=0; k<4; k++) | ||
| + | dp[i][j][k]=f[i][j][k]=0; | ||
| + | } | ||
| + | } | ||
| + | dp[1][1][0]=1; | ||
| + | q.push_back(maxn*4+4); | ||
| + | while(!q.empty()) { | ||
| + | int qf=q.front(); | ||
| + | int tmp=qf; | ||
| + | q.pop_front(); | ||
| + | int fx=tmp%4; | ||
| + | tmp/=4; | ||
| + | int y=tmp%maxn; | ||
| + | tmp/=maxn; | ||
| + | int x=tmp; | ||
| + | if(tmp>n) continue; | ||
| + | if(a[x][y]<4) { | ||
| + | for(int i=0; i<4; i++) { | ||
| + | int tmpi=0; | ||
| + | while(tmpi<2&&wg[i][tmpi]!=fx) tmpi++; | ||
| + | if(tmpi==2) continue; | ||
| + | int lfx=wg[i][1-tmpi]; | ||
| + | int xx=x+dx[lfx],yy=y+dy[lfx]; | ||
| + | int ffx=lfx>1?(lfx-2):(lfx+2); | ||
| + | if(check(xx,yy)&&!dp[xx][yy][ffx]) { | ||
| + | dp[xx][yy][ffx]=1; | ||
| + | f[xx][yy][ffx]=qf; | ||
| + | q.push_back(xx*maxn*4+yy*4+ffx); | ||
| + | //printf("%d\n",xx*maxn*4+yy*4+ffx); | ||
| + | } | ||
| + | } | ||
| + | } else { | ||
| + | for(int i=0; i<2; i++) { | ||
| + | int tmpi=0; | ||
| + | while(tmpi<2&&zg[i][tmpi]!=fx) tmpi++; | ||
| + | if(tmpi==2) continue; | ||
| + | int lfx=zg[i][1-tmpi]; | ||
| + | int xx=x+dx[lfx],yy=y+dy[lfx]; | ||
| + | int ffx=lfx>1?(lfx-2):(lfx+2); | ||
| + | if(check(xx,yy)&&!dp[xx][yy][ffx]) { | ||
| + | dp[xx][yy][ffx]=1; | ||
| + | f[xx][yy][ffx]=qf; | ||
| + | q.push_back(xx*maxn*4+yy*4+ffx); | ||
| + | //printf("%d\n",xx*maxn*4+yy*4+ffx); | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | if(!dp[n+1][m][0]) { | ||
| + | puts("NO"); | ||
| + | continue; | ||
| + | } | ||
| + | puts("YES"); | ||
| + | pans.clear(); | ||
| + | dfs(n+1,m,0); | ||
| + | int sz=pans.size(); | ||
| + | printf("%d\n",sz); | ||
| + | for(int i=0; i<sz; i++) { | ||
| + | int tmp=pans[i]; | ||
| + | if(tmp<maxn*maxn) { | ||
| + | printf("%d %d %d\n",0,tmp%(maxn*maxn)/maxn,tmp%maxn); | ||
| + | }else { | ||
| + | printf("%d %d %d %d\n",1,tmp/(maxn*maxn)*90,tmp%(maxn*maxn)/maxn,tmp%maxn); | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | return 0; | ||
| + | } | ||
| + | |||
| + | </code> | ||
| + | |||
| + | </hidden> | ||
| ===== G. Game of Swapping Numbers ===== | ===== G. Game of Swapping Numbers ===== | ||
| 行 59: | 行 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; | ||
| 行 211: | 行 493: | ||
| jxm：玄学场，打表、随机化yyds | jxm：玄学场，打表、随机化yyds | ||
| + | |||
| + | 王智彪：不会写大模拟的wzb是真的屑，细节处理不到位。 | ||
2020-2021/teams/legal_string/组队训练比赛记录/contest3.1626578448.txt.gz · 最后更改: 2021/07/18 11:20 由 jxm2001
