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

2025-10-22 ZR-J 模拟赛 赛后总结【ZR】

光速打完前三题,然后被 T4 击败。

结果挂完了。

50+10+100+0。

T1 Letters

题意

给定 \(n\) 个单词,对于这些单词组成的集合的所有子集,问这些子集中 az 26 个字母均出现过至少一次的子集总数。

赛时

经过 0 秒的思考糊上去个 bitset\(O(\frac{n2^n}{w})\) 做法。结果复杂度少算个 \(n\) 挂成 50pts。

题解

我觉得不需要写什么题解了。暴力跑 dfs 复杂度比我 bitset 低。

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3fll
using namespace std;int n;
int a[26];
long long ans=0;void dfs(int x,int nw=0){if(x==n+1) ans+=(nw==(1<<26)-1);else{dfs(x+1,nw);dfs(x+1,nw|a[x]);}
}int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;i++){string s;cin>>s;for(char c:s) a[i]|=(1<<(c-'a'));}dfs(1,0);cout<<ans;return 0;
}

T2 Circle

题意

平面上有 \(n\) 个圆,圆心为 \((x_i,0)\),半径为 \(r_i\)

圆之间只会相切,不会相交。

问这些圆把平面分成多少部分。

赛时

严厉批判 ZR 不给大洋里。

结果挂成 10pts。差点没给我 rating 干开线。

题解

把圆转化成数轴上的线段,那么每个圆的贡献为 \(1\) 当且仅当这条线段所在的所有位置均被其他线段所覆盖。

所以把线段按长度排序,然后上个线段树就解决了。

或者用个别的神秘数据结构比如珂朵莉树。

抄了 mhh 的思路。

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3fll
using namespace std;int n;
struct node{int l,r;bool operator<(const node&_Q)const{return r-l+1<_Q.r-_Q.l+1;}bool operator==(const node&_Q)const{return l==_Q.l&&r==_Q.r;}
}a[300010];vector<int> vec;
map<int,int> mp;int unq;int fa[600010];struct node2{int l,r,v,lz;
}t[2400010];void pushdown(int p){if(t[p].lz){t[p<<1].v=1;t[p<<1].lz=1;t[p<<1|1].v=1;t[p<<1|1].lz=1;}
}
void pushup(int p){t[p].v=t[p<<1].v&t[p<<1|1].v;
}void build(int l,int r,int p=1){t[p]={l,r,0,0};if(l==r) return;int mid=(l+r)>>1;build(l,mid,p<<1);build(mid+1,r,p<<1|1);pushup(p);
}void change(int l,int r,int p=1){if(l<=t[p].l&&t[p].r<=r){t[p].v=1;t[p].lz=1;}else{if(t[p].lz) return;pushdown(p);int mid=(t[p].l+t[p].r)>>1;if(l<=mid) change(l,r,p<<1);if(r>mid) change(l,r,p<<1|1);pushup(p);}
}int query(int l,int r,int p=1){if(l<=t[p].l&&t[p].r<=r) return t[p].v;if(t[p].lz) return 1;pushdown(p);int res=1;int mid=(t[p].l+t[p].r)>>1;if(l<=mid) res&=query(l,r,p<<1);if(r>mid) res&=query(l,r,p<<1|1);return res;
}int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;i++){int x,r;cin>>x>>r;a[i]={x-r,x+r};}for(int i=1;i<=n;i++) vec.push_back(a[i].l);for(int i=1;i<=n;i++) vec.push_back(a[i].r);sort(vec.begin(),vec.end());mp[vec[0]]=++unq;for(int i=1;i<vec.size();i++) if(vec[i]!=vec[i-1]) mp[vec[i]]=++unq;for(int i=1;i<=n;i++) a[i].l=mp[a[i].l];for(int i=1;i<=n;i++) a[i].r=mp[a[i].r]-1;build(1,unq);int ans=1;sort(a+1,a+1+n);for(int i=1;i<=n;i++){if(a[i]==a[i-1]) continue;if(a[i].l>a[i].r) continue;ans+=query(a[i].l,a[i].r)+1;change(a[i].l,a[i].r);}cout<<ans;return 0;
}

T3 Bag

题意

\(n\) 个物品和 \(m\) 个背包。物品有 \(w_i\) 的价值和 \(c_i\) 的重量。

每个背包只能装一个重量不大于 \(v_i\) 的物品。

最大化价值总和。

题解

显然贪心。

双指针带个堆就够了。

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3fll
using namespace std;int n,k;
struct node{long long w,c;bool operator<(const node&_Q)const{return c<_Q.c;}
}a[300010];
long long v[300010];vector<int> vec;
map<long long,int> mp;int unq;priority_queue<long long> q;int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n>>k;for(int i=1;i<=n;i++) cin>>a[i].c>>a[i].w;for(int i=1;i<=k;i++) cin>>v[i];sort(v+1,v+1+k);sort(a+1,a+1+n);int p=1;long long ans=0;for(int i=1;i<=k;i++){while(p<=n&&a[p].c<=v[i]) q.push(a[p].w),p++;if(!q.empty()) ans+=q.top(),q.pop();}cout<<ans;return 0;
}

总结

挂完了。

严厉谴责 ZR 不给大洋里。

http://www.hskmm.com/?act=detail&tid=37566

相关文章:

  • P5285 [十二省联考 2019] 骗分过样例
  • Liferay Portal与DXP集合提供程序存在授权缺失漏洞分析
  • MapGIS Objects Java计算一条三维线段与一个三角形所在的平面的交点 - 教程
  • layui时间与日期选择器,时间范围查询数据,后端springboot
  • 读书笔记:OpenPBR 规范(2)
  • 轻量级图片信息解析程序
  • 2025.10.23 闲话-全局位运算 max 的解法
  • 习题-无限集与选择公理
  • Error: [WinError 10013] 以一种访问权限不允许的方式做了一个访问套接字的尝试及其解决方法
  • 项目管理软件是不是伪需求?
  • 题解:CF2115F1 Gellyfish and Lycoris Radiata (Easy Version)
  • 低代码如何重塑IT部门价值?
  • LIS 略解
  • 低代码如何引爆全员创新?揭秘技术民主化背后的蒲公英效应
  • LLM学习笔记DAY10
  • 2025工业冰水机/冷水机厂家推荐东莞市凯诺机械,高效制冷稳定运行
  • 2025小型低温/工业/风冷/一体式螺杆冷冻机厂家推荐:东莞凯诺机械专业制冷解决方案
  • 2025水冷螺杆/风冷螺杆冷水机厂家推荐东莞市凯诺机械,高效制冷稳定可靠
  • LLM学习笔记DAY9
  • OJ模拟面试3(异步判题架构)
  • Edge浏览器网页设置深色模式(仅搜索结果界面)
  • 2025 年 AI 编程工具 TOP5 排名:谁在重新定义研发效率?
  • noipd8t2 - Slayer
  • 【Go】go学习笔记
  • todolist
  • 利用排列组合法实现TOPN路径计算
  • 达梦数据库获取判断字段中的json数据中的值
  • 2025 废气处理/废气治理/环保/污水/分子筛/除臭设备推荐榜:上海深城以专利技术破局,3 家企业凭场景适配登榜,助力异味治理升级
  • Web3 行业 Solidity 高级后端开发工程师岗位要求
  • API 搜索的下一代形态-Apipost智能搜索:只需用业务语言描述需求,就能精准定位目标接口!