洛谷：P3811 【模板】乘法逆元 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 推导过程 保证 模数P 为一个质数。 代码 / code

比赛传送门：(5条未读通知) 牛客小白月赛48_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ (nowcoder.com) 比赛感受 C过题数居然还没D高，不过C我也卡了很久，我理解错题意了。 A - 孤独的数组 根据题意不难看出答案只能是0或者-1，因为两个原本互质的数字不可能通过乘一个正整数k使得他们不互质。 所以就是判断是否存在不互质的数字对即可。 代码 / […]

题目传送门：生活在树上 (nowcoder.com) 题目描述 请看原题。 这里介绍两种思路。 思路一 将点 i 当作根，父节点、子节点都当作子节点。 只要建立一个双向边的图就可以完成。相当于先把树建立起来，再把某个点i拉出来作为根，那么这又可以形成一颗新的以i为根的树。 那么每个点能够到达的点就是每个点的孙子节点。 在输入的时间将d = 2的边直接加到答案中，d = 1的记录边，d > 2的全部 […]

参考资料：有什么浅显易懂的Manacher Algorithm讲解？ - 知乎 (zhihu.com) 背景 / Background 1975年，一个名叫Manacher的人发明了一种用O(N)的时间复杂度来解决“最长回文子串”问题的方法。但是网络上对Manacher本人的介绍却很少见。他最大的贡献就是将回文串算法从O(N ^ 2)优化到O(N)。 算法简介 / Introduce to the […]

本题没有传送门，就把题目写清楚吧。 碎碎念 在考场上这道题没想出来，真是寄了。一直在想LCA，然后想dfs，最短路。后面想利用树的性质，怎么都想不出。 思路 先考虑每个点都要走一次且回到起点的情况，那就是每个点往上走，每条边都要走两次。这个可以类比dfs的过程，每条边都要走到两次才能保证回到起点。 由于本题要求无需回到起点，所以用路程减去一个最大深度（最长的一条链）就是答案。 比如这个图，我要从起 […]

题目传送门：Problem - C - Codeforces 题目大意 有N个店，每天有X元，每个店 i 每日限购1件，第一天价格为 ai。每个店每天都涨价1元（第一天是原价）。问最终一共最多可以买多少个东西。多组测试用例。 思路 买东西嘛，肯定是越便宜越好（Greedy贪心）。所以先将所有价格排序，在进行一次前缀和，现在第i天购买前j个店的所有商品总价为prefix[j] + i * j。 这时 […]

题目传送门：Problem - D - Codeforces 题目大意 有 T 组数据，给定长度为 N 的序列 A。 求符合同余条件的连续子序列的最长长度。 同余是指序列中任意两个数字Ai Aj都有同一个确定的 M 使得A i == Aj (mod M)，M >= 2。 思路 通过题意不难想到同余定理：数论中的重要概念。给定一个正整数m，如果两个整数a和b满足a-b能够被m整除，即(a-b) […]

题目传送门：F - Cards (atcoder.jp) 题目大意 给定N张牌，每张牌有两个数字Pi和Qi，所有的牌中P和Q构成两个[1, N]的排列。现在从N张牌中选出任意张牌，请问有多少种选法，使得选出的牌拥有所有[1, N]的数字。 思路 这题看视频吧，有点繁琐不好写。 [AtCoder Beginner Contest 247]简单易懂 A - F算法竞赛刷题记录_哔哩哔哩_bilibil […]

题目传送门：E - Max Min (atcoder.jp) 题目大意 给定N，X，Y和一个长度为N的序列。 求该序列中最大值为X，最小值为Y的连续子序列的数量。 PS：以下所讲的子序列均指连续子序列。 思路 一开始没想到是容斥原理，看了Jinagly大佬的代码才豁然开朗。 函数getRangeOf(X, Y)返回最小值大于等于Y，最大值小于等于X的子序列的数量。 那么根据容斥原理，我们要得到最小 […]

题目传送门：D-造桥_牛客小白月赛47 (nowcoder.com) 题目大意请看原题。 思路 每一个零件相当于一条边，边权为字符串长度，起点是第一个字符，终点为最后一个字符。 我们用dp[i]表示以字符i结尾所能得到的最长的桥的长度，那么就有状态转移方程： 全部更新完成之后，从dp['a'] ~ dp['z']中选出最大输出的即可。 代码