D1T1.铺设道路（贪心）
肯定要挖至少第一个坑的深度，再把后面比现在的坑的最深深度深的差值加起来，更新现在坑得最深深度（因为比现在最深深度浅的可以和之前的一起一次性处理，只用多花时间填更深的差值）。
#include<bits/stdc++.h> #define ll long long #define ri register int #define For(i,l,r) for(ri i=l;i<=r;i++) #define Dfor(i,r,l) for(ri i=r;i>=l;i--) using namespace std; int n,d,tmp; ll ans; inline ll read(){ ll f=1,sum=0; char ch=getchar(); while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();} while(isdigit(ch)){sum=(sum<<1)+(sum<<3)+(ch^48);ch=getchar();} return f*sum; } int main(){ n=read(); For(i,1,n){ d=read(); if(d>tmp) ans+=d-tmp; tmp=d; } printf("%lld ",ans); return 0; }
D1T2.货币系统（背包）
（瞪眼法）发现原有的货币中能且只能保留凑不出来的币值，能被凑出来的币值都不需要保留，背包可以解决。
#include<bits/stdc++.h> #define ri register int #define ll long long #define For(i,l,r) for(ri i=l;i<=r;i++) #define Dfor(i,r,l) for(ri i=r;i>=l;i--) using namespace std; const int M=25005; const int N=105; int T,a[N],f[M],ans,n; inline ll read(){ ll f=1,sum=0; char ch=getchar(); while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();} while(isdigit(ch)){sum=(sum<<1)+(sum<<3)+(ch^48);ch=getchar();} return f*sum; } int main(){ T=read(); while(T--){ n=read(); For(i,1,n) a[i]=read(); sort(a+1,a+n+1); f[0]=1; For(i,1,n){ if(f[a[i]]) continue; For(j,a[i],a[n]){ f[j]|=f[j-a[i]]; } ans++; } printf("%d ",ans); memset(f,0,sizeof(f));ans=0; } return 0; }
D1T3 赛道修建（菊花图+树的直径+二分答案）
55分大众分。
D2T1.旅行（DFS+拓扑排序+基环树）
数据显然分为两种情况
1. n=m-1：一棵树，vector存每个点的子点，点的编号从小到大sort一遍保证字典序最小，最后直接在树上跑dfs即可。
2. n=m： 一棵基环树，即树上有一个环，显然环上有一条边不用跑，拓扑排序（记录出度入度，这里因为无向边所以出度入度合在一起算）标记不在环上的点，然后枚举边，如果边的两个点都在环上那么删掉这条边在树上跑一遍dfs，再比较一下字典序更新答案，然后把边加回来。
#include<bits/stdc++.h> #define ri register int #define ll long long #define For(i,l,r) for(ri i=l;i<=r;i++) #define Dfor(i,r,l) for(ri i=r;i>=l;i--) using namespace std; const int M=5005; int n,m,head[M],ans[M],t,d[M],w[M][M],res[M]; struct node{ int u,v; }e[M<<1]; vector<int>vec[M]; bool vis[M],use[M]; inline ll read(){ ll f=1,sum=0; char ch=getchar(); while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();} while(isdigit(ch)){sum=(sum<<1)+(sum<<3)+(ch^48);ch=getchar();} return f*sum; } inline void work(){ if(!ans[1]){ For(i,1,n) ans[i]=res[i]; return; } For(i,1,n){ if(res[i]>ans[i]) return; if(res[i]<ans[i]){ For(i,1,n) ans[i]=res[i]; return; } } } inline void dfs(int x){ vis[x]=1;res[++t]=x; for(ri i=0;i<vec[x].size();i++){ int v=vec[x][i]; if(vis[v]||!w[x][v])continue; dfs(v); } } inline void topo(){ queue<int>q; For(i,1,n){ if(d[i]==1){ q.push(i); use[i]=1; } } while(!q.empty()){ int u=q.front(),len=vec[u].size(); q.pop(),use[u]=1; For(i,0,len-1){ int v=vec[u][i]; d[v]--; if(d[v]==1){ q.push(v); use[v]=1; } } } } int main(){ n=read(),m=read(); For(i,1,m){ int u=read(),v=read(); e[i]=(node){u,v}; d[u]++,d[v]++; w[u][v]=w[v][u]=1; vec[u].push_back(v),vec[v].push_back(u); } For(i,1,n){ sort(vec[i].begin(),vec[i].end()); } if(m==n-1){ dfs(1); For(i,1,n) printf("%d ",res[i]); return 0; } topo(); For(i,1,m){ int x=e[i].u,y=e[i].v; if(use[x]||use[y]) continue; w[x][y]=w[y][x]=0; memset(vis,0,sizeof(vis)); t=0;dfs(1);work(); w[x][y]=w[y][x]=1; } For(i,1,n) printf("%d ",ans[i]); return 0; }
D2T2.填数游戏（打表找规律）
数学证明显然不会也很麻烦。
这个表其实也不是很好打，跑dfs和一个判定合法与否的函数，看看代码:
#include<bits/stdc++.h> using namespace std; const int N=100;int a[N][N],ans,no_ans,las; inline void ok(int x,int y,int n,int m,int cur){ cur<<=1,cur+=a[x][y]; if(x==n&&y==m){ no_ans|=(cur<las);//比较大小 las=cur; return; } //下面三行也可以好好体会一下跑的顺序 if(y==m) ok(x+1,y,n,m,cur); else if(x==n) ok(x,y+1,n,m,cur); else ok(x,y+1,n,m,cur),ok(x+1,y,n,m,cur); return; } inline int can(int x,int y,int v){a[x][y]=v;no_ans=0;las=0;ok(1,1,x,y,0);return !no_ans; } inline int dfs(int x,int y,int n,int m){ if(x==n+1) return ++ans; for(int i=0;i<=1;i++){ if(can(x,y,i)){ a[x][y]=i; //下面两行好好体会一下路径走的顺序 if(y==m) dfs(x+1,1,n,m); else dfs(x,y+1,n,m); } } return 0; } inline int calc(int n,int m){ans=0;dfs(1,1,n,m);return ans;} int main(){ for(int n=2;n<=7;n++){ printf("ans(%d, %d) = %d ",n,n,calc(n,n)); printf("ans(%d, %d) = %d ",n,n+1,calc(n,n+1)); printf("ans(%d, %d) = %d ",n,n+2,calc(n,n+2)); printf("ans(%d, %d) = %d ",n,n+3,calc(n,n+3)); } return 0; }
然后就发现规律，
第一个很显然，n=1即第三个和n=2和n=3看数据范围就晓得可能有特殊性质，第二(n,m和n,m-1)、五（n+1,n+1和n,n）、六(n,n+1和n,n)个比较难看，基本上就是多猜特殊性质，多输出特殊的组（如n=1,2,3..或者n,n或者n,m和m-1/m+1,n,n和n+1,n+1等等）。
于是打出AC代码：
#include<bits/stdc++.h> #define ri register int #define ll long long #define For(i,l,r) for(ri i=l;i<=r;i++) #define Dfor(i,r,l) for(ri i=r;i>=l;i--) using namespace std; ll f[10],n,m; const int p=1e9+7; inline ll read(){ ll f=1,sum=0; char ch=getchar(); while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();} while(isdigit(ch)){sum=(sum<<1)+(sum<<3)+(ch^48);ch=getchar();} return f*sum; } inline ll ksm(ll a,ll b){ ll ans=1; while(b){ if(b&1) ans=1ll*ans*a%p; a=1ll*a*a%p; b>>=1; } return ans; } int main(){ n=read(),m=read(); if(n>m) swap(n,m); if(n==1){ printf("%lld ",ksm(2,m)); return 0; } f[2]=12,f[3]=112,f[4]=912; For(i,4,n-1) f[i+1]=(8ll*f[i]%p-10ll*ksm(2,i)%p+p)%p; if(n==m){ printf("%lld ",f[n]); return 0; } ll g; if(n==2) g=36; else if(n==3) g=336; else g=(3ll*(f[n]-ksm(2,n))%p+p)%p; printf("%lld ",(ll)g*ksm(3,m-n-1)%p); }