2021暑期cf加训2
比赛链接:https://codeforces.com/group/2g1PZcsgml/contest/338475
A,B,C,F,H,I,J,K;12;今天貌似比之前好了一点。
A
分析:
最长上升子序列。
代码如下:
#include<iostream> #include<cstring> using namespace std; int f[55][30]; char s[55]; int main() { scanf("%s",&s); int n=strlen(s); f[0][s[0]-'a']=1; for(int i=1;i<n;i++) { int c=s[i]-'a'; f[i][c]=1;// for(int j=0;j<26;j++)f[i][j]=max(f[i][j],f[i-1][j]); for(int j=0;j<c;j++)f[i][c]=max(f[i][c],f[i-1][j]+1); //printf("f[%d][%d]=%d ",i,c,f[i][c]); } int mx=0; for(int k=0;k<26;k++)mx=max(mx,f[n-1][k]); printf("%d ",26-mx); return 0; }
B
分析:
BFS。
代码如下:
#include<iostream> #include<queue> #include<cstring> using namespace std; int const N=55; int n,m,len,dx[4],dy[4],stx,sty,edx,edy,ans,vis[N][N][N]; char s[N][N],op[N]; struct Nd{ int x,y,p,cnt; bool operator < (const Nd &a) const {return cnt>a.cnt;} }; priority_queue<Nd>q; void init() { dx[0]=0; dy[0]=-1; dx[1]=1; dy[1]=0; dx[2]=0; dy[2]=1; dx[3]=-1; dy[3]=0; for(int i=0;i<=n;i++) for(int j=0;j<m;j++) { if(s[i][j]=='R')stx=i,sty=j; if(s[i][j]=='E')edx=i,edy=j; } } bool can(int x,int y){if(x<0||x>=n||y<0||y>=m)return 0; return s[x][y]!='#';}//=='.'走不到'E'! int chg(char c){if(c=='L')return 0; if(c=='D')return 1; if(c=='R')return 2; if(c=='U')return 3;} void bfs() { memset(vis,0x3f3f3f3f,sizeof vis); q.push((Nd){stx,sty,0,0}); int nx,ny; while(q.size()) { Nd t=q.top(); q.pop(); if(t.x==edx&&t.y==edy){ans=t.cnt; break;} if(vis[t.x][t.y][t.p]<=t.cnt)continue; vis[t.x][t.y][t.p]=t.cnt; //printf("x=%d y=%d p=%d cnt=%d vis=%d ",t.x,t.y,t.p,t.cnt,vis[t.x][t.y][t.p]); //bool fl=0; //if(t.x==0&&t.y==1&&t.p==2)fl=1,printf("!cnt=%d ",t.cnt); for(int i=0;i<=3;i++){ if(can((nx=t.x+dx[i]),(ny=t.y+dy[i]))&&vis[nx][ny][t.p]>t.cnt+1) q.push((Nd){nx,ny,t.p,t.cnt+1}); //if(fl)printf("can(%d,%d)=%d vis=%d t.cnt+1=%d ",nx,ny,can(nx,ny),vis[nx,ny,t.p],t.cnt+1); } //fl=0; if(t.p>=len)continue; q.push((Nd){t.x,t.y,t.p+1,t.cnt+1}); int dr=chg(op[t.p]); //if(t.x==1&&t.y==2&&t.p==3)fl=1,printf("!!cnt=%d ",t.cnt); if(can((nx=t.x+dx[dr]),(ny=t.y+dy[dr]))){ q.push((Nd){nx,ny,t.p+1,t.cnt}); //if(fl)printf("nx=%d ny=%d ",nx,ny); } else q.push((Nd){t.x,t.y,t.p+1,t.cnt}); } } int main() { scanf("%d%d",&n,&m); for(int i=0;i<n;i++)scanf("%s",&s[i]); scanf("%s",&op); len=strlen(op); init(); bfs(); printf("%d ",ans); return 0; }