Q779’s Blog

【物理】闭合电路的欧姆定律 属于高中物理必修三的内容。要不是会考有实验操作考试我怎么会现在补这个 一、电动势 定义：在电源内部，非静电力把正电荷从负极移动到正极所做的功，与被移动的电荷的电荷量的比值叫做电源的电动势。 公式： \(E = \frac{W}{q}\) （单位：伏特 \(V\) ） 物理意义： 反映电源把其他形式的能转化为电能的本领大小 在数值上等于非静电力把 \(1\ \mathrm{C}\) 的正电荷在电源内部从负极移送到正极所做的功 二、闭合电路的欧姆定律 1. 闭合电路组成 用导线把电源、用电器连成的闭合电路，可以分为外电路和内电路。 外电路：电源以外的电路叫作外电路。 在外电路中，电流由高电势处流向低电势处，沿电流方向电势降低。 内电路：电源内部叫作内电路。 在内电路中，非静电力做功使正电荷由负极移到正极，故电流由电源负极流向电源正极。 因为电源有内阻 \(r\) ，所以沿电流方向电势也降低。 2. 闭合电路的能量转化 外电路：正电荷在恒定电场作用下由正极移向负极。 内电路：非静电力做功，提供全电路消耗的电能。 纯电阻电路有 \[ W = Q_{...

洛谷P3959 [NOIP2017 提高组] 宝藏 题解 题目链接：P3959 [NOIP2017 提高组] 宝藏 题意： 参与考古挖掘的小明得到了一份藏宝图，藏宝图上标出了 \(n\) 个深埋在地下的宝藏屋， 也给出了这 \(n\) 个宝藏屋之间可供开发的 \(m\) 条道路和它们的长度。 小明决心亲自前往挖掘所有宝藏屋中的宝藏。但是，每个宝藏屋距离地面都很远，也就是说，从地面打通一条到某个宝藏屋的道路是很困难的，而开发宝藏屋之间的道路则相对容易很多。 小明的决心感动了考古挖掘的赞助商，赞助商决定免费赞助他打通一条从地面到某个宝藏屋的通道，通往哪个宝藏屋则由小明来决定。 在此基础上，小明还需要考虑如何开凿宝藏屋之间的道路。已经开凿出的道路可以 任意通行不消耗代价。每开凿出一条新道路，小明就会与考古队一起挖掘出由该条道路所能到达的宝藏屋的宝藏。另外，小明不想开发无用道路，即两个已经被挖掘过的宝藏屋之间的道路无需再开发。 新开发一条道路的代价是 \(\mathrm{L} \times \mathrm{K}\)。其中 \(\mathrm{L}\) 代表这条道路的长度，\(\math...

CF1202E You Are Given Some Strings… 题解 题目链接：CF1202E You Are Given Some Strings… 题意： 给定文本串 \(t\) 和 \(n\) 个模式串 \(s_i\) ，求 \[ \sum_{i=1}^n\sum_{j=1}^nf(s_i + s_j) \] \(f(s)\) 定义为 \(s\) 在 \(t\) 中出现的次数，\(s_i+s_j\) 定义为拼接字符串 \(s_i\) 和 \(s_j\) 。 输入格式： 一行 \(t\) ，一行 \(n\) ，接下来 \(n\) 行 \(s_i\) 。 输出格式： 一行，答案。 数据范围： \(1\le |t|,\sum |s_i| \le 2\times 10^5\) 。 这种题肯定是考虑某个串的贡献啦。 这里我们考虑枚举划分点 \(x\) 。记该点前为 \(s_i\) ，该点后为 \(s_j\) 统计出每个 \(x\) 的 \(f(x),g(x+1)\) 分别表示前后的个数。 怎么统计呢？注意到 \(f(x)\) 其实就是 \(t_{1 \cdots x}\)...

洛谷P5829 【模板】失配树 题解 题目链接：P5829 【模板】失配树 题意： 给定一个字符串 \(s\)，定义它的 \(k\) 前缀 \(\mathsf{pre}_k\) 为字符串 \(s_{1\dots k}\)，\(k\) 后缀 \(\mathsf{suf}_k\) 为字符串 \(s_{|s|-k+1\dots |s|}\)，其中 \(1 \le k \le |s|\)。 定义 \(\mathrm{Border}(s)\) 为对于 \(i \in [1, |s|)\)，满足 \(\mathsf{pre}_i = \mathsf{suf}_i\) 的字符串 \(\mathsf{pre}_i\) 的集合。\(\mathrm{Border}(s)\) 中的每个元素都称之为字符串 \(s\) 的 \(\operatorname{border}\)。 有 \(m\) 组询问，每组询问给定 \(p,q\)，求 \(s\) 的 \(\boldsymbol{p}\) 前缀 和 \(\boldsymbol{q}\) 前缀 的 最长公共 \(\operatorname{border}\)...

洛谷P4316 绿豆蛙的归宿 题解 题目链接：P4316 绿豆蛙的归宿 题意： 给出张 \(n\) 个点 \(m\) 条边的有向无环图，起点为 \(1\)，终点为 \(n\)，每条边都有一个长度，并且从起点出发能够到达所有的点，所有的点也都能够到达终点。 绿豆蛙从起点出发，走向终点。 到达每一个顶点时，如果该节点有 \(k\) 条出边，绿豆蛙可以选择任意一条边离开该点，并且走向每条边的概率为 \(\frac{1}{k}\) 。现在绿豆蛙想知道，从起点走到终点的所经过的路径总长度期望是多少？ 输入格式： 输入的第一行是两个整数，分别代表图的点数 \(n\) 和边数 \(m\)。 第 \(2\) 到第 \((m + 1)\) 行，每行有三个整数 \(u, v, w\)，代表存在一条从 \(u\) 指向 \(v\) 长度为 \(w\) 的有向边。 输出格式： 输出一行一个实数代表答案，四舍五入保留两位小数。 数据范围： 保证 \(1 \leq n \leq 10^5,~1 \leq m \leq 2 \times n,~1 \leq u, v \leq n,~1 \leq w \le...

洛谷P4550 收集邮票 题解 题目链接：P4550 收集邮票 题意： 有 \(n\) 种不同的邮票，皮皮想收集所有种类的邮票。唯一的收集方法是到同学凡凡那里购买，每次只能买一张，并且买到的邮票究竟是 \(n\) 种邮票中的哪一种是等概率的，概率均为 \(1/n\)。但是由于凡凡也很喜欢邮票，所以皮皮购买第 \(k\) 次邮票需要支付 \(k\) 元钱。 现在皮皮手中没有邮票，皮皮想知道自己得到所有种类的邮票需要花费的钱数目的期望。 输入格式： 一行，一个数字 \(N\)（\(N \le 10000\)）。 输出格式： 输出要付出多少钱，保留二位小数。 直接求花费比较麻烦，因为不知道确切次数什么的。 俗话说，概率要顺推，期望要逆推。 考虑设 \(f_i\) 表示取了 \(i\) 种邮票，取完剩下的期望次数。显然 \(f_n = 0\) 。 \[ f_i = \frac{i}{n}\times f_i + \frac{n-i}{n} \times f_{i+1} + 1 \] 解下方程就是 \[ f_i = f_{i+1} + \frac{n}{n-i} \] 设 \(g_i\...

洛谷P1850 [NOIP2016 提高组] 换教室 题解 题目链接：P1850 [NOIP2016 提高组] 换教室 题意： 对于刚上大学的牛牛来说，他面临的第一个问题是如何根据实际情况申请合适的课程。 在可以选择的课程中，有 \(2n\) 节课程安排在 \(n\) 个时间段上。在第 \(i\)（\(1 \leq i \leq n\)）个时间段上，两节内容相同的课程同时在不同的地点进行，其中，牛牛预先被安排在教室 \(c_i\) 上课，而另一节课程在教室 \(d_i\) 进行。 在不提交任何申请的情况下，学生们需要按时间段的顺序依次完成所有的 \(n\) 节安排好的课程。如果学生想更换第 \(i\) 节课程的教室，则需要提出申请。若申请通过，学生就可以在第 \(i\) 个时间段去教室 \(d_i\) 上课，否则仍然在教室 \(c_i\) 上课。 由于更换教室的需求太多，申请不一定能获得通过。通过计算，牛牛发现申请更换第 \(i\) 节课程的教室时，申请被通过的概率是一个已知的实数 \(k_i\)，并且对于不同课程的申请，被通过的概率是互相独立的。 学校规定，所有的申请只能在学...

洛谷P1654 OSU! 题解 题目链接：P1654 OSU! 题意： osu 是一款群众喜闻乐见的休闲软件。 我们可以把osu的规则简化与改编成以下的样子: 一共有 \(n\) 次操作，每次操作只有成功与失败之分，成功对应 \(1\) ，失败对应 \(0\) ，\(n\) 次操作对应为 \(1\) 个长度为 \(n\) 的 01 串。在这个串中连续的 \(X\) 个 \(1\) 可以贡献 \(X^3\) 的分数，这 \(X\) 个 \(1\) 不能被其他连续的 \(1\) 所包含（也就是极长的一串 \(1\) ，具体见样例解释） 现在给出 \(n\) ，以及每个操作的成功率，请你输出期望分数，输出四舍五入后保留 \(1\) 位小数。 输入格式： 第一行有一个正整数 \(n\) ，表示操作个数。接下去 \(n\) 行每行有一个 \([0,1]\) 之间的实数，表示每个操作的成功率。 输出格式： 只有一个实数，表示答案。答案四舍五入后保留 \(1\) 位小数。 数据范围： \(1 \le n \le 10^5\) 显然期望dp。但是这个贡献不太好计算。 因为它是一个整体去算的，...

洛谷P1297 [国家集训队]单选错位 题解 题目链接：P1297 [国家集训队]单选错位 题意： gx 和 lc 去参加 noip 初赛，其中有一种题型叫单项选择题，顾名思义，只有一个选项是正确答案。 试卷上共有 \(n\) 道单选题，第 \(i\) 道单选题有 \(a_i\) 个选项，这 \(a_i\) 个选项编号是 \(1,2,3,\ldots,a_i\)，每个选项成为正确答案的概率都是相等的。 lc 采取的策略是每道题目随机写上 \(1 \sim a_i\) 的某个数作为答案选项，他用不了多少时间就能期望做对 \(\sum_{i=1}^n \frac{1}{a_i}\) 道题目。gx 则是认认真真地做完了这 \(n\) 道题目，可是等他做完的时候时间也所剩无几了，于是他匆忙地把答案抄到答题纸上，没想到抄错位了：第 \(i\) 道题目的答案抄到了答题纸上的第 \(i+1\) 道题目的位置上，特别地，第 \(n\) 道题目的答案抄到了第 \(1\) 道题目的位置上。 现在 gx 已经走出考场没法改了，不过他还是想知道自己期望能做对几道题目，这样他就知道会不会被 lc 鄙视了...

洛谷P3802 小魔女帕琪 题解 题目链接：P3802 小魔女帕琪 题意： 从前有一个聪明的小魔女帕琪，兴趣是狩猎吸血鬼。 帕琪能熟练使用七种属性（金、木、水、火、土、日、月）的魔法，除了能使用这么多种属性魔法外，她还能将两种以上属性组合，从而唱出强力的魔法。比如说为了加强攻击力而将火和木组合，为了掩盖弱点而将火和土组合等等，变化非常丰富。 现在帕琪与强大的夜之女王，吸血鬼蕾咪相遇了，夜之女王蕾咪具有非常强大的生命力，普通的魔法难以造成效果，只有终极魔法：帕琪七重奏才能对蕾咪造成伤害。帕琪七重奏的触发条件是：连续施放的 \(7\) 个魔法中，如果魔法的属性各不相同，就能触发一次帕琪七重奏。 请注意，无论前 \(6\) 个魔法是否已经参与施放终极魔法，只要连续 \(7\) 个魔法的属性各不相同，就会再触发一次终极魔法。例如，如果用序号来代表一种魔法，魔法的施放序列为 \(1, 2, 3, 4, 5, 6,7, 1\)，则前 \(7\) 个魔法会触发一次终极魔法，后 \(7\) 个魔法会再触发一次终极魔法。 现在帕琪有 \(7\) 种属性的能量晶体，第 \(i\) 种晶体可以施放出...

洛谷P4438 [HNOI/AHOI2018]道路 题解 题目链接：P4438 [HNOI/AHOI2018]道路 题意： W 国的交通呈一棵树的形状。W 国一共有 \(n-1\) 个城市和 \(n\) 个乡村，其中城市从 \(1\) 到 \(n-1\) 编号，乡村从 \(1\) 到 \(n\) 编号，且 \(1\) 号城市是首都。道路都是单向的，本题中我们只考虑从乡村通往首都的道路网络。 对于每一个城市，恰有一条公路和一条铁路通向这座城市。对于城市 \(i\)， 通向该城市的道路（公路或铁路）的起点，要么是一个乡村，要么是一个编号比 \(i\) 大的城市。没有道路通向任何乡村。除了首都以外，从任何城市或乡村出发只有一条道路；首都没有往外的道路。从任何乡村出发，沿着唯一往外的道路走，总可以到达首都。 W 国的国王小 W 获得了一笔资金，他决定用这笔资金来改善交通。由于资金有限，小 W 只能翻修 \(n-1\) 条道路。小 W 决定对每个城市翻修恰好一条通向它的道路，即从公路和铁路中选择一条并进行翻修。小 W 希望从乡村通向城市可以尽可能地便利，于是根据人口调查的数据，小 W 对...

洛谷P1613 跑路 题解 题目链接：P1613 跑路 题意： cxy 买了一个空间跑路器，每秒钟可以跑 \(2^k\) 千米（\(k\) 是任意自然数）。 当然，这个机器是用 long long 存的，所以总跑路长度不能超过 \(2^{63}-1\) 千米。 cxy 的家到公司的路可以看做一个有向图，cxy 家为点 \(1\)，公司为点 \(n\)，每条边长度均为一千米。 cxy 想每天能醒地尽量晚，所以让你帮他算算，他最少需要几秒才能到学校。 数据保证 \(1\) 到 \(n\) 至少有一条路径。 输入格式： 第一行两个整数 \(n,m\)，表示点的个数和边的个数。 接下来 \(m\) 行每行两个数字 \(u,v\)，表示一条 \(u\) 到 \(v\) 的边。 输出格式： 一行一个数字，表示到公司的最少秒数。 数据范围： \(n \le 50,~m \le 10000\)，最优解路径长度 \(\le 2^{63}-1\)。 倍增好题。注意到贪心不一定是最优的，因此考虑dp。 设 \(g_{i,j,k}\) 表示 \(i,j\) 之间是否存在恰好 \(2^k\) 的路径，...