2020牛客暑期多校第七场

Author Avatar
MorphLing 8月 07, 2020

H.Dividing

标签：整除分块

发现符合要求的(n,k)无非两种，要么n是k的倍数，要么n-1是k的倍数（n=1也算）

于是就把问题转化成求解$\sum_{k=1}^n\lfloor\frac{N}{k} \rfloor+\sum_{k=2}^n(\lfloor\frac{N-1}{k} \rfloor+1)$

可以直接整除分块 $O(\sqrt{n})$求解

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=1e5+5,MOD=1e9+7;

ll T,n,k,m;

ll sum,up,down,last;

int main()
{
    cin>>n>>k;
    if (k<=sqrt(n))
    {
        for (int i=1;i<=k;i++)
        {
            sum=(sum+n/i)%MOD;
            sum=(sum+(n-1)/i+1)%MOD;
        }
        sum=((sum-n)%MOD+MOD)%MOD;
    }
    else
    {
        up=sqrt(n);
        for (int i=1;i<=up;i++)
            sum=(sum+n/i)%MOD;
        down=n/k;
        last=k;
        for (int i=down;i<=up;i++)
        {
            sum=(sum+1ll*i*(last-n/(i+1)))%MOD;
            last=n/(i+1);
        }
        if (1ll*up*(up+1)>n) sum-=up;

        n--;
        up=sqrt(n);
        for (int i=1;i<=up;i++)
            sum=(sum+n/i)%MOD;
        down=n/k;
        last=k;
        for (int i=down;i<=up;i++)
        {
            sum=(sum+1ll*i*(last-n/(i+1)))%MOD;
            last=n/(i+1);
        }
        if (1ll*up*(up+1)>n) sum-=up;
        sum=((sum-n)%MOD+MOD)%MOD;
        sum=(sum+k-1)%MOD;
    }
    printf("%lld\n",sum);
    return 0;
}

B.Mask-Allocation

标签：思维，构造，gcd

题意真的很难看懂

构造方法类似于在n*m的矩阵里填正方形
在这里插入图片描述
比如这个7*4的，需要7组4个就横着看，需要4组7个就把每个正方形旋转90度之后竖着看。直觉上感觉这种构造方法比较优，但是正确性证不来。

写法就是类似于求gcd。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=1e5+5,INF=0x3f3f3f3f;

int T,n,m;

vector<int>ans;

int main()
{
    cin>>T;
    while(T--)
    {
        scanf("%d%d",&n,&m);
        if (n<m) swap(n,m);
        ans.clear();
        while(n%m!=0)
        {
            for (int i=1;i<=n/m*m;i++) ans.push_back(m);
            int t=m;
            m=n%m;
            n=t;
        }
        for (int i=1;i<=n;i++) ans.push_back(m);
        printf("%d\n",ans.size());
        for (auto x:ans) printf("%d ",x);
        printf("\n");
    }
    return 0;
}

C.A-National-Pandemic

标签：树链剖分

树剖的就是一种能实现在$O(log^2n)$的复杂度内修改和查询树上两点路径和的结构。
入门推荐
模板题
其复杂度一方面由线段树logn区间修改查询，另一方面由“任意结点到根最多经过logn条轻边”来保证。

怎么通过查询路径和解决这道题呢？

首先对于操作一，我们希望把这个操作从任意结点转移到根结点上，可以先对x到根每条边权值+2（在查询时作为补充），再修改全局变量global+=w-dep[x]，把操作转化为对根节点的操作。

对于操作二，先查询（操作三）点值，然后对于大于0的部分，单独搞一个变量fix把大于0的部分抵消掉。

对于操作三查询直接给出计算方法
ans=qQuery(x,1)+global-tot(dep[x])+fix[x];
也就是”x到根节点的路径和”+”全局变量”-“操作一的次数”“x的深度”+”操作二的抵消部分”

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=5e4+5;

ll q[N];

int n,m,r,p,fix[N],tot,T,global;

struct segTree{
    ll t[N<<4];
    ll lztag[N<<4];
    void init()
    {
        memset(t,0,sizeof(t));
        memset(lztag,0,sizeof(lztag));
    }
    void pushdown(int o,int l,int r)
    {
        if (lztag[o])
        {
            int mid=(l+r)>>1;
            t[o*2]+=lztag[o]*(mid-l+1);
            t[o*2+1]+=lztag[o]*(r-mid);
            lztag[o*2]+=lztag[o];
            lztag[o*2+1]+=lztag[o];
            lztag[o]=0;
        }
    }
    void pushup(int o,int l,int r)
    {
        t[o]=t[o*2]+t[o*2+1];
    }
    void build(int o,int l,int r)
    {
        if (l==r)
        {
            //t[o]=ord[l]%p;
            return;
        }
        int mid=(l+r)>>1;
        build(o*2,l,mid);
        build(o*2+1,mid+1,r);
        pushup(o,l,r);
    }
    void modify(int o,int l,int r,int tl,int tr,int v)
    {
        if (tl<=l && r<=tr)
        {
            t[o]+=1ll*v*(r-l+1);
            lztag[o]+=v;
            return;
        }
        int mid=(l+r)>>1;
        pushdown(o,l,r);
        if (tl<=mid) modify(o*2,l,mid,tl,tr,v);
        if (tr>mid) modify(o*2+1,mid+1,r,tl,tr,v);
        pushup(o,l,r);
    }
    ll query(int o,int l,int r,int tl,int tr)
    {
        if (tl<=l && tr>=r) return t[o];
        int mid=(l+r)>>1;
        pushdown(o,l,r);
        if (tr<=mid) return query(o*2,l,mid,tl,tr);
        if (tl>mid) return query(o*2+1,mid+1,r,tl,tr);
        return query(o*2,l,mid,tl,tr)+query(o*2+1,mid+1,r,tl,tr);
    }
}ST;

int sz[N],dep[N],son[N],fa[N],top[N],num[N],cnt;

vector<int>G[N];

void init()
{
    memset(sz,0,sizeof(sz));
    memset(fix,0,sizeof(fix));
    tot=0;
    cnt=0;
    fa[1]=-1;
    dep[1]=1;
    top[1]=1;
    global=0;
}

void dfs1(int x)
{
    int mxson=-1;
    son[x]=-1;
    for (auto to:G[x])
    {
        if (to==fa[x]) continue;
        dep[to]=dep[x]+1;
        fa[to]=x;
        dfs1(to);
        if (sz[to]>mxson) mxson=sz[to], son[x]=to;
        sz[x]+=sz[to];
    }
    sz[x]++;
}
void dfs2(int x,int tp)
{
    num[x]=++cnt;
    top[x]=tp;
    if (~son[x]) dfs2(son[x],tp);
    for (auto to:G[x])
    {
        if (to==fa[x] || to==son[x]) continue;
        dfs2(to,to);
    }
}
void qModify(int x,int y,int z)
{
    while(top[x]!=top[y])
    {
        if (dep[top[x]]<dep[top[y]]) swap(x,y);
        ST.modify(1,1,n,num[top[x]],num[x],z);
        x=fa[top[x]];
    }
    if (dep[x]>dep[y]) swap(x,y);
    ST.modify(1,1,n,num[x],num[y],z);
}
void subrootModify(int x,int z)
{
    ST.modify(1,1,n,num[x],num[x]+sz[x]-1,z);
}

ll qQuery(int x,int y)
{
    ll res=0;
    while(top[x]!=top[y])
    {
        if (dep[top[x]]<dep[top[y]]) swap(x,y);
        res+=ST.query(1,1,n,num[top[x]],num[x]);
        x=fa[top[x]];
    }
    if (dep[x]>dep[y]) swap(x,y);
    res+=ST.query(1,1,n,num[x],num[y]);
    return res;
}

ll subrootQuery(int x)
{
    return ST.query(1,1,n,num[x],num[x]+sz[x]-1);
}

void solve()
{
    cin>>n>>m;
    for (int i=1;i<=n;i++) G[i].clear();
    for (int i=1;i<=n-1;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    init();
    dfs1(1);
    dfs2(1,1);
    ST.init();
    for (int i=1;i<=m;i++)
    {
        int opt,x,w;
        scanf("%d",&opt);
        if (opt==1)
        {
            scanf("%d%d",&x,&w);
            qModify(x,1,2);
            global+=w-dep[x];
            tot++;
        }
        if (opt==2)
        {
            scanf("%d",&x);
            int ask=qQuery(x,1)+global-tot*(dep[x])+fix[x];
            if (ask>0) fix[x]-=ask;
        }
        if (opt==3)
        {
            scanf("%d",&x);
            int ask=qQuery(x,1)+global-tot*(dep[x])+fix[x];
            printf("%d\n",ask);
        }
    }
}

int main()
{
    cin>>T;
    while(T--) solve();
    return 0;
}