题解：CF755F PolandBall and Gifts
未来姚班zyl
·
·
题解
题解区的复杂度分析都好奇怪啊，来个正确的复杂度分析！
题目大意
题目翻译已经足够清晰了。
题目分析
首先，建边 i\rightarrow p_i，则每个点的出度、入度都为 1，故图由若干个环组成。
首先考虑第一问：求花费 k 得到最大的贡献。
显然，对于长度为 len 的环，可以花费 i\le \lfloor\frac{len}{2}\rfloor 的代价，获得 2i 的贡献，如果 len 是奇数，还可以在此基础上再花费 1 的代价，获得 1 的贡献。直接贪心即可，复杂度 O(n)。
然后就是第二问：花费 k 能得到的最小代价。
对于长度为 len 的环，第一次花费 1 一定会产生 2 的代价。然后第 2\sim len-1 次花费会产生 1 的代价，第 len 次产生 0 的代价。
所以如果能用若干个环恰好拼出 k 答案就是 k，否则是 k+1。
问题变为 len_i 能否拼出 k，典型的背包问题。
采用二进制分组，对于种类数 $x$，最坏的情况下数量平均，二进制分组后物品数量应为 $O(x\log\frac{n}{x^2})$，我在 geogebra 上输入该函数并发现最差复杂度应为 $O(\sqrt n)$，至少在 $n\le 10^6$ 时这个结论是正确的，欢迎数学大佬来证明或指错。
所以再使用 bitset 背包，复杂度 $O(\frac{n\sqrt n}{w})$。
题解那些不认真分析复杂度的都能有高赞？
```cpp
#include<bits/stdc++.h>
#define rep(x,y,z) for(int x=(y);x<=(z);x++)
#define per(x,y,z) for(int x=(y);x>=(z);x--)
#define repn(x) rep(x,1,n)
#define repm(x) rep(x,1,m)
inline int read(){int s=0,w=1;char c=getchar();while(c<48||c>57) {if(c=='-') w=-1;c=getchar();}while(c>=48&&c<=57)s=(s<<1)+(s<<3)+c-48,c=getchar();return s*w;}
using namespace std;
const int N =1e6+5;
int a[N],n,k,m,p[N];
bool v[N];
inline void dfs(int x,int &w){
w++,v[x]=1;
if(!v[p[x]])dfs(p[x],w);
}
inline int solve1(int k){
int ans=0;
repm(i){
int w=a[i]/2;
ans+=min(w,k)*2,k-=min(w,k);
if(!k)return ans;
}
repm(i)if(a[i]&1){
k--,ans++;
if(!k)return ans;
}
return ans;
}
int c[N];
bitset<500001>B;
inline int solve2(int k){
int pr=k;
k=min(k,n-k),B[0]=1;
repm(i)c[a[i]]++;
rep(i,1,k)if(c[i]){
int kk=1,w=i;
while(1){
if(c[i]>=kk)B=B|(B<<w),c[i]-=kk;
else {
B=B|(B<<(c[i]*i));
break;
}
kk<<=1,w<<=1;
}
}
return pr+(!B[k]);
}
int main(){
n=read(),k=read();
repn(i)p[i]=read();
repn(i)if(!v[i])dfs(i,a[++m]);
cout <<solve2(k)<<" "<<solve1(k)<<'\n';
return 0;
}
```