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

这道题目还是很简单的，做过很多遍了，类似于切割木板的问题。

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

#include #include#include#include#include#include#include#includeusing namespace std;#define LL __int64#define INF 1000000000LL a[330000];priority_queueque;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
  
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#include#include#include#include#include#include#includeusing namespace std;#define maxn 110000#define LL __int64#define mod 1000000007vectorold[maxn];vectornow[maxn];int vis[maxn];void change(int x){    int i;    vis[x]=1;    for(i=0; i>=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  
  
  
C:
  
很明显，如果翻转大于一半，相当于先旋转，然后翻转剩下的。
  
那么我们最多会翻转2*n个数字。然后就暴力枚举当前的状态。
  
然后用线段树储存每个节点有多少长度，然后询问的时候区间求和。
  
  
#include#include#include#include#include#include#include#includeusing 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||llr||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||bed)b=ed;                if(a