Arkweedy's Blog

ABC377 G - Edit to Match (3rd) (挺简单的，不过看来得好好学一下字符串算法了) 相关算法： 字典树 Part 1.题目概述 按顺序给出\(N\)个字符串，对于每个字符串，有两种操作，代价均为1： 1. 删掉最后一个字母 2. 在最后加上任意一个字母 求让每个字符串变成前面任一字符串或者空串的最小代价。 Part 2.分析 由于对第 \(i\) 个串 \(S\) 处理时，要考虑前面 \(i-1\) 个串的匹配问题，很自然想到对前面的串建一棵字典树(trie)。建立字典树时，我们同时记录每个节点到叶子节点的最小距离，那么我们遍历 \(S\) 时，很容易就可以统计出答案。 Part 3.实现 第一次写字典树，前后写了很多很dirty的代码。最后是用链表实现的trie，感觉比数组慢了不少。 对于插入操作，我们递归建树，同时返回与叶子节点的距离，以更新父节点与叶子节点最短距离的信息。对于查询答案的操作，我们遍历字符串，用 \(f[p]\) 表示删除 \(S\) 为字串...

ABC379 G - Count Grid 3-coloring (2nd) (G题之间亦有差距) 相关算法 : dp,枚举，复杂度估计 Part 1.题目概述 一个 \(n \times m\) 的矩阵，里面只有 \(1，2，3，?\),其中 \(?\) 为不确定的数。问有多少种可能使矩阵相邻元素不相同。其中 \(n\cdot m <= 200\)。 Part 2.分析 我们考虑从上到下从左到右逐格dp来确定每格的不同状态可能的情况。 dp设计 设 \(dp[i][val]\) 为填到第 \(i\) 个格子值为 \(val\)...

ABC378 G - Everlasting LIDS (1st) (是每日一寄的开始，虽然好像做不到每日一寄啦) 相关算法：序理论，杨表，钩长公式，dp Part 1.题目概述 题意很简单，给定限定\(A,B\)，要求构造出长为\(A\cdot B-1\)的且具有以下性质的排列\(P\)： 1. 最长上升子序列(LIS)为\(A\). 2. 最长下降子序列(LDS)为\(B\). 3. 存在一个整数\(n\)使得在\(P\)的末尾添加\(n+0.5\)不会改变最长递增子序列和最长递减子序列的长度 求可行的构造方案数，结果输出方案数模素数\(M\)。 Part 2.杨表 解决这题需要一些前置知识：杨表 英式画法的杨表由有限个相邻的方格排列而成，其中，各横行的左边对齐，长度从上到下递增。 标准杨表：在杨表的 n个方格中任意填入1到n中的相异正整数，各行和各列中的数字皆严格递增。 显然，杨表代表着一种二维表示的偏序。而这种拓扑序可以与一个排列的LIS和LDS相关联。 引入RSK算法(杨表的插入算法)： 令 \(S\) 是一个杨表，定义 \(S...

Gym入口 Preface 和小木虫一起vp的，赛后补了队友独立写出来的题以及赛时尝试开的两道金牌题。 题解顺序： M-J-D-H-G-F-B M. V-Diagram 签到题，题意大概是给定一个V型数组，取一个最大平均值的子V型数组。 赛时WA了两次后才得到了正确思路。 首先，V型数组至少有3个元素，而且要求是子数组，那么可以去掉的只有两端不与极小值直接相邻的部分。 可以考虑贪心，如果我们要去掉一端的一部分，那么去掉那端全部不与极小值相邻的元素一定是最优的。(因为我们去掉一端时，是先去掉大的再去掉小的，那么要去掉一定是全部去掉) 而贪心一个一个去是不可取的，因为可能去掉一个元素会让平均值减小，但是去掉那一整段又可以让平均值变大。 而去掉两端一定是劣的(这样把较大的值全全去掉了) 故答案为不去，去掉左端可以去掉的部分，去掉右端可以去掉的部分三者平均值中取最大值。 code: 1234567891011121314151617181920212223242526272829303132333435363738void solve(){ ...

比赛入口 C 很简单，建图找一下最远点即可。 不过因为点值比较离散，所以用map存邻接表(cf传统艺能卡ump，所以还是不用的好)。 code: 12345678910111213141516171819202122232425262728293031void dfs(map<ll, vector<ll>>& nxt, map<ll, bool>& vs, ll p, ll &ans){ vs[p] = true; ans = max(ans, p); for (auto s : nxt[p]) { if (!vs[s] && s != 0) { dfs(nxt, vs, s,ans); } }}void solve(){ int n; cin >> n; vector<ll>a(n + 1); for...

比赛入口 C 为了无后效性，我们对每一对可交换的数对，只计算交换对外层的影响(干扰度是否会减少)。而交换是相对的，所以对该层外层的操作与否也不会影响该层内层是否相对该层进行交换 (也就是说我们不需要真的去交换，只计数即可)。 所以做法即为贪心，我们如果发现交换可以使该层对外层的干扰数减少，那就使ans减去这个差值。任意次序遍历数组(比如说由外到内)均可，毕竟层与层之间没有影响。 code: 1234567891011121314151617181920212223242526272829void solve(){ int n; cin >> n; vector<int>a(n + 2); int sum = 0; for (int i = 1; i <= n; i++) { cin >> a[i]; if (a[i] == a[i - 1]) sum++; } vector<int>k(n +...

2014 G. Milky Days 实际上是一道模拟题， 我们定义关键天为牛奶数目可能会非因为喝掉而改变的那天。 利用一个deque去处理关键天时能否供给牛奶即可 则关键天为 \(\min(最近牛奶过期天，下一个获得牛奶的天)\) 我们一边求解答案一边算下一个关键天是哪个 假设关键天序列为\(a_0,a_1,a_2,a_3...\) 初始化\(a_0 = 1\) 由于一个关键天到下一个关键天前,牛奶只会被喝掉而不会过期、增加，那么我们就可以\(O(1)\)处理掉这一段了。 于是我们的算法是： 1. 算出下一个关键天\(a_{i+1}\) 2. 处理区间\([a_i,a_{i+1}-1]\)...

C. Lazy Narek dp即可； 不过一定要好好读题才行！！ 就是读题读假了和不仔细，才导致vp赛时没有调出来。 这个dp的优化(或者是自然而然的处理)：数组开1维5个位置即可，不需要对m轮全部开一个位置，否则会tle。状态转移时记得滚动，不要在原数组上面改，否则会出问题(可能跑出来同一层选了两次的结果) D. Alter the GCD analysis 前缀和后缀和gcd自然不用多说。逐一枚举\(\{l，r\}\)即使每次枚举求值是\(O(1)\)也会tle。所以要寻求更好的方法求解。 由于一个数的质因子最多只有\(\log n\)个，考虑gcd prefix是单调非升的，那么有如下性质： 只有最多\(\log n\)个位置 \(i\) 使 $ prefix[i] > prefix[i+1] $ ,其余均为 \(prefix[i] = prefix[i+1]\) 对suffix gcd类似。 那么实际上，绝大多数前后缀gcd是相等的。...

D Robert Hood and Mrs Hood 赛时对l,r分别进行了排序,来测算是否有事件进入，实际上这是没有必要的。 可以直接用一个桶来记录。buc[l]--,buc[r+1]--即可。 不难，时间复杂度为\(O(n)\) E - Rendez-vous de Marian et Robin 赛时魔改dijkstra没有改出来(实际上应该也很难改出来) 赛后了解到分层图，直接开悟 做法是对每个节点，建图建一个有马节点，一个无马节点，有horse的节点就让无马节点向有马节点连边。对于给出的边，有马图和无马图同步建图。最后跑一遍Dijkstra就行。 F -...

1988D. The Omnipotent Monster Killer 由于只有相邻节点之间才有影响，树形dp即可。 权值每次至少减半，故杀死所有怪物的轮数不会超过\(\log n\)轮，相邻节点删去的轮数不同。 在有根树上dp，\(dp[i][j]\)代表在节点i在第j轮删除时，节点\(i\)子树的最小贡献。 状态转移： \(dp[i][j] = \sum_{v\in S_i}\min(dp[v][k]),k \neq j\) 1977E. Level Up 线段树+二分 第一次用自己写的线段树板子，爽捏。 对于每个位置，大于最小答案的每个k的取值都可以满足要求，故可以二分答案。check是计算答案为k时，前面的最小答案在1-k区间内的个数(即获得的exp)，然后按照题意判断即可。 一定要注意整型溢出的问题！！！ (因为在check的时候，使用了mid*a[i]与exp比较大小，而mid*a[i]是可能溢出的。) (当然，可以直接比exp/mid 和a[i]) 核心代码：...