【比賽記錄】樹形dp專項測試1
A. Promises I Can't Keep
題目意為求以每個點為根時的期望得分的最大值，換根DP即可。
式子不太難推，半個小時就出來了。太長了不往這寫了。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
#define pb push_back
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=5e5+5;
int n,cnt[maxn];
double a[maxn],f[maxn];
vector<int> e[maxn];
il void dfs1(int u,int fa){
f[u]=a[u];
for(int v:e[u]){
if(v==fa){
continue;
}
dfs1(v,u);
cnt[u]++;
}
for(int v:e[u]){
if(v==fa){
continue;
}
f[u]+=f[v]/cnt[u];
}
}
il void dfs2(int u,int fa){
for(int v:e[u]){
if(v==fa){
continue;
}
double tmp=cnt[u]==1?a[u]:(((f[u]-a[u])*cnt[u]-f[v])/(cnt[u]-1)+a[u]);
f[v]=a[v]+((f[v]-a[v])*cnt[v]+tmp)/(cnt[v]+1);
cnt[v]++;
dfs2(v,u);
}
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
read(n);
for(int i=1,u,v;i<n;i++){
read(u)read(v);
e[u].pb(v),e[v].pb(u);
}
for(int i=1;i<=n;i++){
scanf("%lf",a+i);
}
dfs1(1,0),dfs2(1,0);
double ans=0;
for(int i=1;i<=n;i++){
ans=max(ans,f[i]);
}
// for(int i=1;i<=n;i++){
// cout<<f[i]<<" ";
// }
// puts("");
printf("%.4f",ans);
return 0;
}
}
int main(){return asbt::main();}
/*
4
1 2
2 3
2 4
1 2 3 4
*/
剛這個是考場代碼，直接0分。
原因是：
接下來電流會等概率且不重復經過一個點地流向一個葉子節點
一個葉子節點，不是一個子節點。。。
正解在這里
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
#define pb push_back
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=5e5+5;
int n,a[maxn],cnt[maxn],tot;
long double f[maxn];
vector<int> e[maxn];
il void dfs1(int u,int fa){
f[u]=a[u];
if(fa&&e[u].size()==1){
cnt[u]=1;
}
for(int v:e[u]){
if(v==fa){
continue;
}
dfs1(v,u);
cnt[u]+=cnt[v];
}
for(int v:e[u]){
if(v==fa){
continue;
}
f[u]+=f[v]*cnt[v]/cnt[u];
}
}
il void dfs2(int u,int fa){
for(int v:e[u]){
if(v==fa){
continue;
}
double tmp=(((f[u]-a[u])*cnt[u]-f[v]*cnt[v]))/(tot-cnt[v])+a[u];
tmp=(f[v]-a[v])*cnt[v]+tmp*(tot-cnt[v]);
cnt[v]=tot;
if(e[v].size()==1){
cnt[v]--;
}
f[v]=tmp/cnt[v]+a[v];
dfs2(v,u);
}
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
read(n);
for(int i=1,u,v;i<n;i++){
read(u)read(v);
e[u].pb(v),e[v].pb(u);
}
for(int i=1;i<=n;i++){
read(a[i]);
if(e[i].size()==1){
tot++;
}
}
dfs1(1,0);
// for(int i=1;i<=n;i++){
// cout<<cnt[i]<<" ";
// }
// puts("");
dfs2(1,0);
// for(int i=1;i<=n;i++){
// cout<<f[i]<<" ";
// }
// puts("");
long double ans=-1e18;
for(int i=1;i<=n;i++){
ans=max(ans,f[i]);
}
printf("%.4Lf",ans);
return 0;
}
}
int main(){return asbt::main();}
/*
5
1 2
2 3
3 4
4 5
1 2 3 4 5
*/
B. [COCI2016-2017#4] Rima
考場上想到了倒著建trie，也想到了父親和兒子只有兩種情況，但是忽略了一個很重要的性質，那就是因為沒有兩個相同的字符串，所以最后形成的字符串序列一定是一個長度先減后增的樣子。
所以可以在trie樹上搞一個很簡單的DP，設 \(dp[u]\) 表示以 \(u\) 為結尾的字符串在一端的最長序列，于是當 \(u\) 是一個結尾，且它的兒子也是一個結尾時，就可以轉移。
最終的答案一定是先減后增的情況，式子也不難推。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=3e6+5;
int n,tot,dp[maxn],end[maxn];
vector<pair<int,char> > e[maxn];
char s[maxn];
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
read(n);
for(int i=1;i<=n;i++){
scanf(" %s",s+1);
int len=strlen(s+1);
int p=0;
for(int j=len;j;j--){
for(auto x:e[p]){
if(x.sec==s[j]){
p=x.fir;
goto togo;
}
}
e[p].pb(mp(++tot,s[j]));
p=tot;
togo:;
}
end[p]++;
}
int ans=0;
for(int u=tot;~u;u--){
int mx1=0,mx2=0,cnt=0;
for(auto x:e[u]){
int v=x.fir;
cnt+=end[v];
if(dp[v]>mx1){
mx2=mx1;
mx1=dp[v];
}
else{
mx2=max(mx2,dp[v]);
}
}
if(end[u]){
dp[u]=mx1+max(cnt,1);
}
ans=max(ans,mx1+mx2+max(cnt-2,0)+end[u]);
}
printf("%d",ans);
return 0;
}
}
int main(){return asbt::main();}
C. [CEOI2020] 星際迷航
之前就出過一次這道題，當時改過了，但是那道題數據太水了，所以同一篇代碼拿到這里直接獲得7pts……
先咕著吧
D. 「SMOI-R1」Company
其實很簡單。設 \(a_i\) 為第 \(i\) 棵樹的根為最后的根時對答案的最大貢獻，\(b_i\) 為第 \(i\) 棵樹不為根時對答案的最大貢獻。那么答案為
\[\begin{align}
&\max_{i=1}^n(a_i+\sum_{j=1\land j\ne i}^nb_j)\\
=&\max_{i=1}^n(a_i-b_i)+\sum_{i=1}^nb_i
\end{align}
\]
對于 \(i=1\) 或 \(i=2\)，顯然 \(b_i\) 為 \(x\) 或 \(y\) 的深度，而 \(a_i\) 為離 \(x\) 或 \(y\) 最遠的葉子節點的距離。
對于 \(i\ge 3\)，\(b_i\) 為最深的葉子節點的深度，\(a_i\) 為相距最遠的兩個葉子節點的距離。
樹形DP即可。
然而實在是沒時間寫了，所以也咕著吧（逃
浙公網安備 33010602011771號