E. N Machines
题意：有 \(n\) 个操作 \((+/*,a_i)\)，有 \(S\) 块钱，可以花 \(a\) 把一个 \(+\) 或 \(b\) 把 \(*\) 挪动。求最大值。
题解：这个题有两个关键点我没有想到。其一是枚举挪动哪些乘法的复杂度并不大；其二是枚举乘法后不用每个枚举加法。
只有 \(\log\) 个乘法。考虑枚举集合，注意到如果若有两个乘法 \(x,y\)，\(x<y,a_x\geqslant a_y\) 且 \(x\) 没取而 \(y\) 取了，则取 \(x\) 更优。
故对于每一个数值，只会取一个前缀（此处减弱了结论）。故方案数不会太大，具体来讲是五千。
考虑枚举了一个乘法集合之后，若还能选 \(k\) 个加法，我们需要找出变化量最大的 \(k\) 个来。我们可以二分这个 \(k\) 大值。
注意到若两个加法之间没有乘法，则他们的位置关系是不重要的。所以可以把所有加法分成 \(\log\) 类。
时间复杂度 \(O(n\log n+5000\log^2 V\log n)\)。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
const int mod=1e9+7;
#define inf 1e9
#define ll long long
#define pb push_back
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
const int L=35;vector<ll>Sum[L];
int n,top,M[L],S,a,b,len[L],all;ll mul=1,ans=0;
vector<int>A[L];int vis[L];ll k[L],sum[L];
inline void dfs(int pos,int lim){
if(pos==top+1){
int cnt=0;ll bas=0;
for(int i=1;i<=top;i++)cnt+=vis[i];
if(cnt>S/b)return;
// for(int i=1;i<=top;i++)printf("%d ",vis[i]);puts("");
cnt=(S-cnt*b)/a;k[0]=mul;
cnt=min(cnt,all);
for(int i=1;i<=top;i++){
k[i]=k[i-1];
if(!vis[i])k[i]/=M[i];
bas+=sum[i]*k[i];
// printf("%lld ",k[i]);
}ll l=0,r=4e18,res=0;
// printf("\ncnt=%d bas=%lld\n",cnt,bas);
while(l<=r){
ll mid=(l+r)>>1;int Cnt=0;
// printf("mid=%lld\n",mid);
for(int i=1;i<=top;i++){
int ql=0,qr=len[i]-1,pos=-1;
while(ql<=qr){
int Mid=(ql+qr)>>1;
if(A[i][Mid]*(mul-k[i])>=mid)pos=Mid,ql=Mid+1;
else qr=Mid-1;
}Cnt+=pos+1;
// printf("i=%d pos=%d\n",i,pos+1);
}if(Cnt>=cnt)res=mid,l=mid+1;
else r=mid-1;
}int Cnt=0;ll Ans=0;
// printf("res=%lld\n",res);
for(int i=1;i<=top;i++){
int ql=0,qr=len[i]-1,pos=-1;
while(ql<=qr){
int Mid=(ql+qr)>>1;
if(A[i][Mid]*(mul-k[i])>=res)pos=Mid,ql=Mid+1;
else qr=Mid-1;
}Cnt+=pos+1;
if(pos!=-1)Ans+=(mul-k[i])*Sum[i][pos];
}ans=max(ans,bas+Ans-res*(Cnt-cnt));return;
}dfs(pos+1,max(lim,M[pos]));
if(M[pos]>lim)vis[pos]=1,dfs(pos+1,lim),vis[pos]=0;
}
int main(){
n=read(),S=read(),a=read(),b=read();
char opt;int x;
for(int i=1;i<=n;i++){
opt=getchar();x=read();
if(opt=='*'){
if(x==1)continue;
M[++top]=x;mul*=x;
}else A[top].pb(x);
}for(int i=0;i<=top;i++){
sort(A[i].begin(),A[i].end());
reverse(A[i].begin(),A[i].end());
for(auto x:A[i])sum[i]+=x,Sum[i].pb(sum[i]);
len[i]=A[i].size(),all+=len[i];
}dfs(1,0);printf("%lld\n",ans+mul+sum[0]*mul);
return 0;
}
F. Minecraft Series
题意：给定一个 \(n\times m\) 的网格和其上若干有值的点，求有多少个子正方形负数的 mex 加正数的 mex 不小于一个定值。
题解：我首先考虑的是枚举正方形的边长，只有根号种，然后每个点可以贡献到一个矩形，但是不会做矩形加单点求 mex。
有很多性质没有利用到。比如如果一个正方形已经可以了，那么包含它的正方形也一定可以。
考虑枚举对角线，双指针，就是找到最近的右下端点满足，就用到了上面的性质。
注意到此时每个点也只会加入根号次（若一条对角线会取到这个点，那么这个点对称过去还在形内，故这条对角线与过此点的反对角线有交）。
此时我们只需维护一个数据结构，支持 \(O(1)\) 插入删除，\(O(\sqrt k)\) 查询 mex，经典对值域分块。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
const int mod=1e9+7;
#define inf 1e9
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
const int B=1e3;
int n,m,k,T,az[maxn],af[maxn],sz[maxn],sf[maxn];
vector<vector<int>>A[40005];long long ans;
inline void add(int x){
if(x>0)++az[x],sz[x/B]+=(az[x]==1);
else x=-x,++af[x],sf[x/B]+=(af[x]==1);
}
inline void del(int x){
if(x>0)--az[x],sz[x/B]-=(az[x]==0);
else x=-x,--af[x],sf[x/B]-=(af[x]==0);
}
inline int qmex(){
int mz=0,mf=0;
for(int i=0;;++i)if(sz[i]<B){
for(int j=i*B;;j++)if(!az[j]){mz=j;break;}
break;
}for(int i=0;;++i)if(sf[i]<B){
for(int j=i*B;;j++)if(!af[j]){mf=j;break;}
break;
}return mz+mf-1;
}
inline void Add(int x,int y){for(auto t:A[x][y])add(t);}
inline void Del(int x,int y){for(auto t:A[x][y])del(t);}
int main(){
n=read(),m=read(),k=read(),T=read();
for(int i=1;i<=n;i++)A[i].resize(m+2);
for(int i=1,x,y,z;i<=k;i++){
x=read(),y=read(),z=read();
if(!z||abs(z)>k)continue;
A[x][y].push_back(z);
}++sz[0],++sf[0],++az[0],++af[0];
for(int i=1;i<=m;i++){
int x=1,y=i,X=1,Y=i;Add(x,y);
for(;x<=n&&y<=m;++x,++y){
while(qmex()<T&&X<n&&Y<m){
++X,++Y;
for(int j=x;j<=X;j++)Add(j,Y);
for(int j=y;j<Y;j++)Add(X,j);
}if(qmex()>=T)ans+=min(n-X+1,m-Y+1);
for(int j=x;j<=X;j++)Del(j,y);
for(int j=y+1;j<=Y;j++)Del(x,j);
}
}for(int i=2;i<=n;i++){
int x=i,y=1,X=i,Y=1;Add(x,y);
for(;x<=n&&y<=m;++x,++y){
while(qmex()<T&&X<n&&Y<m){
++X,++Y;
for(int j=x;j<=X;j++)Add(j,Y);
for(int j=y;j<Y;j++)Add(X,j);
}if(qmex()>=T)ans+=min(n-X+1,m-Y+1);
for(int j=x;j<=X;j++)Del(j,y);
for(int j=y+1;j<=Y;j++)Del(x,j);
}
}printf("%lld\n",ans);
return 0;
}