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

2025.10.13 测试

1.

U612392 追忆

是一个小技巧

考虑在序列中尽量向前匹配,在那个位置计数

然后发现要求是对于一个元素,在其前面的元素与其之间的空隙不能有这个字符

所以可以枚举结尾位置

通过 $\sum _{i = 0}^n \binom{i - n - 1}{n - 1} \times 26^{n + k - i} \times 25^{i - n} $

简单计算即可

AC

2.

P11390 [COCI 2024/2025 #1] 教师 / Učiteljica

想到枚举右端点,然后统计和法左端点

\(k = 1\)

维护每种数的合法区间

然后相当于求非零位置和

是区间加和非 0 位置个数

把右端点看成 x 轴,合法左端点放到 y 轴上,其实就是一个简单的扫描线模版,不用离散化

有两种解决方案

  • 维护最小值及其个数

  • 维护区间覆盖次数

我写的第一种

\(k > 1\)

考虑其实是要求每种 k 都出现,相当于是求交集,不好写,转换成求并集容斥就行

复杂度 \(O(2^k \times k \times n \log n)\)

这个容斥的原理和并集转换是一样的

用二项式定理可以简单证明

AC

3.

P4922 [MtOI2018] 崩坏3?非酋之战!

前言

这是一篇 \(O(n)\) 的题解

NOIP 模拟赛放了这道题目

个人认为还是较为简单的

赛时思路完整推导

读完题目,发现没有关于时间的最优化,所以可以发现其实技能的很大一部分是被其他技能单调的

  • 闪避不如大招

  • 爱酱的炸弹不如技能

  • 犹大的誓约不如大招

其实时间暂停和减速都是 buff 在打伤害

  • 奥托之光由于清除 buff,没用

  • 律者之力不如大招

所以其实有用的技能只有 3 个

  1. 大招用于时间暂停 5s

  2. 技能用于获得 1 层燃烧 buff

  3. 分支攻击用于减速

此时设 dp[i][j] 表示当前有 \(i\) 层燃烧 buff , \(j\) 层减速的最大攻击值

直接每次转移三个技能就是 \(O(n^3)\)

for(int j = 0;j <= i;j ++) {for(int k = 0;k <= i - j;k ++) {if(f[j][k] == -inf) continue;int h = f[j][k] + (j + 1) * k * atk;g[j][k] = max(g[j][k] , h + 5 * k * atk + 12 * atk);g[j + 1][k] = max(g[j + 1][k] , h + 7 * atk);g[j][k + 1] = max(g[j][k + 1] , h + 8 * atk);}
}

然后 \(n^2\) 的解法就是通过分析大招与技能 / 大招与分支攻击的最优相对关系

(可以自己设当前有几层燃烧 buff和减速 buff ,然后列关系式)

分析出大招在最后更优

这样 dp 过程中只需要维护两个 buff , 然后每次最后的大招伤害可以 \(O(1)\) 计算

复杂度到了 \(O(n^2)\),已经可以通过了

然而我们可以继续剖析题目性质

我有两个猜测

  1. 三个技能是有顺序的,大概为燃烧,减速,大招

  2. 当 n 很大时显然主要靠燃烧 buff 打伤害

想到这里时 我们不想思考,可以打个表

#include<bits/stdc++.h>
#define int long long
using namespace std;template <typename T>
void _debug(const T& t) { std::cerr << t << '\n'; }
template <typename T, typename... Args>
void _debug(const T& t, const Args&...res) { std::cerr << t << ' '; _debug(res...); }
#define debug(...) _debug(#__VA_ARGS__ " =", __VA_ARGS__)const int N = 1e4 + 10 , inf = 1e18;
int n , hp , atk;
int f[1010][1010] , g[1010][1010] , pr[200][200][200];
void fa(int i) {debug(f[0][0]);int x = 0 , y = 0;for(int j = 0;j <= i;j ++)for(int k = 0;k <= i - j;k ++) if(f[j][k] > f[x][y]) x = j , y = k;debug(x , y , f[x][y]);for(int j = i;j >= 1;j --) {debug(j , x , y , pr[j][x][y]);if(pr[j][x][y] == 2) x --;else if(pr[j][x][y] == 3) y --;else if(!pr[j][x][y]) { cout << "WAWAWA---\n"; exit(0); }}
}signed main() {
//	freopen("c1.in","r",stdin);
//	freopen("c.out","w",stdout);cin >> n >> hp >> atk; atk /= 10;for(int j = 0;j <= n;j ++)for(int k = 0;k <= n;k ++) g[j][k] = -inf;g[0][0] = 0;for(int i = 0;i <= n;i ++) {int mx = 0;for(int j = 0;j <= i;j ++)for(int k = 0;k <= i - j;k ++) f[j][k] = g[j][k] , mx = max(mx , f[j][k]);if(mx >= hp) { fa(i); cout << i << '\n' << "LeiZeProMax Nb!!!"; return 0; }if(i == n) { fa(i); cout << mx << '\n' << "hks"; return 0; }for(int j = 0;j <= i + 1;j ++)for(int k = 0;k <= i + 1 - j;k ++) g[j][k] = -inf;if(i == 30) debug(f[15][15] , g[15][15]);for(int j = 0;j <= i;j ++) {for(int k = 0;k <= i - j;k ++) {if(f[j][k] == -inf) continue;int h = f[j][k] + (j + 1) * k * atk;if(h + 5 * k * atk + 12 * atk >= g[j][k]) pr[i + 1][j][k] = 1;g[j][k] = max(g[j][k] , h + 5 * k * atk + 12 * atk);if(h + 7 * atk >= g[j + 1][k]) pr[i + 1][j + 1][k] = 2;g[j + 1][k] = max(g[j + 1][k] , h + 7 * atk);if(i == 29 && j == 14 && k == 15) debug(g[j + 1][k] , pr[i + 1][j + 1][k]);if(h + 8 * atk >= g[j][k + 1]) pr[i + 1][j][k + 1] = 3;g[j][k + 1] = max(g[j][k + 1] , h + 8 * atk);if(i == 29 && j == 15 && k == 14) debug(g[j][k + 1] , pr[i + 1][j][k + 1]);}}}return 0;
}

打出来发现

看最后一列是转移点

发现是 燃烧减速交错 ?

不对结尾处不同,多打几个发现最后 10 个其实是固定的

所以程序告诉我们答案是 先燃烧减速交错,后 10 个直接叠 5 层减速,最后 5 个用大招

分析原因的话用上面第二个猜测,我们可以考虑只 buff 的伤害, 设当前有 x 层减速, y 层燃烧

则下一次打的伤害即为 \(x \times y\) ,由初中奥数可得,当 \(x + y\) 一定, \(x = y\)\(x \times y\) 最大

所以可得大部分是减速燃烧交错叠加

至于最后的特殊情况,其实也是好感性考虑的

减速其时是为后面每一次都增加 1 秒的攻击事件,是永久的

而大招暂停 5 秒是为当前轮增加 5 秒的攻击事件,是暂时的

从长远来看,我们当然是选择减速,但当后缀攻击次数小于 5 时,暂时性的大招反而具有优势

大招前叠 5 次燃烧,其实也是为了和后面的大招凑平方数

所以如果大招暂停时间更长,其后面的特殊情况的长度也会对应线性增长

至此就没了

代码

代码直接按上面的结论打即可,应该挺短的,注意长度不足 10 的情况

跑到了最优解,不卡常比非线性做法第一名快了 5 倍,线性做法不就应该比平方做法快吗?

下面是我赛时代码,可以参考结构 ?

注意输出的字符串不同

#include<bits/stdc++.h>
#define int long long
using namespace std;template <typename T>
void _debug(const T& t) { std::cerr << t << '\n'; }
template <typename T, typename... Args>
void _debug(const T& t, const Args&...res) { std::cerr << t << ' '; _debug(res...); }
#define debug(...) _debug(#__VA_ARGS__ " =", __VA_ARGS__)const int N = 1e4 + 10 , inf = 1e18;
int n , hp , atk;
int f[1010][1010] , g[1010][1010];
int col[N];
bool check(int x , int y , int mx) {for(int i = 1;i <= 5;i ++) {mx += (x + 1) * y * atk + 8 * atk , y ++;if(mx >= hp) return 1;}for(int i = 1;i <= 5;i ++) {mx += (x + 6) * y * atk + 12 * atk;if(mx >= hp) return 1;}return 0;
}
void dp(int len) {for(int j = 0;j <= len;j ++)for(int k = 0;k <= len;k ++) g[j][k] = -inf;g[0][0] = 0;for(int i = 0;i <= len;i ++) {int mx = 0;for(int j = 0;j <= i;j ++)for(int k = 0;k <= i - j;k ++) f[j][k] = g[j][k] , mx = max(mx , f[j][k]);if(mx >= hp) { cout << i << '\n' << "Tech Otakus Save The World!"; exit(0); }for(int j = 0;j <= i + 1;j ++)for(int k = 0;k <= i + 1 - j;k ++) g[j][k] = -inf;for(int j = 0;j <= i;j ++) {for(int k = 0;k <= i - j;k ++) {if(f[j][k] == -inf) continue;int h = f[j][k] + (j + 1) * k * atk;g[j][k] = max(g[j][k] , h + 5 * k * atk + 12 * atk);g[j + 1][k] = max(g[j + 1][k] , h + 7 * atk);g[j][k + 1] = max(g[j][k + 1] , h + 8 * atk);}}}
}signed main() {cin >> n >> hp >> atk; atk /= 10;if(!hp) { cout << 0 << '\n' << "Tech Otakus Save The World!"; return 0; }if(n <= 300) {for(int j = 0;j <= n;j ++)for(int k = 0;k <= n;k ++) g[j][k] = -inf;g[0][0] = 0;for(int i = 0;i <= n;i ++) {int mx = 0;for(int j = 0;j <= i;j ++)for(int k = 0;k <= i - j;k ++) f[j][k] = g[j][k] , mx = max(mx , f[j][k]);if(mx >= hp) { cout << i << '\n' << "Tech Otakus Save The World!"; return 0; }if(i == n) { cout << mx << '\n' << "MiHoYo Was Destroyed!"; return 0; }for(int j = 0;j <= i + 1;j ++)for(int k = 0;k <= i + 1 - j;k ++) g[j][k] = -inf;for(int j = 0;j <= i;j ++) {for(int k = 0;k <= i - j;k ++) {if(f[j][k] == -inf) continue;int h = f[j][k] + (j + 1) * k * atk;g[j][k] = max(g[j][k] , h + 5 * k * atk + 12 * atk);g[j + 1][k] = max(g[j + 1][k] , h + 7 * atk);g[j][k + 1] = max(g[j][k + 1] , h + 8 * atk);}}}return 0;}else {dp(10);for(int i = 1;i <= n - 10;i ++) {if(i & 1) col[i] = 3;else col[i] = 2;}for(int i = n - 9;i <= n - 5;i ++) col[i] = 3;for(int i = n - 4;i <= n;i ++) col[i] = 1;int x = 0 , y = 0 , mx = 0;for(int i = 1;i <= n;i ++) {int adv = 0;if(col[i] == 1) adv = (x + 6) * y * atk + 12 * atk;else if(col[i] == 2) adv = (x + 1) * y * atk + 7 * atk , x ++;else adv = (x + 1) * y * atk + 8 * atk , y ++;if(mx >= hp - adv) break;mx = mx + adv;if(i == n) { cout << mx << '\n' << "MiHoYo Was Destroyed!"; return 0; }}x = 0 , y = 0 , mx = 0;for(int i = 1;i <= n - 10;i ++) {
//			debug(x , y , mx , check(x , y , mx));int adv = 0;if(i & 1) adv = (x + 1) * y * atk + 8 * atk , y ++;else adv = (x + 1) * y * atk + 7 * atk , x ++;mx += adv;if(check(x , y , mx)) { cout << i + 10 << '\n' << "Tech Otakus Save The World!"; return 0; }
//			debug(i , mx);}
//		cout << "hhh";}return 0;
}

后记

由于作者本人很懒还有点笨,所以这是作者第一篇题解,如果有问题可以私信联系,感谢 ~~

乐一下

搬题时同学把题面改成关于吕布的,

玩过农的都知道,吕布只有 3 个技能,一个一技能附魔(挂 buff),二技能减速,还有大招(血条再厚,一刀带走)

还是写实

4.

P12336 第三心脏

逆天改造

先推柿子

$ \sqrt{a^2 + b^2 + c^2 + d^2} = a \oplus b \oplus c \oplus d $

$ a^2 + b^2 + c^2 + d^2 = (a \oplus b \oplus c \oplus d)^2 \ge d^2 = (d + x)^2 $

拆开得

$ a^2 + b^2 + c^2 + d^2 = (d + x) ^ 2$

\(a^2 + b^2 + c^2 = 2 \times d \times x + x^2\)

\((a \oplus b \oplus c \oplus d)^2 = (d + x) ^ 2\)

\(a \oplus b \oplus c \oplus d = d + x\)

合起来即为

\[\left\{\begin{matrix}a^2 + b^2 + c^2 = 2 \times d \times x + x^2\\ a \oplus b \oplus c \oplus d = d + x \end{matrix}\right.\]

设 x 最高位为 p , 我们让 d 的 \(\le p\) 位,直接可以得到

\[\left\{\begin{matrix}a^2 + b^2 + c^2 = 2 \times d \times x + x^2\\ a \oplus b \oplus c = x \end{matrix}\right.\]

然后我让 x = 1 ,后面的构造可以看出对任意 x 都可以构造

\[\left\{\begin{matrix}a^2 + b^2 + c^2 = 2 \times d + 1\\ a \oplus b \oplus c = 1\\ d \equiv 0 (\bmod 2) \end{matrix}\right.\]

\[\left\{\begin{matrix}\frac{a^2 + b^2 + c^2 - 1}{2} = d\\ a \oplus b \oplus c = 1\\ d \equiv 0 (\bmod 2) \end{matrix}\right.\]

\(b = 2^p + a , c = 2^p + 2^{p + 1} + 1\)

发现成立,

但当 a 为奇数时, \(d \equiv 0 (\bmod 2)\) 不成立

微调一下 \(b = 2^p + a - 1 , c = 2^p + 2^{p + 1}\) 即可

AC

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

相关文章:

  • 2025年注塑加工行业优质企业最新推荐排行榜:助力需求企业精准筛选可靠合作伙伴
  • 2025 年工程管理软件平台公司最新推荐榜:聚焦数字化效能,优选靠谱服务商
  • 被 Excel 格式折腾的那些瞬间---excl格式转换
  • 阵列信号处理中的盲源分离算法
  • 标准版v9.0破解版及软件安装包
  • 内外网传文件有哪些痛点?一文读懂高效传输方案是什么样的
  • win32中的COM接口清单
  • 内存的堆、内存的栈有什么区别
  • 2025 年铝板厂家最新推荐榜:覆盖多系列铝板产品,精选优质企业,为采购者提供专业选型参考
  • 用 AI 批量优化思源笔记排版
  • 2025 年连接线线束厂家最新推荐榜:新能源电子 / 机器人电子等多领域优质企业品控、定制能力及合作案例全面盘点
  • 2025年黄金回收品牌最新权威推荐榜:专业鉴定与高价回收口碑之选,正规资质黄金回收厂家精选指南
  • 2025 年试验机最新推荐榜单:电子万能材料 / 橡胶拉力 / 塑料拉力 / 环刚度 / 冲击试验机优质厂家精选及科研工业合作参考
  • 2025 年国内卷帘门源头厂家最新推荐排行榜:电动 /pvc/ 钢质 / 自动 / 防火卷帘门优质厂家精选
  • 2025 年电容厂家最新推荐排行榜:固态 / 高压 / 牛角 / 安规 / CBB / 超级电容领域优质厂家精选
  • 如何让AI实现自动化 —— PlayWright MCP 实测 - 教程
  • 使用git-filter-repo 清除大文件
  • 2025 年滤筒源头厂家最新推荐排行榜:盘点实力企业及选购要点,涵盖多类型滤筒优质公司水刺/除尘/阻燃/高温滤筒厂家推荐
  • Flutter美观、易用的日历选择组件
  • 2025 年滤袋源头厂家最新推荐排行榜:PTFE/PPS/P84 等多材质滤袋优质品牌精选及选购参考
  • 2025年最新销售管理系统使用指南:顶级销售是如何使用CRM系统? - SaaS软件
  • 2025 年激光焊锡源头厂家最新推荐排行榜:覆盖多行业需求,助力企业精准选优质设备供应商手机摄像头/线材类/通讯行业/FPC柔性线路板激光焊锡厂家推荐
  • 【光照】UnityURP中的[HDR贴图]
  • 2025 年激光粒度仪厂家最新推荐榜单:聚焦行业标杆与新兴势力,助力科研与生产精准选购纳米粒度及Zeta电位仪厂家推荐
  • 第五周第二天5.2
  • ​​电压探头的应用场景与技术选型指南​​
  • 循环调用接口,使用promise.all的应用
  • 部署zabbix proxy代理服务服务器
  • 完整教程:Docker搭建ESPIDF环境,程序下载
  • 基于Java+Springboot+Vue开发的体育用品购物销售商城管理系统源码+运行步骤