题解atcoder agc 004

P3533 [POI2012] RAN-Rendezvous 题目大意：给定外向树森林，每次给定两个起始点，求两个点沿边移动最少步数相遇。 \(n\) 个点，\(n\) 条边，并且每个点有唯一的出边，显然构成了多棵基环树，对于每个基环树分别处理：找出环上的点，因为要求支持求出任意两点距离，前缀和一下 ......

思路分析 前言 题解区好似没有用哈希的啊。 发现大家都在用 map 来存是否出现过数字，但是需要注意的是，map 的单次查询时间复杂度是 \(\mathcal O(\log n)\) 的，对于大规模的数据就很可能会 TLE。所以，我们可以使用哈希的方法来判断数字是否出现过。 浅谈哈希 哈希，是通过哈 ......

A.Two Towers 题目描述： 有 \(a,b\) 两座由红蓝色方块垒成的塔,其中 \(a\) 的高度为 \(n\) ； \(b\) 的高度为 \(m\) ，用 R 代表红色；用B代表蓝色。 你可以多次把其中一座顶端的方块移到另一座的顶端（可以不移动）。问有没有一种方法可以使两座塔中均没有连续 ......

思路分析 前言 又是一道小模拟题，不过细节巨多，可以用来锻炼自己的代码能力。 解法 本题实际上就是模拟长除法的计算过程，其中每一步除法时都有被除数及其余数，当被除数出现重复时就表示出现循环节了。所以需要记录每一次的被除数及其在循环小数中的位置，需要判断当除数不够除，每一次补零也需要记录其对应的位置。 ......

题目链接 要想使得数字 \(x\) 是中位数，就必须选出 \(k\) 个小于 \(x\) 的数和 \(k\) 个大于 \(x\) 的数。 我们考虑对数字附上特殊值，小于 \(x\) 的数赋值为 \(-1\)，大于 \(x\) 的数赋值为 \(1\)，\(x\) 则赋值为 \(0\)，那么若一段包含 ......

Codeforces Round 895 (Div. 3) F~G F. Selling a Menageri 考虑如何让卖出的价格翻倍，那么自然是从 \(i \to a_i\) 。通过这样连边，我们可以发现，边集构成了基环树森林。显而易见的是，如果不考虑环，那么图就是拓扑图，按照拓扑关系跑一遍，就 ......

思路分析 前言 一道比较简单的数学题。 解法 根据题意可以推算出最大值 $v=\Big(1-\dfrac{1}{2{M+1}}\Big)\times2{2{E-1}}=A\times10B$。因为两边都比较大，所以可以同时求以 $10$ 为底的对数：$\lg v=\lg(2{M+1}-1)-(M+1 ......

洛谷题目链接 AT原题 考虑构造出来的序列 \(a\) 的特征，因为每次会给 \(a_i\) 加 \(1\)，\(a_j\) 加 \(2\)，所以每次操作后 \(\sum a_i\) 会加上 \(3\)。 所以有\(\sum a_i =3m\) 。 又因为每次操作只给一个数加 \(1\)，所以每次操 ......

Problem StatementSnuke got positive integers $s_1,...,s_N$ from his mother, as a birthday present. There may be duplicate elements. He will circle som ......

CF29D Ant on the Tree 题目知识点：LCA。 题目传送门 题意 给定一棵以 \(1\) 为节点的树，再给定树的所有叶子节点的一个序列。 现在执行一个操作：从 \(1\) 开始遍历每个节点，并返回根，要求每条边经过的次数一定为 \(2\) 。 问是否能够使得访问节点序列中叶子节点的 ......

题目大意： 给定一些指令，计算需要多大的舞台。 这是一道大模拟！！！ 只要遍历每次指令，然后判断是否摔倒，摔倒输出`-1`否则记录，最后求出面积就行了。 最后附上代码 1 #include <bits/stdc++.h> 2 using namespace std; 3 const int xx[] ......

题意 给定一个环形 01 序列，每次变化时，对于每个位置，如果前一个值是 1 ，则当前值翻转。求变化 B 次后的序列。 思路 由于 B 的值很大，所以如果对每一次变化进行模拟，效率非常低下。 不难发现，每一次变化后的状态完全是由当前状态决定的，而 N 的范围很小，所以可能的状态总数 2^N 也不是很 ......

一道递推 由于对于一个数 x ,可得 x+10-x=10（废话） 于是问题就变成了 0+m 次,然后 x+m 就变成 0+x+m （还是废话） 于是可以写一个递推。 首先对于函数 f(m) 可分为 m ≤ 9 和 m>9 ,然后可得出递推式结果为 1 或 f(m-9)+f(m-10) ，所以我们可以 ......

康了康唯一的题解，说没必要用DP，我就给出DP的解法。 这其实是道水题，唯一的坑是有可能楼上没有开的灯，坑了我们机房的一堆人（ WA on test 4 ），剩下的就是DP。 我们用 a[n][0],表示第 n 层的第一个房间，用 a[n][1]，表示第 n 层的最后一个房间。 这里提供一个收集型的 ......

## 主要题意：有 $n$ 个礼物，要两两合并，然后除以 $k$ 最后求和最大。 ## 思路：先加入每个数除以 $k$ 的商（单独组成 $k$ 的个数），然后全部 $ \bmod \ k$ 存入数组，排序，最后双指针一个前一个后求两个余数可以大于等于 $k$ 的两个礼物。 ## 代码： ```cpp ......

## 主要题意：> 有 $n$ 个任务，必须在 $s_i$ 到 $t_i$ 之间完成，求每个任务最大可以完成多久（优先前面的最大）。## 思路> 就拿一个变量记录当前时间，然后贪心选择 $a[i].t$ 和 $ a[i + 1].t$ 中的最小值，（应为至少也要给下一个任务留 $1$ 的时间），最后 ......

【题解】[ABC318G] Typical Path Problem 题目链接 G - Typical Path Problem 题意概述 给定一个 \(n\) 个点 \(m\) 条边的无向连通图。 给定三个该图上的不同顶点 \(A,B,C\)，问是否存在一条从 \(A\) 到 \(C\) 的简单路 ......

### [题目链接](https://www.luogu.com.cn/problem/P1419) ## description 给定一个长度为 $n$ 的序列（值域为 $[-10^4,10^4]$）和正整数 $st,ed$。 求一个区间，使得其长度 $\in [st,ed]$ 且平均值最大，输出 ......

根据题意，我们可以发现这是一道树形 dp。首先考虑设计状态，注意到 $k$ 较小，那么我们可以在 dp 数组里面塞一维来维护特殊颜色点的个数。然后题目里有颜色编号的大小限制，所以第三维用 $0/1/2$ 来分别表示当前颜色小于/等于/大于 $k$ 的情况。那么这样的话就是用 $f_{i,j,0/1/ ......

需求：三个和尚的身高需要手动输入，请用程序实现这三个和尚的最高身高。 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(Sys ......

你考虑对于每一条边打上时间标记，然后在树上 `DFS` 的时候维护一下以 $u$ 为根的答案即可，然后将答案合并，反正很简单，看代码就懂。 **code:** ```cpp #include using namespace std; const int NN = 2e5 + 8; int t,n; ......

你考虑我们需要构造出一组解，显然地这样的解有很多很多种（${60^{60}}$ 显然是及其地大）。 那关键是我们如何进行构造。 我们很容易知道每个集合里面 $> 30$ 的数只有一个。 所以我们可以在 $[1,30]$ 中随机 $a_i$，直到满足的组数恰好小于等于 $a_i$，添加的时候维护数组 ......

> 交互题。 > > 考虑题意即为找到 $1$ 所在内向基环树上的所有点。 我们考虑我们怎么找到环上的点，我们考虑我们可以 $O(\log n)$ 询问到一个环上的点，方法即为将 $k$ 定为一个大数，然后二分点集。然后我们便可以在 $O(n\log n)$ 的时间复杂度内找到所有环上的点（我们一会 ......

# [AGC058D] Yet Another ABC String [Atcoder：[AGC058D] Yet Another ABC String](https://atcoder.jp/contests/agc058/tasks/agc058_d) [洛谷：[AGC058D] Yet Ano ......

你考虑，我们如果没有重合就将元素删去的操作，我们就有答案：$n \times (m+1) - \sum\limits_{i=1}^n a_i$ 但是，我们显然最后的答案是小于这个的，如果有两个数在 $i$ 相撞，那么我们的答案就会减少 $(m-i+1)$ 我们设 $f_{i,j}$ 表示两个数分别在 ......

## [AGC051D] C4（2807） ### Problem 有一张 $4$ 个点 $4$ 条边的简单无向连通图，点的编号分别为 $1,2,3,4$ ，边分别连接着 $e1:(1,2),e2:(2,3),e3:(3,4),e4:(4,1) $。 给定 $4$ 个数 $v_1,v_2,v_3,v ......

评价：感觉这场题目质量不咋地啊，都是一些乱搞题 ## A.Make M ### 题目描述： $N$ 是一个正奇数。我们称一个长度为 $N$ 的序列 $S$ 是 **M 型**序列，当前仅当对于所有的 $i=2,4,6,\dots,N-1$（即偶数位），都有 $S_{i-1}S_{i+1}$。 现在给 ......

你考虑，我们很容易地可以构造一个 $n^2$ 的 `DP`： - $f_{i,j}$ 表示当前在 $i$ 张牌，还可以摸 $j$ 张牌的最大分数。转移也很好转移，你考虑一眼就会。 但是我们显然要缩减复杂度，我们看到数据范围 $10^5$，想到了根号。 分块？？？显然不行。莫队？？？都没有区间查询，怎 ......

一、题目描述： 给你一颗 $n$ 个点的树，有 $m$ 组询问。 一个点如果被攻占，那么这个点就不能通行了。 第 $i$ 次询问给出 $k_i$ 个关键点，关键点不能被攻占。 求最少攻占多少个点可以使得关键点两两不连通。若不可能，输出 $-1$。 数据范围：$1\le n,m\le 1\times ......

# [arc124_e](https://www.luogu.com.cn/problem/AT_arc124_e) 一种方案的权值为 $\prod\limits_{1\leq i\leq n} b_i$，考虑其组合意义，就是每个人在自己最终的球中选一个。 可以发现要么拿自己原来的球，要么拿上一个人 ......