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

abc426 题解

abc426 题解

abc426

赛时 ABCD,E 被卡精度卡了30min,21:41 改为 long double 过了 /ll

A

水题,懒得写

B

同上

C

拿树状数组硬跑,每次记录当前的 \(x\) 的最大值(即当前序列最大值)

for(int i = 1; i <= n; i++) add(i, 1);
int lim = 0;
while(q--) {int x = rd(), y = rd();if(x <= lim) {wr(0);continue;}int ans = ask(x)-ask(lim);add(y, ans);lim = x;wr(ans);
}

D

不难发现最优情况一定是固定序列中最长的一段 \(0/1\),然后将剩下的 \(0/1\) 计算答案

具体实现即对于固定 \(0/1\) 的最长段分别跑一遍,记录答案最小值

以当前处理 \(0\) 的最长段为例,答案即为 除最长段以外的所有 \(0\) 的个数 \(\times2\)(变为 \(1\) 再变回为 \(0\))+ 所有 \(1\) 的个数

for(int i = 1; i <= n; i++) {if(s[i] == '0') {cnt0++;f[i][0] = f[i-1][0]+1;f[i][1] = 0;max0 = max(max0, f[i][0]);}else {cnt1++;f[i][0] = 0;f[i][1] = f[i-1][1]+1;max1 = max(max1, f[i][1]);}
}
ans = min(cnt1+(cnt0-max0)*2, cnt0+(cnt1-max1)*2);
wr(ans);

E

题意即为两动点找最小值,不难发现整个过程可分为两段,即两点都在动和只有一点在动。并且,根据数学知识,距离与时间的关系为二次函数的形式,所以可以通过三分或直接求解来解决

不过我忘了三分咋写了,于是就用二次函数硬解了

根据向量相关知识,我们设:

\(td=tg-ts,ad=ag-as\)

\(tv=\frac{td}{|td|},av=\frac{ad}{|ad|}\)(即方向向量)

设二次函数为 \(y=ax^2+bx+c\)

第一段(两点都动)中,对应的参数即为

\(a=(tv-ta)^2\)

\(b=(ts-as)\cdot(tv)\)

\(c=(ts-as)^2\)

\(x\in[0,\min(|ta|,|ad|)]\)

根据数学知识直接求最小值

第二段中,我们设 \(|ta|<|ad|\)

\(a=1\)

\(b=2\times(ts-ag)\cdot(tv)\)

\(c=(ts-ag)^2\)

\(x\in[\min(|ta|,|ad|),\max(|ta|,|ad|)]\)

\(|ta|>|td|\) 的情况同理

于是得出答案

不过要注意各种精度问题,包括但不限于 eps,long double 等的应用

cin >> ts.x >> ts.y >> tg.x >> tg.y >> as.x >> as.y >> ag.x >> ag.y;
long double dist, disa, ans;
pos td = (tg-ts), ad = (ag-as), tv, av;
dist = dis(td);
disa = dis(ad);
if(dist > eps) tv = (1.0/dist)*td;
else tv = {0, 0};
if(disa > eps) av = (1.0/disa)*ad;
else av = {0, 0};
long double a = dot(tv-av, tv-av);
long double b = dot(ts-as, tv-av)*2;
long double c = dot(ts-as, ts-as);
long double lim = min(dist, disa);
ans = cal(a, b, c, 0, lim);
if(dist > disa+eps) {a = 1;b = 2*dot(ts-ag, tv);c = dot(ts-ag, ts-ag);ans = min(ans, cal(a, b, c, lim, dist));
}
if(disa > dist+eps) {a = 1;b = -2*dot(tg-as, av);c = dot(tg-as, tg-as);ans = min(ans, cal(a, b, c, lim, disa));
}
printf("%.6Lf\n", ans);

F

不难发现,答案即为大于 \(k\) 的个数乘 \(k\) 加上所有不大于 \(k\) 的值

考虑线段树解决

线段树维护区间最小值和区间正数的数量

每次操作处理所有不大于 \(k\) 的值,然后将其赋值为 \(\inf\)

然后查询区间减去 \(k\) 后正数的数量

最后区间减掉 \(k\)

由于每个 \(a_i\) 只会变为负数一次,所以复杂度是对的

void pushup(ll p) {t[p].minn = min(t[ls(p)].minn, t[rs(p)].minn);t[p].cnt = t[ls(p)].cnt+t[rs(p)].cnt;
}
void pushdown(ll p) {if(t[p].lzy == 0) return;t[ls(p)].minn += t[p].lzy;t[rs(p)].minn += t[p].lzy;t[ls(p)].lzy += t[p].lzy;t[rs(p)].lzy += t[p].lzy;t[p].lzy = 0;
}
void build(ll p, ll l, ll r) {t[p].l = l, t[p].r = r;if(l == r) {t[p].minn = a[l], t[p].cnt = 1;return;}ll mid = (l+r) >> 1;build(ls(p), l, mid);build(rs(p), mid+1, r);pushup(p);
}
void modify(ll p, ll l, ll r, ll v) {if(l <= t[p].l && t[p].r <= r) {t[p].minn += v;t[p].lzy += v;if(t[p].minn <= 0) t[p].cnt = 0;return;}ll mid = (t[p].l+t[p].r) >> 1;pushdown(p);if(l <= mid) modify(ls(p), l, r, v);if(mid < r) modify(rs(p), l, r, v);pushup(p);
}
ll update(ll p, ll l, ll r, ll v) {if(t[p].minn > v) return 0;if(t[p].l == t[p].r) {ll ret = t[p].minn;t[p].cnt = 0;t[p].minn = inf;return ret;}pushdown(p);ll mid = (t[p].l+t[p].r) >> 1, res = 0;if(l <= mid) res += update(ls(p), l, r, v);if(mid < r) res += update(rs(p), l, r, v);pushup(p);return res;
}
ll query(ll p, ll l, ll r) {if(l <= t[p].l && t[p].r <= r) return t[p].cnt;pushdown(p);ll mid = (t[p].l+t[p].r) >> 1, res = 0;if(l <= mid) res += query(ls(p), l, r);if(mid < r) res += query(rs(p), l, r);return res;
}
void solve() {n = rd();for(ll i = 1; i <= n; i++) a[i] = rd();build(1, 1, n);q = rd();while(q--) {ll l = rd(), r = rd(), k = rd(), ans = 0;ans = update(1, l, r, k)+k*query(1, l, r);wr(ans);modify(1, l, r, -k);}
}

G

题意即为多次询问区间 01 背包问题

考虑从分治入手

首先考虑两个 01 背包(可选物品不同)如何合并

很显然,记录前缀最大值,然后合并,即:

\(f_{i,j}=\max_{k=1}^jf_{i,k},g_{i,j}=\max_{k=1}^jg_{i,k}\)

\(h_{i,j}=max_{k=1}^j(f_{i,k}+g_{i,j-k})\)

回到原题,将所有问题先离线处理

设目前分治区间为 \([l,r]\),对于所有问题 \([i,j]\in[l,r]\),可以分为三类:

  1. \(j<mid\),这类我们放到 \([l,mid]\) 分治
  2. \(i>mid\),这类我们放到 \([mid+1,r]\) 分治
  3. 剩下的,很显然 \(mid\in[i,j]\),我们现在处理

\(f_{i,j}\)\([i,mid]\) 内的物品容量为 \(j\) 的最大值

\(g_{i,j}\)\([mid+1,i]\) 内的物品容量为 \(j\) 的最大值

则对于询问 \(l,r,c\),其答案即为我们上面提到的 \(f_{l,c}\)\(g_{r,c}\) 的合并

时间复杂度为 \(O(\sum len\times c)=O(cn\log n)\)

这种方法也被称为“猫树分治”

具体细节见代码

void solv(ll L, ll R, vector <ques> q) {if(L == R) {for(auto [l, r, c, id] : q) ans[id] = (c>=h[l])?w[l]:0;return;}// 处理问题ll mid = (L+R) >> 1;vector <ques> q1, q2, qq;for(auto Q : q) {if(Q.r <= mid) q1.eb(Q);else if(Q.l > mid) q2.eb(Q);else qq.eb(Q);}solv(L, mid, q1);solv(mid+1, R, q2);// 计算前后缀for(ll i = mid+1; i >= L; i--) for(ll j = 0; j <= 500; j++) f[i][j] = 0;for(ll i = mid; i >= L; i--) {for(ll j = 500; j >= 0; j--) {if(j >= h[i]) f[i][j] = max(f[i+1][j], f[i+1][j-h[i]]+w[i]);else f[i][j] = f[i+1][j];}}for(ll i = mid; i <= R; i++) for(ll j = 0; j <= 500; j++) g[i][j] = 0;for(ll i = mid+1; i <= R; i++) {for(ll j = 500; j >= 0; j--) {if(j >= h[i]) g[i][j] = max(g[i-1][j], g[i-1][j-h[i]]+w[i]);else g[i][j] = g[i-1][j];}}// 处理当前问题for(auto [l, r, c, id] : qq) {for(ll i = 0; i <= c; i++) ans[id] = max(ans[id], f[l][i]+g[r][c-i]);}
}
void solve() {n = rd();for(ll i = 1; i <= n; i++) h[i] = rd(), w[i] = rd();m = rd();vector <ques> q;for(ll i = 1; i <= m; i++) {ll l = rd(), r = rd(), c = rd();q.eb((ques){l, r, c, i});}solv(1, n, q);for(ll i = 1; i <= m; i++) wr(ans[i]);
}
http://www.hskmm.com/?act=detail&tid=24798

相关文章:

  • 运行npp并打开实时双向同步的今日日记纯文本文档 2025年10月5日
  • 完整教程:python学习打卡day43
  • mac 下修改本机hosts
  • 2025测振仪厂家最新企业品牌推荐排行榜,自动诊断测振仪,防爆测振仪,智能测振仪,诊断故障测振仪推荐!
  • 【JNI】JNI环境搭建
  • CS自学笔记
  • vue: 报错: vue ResizeObserver loop completed with undelivered notifications.
  • 原来一个人真的是通过别人认识自己的
  • ds调度mssql多个T-SQL语句同步阻塞实现
  • 2025提升门厂家最新企业品牌推荐排行榜,保温提升门,钢质提升门,消防提升门,分段式提升门,工业提升门公司推荐!
  • 高考数学易错考点02 | 临阵磨枪 - 指南
  • 2025升降机厂家最新企业品牌推荐排行榜,固定式升降机,液压升降机,电动升降机,铝合金式升降机公司推荐!
  • 在 2025 年安装 Visual Studio 2013
  • 算法伦理与机器学习研究获PROSE奖
  • 实验1 C语言开发环境使用和数据类型、运算符、表达符
  • UiPath推出全新AI代理开发功能,简化自动化构建流程
  • 2025年T型螺栓厂家TOP企业品牌推荐排行榜,光伏T型螺栓,不锈钢T型螺栓,地铁专用T型螺栓,高铁T型螺栓公司!
  • 2025 年碳纤维布厂家最新推荐排行榜:精选建筑碳纤维布 ,加固碳纤维布,300克碳纤维布,碳纤维加固布公司
  • MySQL Docker 容器化部署全指南
  • 2025热浸塑钢管工厂最新企业品牌推荐排行榜 ,NHAP热浸塑钢管,电力热浸塑钢管,N-HAP热浸塑钢管,电力涂塑钢管公司推荐!
  • 2025广告喷绘公司最新推荐榜单, 覆盖广告喷绘广告牌,广告喷绘写真,广告喷绘广告牌写真,广告喷绘门头服务!
  • 详细介绍:ck-editor5的研究 (5):优化-页面离开时提醒保存,顺便了解一下 Editor的生命周期 和 6大编辑器类型
  • 10.5阅读笔记
  • 实用指南:电脑装的数据越多,会不会越重
  • [算法/数据结构] 数据结构与算法
  • 图论new
  • 2025夹丝玻璃厂家最新企业品牌推荐排行榜,艺术夹丝玻璃,淋浴房夹丝玻璃,极简门夹丝玻璃,金属夹丝玻璃公司推荐!
  • 斜率优化dp复习笔记
  • 掌握形式验证,护航芯片安全
  • 数位DP