最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

当前速读：CF1753EF

来源：博客园

E. N Machines

题意：有 \(n\) 个操作 \((+/*,a_i)\)，有 \(S\) 块钱，可以花 \(a\) 把一个 \(+\) 或 \(b\) 把 \(*\) 挪动。求最大值。

题解：这个题有两个关键点我没有想到。其一是枚举挪动哪些乘法的复杂度并不大；其二是枚举乘法后不用每个枚举加法。

只有 \(\log\) 个乘法。考虑枚举集合，注意到如果若有两个乘法 \(x,y\)，\(x


(相关资料图)

故对于每一个数值，只会取一个前缀（此处减弱了结论）。故方案数不会太大，具体来讲是五千。

考虑枚举了一个乘法集合之后，若还能选 \(k\) 个加法，我们需要找出变化量最大的 \(k\) 个来。我们可以二分这个 \(k\) 大值。

注意到若两个加法之间没有乘法，则他们的位置关系是不重要的。所以可以把所有加法分成 \(\log\) 类。

时间复杂度 \(O(n\log n+5000\log^2 V\log n)\)。

点击查看代码
#includeusing namespace std;const int maxn=1e6+10;const int mod=1e9+7;#define inf 1e9#define ll long long#define pb push_backinline 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;vectorSum[L];int n,top,M[L],S,a,b,len[L],all;ll mul=1,ans=0;vectorA[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，经典对值域分块。

点击查看代码
#includeusing namespace std;const int maxn=1e6+10;const int mod=1e9+7;#define inf 1e9inline 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>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]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)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)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;}

关键词： 点击查看 我们需要 位置关系