题解：CF755F PolandBall and Gifts

· · 题解

考虑每一个置换环。假设长度为 n 的置换环上有 x 个人没带礼物，那么这个环上最少有几个人收不到礼物，最多几个人收不到礼物？

最少肯定是将这个环上所有节点聚集在一起，因此：

f_{\min}(x) = \left\{ \begin{matrix} x+1, & x \le n-1 \\ x, & x = n \end{matrix} \right.

使用调整法容易发现，最终必定只有最多 1 个环既有带礼物的又有不带礼物的，这时最小答案是 k+1；如果不存在一个环既有带礼物的又有不带礼物的，这时最小答案是 k。

因此我们只需要判断后一种情况是否可行，那本质就是将所有置换环长度做 0/1 背包。

一种方法是将所有大小相同的背包合并，变成多重背包后二进制分组，使用 bitset 优化。

具体复杂度分析参见其他题解。

另一种方法（我自己想的）是直接无脑分治。如果这种环的长度 \ge 100，直接使用 bitset。显然这样的环不会超过 10^4 个，使用 bitset 能接受。

如果这种环的长度 < 100，使用多重背包（不过单调队列都不需要）可以做到 O(n) 一次。

总的运算量为 10^8 数量级。

最大值是简单的。对于偶环，如果长度为 n，在前 \dfrac{n}{2} 次加入可以糟蹋 2 个人，后 \dfrac{n}{2} 次加入就糟蹋不了人。

对于奇环，如果长度为 n，在前 \dfrac{n-1}{2} 次加入可以糟蹋 2 个人，中间一次加入可以糟蹋 1 个人，后 \dfrac{n-1}{2} 次加入可以加入 0。

直接贪心选最大的。

#include<bits/stdc++.h>
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=1e6+10;
int n,k,p[MAXN],vis[MAXN],cnt[MAXN];
vector<int> len;
bitset<MAXN> dp;
int main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>k;
    ffor(i,1,n) cin>>p[i];
    ffor(i,1,n) if(!vis[i]) {
        int tlen=1,u=p[i];
        while(u!=i) ++tlen,vis[u]=1,u=p[u];
        vis[i]=1,len.push_back(tlen);
    }
    dp[0]=1;
    for(auto id:len) if(id<=100) cnt[id]++;
    else dp|=(dp<<id);
    ffor(i,1,100) {
        ffor(mod,0,i-1) {
            int lst=-0x3f3f3f3f;
            for(int j=mod;j<=n;j+=i) {
                if(dp[j]) lst=j;
                else if((j-lst)<=cnt[i]*i) dp[j]=1;
            }
        }
    }
    if(dp[k]) cout<<k<<' ';
    else cout<<k+1<<' ';
    vector<int> del;
    for(auto id:len) {
        if(id%2==0) ffor(i,1,id/2) del.push_back(0),del.push_back(2);
        else {
            del.push_back(1);
            ffor(i,1,id/2) del.push_back(0),del.push_back(2);
        }
    }
    sort(del.begin(),del.end());
    int sum=0;
    ffor(i,0,k-1) sum+=del[n-1-i];
    cout<<sum;
    return 0;
}