题解p9858 2008 cold

传送门 前排提醒：本篇题解没有使用压位和快速幂，运用了一种预处理的思想，希望能提供一种新的思路。 首先将 \(2^{p}-1(d)\) 转换为 \(1111…111(b)\)。 关于第一问： 我们先考虑 \(2\) 进制转 \(8\) 进制，将每 \(3\) 位转为 \(1\) 位，即每 \(\lo ......

传送门 题目大意： 一个 \(n\) 个叶子节点，一个节点最多可以有 \(k\) 条边连向子节点，每个节点 \(i\) 有一个权值 \(P_{i}\)。记每个节点子树内点的个数（不包括它自己）为 \(son_{i}\)，那么每个节点对答案的贡献就是 \(son_{i}^2 \times P_{i}\ ......

传送门 首先可以将题意大概可以简化为：取两端不重复的连续子序列，组成一个最长的连续递增子序列。 我们先 dp 预处理出以 \(i\) 为结尾的连续递增子序列长度 \(dpr_{i}\)。 同样预处理出以 \(i\) 为开头的连续递增子序列长度 \(dpl_{i}\)。 考虑对于每个 \(dpr_{i ......

题解 Codeforces Round 901 (Div. 1) / CF1874A~E 比赛情况：过了 AB。赛后发现 B 是假复杂度。 https://codeforc.es/contest/1874 A. Jellyfish and Game Problem Alice & Bob 又在博弈， ......

思路 题目要求的是 \(\max_{a = 1}^{n}\{\sum_{i = 1}^{a}\sum_{j = 1}^{a}{A_j}\}\)，所以我们将 \(\sum_{i = 1}^{a}\sum_{j = 1}^{a}{A_j}\) 化简一下，得： \[i \times A_1 + (i - ......

思路 首先我们可以发现，在任意一个节点数量大于 \(1\) 的强连通分量中的点都满足条件。 所以，我们可以对这张图跑一边 TarJan。 但是这样是错的，因为我们还需要考虑节点数量为 \(1\) 的强连通分量。 如果这种连通分量能够到达任意一个节点数量大于 \(1\) 的强连通分量，那么，这个连通分 ......

题意 传送门 有一个长度为\(n\)的歌单，问最长多少首歌互不相同？ 每首歌用一个\(1-10^9\)的整数表示。 样例输入 8 1 2 1 3 2 7 4 2 样例输出 5 算法 双指针算法。桶思想。 对于歌单中重复出现的数，可以用桶来存储。 定义两个指针i,j，i指向大数，j指向小数。当出现某个 ......

题目链接 先将所有作业按位置排序。 直接贪心显然是不行的，因为我们没有办法确定对于一个时间较久的作业，是在原地等待，还是在未来的某个节点返回，并且无法确定是那个节点，所以只能考虑 \(dp\)。 对于此类可以倒来倒去的问题，通常考虑区间 \(dp\)，若设 \(f_{i,j}\) 表示完成区间 \( ......

题目传送门 简化题意 有 \(t\) 组询问，每次询问是否能从 \(1 \sim n\) 中选择 \(k\) 个数使得它们的和为 \(x\)。 解法 考虑临界情况，从 \(1 \sim n\) 中选择最小的 \(k\) 个数时和为 \(\sum\limits_{i=1}^k i=\dfrac{(k+ ......

题目大意 题目大意 给定一个 \(n\) 个点和 \(m\) 条边的有向图，并给定 \(p_1, p_2, \cdots, p_n\) 表示第 \(i\) 个点的拓扑序必须小于等于 \(p_i\)，求出每个点的最小拓扑序。 题解 题解 题目要求拓扑序尽量小，转换一下就是在反图上拓扑序尽量大。考虑拓扑 ......

好可恶一道题，怎么没人告诉我输出之间有空行（ 思路是先抽象成图，然后跑一边dfs记录边的前后顺序。 对于不能成环的情况，只需要再开个数组记录度数判断奇点即可。 若存在奇点则break掉，剩下的跑dfs、 //produced by miya555 //stupid mistakes:1.多测要清空 ......

找点图论练习题写，发现hdu又寄了，那就发到blog里吧。 思路：tarjan缩点判断DAG中点数是否为1。若是，则该图为强连通图。 //produced by miya555 //stupid mistakes:多测记得清空 //ideas:tarjan模板 #include<bits/stdc+ ......

题目链接 首先可以想到设状态 \(k_1,k_2\) 表示小 \(a\) 和小 \(uim\) 分别表示他们目前取得的得分，那么最终的答案便是 \(k_1=k_2\) 的时候。 但是这样设置状态的复杂度无疑是高的。并且十分浪费，所以考虑设 \(z\) 表示 \(k_1-k_2\) 的值。那么 \(z ......

题目传送门 前置知识 快速幂 解法 推式子： \(\begin{aligned} Z_n+Z_{n-1}-2Z_{n-2}&=(Z_n-Z_{n-2})+(Z_{n-1}-Z_{n-2}) \\ &=(S_n+Q_n-S_{n-2}-Q_{n-2})+(S_{n-1}+Q_{n-1}-S_{n-2} ......

Problem 考察算法：拓扑排序 + \(DP\) + \(Dijkstra\)。 题目简述 给出一个无向无权图，问从顶点 \(1\) 开始，到其他每个点的最短路有几条。 思路 先求出 \(1\) 号点到每个点的最短路 \(d_i\) 。 分析每条边 $(x,y) $： 如果 d[x] + 1 = ......

Problem 题目概述 给你一个无向图，边权都为 \(1\) ，求：离 \(1\) 号点最远的点的编号、最远的距离、有几个点是离 \(1\) 号点最远的。 思路 直接用：优先队列 \(BFS\)，先求出 \(1\) 号点到每个点的最短路，存到 \(dis\) 数组中，然后再求 \(max(dis[ ......

我咕咕咕了这道题半年之久？ 好像洛谷好多题解都被 hack 了啊。 （本题解现有 hack 均通过） 题目链接 折叠题干 [POI2008] PER-Permutation 题目描述 Multiset is a mathematical object similar to a set, but ea ......

Codeforces Round 699 & 772题解 今天手感确实不错，看来合理的训练配合合理的休息是很重要的。前些日子的努力没白费。不过，怎么说呢，现在的形势不是我把算法题和基础知识做好的就行了，该从系统的角度去作为一个ld去思考问题了，感觉自己还是有点欠缺的，不过我也在积极努力的学习中，希望 ......

[POI2003] Monkeys 题解 正着做貌似不好做，发现猴子是否掉落取决于“最后一根稻草”，也就是最后撒手的那个猴子，那我们考虑倒着把猴子网拼回去。这样，每群猴子掉落的时刻就是与 \(1\) 号猴子连通的时刻。 利用并查集可以维护猴子的连通性，但是怎么更新答案呢？这里用 vector 进行了 ......

Problem 题目概括 $n \times m $ 的网格，有些格子是障碍格。\(0\) 无障碍，\(1\) 有障碍。机器人有体积，总是在格点上。 有5种操作： 向前移动 \(1/2/3\) 步 左转 \(/\) 右转 每次操作需要 \(1\) 秒。 求从 \(x_1,y_1\) 到 \(x_2, ......

Problem 考察知识点：二分、贪心。 题目描述 对于给定的一个数组，现要将其分成 \(M\) 段，并要求每段连续，且每段和的最大值最小。 思路 二分答案出每段和最大值的最小值，然后贪心检验是否满足。 难点在 \(check\) 上。 策略：每次开始循环，如果没有超范围，就一直选，知道选满为止，求 ......

题意 给定一个有向无环图，对于任意一条边 \((u_i, v_i)\)，有 \(u_i < v_i\)。 定义一次从节点 \(u\) 开始的移动为如下过程： \(\tt{Alice}\) 选择从 \(u\) 出发的且未被删除的一条边。 \(\tt{Bob}\) 在从 \(u\) 出发的且未被删除的边 ......

题目传送门 前置知识 单调栈 简化题意 在一个 \(n \times n\) 的正方形内找到最大的由 \(0\) 组成的子矩形的面积。 解法 令 \(f_{i,j}(1 \le i,j \le n)\) 表示从 \((1,j)\) 到 \((i,j)\) 中以 \((i,j)\) 结尾的均为 \(0 ......

题目大意 题目大意 给你 \(n\) ( \(1\leqslant n\leqslant 5\cdot 10^5\) ) 条线段 \([l_1, r_1], [l_2, r_2], \cdots, [l_n, r_n]\) ( \(1\le l_i < r_i\le 2n\) )。保证每条线段的端点 ......

题目大意 给出一个大小为 \(n\) 的树，\(q\) 次询问，每次给出一个大小为 \(m\) 的点集，判断是否有一条链覆盖这些点（这条链可以经过其他点）。 \(n,\sum m\leqslant 2\cdot 10^5\) , \(q\leqslant 10^5\)。 提示 提示 1 思考将 $m ......

这场的G怎么这么毒瘤啊/kk 听说正解是DP？我爆搜头一个表示不服！ statement 找出三元组 \((S, a, b)\) 的数量，使得 \(S\) 在 \(a\) 进制下和在 \(b\) 进制下的差为 \(X\) ，其中 \(0 \leq S_i <(min(a, b, 10))\) 。 首 ......

A. Two Vessels Problem 题目 Sol & Code 签到题 #include <bits/stdc++.h> typedef long long ll; int min(int a, int b) { return a < b ? a : b; } int max(int a, ......

题意 已知 \(m\) 个坏素数 \(b_i\)，定义一个数 \(x\) 的分值 \(f(x)=f(\frac xp)+k\)，其中 \(p\) 为 \(x\) 的最小质因数，如果 \(p\) 为坏素数则 \(k=-1\)，否则 \(k=1\)，初始 \(f(1)=0\)，一个数组的分值为其中所有数 ......

打篇题解巩固一下。 题意 给你两个集合 \(A\) 和 \(B\)，对于任意 \(A\) 集合中的元素，我们可以进行 \(2\) 种操作：\(a_i\gets \left\lfloor\frac{a_i}{2}\right\rfloor\) 或 \(a_i\gets 2\times a_i\)。问最 ......

题目传送门 前言 中文题目可以看 link 。 前置知识 Kruskal 重构树 | 最近公共祖先 简化题意 给定一个 \(N\) 个点 \(M\) 条边的有向图，共有 \(S\) 次询问，每次询问从 \(L\) 到 \(H\) 所有的路径中最小的权值的最大值（多组数据）。 本题即最大瓶颈路问题。 ......