CXJY-Day 7
FLAG: 想不明白T3
填树(tree)
【题目描述】
给定一棵$n(n≤500)$个点的有根树（1号点是根），你需要在每一个点上填一个在$[1,m]$之间的正整数，满足每个点上填的数都是它父亲上填的数的倍数（可以是1倍）。由于1号点没有父亲，所以填任何数都满足条件。
输出符合条件的方案数，模$10^9+7$。
【输入格式】
第一行两个正整数n,m，表示树的点数以及填数的最大值。
接下来m行，每行两个正整数表示一条边。
【输出格式】
输出一行答案，模$10^9+7$。
【输入样例】
3 2
1 2
1 3【输出样例】
5【数据范围与约定】
对于30%的数据，$n≤5,m≤5$
对于60%的数据，$n≤100,m≤500$
对于100%的数据，$n≤1000,m≤10000$
题解
暴力转移即可
$f[i][j]$表示以i为根的子树，i处填j的方案数
每次枚举父亲的因数，从儿子转移即可$O(nmlog_m)$，注意常数优化
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct path{
int Next,y;
}Pth[2005];
int cnt,head[1005];
void add(int x,int y){
cnt++;
Pth[cnt].y=y;
Pth[cnt].Next=head[x];
head[x]=cnt;
}
int n,m;
ll dp[1005][10005],mod=1e9+7;
void dfs(int x,int prv){
bool fl=0;
for (int i=1;i<=m;++i) dp[x][i]=1;
for (int i=head[x];i;i=Pth[i].Next){
int y=Pth[i].y;
if (prv==y) continue;
fl=1;
dfs(y,x);
for (int j=1;j<=m;++j){
ll sum=0;
for (int k=j;k<=m;k+=j){
sum+=dp[y][k];
if (sum>=mod) sum-=mod;
}
dp[x][j]*=sum;
dp[x][j]%=mod;
}
}
}
int main(){
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
cin>>n>>m;
for (int i=1;i<n;++i){
int x,y;
scanf("%d%d",&x,&y);
add(x,y); add(y,x);
}
dfs(1,0);
ll ans=0;
for (int i=1;i<=m;++i){
ans+=dp[1][i];
ans%=mod;
}
cout<<ans<<endl;
return 0;
}发放纪念衫(tshirts)
【题目描述】
小R打算举办一场网络赛，为了吸引大家前来参加，小R要给网络赛排名前k的选手发放比赛的纪念衫（我们假设比赛中没有同分的选手）。小R事先统计了所有选手的衣服尺寸，有些选手需要特定尺寸的衣服，而有些选手则可以同时接受两个相邻尺寸的衣服。例如有$S,M,L,XL$这四个尺寸的衣服，如果一个选手只能接受M尺寸，则如果他进入了前k名，则小R需要给他发放一件M尺寸的衣服；如果一个选手同时能接受M和L尺寸，则如果他进入了前k名，则小R即可以给他发放一件M尺寸的衣服，也可以给他发放一件L尺寸的衣服。不会有任何一个选手同时能接受S和L尺寸，因为这两个尺寸不相邻。
由于现在比赛还没有开始，小R并不知道谁会进入前k名，因此小R需要准备足够的纪念衫，使得无论哪k位选手进入了前k名，每位前k名的选手都能获得一件尺寸合适的纪念衫。
现在小R想知道他至少要准备多少纪念衫。
【输入格式】
第一行两个正整数$n,k$。其中n表示纪念衫有n种尺寸，$k$表示发放纪念衫的数量。
第二行$n$个正整数，第i个正整数表示只能接受尺寸$i$的选手数$a_i$。
第三行$n-1$个正整数，第i个正整数表示同时能接受尺寸$i$和尺寸$i+1$的选手数$b_i$。
【输出格式】
输出一行答案。
【输入样例1】
5 10
1 4 3 2 3
2 3 4 2【输出样例1】
19【数据范围与约定】
对于20%的数据，$n≤5,k≤10$
对于40%的数据，$n≤50,k≤200$
对于70%的数据，$n≤3000,k≤10^9$
对于100%的数据，$n≤10^5,k≤10^9,a_i,b_i≤10^8$。
题解
贪心
先要分配给a
首先要满足$\sum_{i=l}^{r}t_i \ge \min(\sum_{i=l}^{r}a_i+\sum_{i=l+1}^{r}b_i,k)$
因此可以发现$t_1=\min(a_1,k)$
$t_2\ge \min(a_2,k),t_2\ge \min(a_1+a_2+b_1,k)-t_1$
同理$t_3$有3个条件，可以得到一个$n^2$的做法
考虑单调队列优化，$t_i\ge pa_i+pb_{i-1}-pa_{j-1}-pb_{j-1}-pt_{i-1}+pt_{j-1}$p为前缀和
只考虑$-pa_{j-1}-pb_{j-1}+pt_{j-1}$在j上取的最大值
同时要考虑和大于k时，直接弹出即可（其实还是要记一下的）
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
ll k,a[100005],b[100005],t[100005],pa[100005],pb[100005],pt[100005];
int main(){
freopen("tshirts.in","r",stdin);
freopen("tshirts.out","w",stdout);
cin>>n>>k;
for (int i=1;i<=n;++i){
scanf("%lld",&a[i]);
pa[i]=a[i]+pa[i-1];
}
for (int i=1;i<n;++i){
scanf("%lld",&b[i]);
pb[i]=b[i]+pb[i-1];
}
t[1]=pt[1]=min(k,a[1]);
deque <pair<ll,int> > q;
q.push_back(make_pair(0,1));
int l=1;
for (int i=2;i<=n;++i){
while (pa[i]+pb[i-1]-pa[l-1]-pb[l-1]>=k) l++;
if (l!=1) t[i]=k-(pt[i-1]-pt[l-2]);
while (!q.empty() && q.front().second<l) q.pop_front();
ll v=-pa[i-1]-pb[i-1]+pt[i-1];
while (!q.empty() && q.back().first<=v) q.pop_back();
q.push_back(make_pair(v,i));
if (!q.empty()){
t[i]=max(t[i],q.front().first+pa[i]+pb[i-1]-pt[i-1]);
}
t[i]=max(t[i],min(a[i],k));
pt[i]=pt[i-1]+t[i];
}
ll ans=0;
for (int i=1;i<=n;++i) ans+=t[i];
cout<<ans<<endl;
return 0;
}错误算法(wrong)
【题目描述】
给定一个1到n的排列$p={p_1,p_2,…,p_n}$。求排列p中有多少个逆序对。
小R想出了一个算法来解决这个问题，对于每一个$i(1≤i≤n)$，如果$i>p_i$，则将$i-p_i$累加进答案。即答案等于$\sum_imax(i-p_i,0)$。很快小R就发现这个算法是错误的，例如对于$4,3,1,2$，小R计算出来的答案是$0+0+2+2=4$，而实际的逆序对数量应该是5个。
但是小R已经把程序写完并交上去了。现在他知道了测试数据中n的值，以及排列p中的前$m(0≤p≤n)$个数${p_1,p_2,…,p_m}$，他想知道在这些条件有多少种排列能使得他的算法输出的结果是正确的。
你只需要计算答案$mod 10^9+7$的值即可。
【输入格式】
第一行一个正整数$T(T≤10)$，表示数据组数。
接下来T行，每行表示一组数据。每行的前两个非负整数n,m含义如题面中所述，接下来m个数表示排列的前m个数$p_1,p_2,…p_m$。
【输出格式】
对于每组数据，输出一行，表示答案$mod10^9+7$的值。
【输入样例】
5
3 0
7 0
6 1 3
10 4 3 9 6 5
5 2 2 1【输出样例】
5
429
28
0
5【样例解释】
对于第一组数据，共有以下5个排列使得小R算法的结果正确：
$1,2,3$
$1,3,2$
$2,3,1$
$2,1,3$
$3,1,2$
【数据范围与约定】
对于20%的数据，$n≤10$
对于40%的数据，$n≤20$
对于60%的数据，$n≤50$
对于另外20%的数据，$m=0$
对于100%的数据，$n≤200,T≤10$
题解
可以发现，两者答案相等的条件是数列中不存在长度大于2的连续下降子段（显然。。。）
先检查读入的数是否满足条件
设$f[i][j]$为前i个数，最大值为j的合法方案数
$f[i+1][k]+=f[i][j](k>j),f[i+1][j]+=f[i][j](j!=i)$
最后输出$f[n][n]$即可
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,p[205];
ll dp[205][205],mod=1e9+7;
void solve(){
cin>>n>>m;
int mt=0;
memset(dp,0,sizeof dp);
for (int i=1;i<=m;++i){
scanf("%d",&p[i]);
mt=max(mt,p[i]);
}
for (int i=3;i<=m;++i){
if (p[i-2]>p[i-1]&&p[i-1]>p[i]){
cout<<0<<endl;
return;
}
}
dp[m][mt]=1;
for (int i=m;i<=n;++i){
for (int j=mt;j<=n;++j){
if (i!=j) dp[i+1][j]=(dp[i+1][j]+dp[i][j])%mod;
for (int k=j+1;k<=n;++k){
dp[i+1][k]=(dp[i+1][k]+dp[i][j])%mod;
}
}
}
cout<<dp[n][n]<<endl;
}
int main(){
freopen("wrong.in","r",stdin);
freopen("wrong.out","w",stdout);
int t;
cin>>t;
while (t--) solve();
return 0;
}树
-
树上分治
处理经过树的重心有关询问
删去重心
递归子树求解
例题
链计数POJ1741(给定一个N个节点的带权树，定义dist(u,v)为u，v两点之间的最短路径长度，路径长度定义为路径上所有边的权和。对于两个不同的点a，b，如果满足dist(a,b)<=k,称为合法点对，求合法点对的个数)
link考虑经过点g的贡献，求出所有点与g的距离，用两个指针计算即可 链的条件最值
给定一颗无根树，每个点上带两个权值，分别是w和h。要求一条w值和最大的链，其h值不超过给定的hmax
找到每个点与g之间的w和与h和，权值线段树 给出一棵树，给定3个点之间的距离x,y,z,求出三个点可行的方案数
把x，y，z转化为距离同一个点距离为a,b,c的三个点$x=a+b,y=b+c,z=c+a$ CC TUPLES2 link
给定一棵树，你需要选3条路径，使得满足以下两个条件中的一个：
1. 3条路径互不相交（点相交） 2. 3条路径两两相交 3. 方案数模$1e9+7$ 4. $N<=300000$ 直接把两部分的答案分别求出来想加，对于三条路径没交的情况，设状态$f[i][j][k][s]$表示做到$i$节点的子树，选了$j$条路径，$k$条伸出$i$，$i$是否已经被一条路覆盖，我们只需要讨论一下两条路径是否会在节点i相交变成一条，然后就是经典的树形dp了。对于三条路径必须有交的情况。我们可以枚举深度最小的三条路径的交点x，然后枚举一下有多少条路径在x的子树内，多少条有部分在子树外，分别统计一下个数乘起来。
本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/cxjy-day-7/
