• 树形DP杂题

    引

    对老师布置的题目稍微记录一下吧
    也算对树形 D P DP DP 的巩固

    T1 Ostap and Tree

    题目传送门

    由于有 距离 k 距离k 距离k 的限制，设计二维 d p dp dp

    设计状态：

    f i , j : i 的子树内，离 i 最近的染色点与 i 距离为 j 且若 j < = k , 那么 i 的子树满足题目限制的方案数 f_{i,j}:i的子树内 ，离i最近的染色点与i距离为j\\ 且若j<=k,那么i的子树满足题目限制的方案数 fi,j​:i的子树内，离i最近的染色点与i距离为j且若j<=k,那么i的子树满足题目限制的方案数

    状态转移：

    考虑父节点 u u u 与 子节点 v v v 的合并
    若枚举 i , j i,j i,j ,那么考虑 f u , i f_{u,i} fu,i​ 与 f v , j f_{v,j} fv,j​ 可以转移到哪里
    我们有 ：
    1.当 i + j ≤ k ∗ 2 i+j\leq k*2 i+j≤k∗2 时
    \quad f u , min ⁡ ( i , j ) ← f u , i ∗ f v , j f_{u,\min(i,j)} \gets f_{u,i} *f_{v,j} fu,min(i,j)​←fu,i​∗fv,j​
    2.当 i + j > k ∗ 2 i+j> k*2 i+j>k∗2 时
    \quad f u , max ⁡ ( i , j ) ← f u , i ∗ f v , j f_{u,\max(i,j)} \gets f_{u,i} *f_{v,j} fu,max(i,j)​←fu,i​∗fv,j​
    只能说都是状态设计的功劳

    #include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int N=2e2+7,K=55 , INF=1e9;
const ll mod=1e9+7;
int n,k;
ll f[N][K],ans;
vector G[N];
void dfs(int u,int fa) {
	f[u][0]=f[u][k+1]=1;
	for(int v:G[u]) {
		if(v== fa) continue; 
		dfs(v,u);
		vector tmp(k*2+5) ;
		for(int i=0;i<=k<<1;i++) for(int j=0;j<=k<<1;j++) {
			if(i+j<=(k<<1))tmp[min(i,j+1)]=(tmp[min(i,j+1)]+f[u][i]*f[v][j]%mod)%mod;
			else tmp[max(i,j+1)]=(tmp[max(i,j+1)]+f[u][i]*f[v][j]%mod) %mod;
		}
		for(int i=0;i<=k<<1;i++) f[u][i]=tmp[i];
	}
}
int main() {
	scanf("%d%d",&n,&k);
	for(int i=1,u,v;i
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34

    T2 实验比较

    题目传送门

    显然 ，根据 < < < 关系建边， = = = 缩点
    若没有 = = = ,那么这将是一道十分友好的题，稍微运用一下组合数学即可，状态也会十分简单
    多设一维限制 = = = 等号即可，注意判环的无解情况

    #include 
#include 
#include 
#include 
#include 
using namespace std;
inline int read() {
	int res = 0; bool bo = 0; char c;
	while (((c = getchar()) < '0' || c > '9') && c != '-');
	if (c == '-') bo = 1; else res = c - 48;
	while ((c = getchar()) >= '0' && c <= '9')
		res = (res << 3) + (res << 1) + (c - 48);
	return bo ? ~res + 1 : res;
}
inline char get() {
	char c; while ((c = getchar()) != '<' && c != '='); return c;
}
const int N = 135, M = 265, ZZQ = 1e9 + 7;
int n, m, X[N], Y[N], fa[N], ecnt, nxt[M], adj[N], go[M], in[N], cnt[N],
f[N][N], sze[N], C[N][N], g[N];
bool eq[N], its[N];
void init() {
	int i, j; for (i = 0; i <= 120; i++) C[i][0] = 1;
	for (i = 1; i <= 120; i++) for (j = 1; j <= i; j++)
		C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % ZZQ;
}
void add_edge(int u, int v) {
	nxt[++ecnt] = adj[u]; adj[u] = ecnt; go[ecnt] = v;
	nxt[++ecnt] = adj[v]; adj[v] = ecnt; go[ecnt] = u;
}
int cx(int x) {
	if (fa[x] != x) fa[x] = cx(fa[x]);
	return fa[x];
}
bool zm(int x, int y) {
	int ix = cx(x), iy = cx(y);
	if (ix != iy) fa[iy] = ix;
	else return 1;
	return 0;
}
void dfs(int u, int fu) {
	int i, j, k; sze[u] = f[u][1] = 1;
	for (int e = adj[u], v; e; e = nxt[e]) {
		if ((v = go[e]) == fu) continue; dfs(v, u);
		for (i = 1; i <= n; i++) g[i] = 0;
		for (i = 1; i <= sze[u] + sze[v]; i++) for (j = 1; j <= sze[u]; j++)
		for (k = 1; k <= sze[v]; k++) {
			int x = k - i + j; if (x < 0) continue;
			(g[i] += 1ll * f[u][j] * f[v][k] % ZZQ *
				C[i - 1][j - 1] % ZZQ * C[j - 1][x] % ZZQ) %= ZZQ;
		}
		for (i = 1; i <= sze[u] + sze[v]; i++) f[u][i] = g[i];
		sze[u] += sze[v]; 
	}
}
int main() {
	int i; n = read(); m = read(); init();
	for (i = 1; i <= n; i++) fa[i] = i;
	for (i = 1; i <= m; i++) X[i] = read(),
		eq[i] = get() == '=', Y[i] = read();
	for (i = 1; i <= m; i++) if (eq[i]) zm(X[i], Y[i]);
	for (i = 1; i <= n; i++) its[in[i] = cx(i)] = 1;
	for (i = 1; i <= n; i++) fa[i] = i;
	for (i = 1; i <= m; i++)
		if (!eq[i]) {
			add_edge(in[X[i]], in[Y[i]]); cnt[in[Y[i]]]++;
			if (zm(in[X[i]], in[Y[i]])) return printf("0\n"), 0;
		}
	for (i = 1; i <= n; i++) if (its[i] && !cnt[i]) add_edge(n + 1, i);
	int ans = 0; dfs(n + 1, 0); for (i = 1; i <= sze[n + 1]; i++)
		ans = (ans + f[n + 1][i]) % ZZQ; cout << ans << endl;
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73

    T3 podjela

    题目传送门

    对题目中的限制，第二维开不下…
    观察到答案的数量级应该是与 n n n 同阶
    严谨的证明一下就是 a n s ≤ n − 1 ans\le n-1 ans≤n−1
    因为 n − 1 n-1 n−1 次后我们一定可以将每一条边遍历到，合理规划方案即可满足条件
    那么就有了状态，将答案放进状态中，最后统计合法的最值即可

    设计状态：

    f i , j : i 的子树中，操作 j 次后，除 i 的节点都合法， i 最多能获得的钱 f_{i,j} :i的子树中，操作j次后，除i的节点都合法，i最多能获得的钱 fi,j​:i的子树中，操作j次后，除i的节点都合法，i最多能获得的钱
    注意，可能会欠款，也就是 f i , j < 0 f_{i,j}<0 fi,j​<0

    状态转移：

    转移是个树上背包
    f u , i + j + 1 ← f u , i + f v , j ( v 的钱转移到 i 上 ) 若 v 不欠款，即 f v , j ≥ 0 , 就有 f u , i + j ← f u , i f_{u,i+j+1}\gets f_{u,i}+f_{v,j}(v的钱转移到i上)\\ 若v不欠款，即f_{v,j}\ge0,就有f_{u,i+j}\gets f_{u,i} fu,i+j+1​←fu,i​+fv,j​(v的钱转移到i上)若v不欠款，即fv,j​≥0,就有fu,i+j​←fu,i​

    a n s ans ans就是第一个 f 1 , i ≥ 0 f_{1,i}\ge0 f1,i​≥0时取i即可

    #include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int N=2e3+7,INF=1e9;
int n,X;
int v[N],f[N][N],sz[N],g[N];
vectorG[N];
void dfs(int u,int fa) {
	for(int i=0;i<=n;i++) f[u][i]=-INF;
	f[u][0]=X-v[u],sz[u]=1;
	for(int v:G[u]) {
		if(v==fa) continue;
		dfs(v,u); 
		sz[u]+=sz[v];
		for(int i=0;i<=sz[u]+1;i++) g[i]=-INF;
		for(int i=0;i<=sz[u]-sz[v];i++) {
			for(int j=0;j<=sz[v];j++) {
				g[i+j+1]=max(g[i+j+1],f[u][i]+f[v][j]);
				if(f[v][j]>=0) g[i+j]=max(g[i+j],f[u][i]);
			}
		}
		for(int i=0;i<=sz[u]+1;i++) f[u][i]=g[i];
	}
}
int main(){
	scanf("%d%d",&n,&X);
	for(int i=1;i<=n;i++) scanf("%d",&v[i]);
	for(int i=1,u,v;i=0) return printf("%d\n",i),0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38

    T4 赛道修建

    题目传送门

    • 二分答案 + 贪心 二分答案+贪心 二分答案+贪心 即可，贪心时用好 s e t set set 即可
      据说可以用 v e c t o r vector vector 维护，不过又不卡 s e t set set 不用白不用
      代码虚长
    #include 
#include 
#include 
using namespace std;
const int N=5e4+7;
int n,m,head[N],tot,ans,up;
struct node{ int to,next,w; }e[N<<1];

multiset s[N];
multiset::iterator it;

inline int read(){
    register int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return (f==1)?x:-x;
}

void Add(int x,int y,int w){
	e[++tot]=(node) {y,head[x],w};
    head[x]=tot;
}

int Dfs(int x,int fa,int k){
    s[x].clear();
    for(int i=head[x],y,val;i;i=e[i].next){
        y=e[i].to; if(y==fa) continue;
        val=Dfs(y,x,k)+e[i].w;
        if(val>=k) ans++;
        else s[x].insert(val);
    }
    int Max=0;
    while(!s[x].empty()){
        if(s[x].size()==1) return max(Max,*s[x].begin());
        it=s[x].lower_bound(k-*s[x].begin());
        if(it==s[x].begin()&&s[x].count(*it)==1) it++;
        if(it==s[x].end()){
            Max=max(Max,*s[x].begin());
            s[x].erase(s[x].begin());
        }
        else {
            ans++;
            s[x].erase(s[x].find(*it));
            s[x].erase(s[x].find(*s[x].begin()));
        }
    }
    return Max;
}

int Check(int k){
    ans=0;
    Dfs(1,0,k);
    return (ans>=m);
}

int Dfs1(int x,int fa){
    int sum1=0,sum2=0;
    for(int i=head[x],y;i;i=e[i].next){
        y=e[i].to; if(y==fa) continue;
        sum2=max(sum2,Dfs1(y,x)+e[i].w);
        if(sum1>1;
        if(Check(mid)) l=mid;
        else r=mid-1;
    }
    printf("%d\n",l);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82

    T5 Aerial Tramway

    题目传送门

    很有意思的一题，直入主题
    引用别人的话：

    我们首先发觉每个可以连的区间都是不相交的，只有相邻和包含关系，所以是 O ( n ) O(n) O(n) 个（其实最多只有 n 2 \frac{n}{2} 2n​ 个）。然后这段区间跟相邻的是没有关系的。跟这段区间有关的只有包含的区间。所以我们可以递归的考虑这个问题。

    一段区间与其包含的区间之间建边

    设计状态：

    f i , j , k : i 的子树分配了 j 个缆车，子树内被覆盖最多的点被覆盖了 k 次 f_{i,j,k}:i的子树分配了j个缆车，子树内被覆盖最多的点被覆盖了k次 fi,j,k​:i的子树分配了j个缆车，子树内被覆盖最多的点被覆盖了k次

    状态转移

    是一个经典的树上背包，注意 前缀 max ⁡ 前缀\max 前缀max 优化,单次求解为 O ( n 2 ) O(n^2) O(n2)
    总的复杂度为 O ( T n 2 ) O(Tn^2) O(Tn2)

    #include 
#include 
using namespace std;
const int N=2e2+7,INF=1e9;
int n,m,k,ca,cb,ans;
int x[N],y[N],b[N],g[N],nxt[N],sz[N],f[N][N][10],t[N][10];
struct st {int l,r,w;} a[N];
inline void up(int&a,int b){if(a=m;i--) for(int b=0;b<=k;b++) 
            t[a][b]=f[x][a][b];
        for(int a=min(sz[x],m);~a;a--) for(int c=min(sz[i],m-a);~c;c--) {
            int t1=-INF,t2=-INF;
            for(int b=0;b<=k;b++) {
                up(t1,f[i][c][b]);       
                up(t2,f[x][a][b]);
                up(t[a+c][b],max(f[x][a][b]+t1,f[i][c][b]+t2));
            }
        }
        sz[x]+=sz[i];
        for(int a=min(sz[x],m);a>=m;a--) for(int b=0;b<=k;b++) 
            f[x][a][b]=t[a][b];
    }
    if(!x)return;
    sz[x]++;
    for(int a=min(sz[x],m-1);~a;a--) for(int b=k-1;~b;b--) 
        up(f[x][a+1][b+1],f[x][a][b]+::a[x].w);
}
int main(){
    int T;while(~scanf("%d%d%d",&n,&m,&k)){
        k--;
        for(int i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]);
        for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) if(y[i]==y[j]){
            bool flag=1;
            for(int k=i+1;k=y[i]) {flag=0; break;}
            if(flag){
                if(i+1==j) b[++cb]=x[j]-x[i];
                else a[++ca]=(st){i+1,j-1,x[j]-x[i]};
            }
        }
        sort(b+1,b+cb+1,greater());
        for(int i=2;i<=cb;i++) b[i]+=b[i-1];
        for(int i=1,j=0;i<=ca;i++){
            for(int k=1;k<=ca;k++)
                if(a[k].la[i].r && (!j||a[k].w
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62

    T6 Mousetrap

    题目传送门

    选好根，就是老鼠所在的位置 t t t 。
    观察好性质，老鼠一进入某个子树就一定会无路可走。
    考虑完情况，老鼠往根的情况二分答案
    详细的题解 贴个链接别人的Blog

    再贴个自己的代码：

    #include 
#include 
#include 
using namespace std;
const int N=1e6+7,INF=1e9;
int n,t,m,l,r,ans;
int sum[N],f[N],fa[N];
vector G[N];
void dfs(int u,int ff) {
    int MAX=0,_MAX=0,cnt=G[u].size()-1; fa[u]=ff;
    if(u!=t) sum[u]=sum[ff]+cnt-1+(u==m);
    for(int v:G[u]) if(v!=ff) {
        dfs(v,u); 
        if(f[v]>=MAX) _MAX=MAX,MAX=f[v];
        else if(f[v]>_MAX) _MAX=f[v];
    }
    f[u]=_MAX+cnt;
}
bool check(int k) {
    int cnt=1;
    for(int u=m,tu=u;u!=t;u=fa[u],cnt++) {
        int x=0;
        for(int v:G[u]) if(v!=fa[u] && v!=tu && f[v]+sum[u]>k) {
            if(!cnt) return 0;
            x++,cnt--;
        }
        k-=x,tu=u;
    }
    return k>=0;
}
int main(){
    scanf("%d%d%d",&n,&t,&m); r=n<<1;
    for(int i=1,u,v;i>1;
        if(check(mid)) ans=mid,r=mid-1;
        else l=mid+1;
    }
    printf("%d\n",ans);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47

    结

    其实还有三道题，但我太懒了，就不写了贴一题目链接
    [PA2015] Rozstaw szyn
    [POI2017] Sabotaż
    [CEOI2017] Chase

  • 相关阅读:
    宝塔+LNMP平台=HTTP文件共享服务
    POSTGRESQL中的SQL高级应用案例——等你来挑战
    el-dialog弹窗拖动
    Linux查看日志文件的常用命令
    为什么公共关系应该在您的社交媒体营销中发挥作用
    JAVA基础算法（11）----- 最大二叉树
    文件不小心删除了怎么恢复？实用的两个小妙招
    Python使用.NET开发的类库来提高你的程序执行效率
    Python类的定义和使用：什么是类？实在不知道啥叫累！
    基于51单片机的温室大棚土壤湿度检测智能语音灌溉通风系统proteus仿真原理图PCB
  • 原文地址：https://blog.csdn.net/PocketSam/article/details/133044766