2020-2021:teams:legal_string:组队训练比赛记录:contest3
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:组队训练比赛记录:contest3 [2021/07/18 09:44] 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 ===== | ||
| 行 65: | 行 234: | ||
| </hidden> | </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; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | ===== J. Journey among Railway Stations ===== | ||
| + | |||
| + | ==== 题意 ==== | ||
| + | |||
| + | 给定 $n$ 个车站，车站 $i$ 开放时间为 $[u_i,v_i]$，从车站 $i$ 到车站 $i+1$ 需要花费 $c_i$ 时间。接下来 $q$ 次操作： | ||
| + | |||
| + | - 询问是否可以从 $x$ 车站出发达到 $y$ 车站，初始时为 $0$ 时刻 | ||
| + | - 修改某个 $c_i$ | ||
| + | - 修改某个 $[u_i,v_i]$ | ||
| + | |||
| + | 注意只能在车站开放时间内进入车站，且车站 $i$ 只能直接到达车站 $i+1$。 | ||
| + | |||
| + | ==== 题解 ==== | ||
| + | |||
| + | 定义时间函数 $f(l,r,t)$ 表示起始时间为 $t$ 时从车站 $l$ 到车站 $r+1$ 需要花费的时间。不难发现 | ||
| + | |||
| + | $$ | ||
| + | f(i,i,t)=\begin{cases} | ||
| + | c_i, & 0\le t\le u_i\\ | ||
| + | c_i+(t-u_i), & u_i\lt t\le v_i | ||
| + | \end{cases} | ||
| + | $$ | ||
| + | |||
| + | 同时对任意 $i\le j\lt k$，有 $f(i,k,t)=f(j+1,k,f(i,j,t))$，利用数学归纳法可以证明 $f(i,j,t)$ 总是形如以下形式： | ||
| + | |||
| + | $$ | ||
| + | f(i,j,t)=\begin{cases} | ||
| + | y, & 0\le t\le x_1\\ | ||
| + | y+(t-x_1), & x_1\lt t\le x_2 | ||
| + | \end{cases} | ||
| + | $$ | ||
| + | |||
| + | 于是考虑线段树维护区间 $[l,r]$ 的时间函数 $f(l,r,t)$ 顺便维护区间合法性即可，时间复杂度 $O(n\log n)$。 | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | const int MAXN=1e6+5; | ||
| + | int u[MAXN],v[MAXN],c[MAXN]; | ||
| + | struct Node{ | ||
| + | bool legal; | ||
| + | LL x1,x2,y; | ||
| + | }s[MAXN<<2]; | ||
| + | Node add(const Node &a,const Node &b){ | ||
| + | Node c; | ||
| + | c.legal=a.legal&&b.legal; | ||
| + | if(c.legal){ | ||
| + | if(a.y>b.x2) | ||
| + | c.legal=false; | ||
| + | else if(a.y>=b.x1){ | ||
| + | c.x1=a.x1; | ||
| + | c.x2=min(a.x2,c.x1+b.x2-a.y); | ||
| + | c.y=b.y+a.y-b.x1; | ||
| + | } | ||
| + | else{ | ||
| + | c.x1=min(a.x2,a.x1+b.x1-a.y); | ||
| + | c.x2=min(a.x2,c.x1+b.x2-b.x1); | ||
| + | c.y=b.y; | ||
| + | } | ||
| + | } | ||
| + | return c; | ||
| + | } | ||
| + | int lef[MAXN<<2],rig[MAXN<<2]; | ||
| + | void push_up(int k){ | ||
| + | s[k]=add(s[k<<1],s[k<<1|1]); | ||
| + | } | ||
| + | void build(int k,int pos){ | ||
| + | s[k].legal=true; | ||
| + | s[k].x1=u[pos]; | ||
| + | s[k].x2=v[pos]; | ||
| + | s[k].y=u[pos]+c[pos]; | ||
| + | } | ||
| + | void build(int k,int L,int R){ | ||
| + | lef[k]=L,rig[k]=R; | ||
| + | int M=L+R>>1; | ||
| + | if(L==R){ | ||
| + | build(k,M); | ||
| + | return; | ||
| + | } | ||
| + | build(k<<1,L,M); | ||
| + | build(k<<1|1,M+1,R); | ||
| + | push_up(k); | ||
| + | } | ||
| + | void update(int k,int pos){ | ||
| + | if(lef[k]==rig[k]){ | ||
| + | build(k,pos); | ||
| + | return; | ||
| + | } | ||
| + | int mid=lef[k]+rig[k]>>1; | ||
| + | if(mid>=pos) | ||
| + | update(k<<1,pos); | ||
| + | else | ||
| + | update(k<<1|1,pos); | ||
| + | push_up(k); | ||
| + | } | ||
| + | Node query(int k,int L,int R){ | ||
| + | if(L<=lef[k]&&rig[k]<=R) | ||
| + | return s[k]; | ||
| + | int mid=lef[k]+rig[k]>>1; | ||
| + | if(mid>=R) | ||
| + | return query(k<<1,L,R); | ||
| + | else if(mid<L) | ||
| + | return query(k<<1|1,L,R); | ||
| + | else | ||
| + | return add(query(k<<1,L,R),query(k<<1|1,L,R)); | ||
| + | } | ||
| + | int main() | ||
| + | { | ||
| + | int T=read_int(); | ||
| + | while(T--){ | ||
| + | int n=read_int(); | ||
| + | _rep(i,1,n)u[i]=read_int(); | ||
| + | _rep(i,1,n)v[i]=read_int(); | ||
| + | _for(i,1,n)c[i]=read_int(); | ||
| + | build(1,1,n); | ||
| + | int q=read_int(); | ||
| + | while(q--){ | ||
| + | int opt=read_int(); | ||
| + | if(opt==0){ | ||
| + | int l=read_int(),r=read_int(); | ||
| + | Node ans=query(1,l,r); | ||
| + | if(ans.legal) | ||
| + | puts("Yes"); | ||
| + | else | ||
| + | puts("No"); | ||
| + | } | ||
| + | else if(opt==1){ | ||
| + | int pos=read_int(); | ||
| + | c[pos]=read_int(); | ||
| + | update(1,pos); | ||
| + | } | ||
| + | else{ | ||
| + | int pos=read_int(); | ||
| + | u[pos]=read_int(); | ||
| + | v[pos]=read_int(); | ||
| + | update(1,pos); | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| ====== 赛后总结 ===== | ====== 赛后总结 ===== | ||
| jxm：玄学场，打表、随机化yyds | jxm：玄学场，打表、随机化yyds | ||
| + | |||
| + | 王智彪：不会写大模拟的wzb是真的屑，细节处理不到位。 | ||
2020-2021/teams/legal_string/组队训练比赛记录/contest3.1626572692.txt.gz · 最后更改: 2021/07/18 09:44 由 jxm2001
