磨磨唧唧的把题目做完了。

A – Phoenix and Science (1348D)

难度标1900，是个人基本都能在练习的时候搓出来的题目。

首先很明显的，第0天最多有1个细菌，第1天最多有$2^1$个……第n天白天执行分裂操作后最多有$2^n$个细菌。同时注意到“开局一条菌，装备全靠爆”，也就是说在接下来的日子里，第$i$天出现的细菌最多可以解决掉$n-i$的增长量。然后就有了贪心的思路：每一天尽可能地分裂，然后稍微注意一下分裂的时机，保证不会溢出。

namespace lovelive{
    typedef long long LL;
    LL POWER[51],n,ansi[50],pow;
    void init(){
        POWER[0] = 1;
        for(int i=1;i<=50;i++){
            POWER[i] = POWER[i-1]<<1;
        }
    }
    void main(){
        cin>>n;
        pow = upper_bound(POWER,POWER+50,n)-POWER-1;
        LL j,remain=n-pow-1;

        for(LL i=0;i<pow;i++){
            j = min((1ll<<i),remain / (pow-i));
            ansi[i] = j;
            remain -= j*(pow-i);
        }

        cout<<pow<<endl;
        for(LL i=0;i<pow;i++)cout<<ansi[i]<<" ";
        cout<<endl;
    }
}

B – Removing Leaves (1385F)

练习时由于漏条件了（connected to the same vertex，删除的叶子结点必须与同一个父节点相连），于是白忙活一场。思路很简单，按照叶子数量从大到小的顺序选择父节点删叶子结点，若叶子结点删完了就更新祖结点的值。

namespace lovelive{
    typedef long long LL;
    typedef set<LL> VEC;

    vector<VEC > edge,leaves;
    LL n=0,a,b,k,ans;

    struct comp {
        bool operator() (LL a, LL b) const {
            if (leaves[a].size() == leaves[b].size()) return a < b;
            return leaves[a].size() > leaves[b].size();
        }
    };
    set<LL,comp> q;

    void clear(){
        q.clear();ans = 0;
        edge = leaves = vector<VEC>(n+1);
    }
    void addEdge(LL a,LL b){
        edge[a].insert(b);
        edge[b].insert(a);
    }
    void main(){
        cin>>n>>k;
        clear();
        for(int i=1;i<n;i++){
            cin>>a>>b;
            addEdge(a,b);
        }
        for(int i=1;i<=n;i++){
            if(edge[i].size()==1){
                VEC::iterator fa = edge[i].begin();
                leaves[*fa].insert(i);
            }
        }
        for(int i=1;i<=n;i++){
            q.insert(i);
        }

        while(true){
            LL cur = *q.begin();
            if(leaves[cur].size()<k)break;
            for(LL cnt=1;cnt<=k;cnt++){
                LL leaf = *leaves[cur].begin();
                edge[cur].erase(leaf);
                edge[leaf].erase(cur);
                q.erase(cur);
                q.erase(leaf);
                leaves[cur].erase(leaf);
                if(leaves[leaf].count(cur)){
                    leaves[leaf].erase(cur);
                }
                if(edge[cur].size()==1){
                    LL to = *edge[cur].begin();
                    q.erase(to);
                    leaves[to].insert(cur);
                    q.insert(to);
                }
                q.insert(cur);
                q.insert(leaf);
            }
            ans++;
        }
        cout<<ans<<endl;
        return;
    }
}

C – Carrots for Rabbits (1428E)

贪心

namespace lovelive{
    typedef long long LL;
    LL n,k,ai[100005],ans;

    LL cal(LL val,LL cnt){
        LL ans;
        LL per = (val / cnt);
        LL rem = val - cnt * per;//多出来的就每块一片
        ans = per * per * (cnt - rem);
        ans += (per+1) * (per+1) * (rem);
        return ans;
    }
    struct PAIR{
        LL val,cnt;
        friend bool operator < (const PAIR& a,const PAIR b){
            return cal(a.val,a.cnt) - cal(a.val,a.cnt+1) < 
                    cal(b.val,b.cnt) - cal(b.val,b.cnt+1);
        }
    };
    priority_queue<PAIR> q;
    void main(){
        cin>>n>>k;ans = 0;
        for(LL i=1;i<=n;i++){
            cin>>ai[i];
            ans += ai[i]*ai[i];
            q.push({ai[i],1});
        }
        for(LL i=n;i<k;i++){
            PAIR cur = q.top();q.pop();
            ans -= cal(cur.val,cur.cnt) - cal(cur.val,cur.cnt +1);
            cur.cnt++;
            q.push(cur);
        }
        cout<<ans<<endl;
    }
}