D1T2 时间复杂度（模拟）
难点在于1.保持耐心 2.模拟题一定要在草稿纸上考虑各种情况&处理后打代码 3.多造几组卡/特殊的数据测试
#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; string a,b; int sen,com,cir,use[27],g[27],plex,go,ad[100],maxx,n,o; 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(){ o=read(); while(o>0){ sen=com=cir=plex=go=maxx=n=0;o--; memset(use,0,sizeof(use)),memset(ad,0,sizeof(ad)); while(b[0]!='O'){ a=b;cin>>b; } for(int i=0;i<a.length();i++) sen=sen*10+a[i]-'0'; for(int i=4;i<b.length()-1;i++) com=com*10+b[i]-'0'; while(sen>0){ sen--;cin>>a; if(a[0]=='F'){ cir++;cin>>a; if(use[a[0]-96]) cir=-1; else use[a[0]-96]=1,g[cir]=a[0]-96; cin>>a>>b; if(a[0]!='n'&&b[0]=='n'&&go==0) plex++,ad[cir]=1; else if(((a.length()==b.length()&&a>b)||(a.length()>b.length())||(a[0]=='n'&&b[0]!='n'))&&go==0) go=1,n=cir; } else{ maxx=max(maxx,plex);use[g[cir]]=0; if(ad[cir]==1) plex--,ad[cir]=0; cir--; if(n>0&&cir<n) go=n=0; } if(cir==-1) printf("ERR "),sen=-1; } if(cir>0) printf("ERR "); if(cir==0&&maxx==com) printf("Yes "); if(cir==0&&maxx!=com) printf("No "); } return 0; }
D1T3逛公园（）
D2T2 宝藏（DFS+剪枝）
40分的暴力分只要稳很好拿，注意自己造数据多测验。
看到n的范围这么小，大部分都会想到状压DP，但其实DFS+剪枝就可以非常快地跑过这道题，所以后期复习一定要注意基础算法的彻底理解与各种应用，比如这道题利用的是DFS求全排列的一种思想，并非常见的DFS操作。
正确性在于题面所给，“小明不想开发无用道路，即两个已经被挖掘过的宝藏 屋之间的道路无需再开发。”。
70分代码如下：
#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=20; int a[M],l[M],cost[M][M],ans=2e9,tmp,m,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; } inline void dfs(int x,int num){ if(num==n){ ans=min(tmp, ans); return; } if(tmp>=ans) return; For(i,1,n){ if(l[i]) continue; For(j,1,n){ if(cost[i][j]==2e9||!l[j]||i==j) continue; tmp+=l[j]*cost[j][i];l[i]=l[j]+1; dfs(i,num+1); tmp-=l[j]*cost[j][i];l[i]=0; } } } int main() { n=read(),m=read(); For(i,1,n){ For(j,1,n){ cost[i][j]=2e9; } } For(i,1,m){ int u=read(),v=read(),w=read(); cost[u][v]=cost[v][u]=min(cost[u][v],w); } For(i,1,n){ l[i]=1;dfs(i,1);l[i]=0; } printf("%lld ",ans); return 0; }
AC代码如下：
#include<bits/stdc++.h> #define For(i,l,r) for(int i=l;i<=r;i++) using namespace std; const int M=20; int n,m,c[M][M],d[M],du[M][M],tmp,p,vis[M],lev[M],cnt,tot,ans=2e9; inline int read(){ int 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 bool cmp(int a,int b){return c[p][a]<c[p][b];} inline void dfs(int x,int y){ For(i,x,cnt){ if(tot+tmp*lev[vis[i]]>=ans) return; For(j,y,d[vis[i]]){ if(!lev[du[vis[i]][j]]){ cnt++; vis[cnt]=du[vis[i]][j]; tmp-=c[vis[cnt]][du[vis[cnt]][1]]; tot+=c[vis[i]][vis[cnt]]*lev[vis[i]]; lev[vis[cnt]]=lev[vis[i]]+1; dfs(i,j+1); tot-=c[vis[i]][vis[cnt]]*lev[vis[i]]; lev[vis[cnt]]=0; tmp+=c[vis[cnt]][du[vis[cnt]][1]]; cnt--; } } y=1; } if(cnt==n){ if(tot<ans) ans=tot; return; } } int main(){ n=read(),m=read(); For(i,1,n){ For(j,1,n){ c[i][j]=2e9; } } For(i,1,m){ int u=read(),v=read(),w=read(); if(c[u][v]<w) continue; if(c[u][v]==2e9) du[u][++d[u]]=v,du[v][++d[v]]=u; c[u][v]=c[v][u]=w; } For(i,1,n){ p=i; sort(du[i]+1,du[i]+d[i]+1,cmp); tmp+=c[i][du[i][1]]; } For(i,1,n){ tot=0,cnt=1; vis[1]=i; tmp-=c[i][du[i][1]]; lev[i]=1; dfs(1,1); lev[i]=0; tmp+=c[i][du[i][1]]; } printf("%d ",ans); return 0; } /* 8 7 1 2 3 2 3 3 3 4 3 4 5 3 5 6 3 6 7 3 7 8 3 */