【题解】[CF1753E] N Machines
william555
·
·
题解
场上口胡了，但是只剩 20 分钟了，最后没写完……
看一下题目中初始结果不超过 $2\times 10^9$ 的限制，很明显乘法操作就很少了。考虑对于操作序列，将乘法放在前面，加法放在后面所得结果最小，但是最后结果也肯定不小于乘法操作的 $a_i$ 之积。所以 $a_i>1$ 的乘法操作最多也就 $\log_2 2\times 10^9 = 31$ 次。
考虑修改的策略，肯定是将一些乘法操作移到末尾，一些加法操作移到开头。
于是可以写出暴力：枚举将哪些乘法操作移到末尾，然后对于所有加法操作，算出将其移到开头的价值，选出最大的若干个。考虑到乘法操作有 $O(\log A)$ 个，加法操作有 $O(n)$ 个，最后复杂度就为 $O(An)$。显然跑不过……
于是发掘性质：
1. 对于 $a_i$ 相同的乘法操作，肯定选前面的进行操作。证明：对于 $a_i$ 相同的操作，选前面的能够影响到更多的加法操作，一定不劣。
2. 对于所有加法操作，按其在第几个乘法之后分段，每一段肯定会选 $a_i$ 大的。证明：对于加法操作将其放在开头之后带来的贡献均可以表示为：$X\times a_i$，其中 $X$ 之与当前操作在第几段有关，所以对于每一段，肯定要选 $a_i$ 大的。
性质 1 直接让爆搜的状态数变得很少，貌似不会超过 $2^{11}$。
爆搜出哪些乘法被放在末尾以后，再根据性质 2 来快速求出加法操作的贡献：将每一段的 $a_i$ 排序，假设当前还可以移动 $k$ 个加法操作，二分这 $k$ 次操作做出的最小贡献 $mid$，然后对于每一段，二分出贡献不小于 $mid$ 的有多少个 $a_i$，然后看可选的位置数量 $cnt$ 是否不小于 $mid$ 来完成二分。
然后需要维护每一段排序后 $a_i$ 的前缀和来统计答案。
总时间复杂度 $O(2^{11} \times \log_n^2)$。
```c++
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int in(){
int x;
scanf("%d",&x);
return x;
}
const int N=1e6+5;
int n,m,o,A,B,C,all;
int a[N],b[N];
map<int,int> id;
vector<int> v1[100],v2[100];
vector<ll> s[100];
int mark[N];
int cnt;ll sum,ans;
void check(ll X){
ll now=all;
cnt=sum=0;
for(int i=0;i<=m;i++){
if(i&&!mark[i])now/=b[i];
if(all==now)continue;
int l=0,r=v2[i].size()-1,mid;
while(l<=r){
mid=l+r>>1;
if(1ll*v2[i][mid]*(all-now)>=X)l=mid+1;
else r=mid-1;
}
cnt+=l;if(l>0)sum+=s[i][l-1]*(all-now);
}
}
void calc(int D){
ll l=0,r=1e18,mid,res;
D/=A;
int now=all;res=all;
for(int i=0;i<=m;i++){
if(i&&!mark[i])now/=b[i];
if(s[i].size()){
res+=s[i].back()*now;
}
}
while(l<=r){
mid=l+r>>1;
check(mid);
if(cnt<=D)r=mid-1;
else l=mid+1;
}
check(r);
res+=sum-max(0,cnt-D)*r;
ans=max(ans,res);
}
void dfs(int x,int y){
if(1ll*y*B>C)return;
if(x==o+1){
calc(C-y*B);
return;
}
dfs(x+1,y);
for(int p:v1[x]){
y++;
mark[p]=1;
dfs(x+1,y);
}
for(int p:v1[x])mark[p]=0;
}
int main(){
n=in(),C=in(),A=in(),B=in();
ans=1,all=1;
for(int i=1;i<=n;i++){
char op=getchar();
while(op!='*'&&op!='+')op=getchar();
scanf("%d",&a[i]);
if(op=='*'){
if(a[i]>1){
ans*=a[i];
if(!id[a[i]])id[a[i]]=++o;
m++;b[m]=a[i];all*=b[m];
v1[id[a[i]]].push_back(m);
}
}else ans+=a[i],v2[m].push_back(a[i]);
}
for(int i=0;i<=m;i++){
sort(v2[i].begin(),v2[i].end(),greater<int>());
s[i]=vector<ll>(v2[i].size(),0);
for(int j=0;j<s[i].size();j++){
s[i][j]=v2[i][j];
if(j)s[i][j]+=s[i][j-1];
}
}
dfs(1,0);
cout<<ans<<endl;
return 0;
}
```