元素选择题解
sbno333
·
·
题解
Subtask 1
暴搜。
Subtask 2
设 dp_i 表示 n=i 时需要操作的次数，然后枚举 j，判断能否从 j 转移到 i，判断方法就是每个盒子最多放 j 个小球，那么就是需要 \lfloor\frac{i}{j}\rfloor\times (i\bmod j)+\frac{\lfloor\frac{i}{j}\rfloor\times(\lfloor\frac{i}{j}\rfloor-1)}{2}\times j\le k 是否成立，并且需要满足 j\times m\ge i，暴力转移即可。
Subtask 3
注意到可以二分，复杂度 O(n\log n)。
Subtask 4
注意到可以双指针，复杂度 O(n)。
Subtask 5
## Subtask 6
我们不妨换个方向思考，设 $g_i$ 表示进行 $i$ 此操作，最多能处理的 $n$，每次 $g_i$ 由 $g_{i-1}$ 为基准，向上面一样二分答案得到。
注意到当 $n\le k$ 时，每次膨胀必然膨胀两倍以上（因为可以构造 $g_{i+1}=2g_i$，此时 $g_i$ 个放在 $0$ 号盒子，剩下的放在 $1$ 号盒子，答案一定不劣于这个，即 $g_{i+1}\ge2g_i$）。
然后复杂度就是 $O(\log^2 n)$，如果有较好的推式子能力或许可以 $O(\log n)$。
## Subtask 7
留给复杂度比较神秘的人，或者挂分的。
## Subtask 8
在当 $g_i\ge k$ 时，我们发现有 $g_{i+1}=g_i+k$，简单数学，可以让这部分做到 $O(1)$，最终复杂度为 $O(T\log^2 n)$，最快能做到 $O(T\log n)$，如果你比这个还快，欢迎私信。
```cpp
#include<bits/stdc++.h>
#define int __int128
using namespace std;
void _main(){
long long c1,c2,c3;
int n,m,k;
cin>>c1>>c2>>c3;
n=c1,m=c2,k=c3;
if(n==1){
cout<<0<<endl;
return;
}
if(m==1){
cout<<-1<<endl;
return;
}
int p;
p=1;
int ans;
ans=0;
while(p<n&&p<k){
ans++;
int l,r;
l=p,r=min(p*m,n);
while(l<r){
int mid;
mid=l+r+1;
mid>>=1;
int z;
z=mid/p;
int g;
g=mid%p;
if(z*g+z*(z-1)/2*p<=k){
l=mid;
}else{
r=mid-1;
}
}
p=l;
}
if(p>=n){
cout<<(long long)ans<<endl;
return;
}
ans+=(n-p+k-1)/k;
cout<<(long long)ans<<endl;
}
signed main(){
long long t;
cin>>t;
while(t--){
_main();
}
return 0;
}
```