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

MZOI 20251011【CSP-】模拟 T2 序列区间

好题集第四篇。

题意 给一个长度为 $n$ 的正整数序列 $a$ 和一个常数 $k$,求 $a$ 中有多少对 $(l,r)$ 满足 $\frac{\prod_{i=l}^{r}}{\sum_{i=l}^{r}}=k$。

这里用 \(mina\) 表示数组中的最小值,用 \(maxa\) 表示数组中的最大值。

对于前 \(30\%\) 的测试点,\(n\le10\)\(maxa\le10\)

对于前 \(60\%\) 的测试点,\(n\le100\)

对于前 \(80\%\) 的测试点,\(mina\ge2\)

对于 \(100\%\) 的测试点,\(n\le 2\times10^5\)\(k\le10^5\)\(maxa\le10^8\)\(mina\ge1\)

Hint 1 想想对于 $60$ 分的数据的做法。
Hint 2 考虑 $80$ 分的数据,能不能发现“人类智慧”?
Hint 3 考虑 $100$ 分的数据,对于有 $1$ 出现的情况,如何处理这些 $1$?
Solution 设一段区间的乘积为 $tim$,区间和为 $sum$。

我们来看一堆 \(1\) 连续的情况。

假如现在区间 \([l,r]\) 全部都是 \(1\),那么 \(tim=1\)\(sum=r-l+1\)。假设现在我们后面又多了 \(cnt\)\(1\),那么现在如果它要计入贡献的话就要满足 \(tim=k\times(sum+cnt)\),也就是 \(1=k\times(sum+cnt)\)。于是我们得到 \(cnt\) 的范围: \(1\le cnt\le\frac{1}{k}-sum\)。所以在这个范围内的 \(cnt\) 就可以计数。

但是直接枚举每一个 \(1\),复杂度就会变成 \(O(n^2)\),如何优化呢?

我们可以维护一个 \(rt\) 数组,来记录这一段连续的 \(1\) 的右端点。所以我们遇到这些 \(1\) 就可以一起处理,而不是直接遍历,从而把复杂度降下来。

总时间复杂度均摊 \(O(n)\)

Code
#include <bits/stdc++.h>
#define loop(i,a,b) for(int i=(a);~i;i=(b))
#define eb emplace_back
#define pb push_back
#define print(x,c) write(x),putchar(c),flush()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
constexpr int N = 2e5 + 15;
constexpr ll INF = 2e18;namespace FAST_IO {
#define IOSIZE 300000char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)template <typename T> inline void read (T &x) {	x = 0; T f = 1;char ch = getchar ();while (!isdigit (ch)) {if (ch == '-') f = -1; ch = getchar ();}while (isdigit (ch)) {x = (x << 1) + (x << 3) + (ch ^ '0'); ch = getchar ();} x *= f;}template <> inline void read (double &x) { x = 0; int f = 1;char ch = getchar ();while (!isdigit (ch)) { if (ch == '-') f = -1; ch = getchar ();} while (isdigit (ch)) x = x * 10 + (ch - '0'), ch = getchar ();if (ch == '.') {ch = getchar (); for (double t = 0.1; isdigit (ch); t *= 0.1) x += t * (ch - '0'), ch = getchar ();}x *= f;}inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }template <typename T, typename ...Args> inline void read (T &x, Args &...args) {read(x); read(args...);}template <typename T> inline void write (T x) {	if (x < 0) putchar ('-'), x = -x; if (x > 9) write (x / 10); putchar (x % 10 + 48);}inline void write(char *x) { while (*x) putchar(*x++); }inline void write(const char *x) { while (*x) putchar(*x++); }inline void flush() { if (p3 != obuf) { fwrite(obuf, 1, p3 - obuf, stdout);p3 = obuf;}}
}
using namespace FAST_IO;int n;
ll k;
int a[N];
ll ans;
int rt[N];int main () {read (n, k);for (int i = 1; i <= n; ++ i) {read (a[i]);}for (int i = n; i >= 1; -- i) {if (a[i] == 1) {rt[i] = (a[i + 1] == 1) ? rt[i + 1] : i;} else rt[i] = i;}for (int l = 1; l <= n; ++ l) {ll sum = 0, tim = 1;for (int r = l; r <= n; ) {if (a[r] == 1) {int cnt = rt[r] - r + 1;if (tim % k == 0) {ll tmp = tim / k - sum;if (tmp >= 1 && tmp <= cnt) ++ ans;}sum += cnt;r = rt[r] + 1;} else {if (tim * a[r] > INF) break;tim *= a[r];sum += a[r];if (tim == k * sum) ++ ans;++ r;}}}print (ans, '\n');return 0;
}
http://www.hskmm.com/?act=detail&tid=28666

相关文章:

  • SAP 中CONCATENATE 空格的时候,空格不生效
  • Java的各类定时任务实现
  • 03:运算符
  • JavaScript内存泄露原因及解决方案
  • 数据类型扩展
  • 2025 年最新金蝶云服务商推荐榜单:聚焦铂金伙伴技术实力与万级客户口碑,助力企业数字化转型精准选型上海金蝶云服务商推荐
  • OIFHA251011 比赛总结
  • P2051 [AHOI2009] 中国象棋 个人题解
  • 一种智能调度分布式路径计算解决方案
  • 使用 C++ 和 minizip 实现 ZIP 压缩解压工具
  • 一看就懂,Oracle认证体系中的OCP中级认证
  • 2025 年试验机生产厂家最新推荐榜单:聚焦优质企业,助力精准选购高低温等各类试验设备弹簧拉压/弹簧疲劳/高频弹簧疲劳/U型弹簧专用试验机厂家推荐
  • IIS/如何查看IIS上部署网站的实时连接数
  • 拼叨叨砍价系统:实体店低成本引流的营销利器
  • 2025 自动门生产厂家最新推荐榜:权威筛选优质品牌,含选购指南与实力厂家深度解析
  • 医德出诊排班挂号管理系统:医院高效运营与便民服务的智能解决方案
  • 一佳教育培训课程系统小程序:一站式教育数字化解决方案
  • Supabase:无需后端代码的 Web 开发完整解决方案
  • Halo RAG!
  • SLS Copilot 实践:基于 SLS 灵活构建 LLM 应用的数据基础设施
  • 2025 木饰面源头厂家最新推荐榜单:21 年标杆企业领衔,背景墙/全屋 /格栅/碳晶板全品类最新推荐及选购指南
  • 2025 年北京市管道疏通公司最新推荐排行榜:覆盖多城区、高压技术赋能的优质企业优选榜单西城区/朝阳区/丰台区/石景山/海淀区管道疏通公司推荐
  • 2025 年北京市清理化粪池公司最新推荐排行榜:聚焦高压技术与全城服务的权威甄选朝阳区/丰台区/海淀区/通州区清理化粪池厂家推荐
  • 报表方案Stimulsoft 2025.4 重磅发布!新增AI报表助手、C#脚本支持、全新图表类型等多项功能!
  • Prometheus的Exporter的数据采集机制
  • 2025 年珠三角 / 中山 / 东莞 / 佛山厂房出售公司推荐:中创集团产业生态型厂房的价值与服务解析
  • CTFshow-web方向(更新中)
  • 拷贝和上传文件,涉及隐私协议
  • 2025储罐厂家,钢衬塑储罐,钢塑复合储罐,化工储罐,防腐储罐,PE储罐,盐酸储罐,硫酸储罐,聚丙烯储罐,不锈钢储罐,次氯酸钠储罐各类型最新推荐榜:品质卓越与技术创新的行业先锋!
  • 2025 年国内标志牌生产厂家最新推荐排行榜:聚焦优质企业助力客户精准选择道路/限速/公路/施工/警示/限高/三角/安全标志牌厂家推荐