T1 DP

考慮實(shí)際上合并顏色的過(guò)程就相當(dāng)于一棵樹(shù)的節(jié)點(diǎn)合并，正著處理不太方便，因?yàn)槲覀兛偛荒芎芊奖愕赜涗洜顟B(tài)，考慮倒過(guò)來(lái)思考，最后的
炮彈顏色是什么，又是怎樣合成的？

這樣，我們能找到一個(gè)幾乎一樣的子問(wèn)題：用來(lái)合成最后一個(gè)炮彈的每個(gè)炮彈，顏色是什么，每個(gè)炮彈又是如何生成的。

不妨考慮來(lái)設(shè)計(jì)這個(gè)狀態(tài):

• f[i,j] 表示使用i個(gè)球合成一個(gè)顏色j的方案數(shù)，不難發(fā)現(xiàn)轉(zhuǎn)移復(fù)雜度爆了

• 優(yōu)化為 f[i,j,k] 表示使用i個(gè)球合成k個(gè)顏色j的方案數(shù) , 這樣來(lái)說(shuō)時(shí)間復(fù)雜度就可以了

等等，這個(gè)狀態(tài)好像有點(diǎn)問(wèn)題，似乎出現(xiàn)了一種反規(guī)則的事件，這樣做貌似會(huì)使我們的轉(zhuǎn)化不合法：

1 1 1 4
1 1 1 2 2|||2
1 1 1 2 2|||3 3 3
1 1 1 2 2|||2 2 3 3
這樣不就提前轉(zhuǎn)化了嗎

我們更改DP狀態(tài)為 f[i,j,k,z] 表示本過(guò)程頭部合成過(guò)程中不能出現(xiàn)z顏色，注意是一直不能出現(xiàn)，而不是最后一次合并，因?yàn)橐坏┰陬^部出現(xiàn)就會(huì)發(fā)生“提前轉(zhuǎn)化”

• \(f[i,j,k,z]=\sum_{s1} f[s1,j,1,z]*f[i-s1,j,k-1,j]\) (為什么會(huì)面要限制頭部不能出現(xiàn) \(j\) ，因?yàn)槲覀僁P要嚴(yán)格遵循式子的意義，這樣才能不重不漏)
• \(f[i,j,1,z]=\sum_{y \neq z} f[i,y,b[y],z]\)

int f[505][12][12][12];
  
signed main() {
    cin>>n>>m;
    for(int i=1;i<=m;i++) {
        a[i]=read(),b[i]=read();
        c[b[i]].push_back(i);
    }
    for(int i=1;i<=m;i++) 
        for(int j=0;j<=m;j++) f[1][i][1][j]=1;
    for(int i=2;i<=n;i++) 
        for(int nw=1;nw<=m;nw++) {
            for(int cnt=2;cnt<=a[nw];cnt++) {
                for(int no=0;no<=m;no++) {
                    for(int s1=1;s1<i;s1++)
                        f[i][nw][cnt][no]+=f[s1][nw][1][no]*f[i-s1][nw][cnt-1][nw]%P,
                        f[i][nw][cnt][no]%=P;
                }
            }
            for(int no=0;no<=m;no++) 
                if(nw!=no) f[i][b[nw]][1][no]+=f[i][nw][a[nw]][no],
                           f[i][b[nw]][1][no]%=P;
        }
    int ans=0;
    for(int i=1;i<=m;i++) 
        ans+=f[n][i][1][0],ans%=P;
    cout<<ans;
    return 0;
}

T2 隨機(jī)化亂搞

【題目背景】

《For The King》是一款結(jié)合桌游和 roguelike 類(lèi)型元素的跨界策略 RPG
游戲。這段驚心動(dòng)魄的冒險(xiǎn)，還要從法汝大陸開(kāi)始，國(guó)王突遭不測(cè)，女王緊急召喚勇士們踏上命運(yùn)之路，破解謎團(tuán)阻止厄運(yùn)，一路升級(jí)尋找真相。

小 T，小 B 和小 Z 入坑了《4 the king》。游玩的時(shí)候他們選擇了一個(gè)"以
99%的概率成功，1%的概率死亡"的選項(xiàng)，然后似了。

小 T 重開(kāi)了個(gè)單人檔。

【題目描述】

小 T 創(chuàng)建存檔時(shí)，得知了這個(gè)存檔的地圖：地圖上有 \(n\) 個(gè)格子，被 \(n-1\)
條邊連通，構(gòu)成一棵樹(shù)。地圖上共有 \(n\) 只怪物，第 \(i\) 只怪物在編號(hào)為 \(i\)
的格子上。在開(kāi)始游戲前，小 T
可以選中一個(gè)連通塊，然后清除這個(gè)連通塊上的怪物，并獲得相應(yīng)的增益。

具體地，小 T 有兩種屬性，攻擊力與怒氣值，初始均為 \(0\)。第 \(i\)
個(gè)怪如果在連通塊內(nèi)，就會(huì)給小 T 增加 \(a_i\) 點(diǎn)攻擊力以及 \(b_i\)
點(diǎn)怒氣值。此外，第 \(i\) 只怪物有 \(c_i\) 點(diǎn)血量。小 T
在清除怪物后，還會(huì)獲得一定量的金幣。設(shè) \(A\) 為小 T 最終的攻擊力，\(B\) 為小
T 最終的怒氣值，\(C\) 為清除的怪物血量之和，那么小 T 會(huì)獲得 \(AB-C\)
個(gè)金幣。由于金幣在這個(gè)游戲中很重要，所以小 T
想知道如何能獲得最多的金幣。小 T
也可以選擇直接跳過(guò)這個(gè)游戲前的階段，那么他會(huì)獲得 \(0\) 個(gè)金幣。

（注：最終的攻擊力 \(A\) 即為所有選中怪物的 \(a_i\) 之和，\(B,C\) 同理）

小 T 會(huì)重開(kāi)很多個(gè)檔，所以本題有多組詢(xún)問(wèn)。

【輸入格式】

第一行為數(shù)據(jù)組數(shù) \(T\)，接下來(lái)依次輸入每組數(shù)據(jù)。對(duì)于每組數(shù)據(jù)：

第一行一個(gè)整數(shù) \(n\)，表示地圖上的格子數(shù)。

接下來(lái) \(n\) 行，每行三個(gè)整數(shù) \(a_i,b_i,c_i\)，代表第 \(i\) 個(gè)怪的屬性。

再接下來(lái) \(n-1\) 行每行兩個(gè)整數(shù)，表示地圖上的一條邊。

【輸出格式】

對(duì)于每組數(shù)據(jù)，輸出兩行。

第一行一個(gè)整數(shù) \(ans\)，表示獲取的最大金幣數(shù)。

第二行一個(gè)長(zhǎng)度為 \(n\) 的 01 字符串表示方案。第 \(i\) 個(gè)字符為 1
表示選中了第 \(i\)
個(gè)格子，否則沒(méi)有選中。（如果選擇跳過(guò)這個(gè)階段，則需要輸出 \(n\) 個(gè) 0）
————————————
首先這個(gè)題看著就很能亂搞

考慮說(shuō)如果確定結(jié)束時(shí)A與B的值，那么對(duì)于一個(gè)點(diǎn)來(lái)說(shuō)，他加不加入我們是可以貪心的

if((ra-A[i])*(rb-B[i])+C[i]<=ra*rb) {
     A[p]+=A[i],B[p]+=B[i],C[p]+=C[i];
}

所以我們隨機(jī)一個(gè)A,B跑上述貪心，然后得到一個(gè)近似解，在近似解周?chē)倥茇澬模敲淳涂梢酝ㄟ^(guò)水?dāng)?shù)據(jù)

int T,n,a[N],b[N],c[N],A[N],B[N],C[N],D;
 
int sa,sb,ra,rb,wa,wb,tmp;
 
vector<int > v[N];
bitset<N > ans[N],vis;
 
void dfs(int p,int f) {
    A[p]=a[p],B[p]=b[p],C[p]=c[p];
    for(int i:v[p]) {
        if(i==f) continue;
        dfs(i,p);
        if((ra-A[i])*(rb-B[i])+C[i]<=ra*rb) {
            A[p]+=A[i],B[p]+=B[i],C[p]+=C[i];
        }
    }
    if(A[p]*B[p]-C[p]>tmp) {
        tmp=A[p]*B[p]-C[p];wa=ra,wb=rb;
    }
}
 
void answer(int p,int f) {
    A[p]=a[p],B[p]=b[p],C[p]=c[p];
    ans[p][p]=1;
//  cout<<p<<" "<<ans[p][p]<<endl;
    for(int i:v[p]) {
        if(i==f) continue;
        answer(i,p);
        if((wa-A[i])*(wb-B[i])+C[i]<wa*wb) {
            A[p]+=A[i],B[p]+=B[i],C[p]+=C[i];
            ans[p]|=ans[i];
//          cout<<i<<" "<<p<<" "<<ans[i][i]<<endl;
//          for(int j=1;j<=n;j++) printf("%lld",(int)ans[p][j]);cout<<endl;
        }
    }
    if(A[p]*B[p]-C[p]==tmp) {
        tmp=A[p]*B[p]-C[p];wa=ra,wb=rb;
        vis=ans[p];
//      cout<<p<<" ";
    }
}
 
void tidy() { for(int i=1;i<=n;i++) A[i]=B[i]=C[i]=0; }
 
void Solve() {
    mt19937 t1(time(0));
    mt19937 t2(t1());mt19937 t3(t2());mt19937 t4(t3());mt19937 t5(t4());mt19937 t6(t5());
    mt19937 rd(t5());
    int number=0;
    while(number<=up/n) {
        ra=(rd()%sa+1),rb=(rd()%sb+1);
        ra>>=(rd()%8),rb>>=(rd()%8);
        dfs(1,0);tidy();
        number++;
    }
    number=0;
    sa=wa,sb=wb;
    while(number<=up/n) {
        ra=(int)(sa+rd()%(sa/2+1)-sa/4+1);
        rb=(int)(sb+rd()%(sb/2+1)-sb/4+1);
        dfs(1,0);tidy();
        number++;
    }
    answer(1,0);
    cout<<tmp<<endl;
    for(int i=1;i<=n;i++) printf("%lld",(int)vis[i]);cout<<endl;
}
void Clear(){
    sa=sb=0;wa=wb=0,tmp=0;vis.reset();
    for(int i=1;i<=n;i++) v[i].clear(),a[i]=b[i]=c[i]=0,ans[i].reset();
}
 
signed main() {
    cin>>T;
    while(T--) {
        cin>>n;
        for(int i=1;i<=n;i++) {
            a[i]=read(),b[i]=read(),c[i]=read();
            sa+=a[i],sb+=b[i];
        }
        for(int i=1;i<n;i++) {
            int x=read(),y=read();
            v[x].push_back(y),v[y].push_back(x);
        }
        Solve();Clear();
    }
     
    return 0;
}