@贪心个人总结二-个人总结

· · 个人记录

贪心，要尝试缩小贪心的范围，发现最优解的性质

例如CF1082E，最优解的区间一定a[l]=a[r]，这样就极大的减小了我们枚举的范围。

贪心的关键一环是策略！

如果限制条件过于严格，难以证明，那么不妨考虑较松的限制条件，然后证明某种策略下，满足较松的限制条件的方案也满足较强的限制条件。

CF201E

设答案为k，

我们首先转化成k\times n的01矩阵，每一列都不同，每一行的1个数\le m。

然后考虑如何验证？我们可以二分k的值。如何check？

我们可以先降低要求，解决“1的总数\le k\times m”是否可行。

我们肯定先选择1个数较少的情况。具体来说，如果剩下t个1可用，则有i个1的情况有\min(t/i,C^i_k)种。

如何维护C？其实很大的话，手动设一个正无穷即可。

il int fit(const LL &x) {return x>inf?inf:x;}
bool check(int k)
{
    LL res=(LL)k*m,cnt=0;
    int cik=1;
    for(ri i=0; i<=k&&res>=i&&cnt<n; ++i)
    {
        int p=min(i?fit(res/i):inf,cik);
        cnt+=p;
        res-=(LL)p*i;
        cik=fit((LL)cik*(k-i)/(i+1));
    }
    return cnt>=n;
}

CF79D

唉，套路没有掌握全。

首先，这道题做的是区间取反，我们将序列差分一下，这样就只会影响两个位置了。

考虑序列中如果只有两个1：x1,x2，那么实际就是问，从x1出发，每次跳x2，最少几步能到。

我们可以BFS预处理出20个点相互的最短路，然后变成完全图的最大权匹配，状压DP即可。