CF每日4题

1500左右的做到还是有点吃力

2093E 1500 二分答案

题意：给定一个长度为 n 的数组，现在要把它切成 k 份，求每一份最小的MEX中的最大值。

• 就是找最大值，但是这个值是所有段最小的值
• 采用二分答案，二分这个值，check这个值是否是分成k段最小的

二分查找扫盲
因为尽量找最大值 向右查找 使用上文章中模板二

while (l < r)
{int mid = l + r + 1 >> 1;	//(l+r+1)/2if (check(mid))  l = mid;else r = mid - 1;
}

答案在l中

const int N=2e5+10;
int n,k;
int a[N];
bool check(int mx){set<int>vis;int cnt=0;forr(i,1,n){if(a[i]<mx)vis.insert(a[i]);if(vis.size()==mx){cnt++;vis.clear();}}return cnt>=k;//分的组数大，说明mx较小，选择右区间
}
void solve(){cin>>n>>k;forr(i,1,n){cin>>a[i];}int l=0,r=n;while (l<r){int mid=(l+r+1)>>1;if(check(mid)){l=mid;}else r=mid-1;}cout<<l<<endl;
}

2093D 1400 分治

参考文章

• 题意：正方形格子边长$2^n$，从大到小按${}_3^1$${}_2^4$的形式填格子
• 对每个大格子分成四份进行处理（每条边进行分治） 维护每份格子的左上角坐标，区间值
  

const int N=60;
int tp[N+3];
void q1(int x,int y,int len,int mn,int mx){if(len==1)return cout<<mn<<endl,void();int rg=mx-mn+1;//方块的区间if(x<=len/2&&y<=len/2){//1q1(x,y,len/2,mn,mn+rg/4-1);}if(x>len/2&&y>len/2){//2q1(x-len/2,y-len/2,len/2,mn+rg/4,mn+rg/2-1);}if(x>len/2&&y<=len/2){//3q1(x-len/2,y,len/2,mn+rg/2,mn+rg/4*3-1);}if(x<=len/2&&y>len/2){//4q1(x,y-len/2,len/2,mn+rg/4*3,mx);}
}
void q2(int x,int y,int d,int len,int mn,int mx){// cout<<x<<' '<<y<<' '<<mn<<' '<<mx<<endl;if(len==1)return cout<<x<<' '<<y<<endl,void();int rg=mx-mn+1;//不用mx/4确定区间  使用最大值最小值距离去规定区间if(d<=mn+rg/4-1){//1  q2(x,y,d,len/2,mn,mn+rg/4-1);}else if(d<=mn+rg/2-1){//2q2(x+len/2,y+len/2,d,len/2,mn+rg/4,mn+rg/2-1);}else if(d<=mn+rg/4*3-1){//3q2(x+len/2,y,d,len/2,mn+rg/2,mn+rg/4*3-1);}else if(d<=mx){//4q2(x,y+len/2,d,len/2,mn+rg/4*3,mx);}
}
void solve(){int n,q;cin>>n>>q;forr(i,1,q){char c1,c2;cin>>c1>>c2;if(c1=='-'){int x,y;cin>>x>>y;q1(x,y,tp[n],1,tp[n*2]);}else {int d;cin>>d;q2(1,1,d,tp[n],1,tp[2*n]);}}
}
signed main()
{ios::sync_with_stdio(false), std::cin.tie(nullptr), std::cout.tie(nullptr);int _ ;_ = 1;tp[0]=1;forr(i,1,N){tp[i]=tp[i-1]*2;// tp[i]=(1<<i);cout<<tp[i]<<endl;}cin>>_;while (_--){solve();}return 0;
}

2092C 1200 思维 贪心

• 选两个数$a,b$，一奇一偶，一个+1一个-1，最后两数仍是一奇一偶，可以重复操作直至$a+b,0$或$a+b-1,1$
• 奇+偶=奇 最后答案一定是个奇数，对原数列分奇偶
• 答案最优情况
  • 所有偶数都放入一个奇数中
  • 其他的奇数化成$a+b-1,1$，放到偶数中，加入那个最大的奇数

void solve(){int n,ans=0,fg=0;cin>>n;vector<int>o,e;forr(i,1,n){int a;cin>>a;if(a&1)o.push_back(a);else e.push_back(a);}sort(o.begin(),o.end());sort(e.begin(),e.end());int lo=o.size(),le=e.size();if(lo&&le){for(auto i:e)ans+=i;    forr(i,0,lo-2){ans+=o[i]-1;}ans+=o[lo-1];}else if(!lo){ans=e[le-1];}else if(!le){ans=o[lo-1];}cout<<ans<<endl;
}

2091D 1200 水 模拟

void solve(){int n,m,k;cin>>n>>m>>k;int a=(k+n-1)/n;//每行最大桌子数int ad=max(2*a-1-m,0ll);//少的空格数int cnt=a-ad;//段数int ans=(a+cnt-1)/cnt;// cout<<a<<' '<<ad<<' ';cout<<ans<<endl;
}