啊......又考了一次式
好像比上次又有了一点进步？心情稍微好了点吧
这次整场考试心态比较平和（也许是因为之前都考崩了这次也不太在乎成绩），能很冷静地思考题目
T1，没看懂题目然而得了40pts，233
T2，暴搜AC，我吹爆
T3，没看到数据范围，打了个啥也过不了的状压dp，只得到了骗的十分
总分40+100+10=150，rank7，继续加油吧
T1：引子
看懂题，直接模拟就好了
#include<bits/stdc++.h> #define ll long long #define cri const register int #define re register #define ll long long using namespace std; char s[1010][1010]; int xx[121000],yy[121000],v[1010][1010],is[1010][1010],dep[120010]; void walk(int,int,int,int); void dfs(cri x,cri y,cri now){ int a=x,b=y,aa=x,bb=y; while(s[a][b]!='|') b--; while(s[a+1][b]!='+') a++; while(s[aa][bb]!='|') bb++; while(s[aa+1][bb]!='+') aa++; while(s[a][b]!='+'){ if(s[a][b-1]=='-') walk(a,b-1,0,now); if(s[aa][bb+1]=='-') walk(aa,bb+1,1,now); a--;aa--; } printf("%d ",now); } void get(cri x,cri y,cri now){ int a=x,b=y; while(s[a][b]!='|') b--; while(s[a][b]!='+') a--; while(s[a][b+1]=='-'||s[a][b+1]=='+') is[a][b]=now,b++; is[a][b]=now; } int du[120010],f[120010],aa[120010]; int main(){ int n,m,num=0; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%s",s[i]+1); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(s[i][j]>='1'&&s[i][j]<='9'){ num++; int a=0; while(s[i][j]>='0'&&s[i][j]<='9') a=(a<<3)+(a<<1)+s[i][j]-'0',j++; aa[num]=a; xx[a]=i,yy[a]=j-1; } } } for(int i=1;i<=num;i++) get(xx[aa[i]],yy[aa[i]],aa[i]); dfs(xx[1],yy[1],1); } void walk(int x,int y,int iss,int now){ if(iss==2&&s[x][y]=='-'){ f[is[x][y]]=now; du[now]++; dfs(x+1,y,is[x][y]); return; } if(!iss) if(s[x][y]!='+') walk(x,y-1,0,now); else walk(x+1,y,2,now); if(iss==1){ if(s[x][y]!='+') walk(x,y+1,1,now); else walk(x+1,y,2,now); } if(iss==2){ if(s[x][y]!='+') walk(x+1,y,2,now); else if(s[x][y+1]=='-') walk(x,y+1,1,now); else walk(x,y-1,0,now); } }
T2：可爱精灵宝贝
嘛......dp的题解网上一大把，我写一下搜索的吧
我们观察每次行动一定是从一个小精灵跳到另一个小精灵
那么我们可以这样搜索：
1，将小精灵按位置sort
2，维护当前可跳到的左右两个小精灵
3，排除超时的小精灵
4，分别向左向右跳
可以再加一个最优性减枝，可以从32ms优化到25ms，233
#include<bits/stdc++.h> #define ll long long #define cri const register int #define re register #define ll long long using namespace std; int ma=0,n,k,m,ans=0,sum=0,can[5000]; struct node{ int a,b,t; friend bool operator <(const node A,const node B){ if(A.a==B.a) return A.b<B.b; return A.a<B.a; } }p[1100]; void dfs(cri sta,int l,int r,cri tim,int sor,int lst){ while(r<=m&&p[r].a==sta){ lst-=p[r].b; if(p[r].t>=tim) sor+=p[r].b; r++; } while(l&&p[l].a==sta){ lst-=p[l].b; if(p[l].t>=tim) sor+=p[l].b; l--; } if(lst+sor<=ans||sor+can[ma]-can[tim]<=ans) return; while(l&&p[l].t<sta-p[l].a+tim) lst-=p[l].b,l--; while(r<=m&&p[r].t<p[r].a-sta+tim) lst-=p[r].b,r++; if(!l&&r>m) { ans=max(ans,sor); return; } if(r<=m) dfs(p[r].a,l,r,tim+p[r].a-sta,sor,lst); if(l) dfs (p[l].a,l,r,tim+sta-p[l].a,sor,lst); } int main(){ scanf("%d%d%d",&n,&k,&m); for(int i=1;i<=m;i++){ scanf("%d%d%d",&p[i].a,&p[i].b,&p[i].t); if(abs(p[i].a-k)+1>p[i].t) --i,--m; else sum+=p[i].b,can[p[i].t]+=p[i].b,ma=max(p[i].t,ma); } for(int i=1;i<=ma;i++) can[i]+=can[i-1]; sort(p+1,p+m+1); int l=lower_bound(p+1,p+m+1,node{k,-1,0})-p; dfs(k,l-1,l,1,0,sum); printf("%d ",ans); }
T3：相互再归的鹅妈妈
%%%命运石之门
然而我并不会做，咕着以后再说吧