第一个测试点启发选手想出，要分矩形内部和矩形相接处的来计算
内部的显然是（长-1）×（宽-1）×2
相接处：先按照（x,xx）进行二元组排序，可以大大减少情况数，见代码
和模拟9的T1的DP差不多
定义$f[i][j]$表示第i天后，最大难度值为j的方案数
转移：1：到i-1天时最大值已经是j，则第i天可以为1～j，$f[i-1][j]*j$
2：到i-1时最大值不是j，第i天j是最大，$\sum \limits_ {k=1}^{j-1}f[i-1][k]$
$f[i][j]=f[i-1][j]*j+\sum \limits_{k=1}^{j-1} f[i-1][k]$ 时间复杂度$O(n^3)$
最终答案：
对于每k天的劳累值：
每天有m种情况，k天就是$m^k$中情况
所以 $\frac{\sum\limits_{j=1}^{m}f[k][j]*w[j]}{m^k}$
在总的$n-k+1$天中每天是相同的
最终答案：ans=$(n-k+1)*\frac{\sum\limits_{j=1}^{m}f[k][j]*w[j]}{m^k}$
当然可以稍做简化，不用dp，
在k天中，i^k 是 最大难度值可能是i，但不可能是更大的情况数，（i-1）^k同理，那么相减就是最大值为i的方案数
方案数就是 $\frac{\sum\limits_{j=1}^{m} j^k-(j-1)^k*w[j]}{m^k}$
考虑到k=1e5的情况，此时不用管小桶，就是求往里放了多少，跟「雨天的尾巴」一样
先将颜色离散化
对每个节点，开一个动态开点的，维护放入的颜色个数（也是种类）的线段树，
读入时将将颜色种类插入，dfs再进行合并子树
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<set> 6 #include<algorithm> 7 #define mid ((l+r)>>1) 8 using namespace std; 9 int read() 10 { 11 int f=1,x=0;char ch=getchar(); 12 while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();} 13 while(ch<='9'&&ch>='0'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} 14 return f*x; 15 } 16 const int maxn=1e5+5; 17 int cn; 18 int k[maxn],fa[maxn],c[maxn],cc[maxn],pos[maxn],ans[maxn]; 19 int tot,rt[40*maxn],lc[40*maxn],rc[40*maxn],sum[40*maxn]; 20 set<int>c1[maxn]; 21 struct node{ 22 int v,nxt; 23 }e[2*maxn];int nu,h[maxn]; 24 void add(int x,int y) 25 { 26 e[++nu].v=y; 27 e[nu].nxt=h[x]; 28 h[x]=nu; 29 } 30 void predfs(int x,int f) 31 { 32 fa[x]=f; 33 for(int i=h[x];i;i=e[i].nxt) 34 { 35 int y=e[i].v; 36 if(y==f)continue; 37 predfs(y,x); 38 } 39 } 40 void insert(int &root,int l,int r,int w) 41 { 42 if(!root) root=++tot; 43 if(l==r){sum[root]=1;return;} 44 if(w<=mid) insert(lc[root],l,mid,w); 45 else insert(rc[root],mid+1,r,w); 46 sum[root]=sum[lc[root]]+sum[rc[root]]; 47 } 48 int merge(int x,int y,int l,int r) 49 { 50 if(!x||!y)return x+y; 51 if(l==r)return x; 52 lc[x]=merge(lc[x],lc[y],l,mid); 53 rc[x]=merge(rc[x],rc[y],mid+1,r); 54 sum[x]=sum[lc[x]]+sum[rc[x]]; 55 return x; 56 } 57 void dfs(int x,int f) 58 { 59 for(int i=h[x];i;i=e[i].nxt) 60 { 61 int y=e[i].v; 62 if(y==f)continue; 63 dfs(y,x); 64 rt[x]=merge(rt[x],rt[y],1,cn); 65 } 66 ans[x]=sum[rt[x]]; 67 } 68 int main() 69 { 70 //freopen("data","r",stdin); 71 const int n=read(); 72 for(int i=1;i<n;i++) 73 { 74 int x=read(),y=read(); 75 add(x,y);add(y,x); 76 } 77 predfs(1,0); 78 for(int i=1;i<=n;i++) k[i]=read(); 79 const int m=read(); 80 if(n<=1000&&m<=1000) 81 { 82 for(int i=1;i<=m;i++) 83 { 84 int x=read(),col=read(); 85 while(x) 86 { 87 if(k[x]) 88 { 89 k[x]--; 90 if(c1[x].find(col)==c1[x].end()) 91 { 92 c1[x].insert(col); 93 ans[x]++; 94 } 95 } 96 x=fa[x]; 97 } 98 } 99 } 100 else 101 { 102 for(int i=1;i<=m;i++) pos[i]=read(),c[i]=read(),cc[i]=c[i]; 103 sort(cc+1,cc+m+1); 104 cn=unique(cc+1,cc+m+1)-cc-1; 105 for(int i=1;i<=m;i++) 106 { 107 c[i]=lower_bound(cc+1,cc+cn+1,c[i])-cc; 108 insert(rt[pos[i]],1,cn,c[i]); 109 } 110 dfs(1,0); 111 } 112 int Q=read(); 113 while(Q--) 114 { 115 int x=read(); 116 printf("%d\n",ans[x]); 117 } 118 } 119 /* 120 g++ 2.cpp -o 2 121 ./2 122 123 */ View Code
注意： 普通的线段树，只开一个，重复使用
对于每个操作：x,col, vector<int> ty[x]存x节点的放入颜色种类，ti[x]存放入时间
predfs出1，每个点即将放入的小球个数size（不考虑k的限制）2，重儿子（size最大）的标号
统计答案（dfs）：思想：
先处理子节点（先轻儿子，后重儿子），（递归回来后要不断对线段树清空）
然后依次在线段树中插入（inser）重儿子，自己，和轻儿子的信息，
然后就可以查询（query）了
之后将x，和轻儿子的信息合并（merge）到重儿子身上，以供父节点使用
（将轻的向重的上合并，这就是启发式合并的思想）
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<set> 6 #include<algorithm> 7 #include<vector> 8 #define mid ((l+r)>>1) 9 #define lc (x<<1) 10 #define rc (x<<1|1) 11 using namespace std; 12 int read() 13 { 14 int f=1,x=0;char ch=getchar(); 15 while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();} 16 while(ch<='9'&&ch>='0'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} 17 return f*x; 18 } 19 const int maxn=5e5+5; 20 int cn,m; 21 int k[maxn],cc[maxn],ans[maxn],son[maxn]; 22 int size[10*maxn],an[10*maxn],siz[10*maxn],lazy[10*maxn],t[10*maxn]; 23 vector<int>ty[10*maxn]; 24 vector<int>ti[10*maxn]; 25 struct node{ 26 int v,nxt; 27 }e[2*maxn];int nu,h[maxn]; 28 inline void add(int x,int y) 29 { 30 e[++nu].v=y; 31 e[nu].nxt=h[x]; 32 h[x]=nu; 33 } 34 void predfs(int x,int f)//预处理出子树的大小和重儿子 35 { 36 size[x]=ty[x].size(); 37 for(int i=h[x];i;i=e[i].nxt) 38 { 39 int y=e[i].v; 40 if(y==f)continue; 41 predfs(y,x); 42 size[x]+=size[y]; 43 if(size[y]>size[son[x]]) 44 son[x]=y; 45 } 46 } 47 inline void pushdown(int x) 48 {//将x的儿子节点清空，避免了每次的全部清空 49 lazy[lc]=lazy[rc]=1; 50 lazy[x]=an[lc]=an[rc]=siz[lc]=siz[rc]=0; 51 } 52 inline void pushup(int x) 53 { 54 an[x]=an[lc]+an[rc]; 55 siz[x]=siz[lc]+siz[rc]; 56 } 57 inline void updata(int x,int l,int r,int val,int derta,int sum) 58 { 59 an[x]+=derta,siz[x]+=sum; 60 if(l==r)return; 61 if(lazy[x]) pushdown(x); 62 if(val<=mid)updata(lc,l,mid,val,derta,sum); 63 else updata(rc,mid+1,r,val,derta,sum); 64 pushup(x); 65 } 66 inline int query(int x,int l,int r,int sum) 67 { 68 if(sum<=0)return 0 ; 69 if(l==r) return an[x]; 70 if(lazy[x]) pushdown(x); 71 if(siz[lc]<=sum) 72 return an[lc]+query(rc,mid+1,r,sum-siz[lc]); 73 else 74 return query(lc,l,mid,sum); 75 } 76 inline void merge(int x,int y) 77 { 78 for(int i=0;i<ty[y].size();i++) 79 ty[x].push_back(ty[y][i]),ti[x].push_back(ti[y][i]); 80 ty[y].clear(),ti[y].clear(); 81 } 82 inline void clea(int x)//清空维护时间的线段树，用lazy标记，不全清 83 {//an答案数组 siz线段树子树大小 84 an[1]=siz[1]=0,lazy[1]=1;//标记是否需要用的时候清空 85 for(int i=0;i<ty[x].size();i++) 86 t[ty[x][i]]=0;//t维护color的出现时间 87 } 88 inline void inser(int x) 89 { 90 for(int i=0;i<ty[x].size();i++) 91 { 92 int col=ty[x][i],tim=ti[x][i]; 93 if(!t[col])updata(1,1,m,tim,1,0),t[col]=tim; 94 else if(t[col]>tim) 95 { 96 updata(1,1,m,t[col],-1,0);//把时间靠后的小球对an做的贡献减掉 97 updata(1,1,m,tim,1,0);//把时间靠前到小球对an的贡献加上，但是都不改变个数 98 t[col]=tim; 99 } 100 updata(1,1,m,tim,0,1);//最后加上这一个的个数 101 } 102 } 103 void dfs(int x,int f) 104 { 105 for(int i=h[x];i;i=e[i].nxt) 106 { 107 int y=e[i].v; 108 if(son[x]==y||y==f)continue; 109 dfs(y,x); 110 clea(y);//清空线段树的信息 111 } 112 if(son[x]) dfs(son[x],x);//遍历完所有儿子，最后遍历重儿子，且线段树中存有重儿子信息 113 inser(x);//把x的信息放入线段树 114 for(int i=h[x];i;i=e[i].nxt) 115 { 116 int y=e[i].v; 117 if(y==f||y==son[x])continue; 118 inser(y);//把y节点的信息放入线段树 119 } 120 ans[x]=query(1,1,m,k[x]); 121 if(son[x]) 122 { 123 merge(son[x],x);//将x和重儿子节点信息合并 124 swap(ty[son[x]],ty[x]),swap(ti[son[x]],ti[x]); 125 for(int i=h[x];i;i=e[i].nxt) 126 { 127 int y=e[i].v; 128 if(y==f)continue; 129 merge(x,y);//合并轻儿子 130 } 131 } 132 } 133 int main() 134 { 135 // freopen("data","r",stdin); 136 const int n=read(); 137 for(int i=1;i<n;i++) 138 { 139 int x=read(),y=read(); 140 add(x,y),add(y,x); 141 } 142 for(int i=1;i<=n;i++) k[i]=read(); 143 m=read(); 144 for(int i=1;i<=m;i++) 145 { 146 int x=read(),col=read(); 147 if(cc[col]==0) cc[col]=++cn; 148 col=cc[col];//将颜色离散化 149 ty[x].push_back(col),ti[x].push_back(i); 150 //ty存颜色种类，ti存该颜色放入的时间 151 } 152 predfs(1,0); 153 dfs(1,0); 154 int Q=read(); 155 while(Q--) 156 { 157 int x=read(); 158 printf("%d\n",ans[x]); 159 } 160 } View Code转载于:https://www.cnblogs.com/casun547/p/11272484.html
相关资源：模拟电子线路答案（课后题解）