题解归档 - cf755F

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf755F
• 本地来源：problems/cf755F/idea.md
• 题目链接：https://codeforces.com/contest/755/problem/F
• 原始标题：CF755F PolandBall and Gifts

思路

CF755F PolandBall and Gifts

题意

n 个人按置换 p 互送礼物（p_i != i）。恰有 k 人忘记带礼物。i 收到礼物当且仅当：

1. i 本人带了要送出的礼物；
2. 满足 p_x = i 的 x 也带了礼物。

求收不到礼物人数的最小值与最大值。

模型

置换分解为若干环，长度记为 L_1, L_2, ...。

i 收不到 ⟺ i 忘记 或 inv[i] 忘记（前驱没带）。

最大值

在长度为 L 的环上放 t 个忘记，最多 min(L, 2t) 人收不到（尽量把忘记点散开，每个覆盖自己与前驱的后继）。

全局：先对每个环取 floor(L/2) 个「+2 槽」，奇数长度环还有一个「+1 槽」，按 k 贪心分配；饱和后答案为 n。

最小值

收不到人数至少为 k（忘记者本人必收不到）。

若能把 k 写成若干整环长度之和，则只让对应整环全部忘记，收不到恰为 k。

否则必须在某个环上只忘记部分点，最优为连续块，收不到 t+1，全局最小为 k+1。

等价：对每种环长做多重背包，判断 k 是否可表示为环长之和；可则 k，否则 k+1。

实现

• 扫置换得环长；
• bitset 多重背包判 dp[k]；
• 最大值按 2-槽 / 1-槽 公式 O(n)。

复杂度

时间 O(n + n/64)，空间 O(n)。

样例

n=5, k=2, p=[3,4,1,5,2]：环 (1,3) 与 (2,4,5)。最小整环 2 → 2；最大各环散放一个忘记 → 4。

结论

AC 代码见 solution.cpp。

代码

来源：problems/cf755F/solution.cpp

/* Author: likely
 * Time: 2026-06-08 04:00:45
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=1000005;
const ll maxk=1000005;
ll p[maxn+5],vis[maxn+5],n,k,i,j,zc,cur,leftt,odd,ans1,ans2;
vector<ll>cyc,val,len,cnt;
bitset<maxk>dp;
int main(){
    cin>>n>>k;
    for(i=1;i<=n;i++) cin>>p[i];
    for(i=1;i<=n;i++){
        if(vis[i]) continue;
        cur=0;
        zc=i;
        while(!vis[zc]){
            vis[zc]=1;
            cur++;
            zc=p[zc];
        }
        cyc.push_back(cur);
    }
    val=cyc;
    sort(val.begin(),val.end(),greater<ll>());
    leftt=k;
    odd=0;
    ans2=0;
    for(i=0;i<(ll)val.size();i++){
        zc=min(val[i]/2,leftt);
        ans2+=zc*2;
        leftt-=zc;
        if(val[i]&1) odd++;
    }
    ans2+=min(leftt,odd);
    dp[0]=1;
    sort(cyc.begin(),cyc.end());
    for(i=0;i<(ll)cyc.size();i++){
        if(i==0 or cyc[i]!=cyc[i-1]){
            len.push_back(cyc[i]);
            cnt.push_back(1);
        }else cnt.back()++;
    }
    for(i=0;i<(ll)len.size();i++){
        cur=cnt[i];
        for(j=1;cur>0;j<<=1){
            zc=min(cur,j);
            dp|=(dp<<(len[i]*zc));
            cur-=zc;
        }
    }
    ans1=k;
    if(k>0 and !dp[k]) ans1++;
    cout<<ans1<<" "<<ans2<<"\n";
    return 0;
}