最后几天了，虽然一堆考试没复习，压力山大，不过都是小事。
这几次的vp我们发挥的还可以，稳铜了。
希望我们队在济南也能有一个好的结果，不留遗憾。

A. Ban or Pick, What’s the Trick

记忆化搜索，好久没做了。当时vp时写了个贪心，wa6了，就想到可能是dp了。
思路：
1.看到k的范围只有10，设计状态dp[round][numa][numb]：在已经进行i轮的基础上，A选了numa个英雄，B选了numb个英雄时的分数。
2.结束状态：当进行到n*2轮的时候，递归返回。
3.状态转移：由于从0开始累计操作，因此偶数轮A行动，奇数轮B行动。一个小的注意点，当A行动完，B行动的时候，需要通过(轮数+1)/2才是A行动的轮数。
4.每个人行动时，都有两种情况。选择己方英雄或ban掉对方英雄。
选择己方：res=max(res,dfs(round+1,numa+1,numb)+a[ra+1])
ban对方：res=max(res,dfs(round+1,numa,numb))此处轮数+1，但A的英雄数并没增加
5.A希望最大化分数，因此取max；B希望最小化分数，因此减去己方英雄值时候取min。

#include 
#define endl '\n'
#define int long long
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))using namespace std;
const int N =2e5+5;
const int inf=1e18;
const int mod=1e9+7;
const double eps=1e-8;
int n,k,a[N],b[N],dp[N][15][15];
int dfs(int round,int numa,int numb)
{if(round==2*n)return 0;if(dp[round][numa][numb]!=-inf)return dp[round][numa][numb];int ra=round/2-numb+numa;int rb=(round+1)/2-numa+numb;if(round%2==0){int res=-inf;if(numaint res=inf;if(numbmemset(dp,-inf,sizeof dp);cin>>n>>k;for(int i=0;i<=2*n;i++)for(int j=0;j<=k;j++) for(int s=0;s<=k;s++) dp[i][j][s]=-inf;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++) cin>>b[i];sort(a+1,a+n+1,greater());sort(b+1,b+n+1,greater());cout<ios;solve();return 0;
}

C. Customs Controls 2

1.各个点到点t的距离相同，需要从终点反向遍历，合并点集。
2.正向存边，处理得到每一个结点的度。
3.进行拓扑遍历合并后的DAG图，dp[u]表示从点1出发的路径长度。

#include 
#define endl '\n'
#define int long long
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
#define PII pair
#define re register
using namespace std;
const int N =7e5+5;
const int inf=1e18;
const int mod=1e9+7;
const double eps=1e-8;
int n,m,f[N],dp[N],d[N];
vectore[N],g[N];
vectormp;
int r_find(int r)
{if(f[r]==r) return f[r];f[r]=r_find(f[r]);return f[r];
}
void solve()
{cin>>n>>m;mp.clear();for(int i=0;i<=n;i++) f[i]=i,dp[i]=d[i]=0,e[i].clear(),g[i].clear();for(int i=1;i<=m;i++){int x,y;cin>>x>>y;e[y].push_back(x);mp.push_back({x,y});}for(int i=1;i<=n;i++){for(int v:e[i])f[r_find(v)]=r_find(e[i][0]);}for(auto cur:mp){int x=cur.first,y=cur.second;g[r_find(x)].push_back(r_find(y));d[r_find(y)]++;}int cnt=0;queueq;for(int i=1;i<=n;i++){if(f[i]==i){cnt++;if(d[i]==0)dp[i]=1,q.push(i);}}while(!q.empty()){int u=q.front();q.pop();cnt--;for(int v:g[u]){dp[v]=max(dp[u]+1,dp[v]);d[v]--;if(!d[v]) q.push(v);}}if(cnt) cout<<"No"<cout<<"Yes"<int ans=dp[r_find(i)];if(i!=1) ans-=dp[r_find(e[i][0])];cout<ios;int T;cin>>T;while(T--)solve();return 0;
}