题解atcoder agc 004

题目传送门 前置知识 快速幂 解法 推式子： \(\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[ ......

洛谷传送门 AtCoder 传送门 考虑若 \(n\) 是奇数怎么做。枚举 Alice 第一次选的数 \(a_i\)，然后考虑把剩下的数两两结成一个匹配，若 Bob 选了其中一个，Alice 就选另一个。容易发现排序后奇数位和它右边的偶数位匹配最优。那么设奇数位的和为 \(A\)，偶数位的和为 \( ......

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

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

AtCoder Beginner Contest 178 E E - Dist Max 曼哈顿距离最大点对 \(ans = max(|x_i-x_j|+|y_i-y_j|)\) 考虑去绝对值，4种情况。sort一下取max即可。 #include <bits/stdc++.h> using name ......

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 - First ABC 2 解题思路 签到 Code #include <bits/stdc++.h> using namespace std; typedef long long LL; void solve() { int n; cin >> n; string s; cin >> s; i ......

打篇题解巩固一下。 题意 给你两个集合 \(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\) 所有的路径中最小的权值的最大值（多组数据）。 本题即最大瓶颈路问题。 ......

题目传送门 前言 本题样例有问题，如果想要样例可以去 vjudge 上。 本题提交后可能会出现 UKE ，建议前往 link 提交，而且本篇题解中所提供的代码也为 link 代码。 前置知识 Kruskal 重构树 | 最近公共祖先 简化题意 给定一个 \(N\) 个点 \(M\) 条边的有向图，共 ......

显然，除非 \(\operatorname{mex}a=0\)，否则不会删除 \(>\operatorname{mex}a\) 的数。而 \(\operatorname{mex}a=0\) 时不对答案产生贡献，因此任意时刻我们都可以忽略 \(a\) 中 \(>\operatorname{mex}a\ ......

Key idea: For a given box and a list of balls that can be placed in this box, we should choose the ball with the smallest R. Proof: say we have box B ......

A - First ABC 2 (abc322 A) 题目大意 给定一个字符串，找到最先出现ABC的位置。 解题思路 直接查找判断即可。 神奇的代码 #include <bits/stdc++.h> using namespace std; using LL = long long; int mai ......

\(N,M\le 1e7\) 接着反射容斥，考虑这道题怎么做 如果去枚举不动步数，加上反射容斥，直接T飞了 把-1/0/1操作转换一下，就成了0/1/2 如果没有限制（不能<0或>m），n步方案就是\((1+x+x^2)^n\) 设\(H=1+x+x^2\quad F=H^n\) 那么对两边求导： ......

第四周题解 7-1 根据后续和中序遍历输出先序遍历 利用数组保存树的后序遍历和中序遍历，根据后续遍历和中序遍历的特点还原树，并根据先序遍历的顺序，即根左右，利用函数递归输出打印，注意输出格式的正确性。 #include<bits/stdc++.h> using namespace std; cons ......

Description 给定 \(n\) 个从上往下圆心重叠的圆盘，给定每个圆盘的直径 \(d_i\) 和容量 \(c_i\)，所有圆盘底下有一个容量为 \(\infty\) 的水池，编号为 \(0\)。\(q\) 次询问，每次给定 \(r\) 和 \(v\) 表示往第 \(r\) 个圆盘里倒 \( ......

【题解】CF1110D Jongmah 代码很短，但是思路我怎么也想不到的神仙 DP。 题意概述 你在玩一个叫做 Jongmah 的游戏，你手上有 \(n\) 个麻将，每个麻将上有一个在 \(1\) 到 \(m\) 范围内的整数 \(a_i\)。 为了赢得游戏，你需要将这些麻将排列成一些三元组，每个 ......

目录题目翻译题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1样例 #2样例输入 #2样例输出 #2样例 #3样例输入 #3样例输出 #3题目简化题目思路AC代码 题目翻译 【题目描述】 你决定用素数定理来做一个调查. 众所周知, 素数又被称为质数，其含义就是除了数字一和本身之外不能被其 ......

题解 SS230928C【构造】 https://notes.sshwy.name/Math/Linear-Algbra/LP-and-its-Dual/ 线性规划好题 problem 有一个 \(n\) 个点 \(m\) 条边的有向图，你需要给每个点赋一个整数权 \(val_i \in [1, n ......

blog。严重怀疑这题放到 2023 年至少 *2000，评绿合情合理。 首先是博弈论。然后数据范围很小。直接暴力 DP 啪的一下上去了，很快啊！ 这就抽象起来了。另一篇题解说不能暴力转移，但是你先预处理出来 \(num(s)\)，然后直接记忆化搜索，暴力枚举每一次操作的字符，这不就做完了吗。 具体 ......