题解 做法133f abc

题目链接 依然枚举每个位置作为最小值的情况，记录“值/下标”二元组，按第一维从大到小排序后，每次将第二位的位置在序列中标成 \(1\)，那么选择的一定是序列里一个 \(1\) 的极长段。加入一个位置检查其左右是否加入过，如果加入过就用并查集合并掉，同时维护极长段的和/左右端点是简单的，复杂度 \(\ ......

[NOIP2022] 建造军营 题解 Part I 观察 注意到如果删掉的边在一个边双连通分量里面，那么无论如何都不会影响 A 国，所以 B 国只会删掉桥，于是把图边双缩点之后，同一个边双里面的点要么都不选，要么随便选至少一个。 Part II DP 再次发现军营一定是一个极大的连通块，所以可以考虑 ......

Archaeology 有一颗带权树，有三个操作： 给一个点打上标记。 删除一个点的标记。 查询有标记的点的导出子树的边权和。 \(n, q \le 10^5\)。 求的实际上就是虚树的大小，求这个有一个常用的方法就是把点按 dfn 排序后相邻点对（首尾也算相邻）之间的距离和除以 2。 所以我们可以 ......

### 题意 给出一串数，请尝试在这串数中找到三段**连续**的子段，使得这三个子段的和分别为 $P$、$Q$ 和 $R$。问：是否可行？ ### 思路 通过观察，观察我们可以发现，其实我们可以根据题目的要求写出一段关系式： $A+P+Q+R+B$（其中 $A$ 表示被选子段前面没被选的子段和，其中 ......

这道题的思路非常简单，经过对样例的分析，我们发现，所有区间的总和为： $\sum_{i = 1}^{n} a_i \times d_i $（其中 $a_i$ 为原数组的第 $i$ 项，$d_i$ 为第 $i$ 个元素被区间覆盖的次数） 这里有一个小细节：对于某一个元素被覆盖的次数我们可用差分进行优化 ......

题意 给出一串数，请问，通过将 \(a_i\) 和 \(a_{i+1}\) 同时加 \(1\) 或减 \(1\)若干次，能否使它单调不减？ 思路 我们发现，如果要让 \(a_i\) 和 \(a_{i - 1}\) 满足单调不减，可以通过修改 \(a_i\) 和 \(a_{i+1}\) 让 \(a_i ......

这个小丑看了好久题目才发现保证 \(t\) 不降。 好像与其他题解做法稍有不同。 思路 其他题解的标记做法非常复杂，怎么办。 我们可以使用适用性可加强大的矩阵乘法。 我们考虑维护： \[\begin{bmatrix} \sum v&\sum a\times b&\sum a&\sum b&len\\ ......

https://atcoder.jp/contests/abc327/tasks/abc327_f 我们将时间看作x轴，位置看作y轴，那么我们随着时间增加，维护新加的点对区间的贡献，同时减去过时的点，线段树区间加法维护最大值即可。 #include<cstdio> #include<algorith ......

B - Round-Robin Tournament 难度: ⭐ 题目大意 给定n个字符串, 每个字符串的长度为n; 如果第i个字符串的第j个字符为'o', 说明i在比赛中赢了j, 如果是'x', 则是j赢了i; 最后按照赢比赛的数量从多到少进行排序; 解题思路 暴力即可; 神秘代码 #includ ......

题意 给你一个数组 \(a1,a2…an\) 请计算有多少个四元组 \((i,j,k,l)\) 符合以下条件: \(1 <= i < j < k < l <= n\) \(a_i=a_k \ \&\&\ a_j=a_l\) \(4<=n<=3000,1<=a_i<=n\) \(input\) 2 5 ......

题目链接 题意简述 给定一个正整数 \(N\)，将它的因数分解式按规定输出。 题目分析 模拟题意即可。 具体地，我们可以枚举 \(2\) 到 \(\lfloor \sqrt N \rfloor\) 中所有数 \(i\)，如果 \(i\) 能整除 \(N\)，则不断地从 \(N\) 中除掉 \(i\) ......

洛谷 AT 完全图的最小生成树是不好求的，但是发现 \(\mathcal{O}(n^2)\) 级别的边中显然有很多都是没有用的，这种时候可以考虑分治。 显然如果对 \(E'(E'\in E)\) 求 MST，没有选择的边一定也不在最后的 MST 的边集中。于是就让选出的边集的并等于原图，然后再求一遍 ......

https://www.luogu.com.cn/problem/UVA10422 A*做法 双倍经验 只能说一摸一样，就是在输入输出上不一样，因为有空格所以建议使用getline之类的输入方式 很显然这题我们不能去移动骑士，那我们就移动空格，而移动空格的方法就是移动马的方法（横1竖2或者竖1横2） ......

CF1436E Complicated Computations mex的定义是：一个区间中没有出现过的数中最小的整数。 对于一个区间，当正整数x在区间中没有出现过、[1, x - 1]（整数）在区间中全部出现过，那么正整数x就是该区间的mex 正整数x在区间中没有出现过 我们一共有n个数字，所有的 ......

[APIO2012] 派遣 题目背景 在一个忍者的帮派里，一些忍者们被选中派遣给顾客，然后依据自己的工作获取报偿。 题目描述 在这个帮派里，有一名忍者被称之为 Master。除了 Master 以外，每名忍者都有且仅有一个上级。为保密，同时增强忍者们的领导力，所有与他们工作相关的指令总是由上级发送给 ......

去年今时，我得了 100 + 0 + 0 + 8 分，太抽象了 QwQ 所以为什么今天才写这个东西？因为今天才做完了 T2…… [NOIP2022] 种花 简单前缀和优化 DP，不谈。 [NOIP2022] 喵了个喵 非常高级的构造题。 看到 \(k = 2n - 1/2\)，我们可能会想到每一个栈 ......

基本概括 当解决这个问题时，我们需要找到满足条件的整数 \(k\)，使得对于给定的序列 \(A=(A_1,A_2,\dots,A_N)\) 中的每个数 \(A_i\)，都满足 \(\gcd(A_i, k) = 1\)。 实现思路 首先，我们可以观察到，如果 \(k\) 是 \(A_i\) 的质因数或 ......

洛谷。 题面 初始状态为全是 \(0\)，将某一为变化的前提是当前节点的前缀（不包括当前节点）是 \(s\) 串的一个后缀，每次变化需要 \(1\) 的代价。问最后要使所有都为 \(1\) 的最小代价。 分析 很有意思的一道题，感觉玩起来跟喵了个喵一样上头。 首先，我们肯定是要先让 \(n\) 这个 ......

大家好，我是毒瘤，喜欢用玄学算法过题。 发现题解区没有这个做法，于是来发一篇。 思路 首先发现如果一个点对 \((u,v)\) 的距离为 \(d\)，那么在这棵树以 \(u\) 为根时，\(v\) 的深度为 \(d\)。 Code ......

原题链接 连 \(S\to A_i\)，流量 \(D_i\)，费用 \(P_i\)，表示最多进货 \(D_i\)，成本为 \(P_i\)。 连 \(A_i\to T\)，流量 \(U_i\)，费用 \(0\)，表示卖出。 连 \(A_i\to A_{i+1}\)，流量 \(+\infty\)，费用 ......

洛谷。 题意 应该好理解的。 分析 我们的所有雪球在同一时间之间的距离都是相同的，因此一段雪，要么是它左侧的第一个所取，要么右侧第一个所取，要么不被取，并且，我们每一个雪球所占有的雪是连续的一段。 我们令 \(L_i\) 表示第 \(i\) 步前所能走的最左点，\(R_i\) 表示第 \(i\) 步 ......

题意 一棵 \(n\) 个结点的树，根节点为 \(1\)，结点 \(i\) 的父亲是 \(f_i\)。\(f_1=f_0=0\)。对于每一个整数 \(i\)，假如 \(f_{f_i}\) 不为 \(0\)，那么就将 \(f_{f_i}\) 与 \(i\) 连上一条边。从每一个结点，每次随机向相邻的结 ......

题目一 简单模拟题 点击查看代码 #include<bits/stdc++.h> using namespace std; #define ebk emplace_back #define x first #define y second typedef pair<int,int> PII; typ ......

第八周 算法题解笔记 1极值点 题目描述 给定一个单峰函数f(x)和它的定义域，求它的极值点 该单峰函数f(x)保证定义域内有且只有一个极值点，且为极大值点 题解 本题感觉和dp关系不大，主要思路是三分法，和二分法非常类似，但没有二分法常用，主要用途是用来求单峰函数的极值 对于任意一个上凸函数，选取 ......

P5522 [yLOI2019] 棠梨煎雪 题解 题目链接 分析1 抛开时间复杂度不谈，先来看看对于每次询问，如何计算合法的字符串个数。 对于每次询问的 \([l,r]\)，我们可以对字符串的每一位按以下种情况讨论（设讨论的这一位为第 \(i\) 位）： \(str[l..r][i]\) 既有 0 ......

题意 给定一个 \(N\) 个点，\(M\) 条边的简单无向图，每个节点有两个值 \(A_i\) 和 \(B_i\)。 现对于每个节点，均可以选择花费 \(A_i\) 的代价将其删去或保留节点。若一个节点被删除，那么所有与其向连的边也会被删除。 定义一个极大联通块的权值为联通块内所有节点的 \(B_ ......

题目描述： 芷萱姐姐有一个长度为 \(N\) 的数列 \(A_i\)。 你可以进行若干次，最多 \(N-1\) 次操作，选择相邻的两个数，删去他们，并在原位置放上他们两个的和。 现在你需要求出可能产生的序列个数。 数据范围： \(1 \le N \le 2 \times 10^5\) \(|A_i| ......

B - 11/11 难度: ⭐ 题目大意 在某个世界一年有n个月, 每个月有di天, 问有多少个日期, 该日期和月份组成的数字都是一样的; eg: 11月的1日, 22月的22日; 解题思路 暴力就行; 神秘代码 #include<bits/stdc++.h> #define int long lo ......

[NOI2010] 超级钢琴 题目描述 小 Z 是一个小有名气的钢琴家，最近 C 博士送给了小 Z 一架超级钢琴，小 Z 希望能够用这架钢琴创作出世界上最美妙的音乐。 这架超级钢琴可以弹奏出 \(n\) 个音符，编号为 \(1\) 至 \(n\)。第 \(i\) 个音符的美妙度为 \(A_i\)，其 ......

三倍经验 P1931 UVA436 SP9340 题意 给你 \(n(n \le 30)\) 种货币及 \(m\) 种汇率，问是否出现套利的情况。 怎么没给 \(m\) 的范围啊 思路 首先把汇率抽象成一张图。容易发现，若一个单位的某种货币经过一个环获得了大于一的代价，说明出现了套利。具体来说，考虑 ......