a：
这道题目还是很简单的，做过很多遍了，类似于切割木板的问题。
把所有的数放在一个优先队列里，弹出两个最大的，然后合并，把结果放进去。依次进行。
#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:树形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 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:
很明显，如果翻转大于一半，相当于先旋转，然后翻转剩下的。
那么我们最多会翻转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 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;}
