Codeforces ラウンド #263 (ディビジョン 1)-A、B、C_html/css_WEB-ITnose

A:

この質問は私も何度もやりましたが、木の板を切る問題に似ています。

すべての数値を優先キューに入れ、最大の 2 つの数値を取り出し、それらをマージし、結果を入力します。順番に進めてください。

rreeeB: ツリー 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];

for 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<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;}

C:

明らかに、反転が半分を超える場合、最初に回転してから残りを反転するのと同じです。

次に、最大 2*n 個の数値を反転します。そして現状を乱暴に列挙する。

次に、線分ツリーを使用して各ノードの長さを保存し、質問するときに間隔を合計します。 ❤️