牛客练习赛26

2019-04-03

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个烟花产生颜色的期望。

1 2	for(int i=1;i<=n;i++) f[i]=(f[i-1]+1.0)p[i]+f[i-1](1.0-p[i]);

对于第2个问题, $g[i][j]$ 表示前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，那么

1
2
3

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))