当前位置: 首页 > news >正文

ACL 第一周模拟赛题解

T1 密码

原题链接

直接枚举修改区间暴力判断是 \(O(n^2)\)

原串很长,但修改操作是将区间变为其区间和,而对于 \(1e5\) 个数字,即使全取 \(9\),其和也不超过 \(6\) 位。

这启示我们在目标串上固定左端点,枚举最多长度为 \(6\) 的区间,表示为“期望通过修改得到的串”,保证两串的前缀与后缀相等时,判断原串中间部分的区间和是否与枚举得到的值相等即可,数据保证有解,放心大胆做即可。

点击查看代码
const int N=1e5+5;
string s,t,p;
int sums[N],a[N],n,R,m;
void xpigeon(){s=" ";cin>>t;n=t.size();s+=t;cin>>p;m=p.size();t=" ";t+=p;for(int i=1;i<=n;i++){a[i]=s[i]-'0';}for(int i=1;i<=n;i++){sums[i]=a[i]+sums[i-1];}while(s[n-R]==t[m-R]) R++;for(int l=1;l<=m && s[l-1]==t[l-1];l++){int tmp=0;for(int r=l;r<=min(m,l+6);r++){if(r>l && tmp==0) break;//前导0tmp=tmp*10+t[r]-'0';if (m-r<=R&& sums[n-m+r]==sums[l-1]+tmp){cout<<l<<" "<<n-m+r<<'\n';return ;}}}
}

T2 艺术家

原题链接
甚至是 STL 好题(?

从集合的角度去考虑,所有人一开始在同一个集合,每次操作相当于分裂,当集合大小为 \(1\) 时,一个艺术家唯一确定,但细想这种做法问题很多且无法解决,首先每次操作的艺术家有重叠,而且分裂的操作也并非好维护,我们把这个角度弃掉。

从出演状态的角度去考虑,一个艺术家能被确定,其演出安排须是所有人中唯一的,因为只有一件作品按照该方案演出,自然就对应得上了。

我们尝试用 \(01\) 串哈希的方式维护每个艺术家的出演状态,\(1\) 为出演,\(0\) 为没有,可以开一个 \(map\) 维护每一种哈希值对应的集合大小,每次操作时先删去原来的哈希,修改后再加入 \(map\),每一次操作过后统一判断这些哈希中集合大小为 \(1\) 的艺术家都有哪些。要注意修改一次哈希可能使得原来不唯一的哈希值变得唯一。

点击查看代码
const int N=1e5+5;
const ull base=2333;
int n,m,ans[N];
ull ha[N];
map<int,set<ull>>mp;
vector<int> to;
void xpigeon(){rd(n,m);memset(ans,0x3f,sizeof(ans));for(int i=1;i<=n;i++){mp[0].insert(i);}ull pw=1;for(int i=1,k;i<=m;i++){pw*=base;rd(k);to.clear();for(int j=1,a;j<=k;j++){rd(a);mp[ha[a]].erase(a);to.pb(ha[a]);ha[a]+=pw;mp[ha[a]].insert(a);to.pb(ha[a]);}for(auto x:to){if(mp[x].size()!=1) continue;auto it=*mp[x].begin();ans[it]=min(ans[it],i);mp[x].erase(it);}}for(int i=1;i<=n;i++){if(ans[i]==0x3f3f3f3f3f3f3f3f) cout<<0<<" ";else cout<<ans[i]<<" ";}
}

T3 度假

原题链接

若最终所有人同时覆盖的区间长度为 \(len\),显然长度越短越容易达成,我们考虑二分答案。

问题来到如何在固定的区间长度下寻找应该被覆盖的对应区间,设函数 \(f(x)\) 表示覆盖以 \(x\) 为左端点长度为 \(len\) 的固定区间的最小代价,\(g_i(x)\) 表示第 \(i\) 个区间覆盖以 \(x\) 为左端点区间长度为 \(len\) 的区间的最小代价,容易得到 \(g_i(x)\) 的函数方程:

\[\begin{align*}g(x)=\begin{cases}L_i-x,& x<L_i\\0,& L_i \le x \le R_i-len+1\\x+len-1-R_i ,& R_i<x+len-1\end{cases} \end{align*}\]

不难发现这个函数是下凸的,把函数图像从前往家里那偷过来:

\(f(x)\) 的函数也偷过来:

两个函数都是下凸的,说明最小值一定在转折点处取得,所以在二分前将左右端点排序,二分计算代价时枚举这些端点即可,代价计算时需要用前缀后缀和加双指针优化一下,方法写在注释里了。

点击查看代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=5e5+5;
int n,L[N],R[N];
ll K,pre[N],suf[N];
bool check(int k){for(int i=1,p=1;i<=n;i++){//[x,x+k-1]//找到第一个不满足 R<=x+k-1 的右端点while(p<=n && R[p]<=L[i]+k-1) p++;//x<=L部分的贡献if(suf[i]-1ll*(n-i+1)*L[i]+//R<=x+k-1 部分的贡献1ll*(L[i]+k-1)*(p-1)-pre[p-1] <=K ) return true;}for(int i=n,p=n;i>=1;i--){//枚举R-k+1作为左端点//找到第一个不满足 x<=L 的左端点while(p>=1 && L[p]>=R[i]-k+1) p--;if(suf[p+1]-1ll*(n-p)*(R[i]-k+1)+1ll*i*R[i]-pre[i]<=K) return true;}return false;
}
int plan_vacation(int _N, std::vector<int> _L, std::vector<int> _R, long long _K){n=_N,K=_K;int mn=1e9;for(int i=1;i<=n;i++){L[i]=_L[i-1],R[i]=_R[i-1];mn=min(mn,R[i]-L[i]+1);}sort(L+1,L+1+n),sort(R+1,R+1+n);for(int i=1;i<=n;i++){pre[i]=pre[i-1]+R[i];}for(int i=n;i>=1;i--){suf[i]=suf[i+1]+L[i];}int l=0,r=mn+1;while(r-l>1){int mid=(l+r)>>1;if(check(mid)) l=mid;else r=mid;}return l;
}
http://www.hskmm.com/?act=detail&tid=20866

相关文章:

  • 万象EXCEL开发(三)格式解读calcChain.xml——东方仙盟练气期 - 指南
  • 302、寄门人
  • 达梦数据库用户开启限制白名单导致自身无法登录
  • 【转发】Nginx配置https
  • 本地文件多人多端同步工具:10款高性价比选择
  • 打破AI孤岛:CIO集成实战指南
  • 密码学学习记录(四)
  • Sharding-Proxy、ShardingSphere 和 Sharding-JDBC区别
  • echarts4升级为echarts5的常见问题
  • ISO 周计算 记录
  • 从 “被动耗能” 到 “主动优化”:MyEMS 开启商业建筑能源管理 “新范式”
  • 【故障排查】视频汇聚EasyCVR接入设备通道数为0?通道编码长度不规范导致
  • 来信小程序管理系统:匿名信息传递与社交互动平台
  • PCIe加速卡设计资料:416-基于Kintex Ultrasacle的万兆网络光纤 PCIe加速卡
  • 多生产者,多消费者
  • GEO优化实战指南:一周内让豆包、Deepseek、Kimi等推荐了我的插件
  • 房产楼盘小程序管理系统:助力房产营销数字化升级的优质解决方案
  • 高速信号处理设计方案:413-基于双XCVU9P+C6678的100G光纤加速卡
  • Teamcenter:结构管理器查询(又称:BOM结构查询)
  • 2025年最好用的同步云盘是哪个?一个老用户的真实体验分享
  • 使用 ShedLock 实现多实例定时任务单执行的常见错误及解决办法
  • 1_二分查找
  • AI元人文:悟空博弈专用芯片
  • 【ACM出版】第五届管理科学和软件工程国际学术会议(ICMSSE 2025)
  • PiXYZ Studio 2021下载地址与安装教程
  • coremail日常操作
  • Win 10 LSTC 使用 Podman - tfel
  • 一生一芯学习:程序,运行时环境与AM(一)
  • 如何用Java25编译Java17的项目
  • [MCP] MCP Resources