首页 > 其他分享 >P4774 倚天屠龙传 题解

P4774 倚天屠龙传 题解

时间:2022-11-04 08:58:59浏览次数:75  
标签:方程 P4774 题解 天屠龙 atk excrt tm mod equiv

其实这道题的主体并不难,主要是细节很多


我们可以把题目分成界限分明的两部分,第一部分,屠每条龙所用的剑只和当前拥有的剑有关。于是可以单独开一个数据结构按题目维护。

另一部分找到最小攻击次数,可以化作以下式子:

\(atk \cdot x \equiv a[i](mod\;p[i])\)

这时我们便能明白题目中所有宝剑攻击力均为1的部分分的含义。因为此时就是标准的exkmp模板。

所以我们要解决的就是x带系数的一元同余方程组。

思考excrt的步骤:

设 \(m = gcd(p_1,p_2...,p_{i-1})\),x满足前i-1个同余方程,则满足前i个方程的解必须为 \(x+tm\) 的形式(t为常数)

那么实际上方程为:\(x+tm \equiv a_i(mod\;p_i)\)

既然x为定值,那么可以把x移动到右边,使方程变为\(tm \equiv a_i-x(mod\;p_i)\)

于是可以化为:\(tm+pa_i=b_i-x\)。即一个以t,p为未知数的二元一次不定方程。然后用扩展欧几里得求解。

发现实际上,当x带系数 atk 时最后一个不定方程可以转化为:

\(tm\cdot atk+pai=b_i-atk\cdot x\)

其实也就是把 \(x+tm\)变成了\(atk(x+tm)\)。

这同样是一个同余方程,所以同样可以用扩欧求解

但要注意几个小问题:

  1. 不同于一般的excrt第一个方程直接赋值解决,这里第一个方程也需要做一次扩欧,所以和后面一起循环就好。

  2. excrt 模板一样,在进行乘法时,也需要__int128或龟速乘帮忙。

  3. 注意题目中必须要砍到龙血量为非正数才能杀死龙,所以当最终答案不足以杀死血最厚的龙时需要不断地加上所有攻击的最小公倍数(为什么是最小公倍数?原因和设m的原因相同)。

  4. 为什么excrtatk要用代码块?因为不这样会有烦人的语法检查

标签:方程,P4774,题解,天屠龙,atk,excrt,tm,mod,equiv
From: https://www.cnblogs.com/closureshop/p/16856510.html

相关文章

  • 2022 CSP-S题解
    T1:假期计划给定\(n\)个点\(m\)条边的无向图,每个点有一个点权。在图中选\(4\)个不同的点,从\(1\)号点出发完成\(5\)段行程:\(1\toA\toB\toC\toD\to1\),每......
  • JOIOI の塔 题解
    题目传送门洛谷上竟然还没有题解...题目分析简单贪心题。考虑倒过来寻找。显然,如果一个J想要配成一座塔,那么必须要找一个OI。O更简单,就是直接找到一个I放上去就......
  • CF912D 小鱼仔 题解
    这是一个很邪门的贪心考虑到最终答案是每个正方形的贡献除以总的正方形个数,而正方形个数容易计算,那么只需最大化贡献。从题面给出的图易得每个点被覆盖的次数是一定的,我......
  • ckeditor粘贴word图片问题解决
    ​ 自动导入Word图片,或者粘贴Word内容时自动上传所有的图片,并且最终保留Word样式,这应该是Web编辑器里面最基本的一个需求功能了。一般情况下我们将Word内容粘贴到Web编辑......
  • [ARC087F] Squirrel Migration 题解
    [ARC087F]SquirrelMigration给你一个\(n\)个节点的树,求一个\(1\simn\)的排列\((p_1,p_2,\dotsp_n)\),使得\(\sumdist(i,p_i)\)最大。求这样的排列个数。答案......
  • 【题解】P8818 [CSP-S 2022] 策略游戏
    【题解】P8818[CSP-S2022]策略游戏这道题应该是CSP-S2022所有题里面最简单的一道了,主要是有点套路,刨开套路,其实就是个静态维护区间最大最小值的板子。作为一名场外......
  • [题解] HDU7060 Separated Number 思路整理
    题目链接HDU7060SeparatedNumber题目大意给一个\(n\)位数,把该数字分成\(k\)段,每种方案的贡献为其分割出的段的数字之和。求所有分法的贡献之和(对\(998244353\)......
  • java 中文乱码问题解决思路
    碰到中文乱码,引起的原因一般为,在编写程序的时候的编码方式与查看的时候的编码方式不一致,从而导致了中文乱码。碰到这种问题,首先要做的就是查看自己编码方式,以String为例St......
  • 2022.11.2 模拟赛题解
    简要题意给定一棵\(n\)个节点的有根树,树根为\(1\)号节点,每个结点有一个权值\(a_i(|a_i|\leq10^9)\),求包含\(1\)的前\(k\)小的连通块的权值。简要题解前置内......
  • 11.2 解题报告&CSP-S 2022题解
    T1用时:\(1\)h期望得分:\(70\)~\(80\)实际得分:\(55\)这题考场写了个常数比较小的\(O(n^3)\)的做法,期望得分\(75\)左右,但是由于bfs忘记打标记导致MLE和TLE,挂......