9.25模拟赛
t1
一些向日葵站在上排在一列花盆上，她们通过传话的方式互相交流。 话说多了，自然就产生了代沟。一旦有了代沟，两个向日葵就不说话了，话就传不过去。 有 m 个向日葵，m 个事件。每一个事件都是这样的： 给定一个 k，排在第 k 的向日葵和排在第 k+1 的向日葵产生了代沟，事件按发生顺序给出。 每一次事件发生后，愚蠢的戴夫想知道有多少个无序数对(a,b)，使得排在 a 和排在 b 的向 日葵事件发生前可以交流，事件发生后无法交流。
线段树维护区间最大值和最小值 即前面后面最近的一次被分割的位置然后算完后在把这次切的位置修改
#include<bits/stdc++.h>
using namespace std;
const int N=1e6;
int Min[N],Max[N];
int a[N];
int n,m,k;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void build(int rt,int l,int r)
{
if(l==r)
{
Min[rt]=N+2;return;
}
int mid=(l+r)>>1;
build(rt<<1,l,mid);
build(rt<<1|1,mid+1,r);
}
void pushup(int rt)
{
Min[rt]=min(Min[rt<<1],Min[rt<<1|1]);
Max[rt]=max(Max[rt<<1],Max[rt<<1|1]);
}
void modify(int rt,int l,int r,int x)
{
if(l==r&&l==x)
{
Max[rt]=x;
Min[rt]=x;return;
}
int mid=(l+r)>>1;
if(mid>=x)modify(rt<<1,l,mid,x);
else modify(rt<<1|1,mid+1,r,x);
pushup(rt);
}
int query(int rt,int l,int r,int L,int R)
{
if(L<=l&&r<=R)return Min[rt];
int mid=l+r>>1;
int res=N+2;
if(L<=mid)res=min(res,query(rt<<1,l,mid,L,R));
if(R>mid)res=min(res,query(rt<<1|1,mid+1,r,L,R));
return res;
}
int query2(int rt,int l,int r,int L,int R)
{
if(L<=l&&r<=R)return Max[rt];
int mid=l+r>>1;
int res=0;
if(L<=mid)res=max(res,query2(rt<<1,l,mid,L,R));
if(R>mid)res=max(res,query2(rt<<1|1,mid+1,r,L,R));
return res;
}
int main()
{
// freopen("t1.in","r",stdin);
//freopen("t1.out","w",stdout);
n=read(),m=read();
memset(Min,0x3f3f3f3f,sizeof(Min));
build(1,1,n);
for(int i=1;i<=m;++i)
{
k=read();
int l=query2(1,1,n,1,k);
int r=query(1,1,n,k+1,n);
// cout<<l<<' '<<r<<endl;
if(l==0)l=0;
if(r>=N+2)r=n;
printf("%lld\n",1ll*(k-l)*1ll*(r-k));
modify(1,1,n,k);
}
return 0;
}t2 给定 n 个节点的树，以及 m 个僵尸（m≥2）。 给定 k，表示僵尸各自最多能走 k 条边（k≤n−1）。 询问所有满足条件的僵尸路径方案数： 结束点编号不小于起始点编号。 不存在所有僵尸的路径交于一点。 僵尸各自的路径包含的边数不超过 k。 答案对 998244353 取模。
好像题有点假 暂时不会
t3
现在有 n 个豌豆射手，要把它们放在长度为 d 的一列草坪上。 每一个豌豆射手都有一个攻击半径 ri，如果将这个豌豆射手放在 pos 位置，那么[pos− ri+1,pos+ri−1]将不能有其他的豌豆射手 戴夫要把这 n 个豌豆射手放在长度为 d 的草坪上，使得它们不会相互攻击，求方案数。答案 对109 + 7取模
神仙计数题
可以发现 当相对位置定下后剩下的就是往里面插空 这个是可以组合数求得
接下来就是求每种状态的方案数
f[i][j][k] 表示前i个中有j个是空闲点 总长度为k的方案数（定义空闲点是这个豌豆射手和左右的豌豆射手之间还没有完全相连还可以放） 这里的长度的定义为需要强制在这几个豌豆射手之间放 因为如果一些点不紧密相连只是空闲点的话周围可以不放格子 而两个之间相连的话之间一定要放够半径的格子
初始化f[0][0][0]=1;
转移 f[i+1][j][k+r[i+1]]=f[i][j][k]j2 每新加入一个点这个点可以和任意一个空闲点合并即紧密相连长度要加上r 乘二是因为可以放在左右两边
f[i+1][j-1][k+2r-1]=f[i][j][k]j(j-1)*2/2 这个新点还可以连接两个空闲点
方程的定义并没有规定顺序只要满足总长度等于即可 而新加一点不管和谁连多加的长度都是固定的 所以这里要乘一个组合数即任选两个连又因为虽然选了两个但这两个的前后关系是不确定的组合数的除2和前后不一样的方案数乘2抵消
f[i+1][j+1][k+1]=f[i][j][k] 即不和之前的空闲点相连 多加一个空闲点 长度也就是强制要用的格子数也要加一
ans=∑C(d-i+n,n)*f[n][1][i] 相当于我们把所以强制要用的格子数浓缩一下有放了豌豆射手的点代替 那些空着的点就是随便放 相当于在剩下的格子和这放了n个豌豆射手的浓缩的点 之间任选n个点放这浓缩的点 （可以放在原位 也可以放在空的点 因为我们保证这些浓缩的点一定已经满足条件了再放在那些空的点也不会冲突 这里感性理解一下）
#include <iostream>
#include <cstdio>
#include <algorithm>
#define ll long long
using namespace std;
const int N=40,M=1600,D=1e5;
const ll mod=1e9+7;
int r[N+10];
ll fac[D+10],inv[D+10],f[N+10][N+10][M+10];
inline ll power(ll a,int b)
{
ll res=1;
for(;b;b>>=1,a=a*a%mod)
if(b&1) res=res*a%mod;
return res;
}
inline ll C(int n,int m)
{
return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
int main()
{
fac[0]=1;
for(int i=1;i<=D;i++)
fac[i]=fac[i-1]*i%mod;
inv[D]=power(fac[D],mod-2);
for(int i=D-1;i>=0;i--)
inv[i]=inv[i+1]*(i+1)%mod;
int n,d; ll ans=0;
scanf("%d%d",&n,&d);
for(int i=1;i<=n;i++)
scanf("%d",&r[i]);
sort(r+1,r+n+1);
f[0][0][0]=1;
for(int i=0;i<=n;i++)
{
for(int j=0;j<=i;j++)
{
for(int k=0;k<=M;k++)
{
int add=r[i+1];
if(j>=1) (f[i+1][j][k+add]+=f[i][j][k]*2*j)%=mod;
if(j>=2) (f[i+1][j-1][k+add*2-1]+=f[i][j][k]*j*(j-1))%=mod;
(f[i+1][j+1][k+1]+=f[i][j][k])%=mod;
}
}
}
for(int i=0;i<=min(d,M);i++)
ans=(ans+C(d-i+n,n)*f[n][1][i]%mod)%mod;
printf("%lld\n",ans);
return 0;
}