码蹄杯刷题

目录

树形dp

M0560

数据结构

MC0562

树形dp

M0560

思路：括号的性质，前缀（后缀）和不能为负数，令dp[u][val]为转移到u时后缀为val的方案数

dp[u][val]可能由两种状态转移过来：
dp[v][val+1]

dp[v][val-1]

两种状态内部的每一个子节点v是相对独立的，所以可以进行累乘

而dp[u][val]的方案数是两种方案数的总和

代码：

void solve(){ int n;cin>>n; vector<vector<int> >g(n+10); for(int i=1;i<=n-1;i++){ int u,v;cin>>u>>v; g[u].push_back(v),g[v].push_back(u); } if(n==1){ cout<<0<<endl; return; } vector<vector<int> >dp(n+10,vector<int>(n+10)); auto dfs=[&](auto &&dfs,int u,int fa)->void{ for(auto v:g[u]){ if(v==fa) continue; dfs(dfs,v,u); } if(g[u].size()==1&&u!=1){ dp[u][1]=1; return; } for(int val=0;val<=n;val++){ int res1=1; if(val<=n-1){ for(auto v:g[u]){ if(v==fa) continue; res1=res1*dp[v][val+1]%mod; } } else res1=0; int res2=1; if(val){ for(auto v:g[u]){ if(v==fa) continue; res2=res2*dp[v][val-1]%mod; } } else res2=0; dp[u][val]=(res1+res2)%mod; } };dfs(dfs,1,-1); cout<<dp[1][0]<<endl; }

数据结构

MC0562

思路：并查集+贪心

代码:

int p[N],cnt[N],edg[N]; int find(int x){ if(x==p[x]) return x; return p[x]=find(p[x]); } void merge(int a,int b){ int x=find(a),y=find(b); // if(x>y) swap(x,y); edg[x]+=1; if(x==y) return; cnt[x]+=cnt[y]; edg[x]+=edg[y]; p[y]=x; } void solve(){ int n,m;cin>>n>>m; for(int i=1;i<=n;i++) p[i]=i,cnt[i]=1; for(int i=1;i<=m;i++){ int u,v;cin>>u>>v; merge(u,v); } int ans=0; for(int i=1;i<=n;i++){ if(i==find(i)){ //cout<<i<<" "<<cnt[i]<<" "<<edg[i]<<endl; if(cnt[i]%2==edg[i]%2) ans+=cnt[i]; else ans+=cnt[i]-1; } } cout<<ans; }