牛客练习赛26
A.平面
这是道好题，考验的是我们的数学能力。
我们可以把X分成两条直线，这不就转化为了n条互不相交直线最多能把平面分成多少部分。
我们知道一个公式:n*(n+1)/2
时间复杂度O(1)
#include<bits/stdc++.h>
using namespace std;
long long n;
int main()
{
scanf("%lld",&n);
n*=2;
cout<<n*(n+1)/2+1;
return 0;
}B.烟花
好题，中等难度。
我一看题目就知道这是道期望dp题。
对于第1个问题，f[i]表示前i个烟花产生颜色的期望。
for(int i=1;i<=n;i++)
f[i]=(f[i-1]+1.0)*p[i]+f[i-1]*(1.0-p[i]);对于第2个问题,表示前i个烟花产生j种颜色的概率。(注意要滚存)
g[0]=(1-p[1]);g[1]=p[1];
for(int i=2;i<=n;i++)
{
for(int j=min(i,k);j;j--)
g[j]=g[j-1]*p[i]+g[j]*(1.0-p[i]);
g[0]*=(1-p[i]);
}时间复杂度：O(n*k)
全部代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,k;
double p[N],f[N],g[N];
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)scanf("%lf",&p[i]);
for(int i=1;i<=n;i++)
f[i]=(f[i-1]+1.0)*p[i]+f[i-1]*(1.0-p[i]);
printf("%.4lf\n",f[n]);
g[0]=(1-p[1]);g[1]=p[1];
for(int i=2;i<=n;i++)
{
for(int j=min(i,k);j;j--)
g[j]=g[j-1]*p[i]+g[j]*(1.0-p[i]);
g[0]*=(1-p[i]);
}
printf("%.4lf",g[k]);
return 0;
}C.城市规划
这题卡了我好久，我还以为可以用监视任务这题的方法，用线段树+贪心做。
但调了好久发现会T（m竟然=1e7）
这题由于只要区间>=1所以，我们就可以用一种简单的方法。
我们发现对于每个右端点，只有最大的左端点有用（想一想为什么）
时间复杂度：O(n)
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,m,a[N];
char buf[1<<21],*p1=buf,*p2=buf;
inline int gc()
{
return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
int ret=0,f=0;
char c=gc();
while(!isdigit(c))
{
if(c=='-')f=1;
c=gc();
}
while(isdigit(c))
{
ret=ret*10+c-48;
c=gc();
}
if(f)return -ret;
return ret;
}
int main()
{
n=read();m=read();
for(int i=1;i<=m;i++)
{
int x=0;x=read();
int y=0;y=read();y--;
a[y]=max(a[y],x);
}
int pre=0,ans=0;
for(int i=1;i<=n;i++)
if(a[i]&&pre<a[i])
{
ans++;
pre=i;
}
printf("%d",ans);
return 0;
}D. xor序列
这题不是线性基裸题吗。
xor有个性质:a xor b =c 那么 a xor c = b
直接查找 a xor b 是否有，有就YES，否则NO
时间复杂度O(50*n)
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,x,y,m,p[55];
void add(int x)
{
for(int i=50;i>=0;i--)
{
if((x>>i)==0)continue;
if(!p[i])
{
p[i]=x;
break;
}
x^=p[i];
}
}
bool pd(int x)
{
for(int i=50;i>=0;i--)
{
if((x>>i)==0)continue;
if(!p[i])return false;
x^=p[i];
}
return true;
}
signed main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++)
{
scanf("%lld",&x);
add(x);
}
scanf("%lld",&m);
while(m--)
{
scanf("%lld%lld",&x,&y);
if(pd(x^y))puts("YES");
else puts("NO");
}
return 0;
}E. 树上路径
这题真的难，不仅思维上难，代码实现上很难（这是我们学校的一场模拟赛的一道题，我现场A了）。
这题一看就是要用树链剖分，关键是如何维护(u, v)路径上节点的权值两两相乘的和 。
我们记一个sum数组表示和，在记一个mul数组记录两两相乘的和。
我们发现如果l-r这段区间集体+val，那么
tree[nod].mul=(tree[nod].mul+(r-l)*tree[nod].sum%p*val%p+(val*val)%p*jc[r-l]%p)%p;
tree[nod].sum=(tree[nod].sum+(r-l+1)*val%p)%p;
lazy[nod]=(lazy[nod]+val)%p;jc[i]=sigema(1-i)
所以这题就这么愉快的解决了
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mid (l+r)/2
const int p=1000000007;
const int N=1000005;
int n,m,opt,x,y,z,tot,val[N],jc[N],fa[N],size[N],dep[N],son[N],top[N],seg[N],rev[N],head[N],lazy[N*4];
struct node{
int sum,mul;
}tree[N*4];
struct node2{
int too,next;
}edge[N*2];
void add(int a,int b)
{
edge[++tot].too=b;edge[tot].next=head[a];head[a]=tot;
}
void dfs1(int u,int f)
{
fa[u]=f;size[u]=1;dep[u]=dep[f]+1;
for(int i=head[u];i;i=edge[i].next)
{
int v=edge[i].too;
if(v==f)continue;
dfs1(v,u);
size[u]+=size[v];
if(size[v]>size[son[u]])son[u]=v;
}
}
void dfs2(int u,int f)
{
if(son[u])
{
seg[son[u]]=++seg[0];
rev[seg[0]]=son[u];
top[son[u]]=top[u];
dfs2(son[u],u);
}
for(int i=head[u];i;i=edge[i].next)
{
int v=edge[i].too;
if(!top[v])
{
seg[v]=++seg[0];
rev[seg[0]]=v;
top[v]=v;
dfs2(v,u);
}
}
}
void pushup(int nod)
{
tree[nod].sum=(tree[nod*2].sum+tree[nod*2+1].sum)%p;
tree[nod].mul=(tree[nod*2].mul+tree[nod*2+1].mul+tree[nod*2].sum*tree[nod*2+1].sum%p)%p;
}
void bian(int nod,int l,int r,int val)
{
tree[nod].mul=(tree[nod].mul+(r-l)*tree[nod].sum%p*val%p+(val*val)%p*jc[r-l]%p)%p;
tree[nod].sum=(tree[nod].sum+(r-l+1)*val%p)%p;
lazy[nod]=(lazy[nod]+val)%p;
}
void pushdown(int nod,int l,int r)
{
bian(nod*2,l,mid,lazy[nod]);
bian(nod*2+1,mid+1,r,lazy[nod]);
lazy[nod]=0;
}
void build(int nod,int l,int r)
{
if(l==r)
{
tree[nod].sum=val[rev[l]]%p;
tree[nod].mul=0;
return;
}
build(nod*2,l,mid);
build(nod*2+1,mid+1,r);
pushup(nod);
}
void add(int nod,int l,int r,int L,int R,int val)
{
if(l==L&&r==R)
{
tree[nod].mul=(tree[nod].mul+(r-l)*tree[nod].sum%p*val%p+(val*val)%p*jc[r-l]%p)%p;
tree[nod].sum=(tree[nod].sum+(r-l+1)*val%p)%p;
lazy[nod]=(lazy[nod]+val)%p;
return;
}
pushdown(nod,l,r);
if(R<=mid)add(nod*2,l,mid,L,R,val);
else if(L>mid)add(nod*2+1,mid+1,r,L,R,val);
else{
add(nod*2,l,mid,L,mid,val);
add(nod*2+1,mid+1,r,mid+1,R,val);
}
pushup(nod);
}
node query(int nod,int l,int r,int L,int R)
{
if(l==L&&r==R)return tree[nod];
pushdown(nod,l,r);
if(R<=mid)return query(nod*2,l,mid,L,R);
else if(L>mid)return query(nod*2+1,mid+1,r,L,R);
else{
node a=query(nod*2,l,mid,L,mid);
node b=query(nod*2+1,mid+1,r,mid+1,R);
node c;
c.sum=(a.sum+b.sum)%p;
c.mul=(a.mul+b.mul+a.sum*b.sum%p)%p;
return c;
}
}
void add2(int x,int y,int val)
{
int fx=top[x],fy=top[y];
while(fx!=fy)
{
if(dep[fx]<dep[fy])swap(x,y),swap(fx,fy);
add(1,1,seg[0],seg[fx],seg[x],val);
x=fa[fx];fx=top[x];
}
if(dep[x]>dep[y])swap(x,y);
add(1,1,seg[0],seg[x],seg[y],val);
}
int find(int x,int y)
{
int fx=top[x],fy=top[y];
node xu,jia;
jia.sum=0;jia.mul=0;
while(fx!=fy)
{
if(dep[fx]<dep[fy])swap(x,y),swap(fx,fy);
xu=query(1,1,seg[0],seg[fx],seg[x]);
jia.mul=(jia.mul+xu.mul+jia.sum*xu.sum%p)%p;
jia.sum=(jia.sum+xu.sum)%p;
x=fa[fx];fx=top[x];
}
if(dep[x]>dep[y])swap(x,y);
xu=query(1,1,seg[0],seg[x],seg[y]);
jia.mul=(jia.mul+xu.mul+jia.sum*xu.sum%p)%p;
jia.sum=(jia.sum+xu.sum)%p;
return jia.mul;
}
signed main()
{
scanf("%lld%lld",&n,&m);
jc[1]=1;
for(int i=2;i<=n;i++)jc[i]=(jc[i-1]+i)%p;
for(int i=1;i<=n;i++)scanf("%lld",&val[i]);
for(int i=1;i<n;i++)
{
scanf("%lld%lld",&x,&y);
add(x,y);
add(y,x);
}
dfs1(1,0);
seg[0]=seg[1]=rev[1]=top[1]=1;
dfs2(1,0);
build(1,1,seg[0]);
while(m--)
{
scanf("%lld",&opt);
if(opt==1)
{
scanf("%lld%lld",&x,&y);
add(1,1,seg[0],seg[x],seg[x]+size[x]-1,y);
}
if(opt==2)
{
scanf("%lld%lld%lld",&x,&y,&z);
add2(x,y,z);
}
if(opt==3)
{
scanf("%lld%lld",&x,&y);
printf("%lld\n",find(x,y));
}
}
return 0;
}时间复杂度：O(n log(n)*log(n))
