题解：P16110 「o.OI R-1」Easy ver.

tuntunQwQ · 2026-04-04 19:31:03 · 题解

树的度数为 2n-2，因为每条边做了 2 次贡献。

考虑先令 n-2 个点的度数为 2，其余两个为 1，此时积为 2^{n-2}。

尝试将一个 2 调整为 3，另一个 2 变成 1，积除去 4 再乘上 3，不如原来优。

综上，将 2 调整为 k 的代价是积除以 2^{k-2+1} 再乘上 k，前者是指数级的，所以 2^{n-2} 就是最优，也就是链。

代码如下，可供参考：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<m;j++){
            cout<<1<<' ';
        }
        cout<<0<<'\n';
    }
    for(int i=1;i<n;i++){
        if(i%2==1){
            for(int j=1;j<m;j++){
                cout<<0<<' ';
            }
            cout<<1<<'\n';  
        }
        else{
            cout<<1<<' ';
            for(int j=1;j<m;j++){
                cout<<0<<' ';
            }
            cout<<'\n';
        }
    }
    for(int j=1;j<=m;j++)cout<<0<<' ';
    return 0;
}