dp

黑白树

一棵n个点的有根树,1号点为根,相邻的两个节点之间的距离为1。树上每个节点i对应一个值k[i]。每个点都有一个颜色,初始的时候所有点都是白色的。
你需要通过一系列操作使得最终每个点变成黑色。每次操作需要选择一个节点i,i必须是白色的,然后i到根的链上(包括节点i与根)所有与节点i距离小于k[i]的点都会变黑,已经是黑的点保持为黑。问最少使用几次操作能把整棵树变黑。

![]()![]()```

include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N=5e5+100;

vector<int>edge[N];
int n,dp[N],ans,node[N],val[N],f[N];

void dfs(int x,int fa) {
dp[x]=val[x];
for(auto &v:edge[x]) if(v!=fa) {
dfs(v,x);
dp[x]=max(dp[x],dp[v]-1);
}
if(!node[x]) {
ans++;
node[fa]=max(node[fa],dp[x]);
}
else node[fa]=max(node[fa],node[x]-1);
}

int main() {
cin>>n;int x;
for(int i=2;i<=n;i++) scanf("%d",&x),edge[x].push_back(i),f[i]=x;
for(int i=1;i<=n;i++) scanf("%d",&val[i]),val[i]--;
dfs(1,0);
cout<<ans;
}


View Code

# [F2 - Pictures with Kittens (hard version)](http://codeforces.com/contest/1077/problem/F2)

### 题意

给你一个数列aa,你需要选择mm个元素,使得连续的kk个元素都至少有一个被选中。

需要你最大化选出来的所有数的和。

### 题解

开多个滑动窗口优化

![]()![]()```
#include&lt;bits/stdc++.h&gt;
using namespace std;
typedef long long ll;
const int N=5e5+100;

ll mod1=1238532465;
ll mod2=2309412751;
ll mod=1e9+7;
map&lt;pair&lt;ll,ll&gt;,int&gt;mp;
int u[N],v[N],vis[N];
ll h1[N],h2[N];
ll m1[N],m2[N];
int main() {
    int cas;cin&gt;&gt;cas;
    m1[0]=m2[0]=1;
    for(int i=1;i&lt;=N-10;i++) {
        m1[i]=m1[i-1]*1235463%mod1;
        m2[i]=m2[i-1]*1030007%mod2;
    }
    while(cas--) {
        int n,m;
        cin&gt;&gt;n&gt;&gt;m;
        mp.clear();
        for(int i=1;i&lt;=n;i++) vis[i]=0,h1[i]=h2[i]=0;
        for(int i=1;i&lt;=m;i++) {
            scanf(&quot;%d%d&quot;,&amp;u[i],&amp;v[i]);
            if(u[i]==v[i]) {
                vis[u[i]]=1;
                continue;
            }
            h1[u[i]]=(h1[u[i]]+m1[v[i]])%mod1;
            h2[u[i]]=(h2[u[i]]+m2[v[i]])%mod2;
            h1[v[i]]=(h1[v[i]]+m1[u[i]])%mod1;
            h2[v[i]]=(h2[v[i]]+m2[u[i]])%mod2;
        }

        ll ans=0;
        for(int i=1;i&lt;=n;i++) if(!vis[i]) {
            ans+= mp[{h1[i],h2[i]}] ;
            mp[{h1[i],h2[i]}]++;
        }
        mp.clear();
        for(int i=1;i&lt;=n;i++) if(vis[i]) {
            ans+= mp[{h1[i],h2[i]}] ;
            mp[{h1[i],h2[i]}]++;
        }
        ll a1,a2,b1,b2;
        for(int i=1;i&lt;=m;i++) if(!vis[u[i]]&amp;&amp;!vis[v[i]]||vis[u[i]]&amp;&amp;vis[v[i]]) {
            if(u[i==v[i]) continue;
            a1=(h1[v[i]]-m1[u[i]]+mod1)%mod1;
            b1=(h2[v[i]]-m2[u[i]]+mod2)%mod2;
            a2=(h1[u[i]]-m1[v[i]]+mod1)%mod1;
            b2=(h2[u[i]]-m2[v[i]]+mod2)%mod2;
            if(a1==a2&amp;&amp;b1==b2) ans++;
        }
        cout&lt;&lt;ans&lt;&lt;endl;
    }
}

View Code

E - The Unbearable Lightness of Weights

题意

给你 nn 个砝码,你知道这些砝码都有什么质量,但是你无法将质量和确切的砝码一一对应。

你的朋友知道每个砝码各是什么质量,你现在可以问她一个问题。你指定一个 kk 和一个 ww,她会告诉你是否有 kk 个砝码质量总和为 ww,(并且给你指出那 kk 个砝码)。现在问你,在这次提问之后你可以确定几个砝码的质量。

题解

  • 可以观察发现 ,当数的种类小于等于2时,答案为n
  • 否则,只能对同一种数字进行询问,可以使用计数dp
  • 计数dp用unordermap来写比较方便

![]()![]()```

include<bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N=1e6+100;

unordered_map<int,int> mp[105];

int n,a[N],cnt[105],sum;

int main() {
cin>>n;
for(int i=1;i<=n;i++) {
cin>>a[i];
if(++cnt[a[i]]==1) sum++;
}
if(sum<=2) return printf("%d",n),0;
mp[0][0]=1;
for(int i=1;i<=100;i++) if(cnt[i]) {
for(int c=99;c>=0;c--) for(auto &v:mp[c]) {
for(int j=1;j<=cnt[i];j++) {
if(j+c>100) break;
mp[j+c][v.first+ij]+=v.second;
}
}
}
int ans=1;
for(int i=1;i<=100;i++) if(cnt[i]) {
for(int j=1;j<=cnt[i];j++)
if(mp[j][j
i]==1) ans=max(ans,j);
}
cout<<ans;
}


View Code

# [Tree](https://ac.nowcoder.com/acm/problem/19782)

### 题意:

修修去年种下了一棵树,现在它已经有n个结点了。
 修修非常擅长数数,他很快就数出了包含每个点的连通点集的数量。
 澜澜也想知道答案,但他不会数数,于是他把问题交给了你,输出mod1e9+7,n=1e5。

### 题解:

- 如果题目只要求求出每个点的子树内联通点集数量,那很显然是 所有儿子dp值加一 的积
- 当时往上衍生的方案数有点难处理,我们发现显然根结点的答案就是dp值
- 假设我们当前处理结点x,我们已知x的父节点的答案,那么很显然为那么往上面衍生的答案数很显然为temp: ans\[fa\]/(dp\[x\]+1) ,所以ans\[x\]=(temp+1)\*dp\[x\]
- 但是这题还有一个坑点 如果之前乘上一个dp\[x\]+1的时候,dp\[x\]+1%mod恰好为0,如今想要将其贡献消除,乘上一个逆元是做不到的
- 可以采用暴力消除影响

![]()![]()```
#include&lt;bits/stdc++.h&gt;
using namespace std;
typedef long long ll;
const int N=1e6+100;

const ll mod=1e9+7;

ll fast(ll x,ll n) {
    ll ans=1;
    for(;n;n&gt;&gt;=1,x=x*x%mod)
        if(n&amp;1) ans=ans*x%mod;
    return ans;
}
ll inv(ll x) {
    return fast(x,mod-2);
}

vector&lt;int&gt;edge[N];
ll dp[N],ans[N],sta[N],f[N];

void dfs(int x,int fa) {
    dp[x]=1;f[x]=fa;
    for(auto &amp;v:edge[x]) if(v!=fa) {
        dfs(v,x);
        dp[x]*=(dp[v]+1);
        dp[x]%=mod;
    }
}

void dfs2(int x,int fa) {
    if(x!=1) {
        if((dp[x]+1)%mod) {
            sta[x]=ans[fa]*inv(dp[x]+1)%mod;
            ans[x]=dp[x]*(1+sta[x])%mod;
        }
        else {
            ll temp=sta[fa]+1;
            for(auto v:edge[fa]) if(v!=x&amp;&amp;v!=f[fa])
                temp=temp*(dp[v]+1)%mod;
            sta[x]=temp;
            ans[x]=(temp+1)*dp[x]%mod;
        }
    }
    for(auto v:edge[x])
        if(v!=fa) dfs2(v,x);
}

int main() {
    int n;cin&gt;&gt;n;
    for(int i=1;i&lt;n;i++) {
        int u,v;
        scanf(&quot;%d%d&quot;,&amp;u,&amp;v);
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    dfs(1,0);
    ans[1]=dp[1];
    dfs2(1,0);
    for(int i=1;i&lt;=n;i++) {
        printf(&quot;%lld\n&quot;,ans[i]);
    }
}

View Code

变大!

![]()

题解:

注意长度为L的线段操作数为L/2,发现这一点就可以dp了

![]()![]()```

include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N=50+10;

int dp[N][N],n,a[N];
int main() {
int cas;cin>>cas;
while(cas--) {
cin>>n;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
memset(dp,0,sizeof dp);
for(int i=1;i<=n;i++) {
int maxx=a[i];
for(int j=i-1;j>=0;j--) {
for(int k=(i-j)/2;k<=i;k++)
dp[i][k]=max(dp[i][k],dp[j][k-(i-j)/2]+maxx*(i-j));
maxx=max(maxx,a[j]);
}
}
for(int i=1;i<=n;i++) printf("%d ",dp[n][i]);cout<<endl;
}

}


View Code

# [K重排列](https://ac.nowcoder.com/acm/contest/4137/J)

![]()

![]()![]()```
#include&lt;bits/stdc++.h&gt;
using namespace std;
typedef long long ll;
const int N=100+1000;
const ll mod=998244353;

ll fac[N],inv[N],inv1[N];
ll fast(ll x,ll n) {
    ll ans=1;
    for(;n;n&gt;&gt;=1,x=x*x%mod)
        if(n&amp;1) ans=ans*x%mod;
    return ans;
}
ll init(){
    fac[0]=fac[1]=1;
    for(int i=2;i&lt;N;i++) fac[i]=fac[i-1]*i%mod;
    inv[N-1]=fast(fac[N-1],mod-2);
    for(int i=N-2;i&gt;=0;i--)
        inv[i]=(inv[i+1]*(i+1))%mod;
    inv1[0]=inv1[1]=1;
    for(int i=2;i&lt;N;i++)
        inv1[i]=(mod-mod/i)*inv1[mod%i]%mod;
}

ll C(ll n,ll m) {
    if(!m||m==n) return 1;
    return ((fac[n]*inv[m]%mod*inv[n-m])%mod);
}
vector&lt;int&gt;a;
ll dp[60];
int main() {
    init();
    int cas;cin&gt;&gt;cas;
    while(cas--) {
        a.clear();memset(dp,0,sizeof dp);
        ll n,k;cin&gt;&gt;n&gt;&gt;k;
        for(int i=2;i&lt;=n&amp;&amp;i&lt;=k;i++) if(k%i==0) a.push_back(i);
        dp[0]=1;
        for(int i=1;i&lt;=n;i++) {
            dp[i]=dp[i-1];
            for(int v:a) if(i&gt;=v)
                dp[i]=(dp[i]+dp[i-v]%mod*C(i-1,v-1)%mod*fac[v]%mod*inv1[v]%mod)%mod;

        }
        cout&lt;&lt;dp[n]&lt;&lt;endl;
    }
}

View Code

CF1093F Vasya and Array

![]()

是大于等于len

dp容斥一下就行了

![]()![]()```

include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int mod=998244353;
const int N=1e5;
ll dp[N][101],s[N];

int n,k,len;
int cnt[N][101],a[N];
int main() {
cin>>n>>k>>len;
if(len==1) return printf("0"),0;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) {
for(int j=1;j<=k;j++)
cnt[i][j]=cnt[i-1][j]+(a[i]==-1||a[i]==j);
}
s[0]=1;
if(a[1]+1) dp[1][a[1]]=s[1]=1;
else {
for(int i=1;i<=k;i++) dp[1][i]=1;
s[1]=k;
}
for(int i=2;i<=n;i++) {
for(int j=1;j<=k;j++) {
if(a[i]!=-1&&a[i]!=j) continue;
dp[i][j]=s[i-1];
if(i>=len) {
int l=i-len;
if(cnt[i][j]-cnt[l][j]==len) {
dp[i][j]=(dp[i][j]-(s[l]-dp[l][j]+mod)%mod+mod)%mod;
}
}
s[i]=(s[i]+dp[i][j])%mod;
}
}
cout<<s[n];
}



View Code

声明:该文章系转载,转载该文章的目的在于更广泛的传递信息,并不代表本网站赞同其观点,文章内容仅供参考。

本站是一个个人学习和交流平台,网站上部分文章为网站管理员和网友从相关媒体转载而来,并不用于任何商业目的,内容为作者个人观点, 并不代表本网站赞同其观点和对其真实性负责。

我们已经尽可能的对作者和来源进行了通告,但是可能由于能力有限或疏忽,导致作者和来源有误,亦可能您并不期望您的作品在我们的网站上发布。我们为这些问题向您致歉,如果您在我站上发现此类问题,请及时联系我们,我们将根据您的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。