CF755F
lsj2009
·
·
题解
不是，哥们，这题解区在说啥啊？？
Description
给定一个排列 \{p_n\} 和正整数 k，我们定义一个 01 序列 \{c_n\} 的代价是 \sum\limits_{i=1}^n c_i c_{p_i^{-1}}；称其是好的当且仅当 \sum\limits_{i=1}^n c_i=k。
求出所有好的 01 序列中代价的最小值/最大值。
## Solution
请注意：我这里的 $k$ 实际上是原题的 $n-k$（同样的，对于答案也取反了），但我觉得原题太反人类了，所以改成这样子了。
排列问题，套路地建出置换环。
**先来考虑最小值：**
对于一个环，我们贪心地想，肯定是我们尽可能地不相邻地选，那么在不相邻的前提条件下肯定是隔一个。
这样子我们就可以在花费 $0$ 的代价下填完 $x=\sum\limits_{i=1}^m \lfloor \frac{len_i}{2}\rfloor$ 个位置。
如果 $k>x$，也就是需要选的位置还有多余，我们就要花费额外代价了。
注意到奇数长度的环和偶数长度的环是不同的：
- 具体地说，奇数长度的环有一个地方会留下长度为 $2$ 的空缺，我们往那个地方里选一个，就只会花费 $1$ 的代价。
- 而操作之后，奇数长度的环的情况就和偶数长度环同理了（可以视作将两个相邻的选的位置合并在一起看）。
- 而对于偶数长度的环，那就是我随便选一个没有被选过的位置，我都会花费 $2$ 的代价（他本身和他的后继节点）。
则我记 $y=\sum\limits_{i=1}^m (len_i\bmod{2})$，我选这些就只要花费 $1$ 的代价。
如果还有剩余（$k>x+y$），那我就需要花费 $2$ 的代价了。
这样子我们就解决了最小值部分，复杂度线性。
**再来考虑最大值：**
这部分就恰恰相反，我们肯定是要尽可能贴近地选，那么对于一个环，我们要不全部选，要么可能会选他的一个连续的部分。
对于前者，选一个长度为 $x$ 的环，我们会获得 $x$ 的贡献；而选择一个长度为 $x$ 的链，我们却只会获得 $x-1$ 的贡献（因为首端是不符合要求的）。
那么也就是，我们肯定还是尽可能地选完整的环，我最多只可能选一条链。
那么现在问题就变成了：我是否可以选出若干个环，使得其环长和为 $k$，如果可以，则答案为 $k$，否则为 $k-1$。
这就是一个 $01$ 背包的可达性 dp 问题，我们直接做是 $\mathcal{O}(n^2)$ 的，使用 ``bitset`` 可以优化到 $\mathcal{O}(\frac{n^2}{w})$，但是还是无法通过。
考虑优化：注意到我们有 $\sum\limits_{i=1}^m len_i=n$；记 $t$ 为不同的环长个数，则我们有 $t=\mathcal{O}(\sqrt{n})$。这个显然，因为卡满时是 $len=1,2,\cdots$，根据高斯求和，和是 $\mathcal{O}(t^2)$ 的，所以 $t$ 是 $\mathcal{O}(\sqrt{n})$ 的。
则我们考虑将环长相同的丢到一起处理，就变成了一个多重背包的问题，这时候考虑二进制分组优化再转成 $01$ 背包，看起来我们就得到了一个 $\mathcal{O}(\frac{n\sqrt{n}\log{n}}{w})$ 的做法，但是实际上我们可以说明他是 $\mathcal{O}(\frac{n\sqrt{n}}{w})$ 的：
- 对于二进制分组的前半部分（即拆分成 $2$ 的幂次），我们考虑一个 $2$ 的幂次 $2^k$ 取乘上一个长度 $w_i$，关于他拆分得到的数 $w_i$ 的集合为 $S_k$，则 $\sum\limits_{x\in S_k} x\le \frac{n}{2^k}$，则 $|S_k|=\mathcal{O}(\sqrt{\frac{n}{2^k}})$。
- 对于所有 $|S_k|$ 求和得到：$\sum\limits_{k\ge 0} |S_k|=\mathcal{O}(\sum\limits_{k\ge 0} \sqrt{\frac{n}{2^k}})=\mathcal{O}(\sqrt{n}\sum\limits_{k\ge 0} \sqrt{\frac{1}{2^k}})=\mathcal{O}(\sqrt{n})$。
- 对于二进制分组的后半部分（即遗留下来的数），同一种长度只会遗留下一个剩余个数，而一共有 $\mathcal{O}(\sqrt{n})$ 种环长，所以我们会得到 $\mathcal{O}(\sqrt{n})$ 个数。
所以我们只会对 $\mathcal{O}(\sqrt{n})$ 个数做 $01$ 背包，故复杂度是 $\mathcal{O}(\frac{n\sqrt{n}}{w})$ 的。
这样子就可以通过此题。
## Code
```cpp
#include<bits/stdc++.h>
//#pragma GCC optimize(3,"Ofast","inline")
//#define int long long
#define i128 __int128
#define ll long long
#define ull unsigned long long
#define ld double
#define PII pair<int,int>
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define rep(k,l,r) for(int k=l;k<=r;++k)
#define per(k,r,l) for(int k=r;k>=l;--k)
#define cl(f,x) memset(f,x,sizeof(f))
#define pcnt(x) __builtin_popcount(x)
using namespace std;
void file_IO() {
freopen(".in","r",stdin);
freopen(".out","w",stdout);
}
bool M1;
const int N=1e6+5;
int p[N],cnt[N],len,n,k;
bitset<N> f;
bool used[N];
void dfs(int u) {
if(used[u])
return;
++len;
used[u]=true;
dfs(p[u]);
}
int solve1(int k) {
int c=0;
rep(i,1,n) {
k-=(i>>1)*cnt[i];
c+=(i&1)*cnt[i];
}
if(k<=c)
return max(k,0);
else
return c+(k-c)*2;
}
int solve2(int k) {
f[0]=1;
rep(i,1,n) {
int base=1,t=cnt[i];
while(base<=t) {
f|=f<<(i*base);
t-=base;
base<<=1;
}
if(t)
f|=f<<(i*t);
}
return f[k]? k:k-1;
}
void solve() {
scanf("%d%d",&n,&k);
k=n-k;
rep(i,1,n)
scanf("%d",&p[i]);
rep(i,1,n) {
if(!used[i]) {
len=0;
dfs(i);
++cnt[len];
}
}
printf("%d %d\n",n-solve2(k),n-solve1(k));
}
bool M2;
signed main() {
//file_IO();
int testcase=1;
//scanf("%d",&testcase);
while(testcase--)
solve();
cerr<<"used time = "<<1000*clock()/CLOCKS_PER_SEC<<"ms\n";
cerr<<"used memory = "<<(&M1-&M2)/1024/1024<<"MB\n";
return 0;
}
```