T1:
考试时写了暴力，枚举每一个，然后判断的时候没有考虑中间过程可能不合法，20分没了
正解：类似数位dp的东西
f[i][x][y]在(x,y)到终点还有i步的方案数
f[0][ex][ey]=1
f[i][x][y]+=f[i-1][x+dx[i]][y+dy[i]]
然后就是怎么求值
ll slove(int *a,int l,bool fg) //a:数，l：长度，fg：a这个数算不算 { ll ans=0; int x=sx,y=sy,s=a[l]; for(int i=l-1;i>=1;i--) //考虑所有比a短的数的贡献 for(int j=1;j<=9;j++) if(check(x+dx[j],y+dy[j])) add(ans,f[i-1][x+dx[j]][y+dy[j]]); //1~1el-1 for(int i=1;i<s;i++) if(check(x+dx[i],y+dy[i])) add(ans,f[l-1][x+dx[i]][y+dy[i]]); //考虑首位不是比s小的贡献 x+=dx[s];y+=dy[s]; //1el~(s-1)el if(!check(x,y)) return ans%P; // x+=dx[s];y+=dy[s]; // add(ans,f[l-1][x][y]); for(int i=l-1;i>=1;i--) //考虑后面首位为s，后面的贡献 { s=a[i]; for(int j=0;j<s;j++) if(check(x+dx[j],y+dy[j])) add(ans,f[i-1][x+dx[j]][y+dy[j]]); x+=dx[s];y+=dy[s]; if(!check(x,y)) return ans%P; // add(ans,f[i-1][x][y]); } if(fg) if(check(x,y)) add(ans,f[0][x][y]); //由于我们每一位都没有到满，所以它自己其实并没有考虑，如果需要还要再加 return ans%P; }
T2：
考场上口胡了一个假的做法，即类似直径去求
我们设f[u]表示u下面的最大亦或和，然后有以下转移：
ans=max(ans,f[u]^f[v])
f[u]=max(f[u],f[v]^a[u])
然而这个算法是错的，只有10分
问题在于亦或不满足最优子结构
亦或的max不一定由两个最大的数亦或而成
T3：
放弃。输出-1，竟然由20分