Codeforces Round #263 (Div. 1)-A,B,C

A：

这道题目还是非常easy的，做过非常多遍了。相似于分割木板的问题。

把全部的数放在一个优先队列里，弹出两个最大的，然后合并，把结果放进去。依次进行。

#include <iostream>

#include<stdio.h>

#include<stdlib.h>

#include<time.h>

#include<vector>

#include<algorithm>

#include<string.h>

#include<queue>

using namespace std;

#define LL __int64

#define INF 1000000000

LL a[330000];

priority_queue<LL>que;

int main()

{

    int n;

    while(~scanf("%d",&n))

    {

        LL sum=0;

        while(!que.empty())que.pop();

        for(int i=1;i<=n;i++)

        {

            scanf("%I64d",&a[i]);

            sum+=a[i];

            que.push(a[i]);

        }

        LL ans=0;

        while(!que.empty())

        {

            LL x=que.top();

            que.pop();

            if(!que.empty())

            {

                LL y=que.top();

                que.pop();

                ans+=x;

                ans+=y;

                que.push(x+y);

            }

            else

            {

                ans+=x;

                break;

            }

        }

        cout<<ans<<endl;

    }

    return 0;

}

B:树形DP

dp[i][0]:以i节点为根的子树对上面的贡献为0时的情况数

dp[i][1]:以i节点为根的子树对上面的贡献为1时的情况数

假设i节点为0

非常明显对于dp[i][1]:

枚举哪颗子树对i贡献了1，假如a,b,c为i的子树，则

dp[i][1]=dp[a][1]*dp[b][0]*dp[c][0]+dp[a][0]*dp[b][1]*dp[c][0]+dp[a][0]*dp[b][0]*dp[c][1];

对于dp[i][0]:

1，假设全部的子树都没有对i贡献

dp[i][0]+=dp[a][0]*dp[b][0]*dp[c][0];

2,存在一个子树对i贡献了1，可是i节点上方的边被切掉

dp[i][0]+=dp[i][1];

假设i节点为1

dp[i][0]=dp[i][1]=dp[a][0]*dp[b][0]*dp[c][0];

#include<iostream>

#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<iostream>

#include<vector>

#include<set>

#include<string>

using namespace std;

#define maxn 110000

#define LL __int64

#define mod 1000000007

vector<int>old[maxn];

vector<int>now[maxn];

int vis[maxn];

void change(int x)

{

    int i;

    vis[x]=1;

    for(i=0; i<old[x].size(); i++)

    {

        if(vis[old[x][i]])continue;

        now[x].push_back(old[x][i]);

        change(old[x][i]);

    }

}

LL dp[maxn][2];

int a[maxn];

LL q_mod(LL a,LL b,LL n)

{

    LL ret=1;

    LL tmp=a;

    while(b)

    {

        //基数存在

        if(b&0x1) ret=ret*tmp%n;

        tmp=tmp*tmp%n;

        b>>=1;

    }

    return ret;

}

LL dos(LL x,LL y,LL z)

{

    x=x*z;

    x=x%mod;

    x=x*q_mod(y,mod-2,mod);

    x=x%mod;

    return x;

}

void dfs(int x)

{

    int leap=0;

    LL sum=1;

    for(int i=0; i<now[x].size(); i++)

    {

        dfs(now[x][i]);

        leap=1;

        sum=sum*dp[now[x][i]][0];

        sum=sum%mod;

    }

    if(leap==0)

    {

        if(a[x]==0)

        {

            dp[x][0]=1;

            dp[x][1]=0;

        }

        else

        {

            dp[x][1]=1;

            dp[x][0]=1;

        }

         // cout<<x<<" "<<dp[x][1]<<" "<<dp[x][0]<<endl;

        return ;

    }

    if(a[x]==0)

    {

        dp[x][0]=sum;

        dp[x][1]=0;

        for(int i=0; i<now[x].size(); i++)

        {

            int y=now[x][i];

            dp[x][1]+=dos(sum,dp[y][0],dp[y][1]);

            dp[x][1]%=mod;

        }

        dp[x][0]+=dp[x][1];

        dp[x][0]%=mod;

    }

    else

    {

        dp[x][1]=sum;

        dp[x][0]=sum;

    }

   //  cout<<x<<" "<<dp[x][1]<<" "<<dp[x][0]<<endl;

}

int main()

{

    int i,n,j;

    int aa,ab;

    while(~scanf("%d",&n))

    {

        memset(vis,0,sizeof(vis));

        for(i=0; i<=n; i++)

        {

            old[i].clear();

            now[i].clear();

        }

        for(i=1; i<n; i++)

        {

            scanf("%d",&aa);

            aa=aa+1;

            ab=i+1;

            //  cout<<" "<<aa<<" -" <<ab<<endl;

            old[aa].push_back(ab);

            old[ab].push_back(aa);

        }

        for(int i=1; i<=n; i++)scanf("%d",&a[i]);

        change(1);

        dfs(1);

        cout<<dp[1][1]<<endl;

    }

    return 0;

}

非常明显，假设翻转大于一半，相当于先旋转。然后翻转剩下的。

那么我们最多会翻转2*n个数字。

然后就暴力枚举当前的状态。

然后用线段树储存每一个节点有多少长度，然后询问的时候区间求和。

#include<iostream>

#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<iostream>

#include<vector>

#include<set>

#include<string>

using namespace std;

#define maxn 110000

#define LL __int64

#define mod 1000000007

#define mem(a,b) (memset(a),b,sizeof(a))

#define lmin 1

#define rmax n

#define lson l,(l+r)/2,rt<<1

#define rson (l+r)/2+1,r,rt<<1|1

#define root lmin,rmax,1

#define now l,r,rt

#define int_now int l,int r,int rt

int have[maxn];

int sum[maxn<<2];

void creat(int_now)

{

    if(l!=r)

    {

        creat(lson);

        creat(rson);

        sum[rt]=sum[rt<<1]+sum[rt<<1|1];

    }

    else

    {

        sum[rt]=1;

    }

}

void updata(int ll,int x,int_now)

{

    if(ll>r||ll<l)return;

    if(ll==l&&l==r)

    {

        sum[rt]=x;

        return ;

    }

    updata(ll,x,lson);

    updata(ll,x,rson);

    sum[rt]=sum[rt<<1]+sum[rt<<1|1];

}

int query(int ll,int rr,int_now)

{

    if(ll>r||rr<l)return 0;

    if(ll<=l&&rr>=r)return sum[rt];

    return query(ll,rr,lson)+query(ll,rr,rson);

}

int leap,st,ed,n;

void chu(int p)

{

    if(leap==0)

    {

        st=st+p;

        ed=ed;

        for(int i=p; i>=1; i--)

        {

            have[st+i-1]=have[st+i-1]+have[st-i];

            updata(st+i-1,have[st+i-1],root);

        }

    }

    else

    {

        ed=ed-p;

        st=st;

        for(int i=p; i>=1; i--)

        {

            have[ed-i+1]=have[ed-i+1]+have[ed+i];

            updata(ed-i+1,have[ed-i+1],root);

        }

    }

}

int main()

{

    int q;

    while(~scanf("%d%d",&n,&q))

    {

        creat(root);

        for(int i=1; i<=n; i++)have[i]=1;

        int len=n;

        leap=0;

        st=1;

        ed=n;

        int a,b,p,t;

        while(q--)

        {

            scanf("%d",&t);

            if(t==1)

            {

                scanf("%d",&p);

                len=ed-st+1;

                int ban=len/2;

                if(p<=ban)

                {

                    chu(p);

                }

                else

                {

                    len=ed-st+1;

                    p=len-p;

                    leap=leap^1;

                    chu(p);

                }

            }

            else

            {

                scanf("%d%d",&a,&b);

                if(leap==0)

                {

                    a=a+st;

                    b=b+st-1;

                }

                else

                {

                    a=ed-a;

                    b=ed-b+1;

                    swap(a,b);

                }

                if(a>ed||b<st)

                {

                    cout<<"0"<<endl;

                    continue;

                }

                if(b>ed)b=ed;

                if(a<st)a=st;

                cout<<query(a,b,root)<<endl;

            }

        }

    }

    return 0;

}

巴特西

Codeforces Round #263 (Div. 1)-A,B,C

最新文章

热门文章