这次真的是… 翻车了啊。 题目都不算难，但方法都没找到，所以…我废了… 诶，基础还是不够扎实啊，要多练练。 好了进正题 1.马拉松（HLOJ#1164） 2.Sta（HLOJ#1635） 3.穿越（HLOJ#1636） 4.最小瓶颈路（HLOJ#1637） （以上是考试的四道题目）
动规题被我做成深搜而且还被re也没谁了… emmm…题面的话… 我懒得搬了。 文件夹19.5.21里面有，HLOJ上表示没有，索性就不搬了，不然太麻烦了，所以之后也不会有了…见谅。 这题是原版的英文题面直接搬来的，翻译得半懂不懂… 很简单推的动规状态转移方程（就是我没想到要用动规，可怜呐 ）。 直接上代码
#include<bits/stdc++.h> using namespace std; #define s1(a,n) sort(a+1,a+n+1) #define s2(a,n) sort(a+1,a+n+1,mc) #define ll long long #define sg string #define st struct #define db double #define f1(i,l,r) for(int i=l;i<=r;++i) #define f2(i,r,l) for(int i=r;i>=l;--i) #define f3(i,a,b) for(int i=a;i;i=b) #define me(a,b) memset(a,b,sizeof(a)) #define sf scanf #define pf printf #define fi(a) freopen(a,"r",stdin) #define fo(a) freopen(a,"w",stdout) #define cn continue #define bk break #define rt return #define ct const ct int maxn=500+10; ct int maxm=+10; int n,k,x[maxn],y[maxn],f[maxn][maxn],tot=9999999; bool mc(int x,int y){ rt x>y; } void init(){ sf("%d%d",&n,&k); me(f,10); f[1][0]=0; f1(i,1,n) sf("%d%d",&x[i],&y[i]); } void work(){ f1(i,2,n) f1(j,0,min(i-1,k)) f1(h,1,i-1) if(j>=i-h-1) f[i][j]=min(f[i][j],f[h][j-i+h+1]+abs(x[i]-x[h])+abs(y[i]-y[h])); } void prin(){ pf("%d",f[n][k]); } int main(){ fi("marathon.in"); fo("marathon.out"); init(); work(); prin(); rt 0; }一道模板题做的极其狼狈，这题真的类似的都做过（树形dp例题5——HLOJ#870），然后一方什么都忘了乱敲… 真的心态不好有影响呐… 泪目的我不想多说什么了，上代码吧…
#include<bits/stdc++.h> using namespace std; #define s1(a,n) sort(a+1,a+n+1) #define s2(a,n) sort(a+1,a+n+1,mycmp) #define ll long long #define sg string #define st struct #define f1(i,l,r) for(int i=l;i<=r;++i) #define f2(i,r,l) for(int i=r;i>=l;--i) #define f3(i,a,b) for(int i=a;i;i=b) #define me(a,b) memset(a,b,sizeof(a)) #define sf scanf #define pf printf #define fo freopen const int maxn=1000000+10; st t5{ int x,y; }e[maxn*2]; ll n,ans=0,Top[maxn],Len[maxn],f[maxn]={},g[maxn],xx,yy; bool mycmp(int x,int y){ return x>y; } void init(int a,int b){ ++ans; e[ans].x=b; e[ans].y=Top[a]; Top[a]=ans; } void gg(int k,int fa){ Len[k]=1; f3(i,Top[k],e[i].y){ if(e[i].x==fa) continue; gg(e[i].x,k); Len[k]+=Len[e[i].x]; f[k]+=f[e[i].x]+Len[e[i].x]; } } void hh(int k,int fa){ if(k!=1) g[k]=g[fa]+n-Len[k]*2; f3(i,Top[k],e[i].y) if(e[i].x!=fa) hh(e[i].x,k); } void work(){ sf("%lld",&n); f1(i,1,n-1){ sf("%lld%lld",&xx,&yy); init(xx,yy); init(yy,xx); } gg(1,0); g[1]=f[1]; hh(1,0); } void print(){ ll sum=-1,cnt; f1(i,1,n) if(sum<g[i]) sum=g[i],cnt=i; pf("%lld",cnt); } int main(){ fo("sta.in","r",stdin); fo("sta.out","w",stdout); work(); print(); return 0; }（这个宏定义是有点早的版本，考试考完粘过来改了一下的）
（过的也太快了吧，没办法题面粘不好，如果以后能补一定补上…）. 这题吗，开始考虑太多然后后来才发现考虑多了，然后方法又用错了，只拿了40分… （呃，代码里有些多余的不想删了，然后本来是来加数据打个标程的，所以宏定义都没了，虽然现在发现没有用…）
#include<bits/stdc++.h> using namespace std; struct node{ int w; char c; }e[400100]; priority_queue< int,vector< int >,greater< int > >q; int n,ans=0,p=1; int main(){ freopen("dragons.in","r",stdin); freopen("dragons.out","w",stdout); scanf("%d\n",&n); for(int i=1;i<=n;i++){ char ch; int k; scanf("%c %d\n",&ch,&k); e[i].w=k; e[i].c=ch; } for(int i=1;i<n;i++){ if(e[i].c=='c') q.push(e[i].w); else if(e[i].c=='e'&&e[i].w==0){ printf("-1"); return 0; } else if(e[i].c=='e'&&i==p){ ++p; continue; } else while(q.size()>e[i].w-1) q.pop(); } if(q.size()<e[n].w){ printf("-1"); return 0; } else while(q.size()){ ans+=q.top(); q.pop(); } printf("%d",ans); return 0; }（这个大根堆很骚呐）
题目都没看懂就结束了（30分钟乱敲一通然后爆0了），时间没安排好呐，其实这题也不难的…就是我太菜了呐。 （总得有点福利吧） 所以最后这个代码也没宏定义。
#include <bits/stdc++.h> using namespace std; struct node{ int x,y,z; }a[200100]; int cnt=0,n,m,k,tot=0,head[100010],fa[100010],ans[1010]={},xx[1010],yy[1010],vis[1010]={}; void add(int x, int y, int z){ a[++tot].x=head[x]; head[x]=tot; a[tot].y=y; a[tot].z=z; } bool operator<(node x,node y){ return x.z<y.z; } int get(int x){ if(x==fa[x]) return x; return fa[x]=get(fa[x]); } void kruskal(){ for(int i=1;i<=n;i++) fa[i]=i; for(int i=1;i<=m;i++){ int x=get(a[i].x); int y=get(a[i].y); if (x == y) continue; fa[y]=x; for(int j=1;j<=k;j++) if(ans[j]==-1&&get(xx[j])==get(yy[j])) ans[j]=a[i].z; } int main() { freopen("package.in","r",stdin); freopen("package.out","w",stdout); memset(ans,-1,sizeof(ans)); scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=m;i++) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z); for(int i=1;i<=k;i++) scanf("%d%d",&xx[i],&yy[i]); sort(a+1,a+1+m); kruskal(); for(int i=1;i<=k;i++) printf("%d\n",ans[i]); return 0; }好的就这样吧，万一真的有人急着想要题面找我，QQ：905829370（虽然我想不会有）。 Over，感谢各位奆佬捧场，GYF感激不尽（orz）。
