menu Shadowice!
CF1401选做
103 浏览 | 2020-09-07 | 阅读时间: 约 2 分钟 | 分类: ACM | 标签:
请注意,本文编写于 42 天前,最后修改于 42 天前,其中某些信息可能已经过时。

D

一句话题意

题面清楚,不写了

思路

计算每条边对f的贡献

若$ m \leq n-1$,则按排序不等式贪心

否则不能放1,最大的质数all in最大权值剩下依然按排序不等式走

代码

#include<cstdio>
#include<algorithm>
using namespace std;const int N=1e5+10;
typedef long long ll;const ll mod=1e9+7;
int al[N];int v[N<<1];int x[N<<1];int ct;
void add(int u,int V)
{
    v[++ct]=V;x[ct]=al[u];al[u]=ct;
}
int siz[N];ll val[N];
int dfs(int u,int f)
{
    siz[u]=1;
    for(int i=al[u];i;i=x[i])
        if(v[i]!=f)
            siz[u]+=dfs(v[i],u);
    return siz[u];
}
int n;int m;ll ans;int pr[N];
# define sz(a,r) \
    for(int i=0;i<=r;i++)a[i]=0;

void clear()
{
    sz(al,n);
    sz(v,ct);
    sz(x,ct);
    ct=0;
    sz(siz,n);
    sz(val,n);
    sz(pr,m);
    n=0;m=0;
}
void solve()
{
    scanf("%d",&n);
    for(int i=1,u,V;i<n;i++)
        scanf("%d%d",&u,&V),add(u,V),add(V,u);
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
        scanf("%d",&pr[i]);
    sort(pr+1,pr+m+1);
    dfs(1,0);
    for(int i=2;i<=n;i++)
        val[i-1]=(ll)siz[i]*(ll)(n-siz[i]);
    sort(val+1,val+n);
    if(n-1>=m)
    {
//        printf("cas n-1>=m\n");
//        for(int i=1;i<=n-1;i++)
//            printf("%d ",(int)val[i]);printf("\n");
//        for(int i=1;i<=m;i++)
//            printf("%d ",pr[i]);printf("\n");
        int hd=n-1;ans=0;
        for(int i=m;i>=1;i--,hd--)
            (ans+=val[hd]%mod*pr[i])%=mod;
        for(int i=hd;i>=1;i--)
            (ans+=val[i]%mod)%=mod;
        int pans=ans;
        printf("%d\n",pans);
    }
    else 
    {
        int hd=m;ans=val[n-1]%mod;
        for(;hd>=n-1;hd--)
            (ans*=pr[hd])%=mod;
        for(int i=n-2;i>=1;i--)
            (ans+=val[i]%mod*pr[i])%=mod;
        int pans=ans;
        printf("%d\n",pans);
    }
}
int main()
{
    int t;scanf("%d",&t);
    for(int i=1;i<=t;i++)
        solve(),clear();
    return 0;
}

Tips

循环变量打错了,i变成了hd,i是无意义的

E

一句话题意

把一个正方形割若干刀,每刀都从一条边开始割,并且每一刀和边平行,求正方形最后剩下几块

思路

变种扫描线

扫描线以下的部分其实无关紧要

计数遵循每一个块在最高的横边上计数一次的规则

从底部开始竖线才对答案有贡献,而顶部开始的竖线不影响联通性

每次横向割完一刀后,顶部开始的线等价于底部开始的线

由于都是前后缀拿树状数组,vector,set什么的维护下就行,很好写

代码

#include<cstdio>
#include<algorithm>
#include<set>
#include<vector>
using namespace std;const int N=1e6+10;
typedef long long ll;
int n;int m;
struct tree_array_pre
{
    ll a[N];
    void add(int x,ll val)
    {
        for(;x<=1e6;x+=x&(-x))a[x]+=val;
    }
    ll sum(int x)
    {
        ll ans=0;
        for(;x;x-=x&(-x))ans+=a[x];
        return ans;
    }
}pre;
struct tree_array_suf
{
    ll a[N];
    void add(int x,ll val)
    {
        for(;x;x-=x&(-x))a[x]+=val;
    }
    ll sum(int x)
    {
        ll ans=0;
        for(;x<=1e6;x+=x&(-x))ans+=a[x];
        return ans;
    }
}suf;
set <int> s;
struct line
{
    int l;int r;
};
vector <line> hor[N];
vector <int> vup[N];
vector <int> vdw[N];
# define VIT  vector<int>::iterator 
# define VLT  vector<line>::iterator 
# define b(x) x.begin()
# define e(x) x.end()
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        line cur;int id;
        scanf("%d%d%d",&id,&cur.l,&cur.r);
        hor[id].push_back(cur);
    }
    for(int i=1;i<=m;i++)
    {
        line cur;int id;
        scanf("%d%d%d",&id,&cur.l,&cur.r);
        if(cur.l==0)
            vup[cur.r].push_back(id),
            pre.add(id,1),
            suf.add(id,1);
        else vdw[cur.l].push_back(id);
    }
    hor[(int)1e6].push_back((line){0,(int)1e6});
    pre.add((int)1e6,1);
    ll ans=0;
    for(int i=0;i<=1e6;i++)
    {
        for(VIT it=b(vdw[i]);it!=e(vdw[i]);++it)
            s.insert(*it);
        for(VLT it=b(hor[i]);it!=e(hor[i]);++it)
            if(it->l==0)
            {
                ans+=pre.sum(it->r);
                while(!s.empty()&&*s.begin()<=it->r)
                {
                    int cur=*s.begin();
                    pre.add(cur,1);
                    suf.add(cur,1);
                    s.erase(s.begin());
                }
            }
            else 
            {
                ans+=suf.sum(it->l);
                while(!s.empty()&&*s.rbegin()>=it->l)
                {
                    int cur=*s.rbegin();
                    pre.add(cur,1);
                    suf.add(cur,1);
                    s.erase(cur);
                }
            }
        for(VIT it=b(vup[i]);it!=e(vup[i]);++it)
            pre.add(*it,-1),
            suf.add(*it,-1);
    }
    printf("%I64d",ans);
    return 0;
}

Tips

stl不支持删除反向迭代器
树状数组,维护前缀和时,插入加lowbit,求和减lowbit

维护后缀和时,插入减lowbit,求和加lowbit

F

一句话题意

很清楚了不写了

思路

reverse操作可以拆成连续的swap操作,想想平衡树怎么支持区间反转就知道了

区间非常好看可以拿线段树维护

无论怎么swap父子关系都不会改变,那维护的区间和也不会改变,事实上每一层有只有两种不同的左右儿子连接方式

所以我们每层打个标记,访问线段树时让线段树自己调整一下变成正确的线段树就可以了

代码

#include<cstdio>
#include<algorithm>
using namespace std;const int N=262144+10;
typedef long long ll;
struct linetree
{
    //int nod_msk[N<<2];
    int dep[N<<2];
    int lev_msk[50];
    int s[N<<2][2];
    ll sum[N<<2];
    void build(int p,int l,int r,int* a)
    {
        if(r-l==1)
        {
            sum[p]=a[l];
            dep[p]=-1;
            return;
        }
        int mid=(l+r)>>1;
        s[p][0]=p<<1,build(p<<1,l,mid,a);
        s[p][1]=p<<1|1,build(p<<1|1,mid,r,a);
        sum[p]=sum[p<<1]+sum[p<<1|1];
        dep[p]=dep[p<<1]+1;
    }
    void check_nod(int id,int p)
    {
        if((s[p][0]!=(p<<1))^lev_msk[dep[id]])
        {
    //        printf("success check\n");
            swap(s[p][0],s[p][1]);
        }
    }
    ll csum(int id,int p,int l,int r,int dl,int dr)
    {
        if(r==dr&&l==dl)
        {
            return sum[p];
        }
        check_nod(id,p);
        int mid=(l+r)>>1;
        ll ret=0;
        if(dl<mid)ret+=csum(id<<1,s[p][0],l,mid,dl,min(dr,mid));
        if(mid<dr)ret+=csum(id<<1|1,s[p][1],mid,r,max(mid,dl),dr);
        return ret;
    }
    void chval(int id,int p,int l,int r,int pos,ll va)
    {
        if(r-l==1)
        {
            sum[p]=va;return;
        }
        check_nod(id,p);
        int mid=(l+r)>>1;
        if(pos<mid)chval(id<<1,s[p][0],l,mid,pos,va);
        else chval(id<<1|1,s[p][1],mid,r,pos,va);
        sum[p]=sum[s[p][0]]+sum[s[p][1]];
    }
    void swp(int lev)
    {
        lev_msk[lev]^=1;
    }
    void prit_rec(int id,int p,int l,int r)
    {
        if(r-l==1)
        {
            return;
        }
        check_nod(id,p);
        int mid=(l+r)>>1;
        prit_rec(id<<1,s[p][0],l,mid);
        prit_rec(id<<1|1,s[p][1],mid,r);
        return;
    }
    void fake_rec(int id,int p,int l,int r)
    {
        if(r-l==1)
        {
            return;
        }
        //check_nod(id,p);
        int mid=(l+r)>>1;
        if((s[p][0]==(p<<1))^lev_msk[dep[id]])
        {
            printf("[%d,%d] is <%d,%d>\n",l,r,(s[p][0]!=(p<<1)),lev_msk[dep[id]]);
            fake_rec(id<<1,s[p][1],l,mid);
            fake_rec(id<<1|1,s[p][0],mid,r);
        }
        else 
        {
            fake_rec(id<<1,s[p][0],l,mid);
            fake_rec(id<<1|1,s[p][1],mid,r);
        }
        return;
    }
    void prit(int p,int l,int r)
    {
        printf("current sequence:");
        fake_rec(p,p,l,r);
        printf("\n");
    }
        
}lt;
int a[N];int n;int m;
int main()
{
//    freopen("tst.in","r",stdin);
//    freopen("my.out","w",stdout);
    scanf("%d%d",&n,&m);n=1<<n;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    lt.build(1,1,n+1,a);
    for(int i=1,id,pr1,pr2;i<=m;i++)
    {
        scanf("%d",&id);
        switch(id)
        {
            case 1:{
                       scanf("%d%d",&pr1,&pr2),
                           lt.chval(1,1,1,n+1,pr1,pr2);
                       break;
                }
            case 2:
                {
                    scanf("%d",&pr1);
                    for(int j=0;j<pr1;j++)
                        lt.swp(j);
                    break;
                }
            case 3:{
                       scanf("%d",&pr1);
                       lt.swp(pr1);
                       break;
                }
            case 4:{
                       scanf("%d%d",&pr1,&pr2);
                       printf("%lld\n",lt.csum(1,1,1,n+1,pr1,pr2+1));
                       break;
                 }
        }
//        printf("i=%d,",i);lt.prit(1,1,n+1);
    }
    return 0;
}

Tips

如果直接将表示区间映射成固定值,在固定值上存储反转标记的话,由于实际节点会乱窜,因此标记和实际的儿子状况不匹配,会出bug

知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议

发表评论

email
web

全部评论 (暂无评论)

info 还没有任何评论,你来说两句呐!