T1 引子
大模拟，很恶心的一道题，做了我俩小时。
这道题纯属考如何输入，解决问题代码十行，输入一百多行。
考试上错了几个点：
- 对题意理解不全，多考虑了很多无用情况。
- 没有用心思考，连样例都不能手玩出来。
- 桶的编号和桶的数量没分清。
- 没有考虑到桶的数量大于数组容量的情况。
然后，0分。
小弟不才。
1 #include<cstdio> 2 #define HZOI std 3 using namespace HZOI; 4 const int N=1003; 5 struct node{ 6 int s,x,z,y; 7 }pos[N*N]; 8 int n,m; 9 char a[N][N]; 10 int tot,be[N][N],num[N*N],vis[N][N]; 11 int when,gt[N<<6][N],ans[N]; 12 int tt,first[N*N]; 13 int dx[4]={0,0,-1,1},dy[4]={1,-1,0,0}; 14 void Dfs(int ); 15 inline char read(); 16 int main() 17 { 18 scanf("%d%d",&n,&m); 19 for (int i=1; i<=n; ++i) 20 for (int j=1; j<=m; ++j) 21 a[i][j]=read(); 22 for (int i=1,old=0; i<=n; ++i,old=0) 23 for (int j=1; j<=m; ++j) 24 if (a[i][j]=='.') old=0; 25 else if (a[i][j]=='+') 26 if (old==0) old=j; 27 else 28 { 29 int g=i+1,flag=0; 30 while (a[g][old]=='|' and a[g][j]=='|') ++g; 31 if (a[g][old]!='+' or a[g][j]!='+') flag=1; 32 else 33 for (int k=old+1; k<j; ++k) 34 if (a[g][k]!='-') 35 flag=1; 36 if (flag) continue; 37 else 38 for (int k=i+1; k<g; ++k) 39 { 40 for (int h=old+1; h<j; ++h) 41 if (a[k][h]^'.') {flag=(flag<<3)+(flag<<1)+(a[k][h]-48);continue;} 42 if (flag) break; 43 } 44 for (int k=i; k<=g; ++k) be[k][old]=be[k][j]=flag; 45 for (int k=old; k<=j; ++k) be[i][k]=be[g][k]=flag; 46 num[++tot]=flag; 47 pos[num[tot]].s=i,pos[num[tot]].x=g; 48 pos[num[tot]].z=old,pos[num[tot]].y=j; 49 old=0; 50 } 51 for (int i=1; i<=tot; ++i) 52 { 53 int id=num[i]; 54 int bian1=pos[id].z-1,bian2=pos[id].y+1; 55 for (int j=pos[id].s; j<=pos[id].x; ++j) 56 { 57 if (a[j][bian1]=='-') 58 { 59 int posi=j,posj=bian1,odi,odj; 60 vis[posi][posj]=vis[posi][posj+1]=1; 61 while (!be[posi][posj]) 62 if (a[posi][posj]=='-') 63 { 64 if (!vis[posi][posj-1] ) vis[posi][posj--]=1; 65 else vis[posi][posj++]=1; 66 continue; 67 } 68 else if (a[posi][posj]=='+') 69 { 70 for (int k=0; k<4; ++k) 71 if (vis[posi+dx[k]][posj+dy[k]] and posi+dx[k]>0 and posi+dx[k]<=n and posj+dy[k]>0 and posj+dy[k]<=m) 72 odi=posi+dx[k],odj=posj+dy[k]; 73 if (a[odi][odj]=='|') 74 { 75 if (a[posi][posj+1]=='-') vis[posi][posj++]=1; 76 else if (a[posi][posj-1]=='-') vis[posi][posj--]=1; 77 continue; 78 } 79 else if (a[odi][odj]=='-') { vis[posi++][posj]=1; continue; } 80 } 81 else if (a[posi][posj]=='|') { vis[posi++][posj]=1; continue; } 82 gt[id][++gt[id][0]]=be[posi][posj]; 83 } 84 if (a[j][bian2]=='-') 85 { 86 int posi=j,posj=bian2,odi,odj; 87 vis[posi][posj]=1,vis[posi][posj-1]=1; 88 while (!be[posi][posj]) 89 if (a[posi][posj]=='-') 90 { 91 if (!vis[posi][posj-1]) vis[posi][posj--]=1; 92 else vis[posi][posj++]=1; 93 continue; 94 } 95 else if (a[posi][posj]=='+') 96 { 97 for (int k=0; k<4; ++k) 98 if (vis[posi+dx[k]][posj+dy[k]] and posi+dx[k]>0 and posi+dx[k]<=n and posj+dy[k]>0 and posj+dy[k]<=m) 99 odi=posi+dx[k],odj=posj+dy[k]; 100 if (a[odi][odj]=='|') 101 { 102 if (a[posi][posj+1]=='-') vis[posi][posj++]=1; 103 else if (a[posi][posj-1]=='-') vis[posi][posj--]=1; 104 continue; 105 } 106 else if (a[odi][odj]=='-') { vis[posi++][posj]=1; continue; } 107 } 108 else if (a[posi][posj]=='|') { vis[posi++][posj]=1; continue; } 109 gt[id][++gt[id][0]]=be[posi][posj]; 110 } 111 } 112 } 113 Dfs(1); 114 for (int i=1; i<=when; ++i) 115 printf("%d ",ans[i]); 116 return 0; 117 } 118 void Dfs(int k) 119 { 120 for (int i=gt[k][0]; i; --i) 121 Dfs(gt[k][i]); 122 ans[++when]=k; 123 } 124 inline char read() 125 { 126 char cc=getchar(); 127 while (cc!='.' and cc!='|' and cc!='-' and cc!='+' and (cc<'0' or cc>'9')) cc=getchar(); 128 return cc; 129 }
T2 可爱精灵宝贝
正解$dp$，毒瘤搜索可是跑过而且飞快（可能是因为数据确实水，$20ms$$AC$的人出极限数据一般跑不过）。
而我连个搜索都不会打，真的。
$dp$定义连状态都错了。
首先离散化，这个很显然了，可是我考试竟然连离散化都不知道。
这道dp题状态还是挺新颖的，定义$f_{i,j,k}$表示我已经走过了$i$到$j$的区间并且现在在$i$点，花费$k$时间所获得的最大收益，$g_{i,j,k}$表示我已经走过了$i$到$j$区间并且现在在$j$点，花费$k$时间所获得的最大收益。
知道了状态，接下来也就不难转移了。
题解上有一个空间优化，就是把g数组和f数组合并到一起，也就是让$f_{i,j,k}$ $i>j$的部分作为g数组，具体的不再赘述。
为了计算$dp$值，我们离散化之后要记录一个距离前缀和，以便很快的计算花费。
还有，在转移$dp$的时候，要考虑清楚$f$和$g$之间的转化，不能盲目的$f$只转移到$f$，$g$只转移到$g$。（然而这题数据水到我dp转移都是错的但是A了，还好及时改正了）。
小弟不才。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #define HZOI std 5 using namespace HZOI; 6 const int N=2e3+3; 7 struct node{ 8 int a,b,t; 9 friend bool operator < (node x,node y) 10 { 11 return x.a<y.a; 12 } 13 }pos[N]; 14 int n,m,k,maxt,ans; 15 int a[N],b[N],c[N],d[N],t[N],cst[N],low[N]; 16 int f[103][103][N],g[103][103][N]; 17 void Dfs(int ,int ); 18 inline int read(); 19 inline int max(int a,int b) {return a>b?a:b;} 20 inline int abs(int a) {return a>0?a:-a;} 21 int main() 22 { 23 n=read(),k=read(),m=read(); 24 for (int i=1; i<=m; ++i) 25 pos[i].a=read(),pos[i].b=read(),pos[i].t=read(),maxt=max(maxt,pos[i].t),c[i]=pos[i].a; 26 sort(c+1,c+m+1); 27 sort(pos+1,pos+m+1); 28 for (int i=1; i<=m; ++i) 29 cst[i]=cst[i-1]+pos[i].a-pos[i-1].a; 30 int len=unique(c+1,c+m+1)-c-1; 31 for (int i=1; i<=m; ++i) 32 { 33 low[i]=abs(k-pos[i].a)+1; 34 pos[i].a=lower_bound(c+1,c+len+1,a[i])-c; 35 } 36 for (int i=1; i<=m; ++i) 37 f[i][i][low[i]]=g[i][i][low[i]]=low[i]>pos[i].t?0:pos[i].b; 38 for (int h=0; h<=maxt; ++h) 39 for (int i=1; i<=m; ++i) 40 { 41 if (h<low[i]) continue; 42 for (int j=i; j<=m; ++j) 43 { 44 if (h<low[j]) continue; 45 if (i>1) f[i-1][j][h+cst[i]-cst[i-1]]=max(f[i-1][j][h+cst[i]-cst[i-1]],f[i][j][h]+(h+cst[i]-cst[i-1]>pos[i-1].t?0:pos[i-1].b)); 46 if (j<m) g[i][j+1][h+cst[j+1]-cst[i]]=max(g[i][j+1][h+cst[j+1]-cst[i]],f[i][j][h]+(h+cst[j+1]-cst[i]>pos[j+1].t?0:pos[j+1].b)); 47 if (j<m) g[i][j+1][h+cst[j+1]-cst[j]]=max(g[i][j+1][h+cst[j+1]-cst[j]],g[i][j][h]+(h+cst[j+1]-cst[j]>pos[j+1].t?0:pos[j+1].b)); 48 if (i>1) f[i-1][j][h+cst[j]-cst[i-1]]=max(f[i-1][j][h+cst[j]-cst[i-1]],g[i][j][h]+(h+cst[j]-cst[i-1]>pos[i-1].t?0:pos[i-1].b)); 49 ans=max(ans,max(f[i][j][h],g[i][j][h])); 50 } 51 } 52 printf("%d ",ans); 53 } 54 inline int read() 55 { 56 int nn=0; char cc=getchar(); 57 while (cc<'0' or cc>'9') cc=getchar(); 58 while (cc>='0' and cc<='9') nn=(nn<<3)+(nn<<1)+(cc^48),cc=getchar(); 59 return nn; 60 }
T3 相互再归的鹅妈妈
去网上搜一下这个题，然后发现，这个题不可做。
咕了。