Codeforces Round #263 (Div. 1)-A,B,C_html/css_WEB-ITnose

A:

This question is still very simple. I have done it many times. It is similar to the problem of cutting a wooden board.

Put all the numbers in a priority queue, pop out the two largest ones, merge them, and put the result in. Proceed in sequence.

#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 1000000000LL 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: Tree DP

dp[i][0]: When the contribution of the subtree rooted at node i to the above is 0 Number of cases

dp[i][1]: Number of cases when the contribution of the subtree rooted at node i to the above is 1

If node i is 0

It is obvious that for dp[i][1]:

enumerate which subtree contributes 1 to i. If a, b, c are subtrees of i, then

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];

For dp[i][0]:

1, if all subtrees do not contribute to i

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

2, there is a subtree that contributes 1 to i, but the edge above the i node is cut off

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

If i node is 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 1000000007vector<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;}

C:

Obviously, if the flip is greater than half, it is equivalent to rotating first and then flipping the rest.

Then we will flip at most 2*n numbers. Then violently enumerate the current status.

Then use the line segment tree to store the length of each node, and then sum the intervals when asking.

#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 rtint 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;}