题解atcoder agc 004

[题目链接](https://www.luogu.com.cn/problem/T355166) 首先考虑没有修改怎么做。 两种做法。 想到询问的形式为保留 $\ge k$ 的连通块个数，那么先将全部数字按照权值排序，然后从后往前做一遍并查集，并同时统计连通块的数量，在询问时只需二分找到第一个 $\ ......

## 题目描述 [here](https://www.luogu.com.cn/problem/CF1666A)。 ## 题解 赛时得分：60/100。 想到了正解，但调不出来，就改写暴力了。。。 首先，我们把问题转化成每个点都入度为 $1$。 我们考虑合法子串只有两种形式： 注意到 `U` 和 ` ......

题目传送门：[P3203 [HNOI2010] 弹飞绵羊](https://www.luogu.com.cn/problem/P3203) # 题意 $n$ 个数，满足 $i #define int long long using namespace std; const int N = 2e5 + ......

posted on 2022-10-08 19:07:28 | under 题解 | [source](https://www.luogu.com.cn/blog/_post/488777) ## problem 交互库有一个长为 $n$ 的颜色序列，你可以询问区间 $[l,r]$ 中有多少种颜色， ......

[link](https://www.luogu.com.cn/problem/CF1051G) 首先可以发现，题目给定的两种操作为我们提供了“反悔机制”，所以有： 结论 $1$：即任何一个可以到达的局面都能到达最优解。 利用这个结论，首先我们先去重。 继续提炼性质，与相差不到 $1$ 的数为基准 ......

下大分！悲！Div 1 只过了 1A！！！ 但还是补完整场 Div 2 吧。 # A. Desorting ## problem 用操作：$[1,i]++,[i+1,n]--$，使得数组不单调不降，求最小操作次数。$n\leq 10^5$。 ## solution 操作等同于在差分数组上选出 $i$ ......

## UOJ #284. 快乐游戏鸡题解（长链剖分+单调栈合并） ### [题面](https://uoj.ac/problem/284) 一番战斗之后，程序猿被计算鸡们赶走了。随着垫子计算鸡一声令下：“追！”，于是计算鸡村全村上下开始乘胜追击。计算鸡们希望在新的一年到来之际给程序猿以重创，出掉这一 ......

~~好一道博弈论水题~~ [题目传送门](https://www.luogu.com.cn/problem/CF1738C) [更好的食用体验](https://www.luogu.com.cn/blog/878137/cf1738c-ti-xie) ## 题目大意： 给定长度为 $ n $ 的数列 ......

Translated by [DeepL](https://www.deepl.com/translator) with my manual modification. Firstly, there is no solution if and only if $B_i\equiv0$ and the ......

首先，我们知道，有一种最小化$T$的通用方法：逐位确定。 这道题可以这么做，然后使用dp判定合法性。 然而这样子没什么前途，需要挖掘这道题的性质。 首先我们会发现：设$S$最小的字符为$x$，$S$有$k$个$x$，这为$T$的前$k$个$x$可以作为$T$的$k$位，而这显然是最优解。 因为我们可 ......

**出处：** Codeforces Round 887 **链接：** https://codeforces.com/problemset/problem/1852/B **题目大意：** 给定一个包含 $n$ 个非负整数的频次序列 $f$ 。 构造任意一个等长的整数序列 $b$ ，要求 ① $b ......

## Solution 设 $g(x)$ 表示 $x$ 的最小**质因子**。 则 $f(x)=n+\dfrac{n}{g(x)}=\dfrac{g(x)+1}{g(x)}\times n$。 分情况讨论： - $g(x)=2$，经过 $1$ 次变换之后，$f(x)$ 增加了一个因子 $3$，减少了 ......

https://codeforces.com/contest/1852/problems # A. Ntarsis' Set https://codeforces.com/contest/1852/problem/A 感觉不是很一眼。 $n$ 和 $k$ 都是 $2 \times 10^5$，~~不 ......

**出处：** Codeforces Round 887 **链接：** https://codeforces.com/problemset/problem/1852/A **题目大意：** 给定一个包含 $n$ 个正整数的表示删除位置的严格升序序列 $p$ ，以及另外一个连续正整数的被删除的无穷序 ......

[洛谷传送门](https://www.luogu.com.cn/problem/AT_agc040_e "洛谷传送门") [AtCoder 传送门](https://atcoder.jp/contests/agc040/tasks/agc040_e "AtCoder 传送门") 比较神奇的题。 考 ......

[洛谷链接](https://www.luogu.com.cn/problem/AT_abc246_d)&[Atcoder 链接](https://atcoder.jp/contests/abc246/tasks/abc246_d) 本篇题解为此题较**简单做法**及**较少码量**，并且码风优良， ......

posted on 2022-10-08 22:03:07 | under 题解 | [source](https://www.luogu.com.cn/blog/_post/488890) 神仙 min-cut，果然，flow 题的难点是想到 flow，非 flow 题的难点是不要想到 flow。 ......

[problem](https://www.luogu.com.cn/problem/P7831) & [blog](https://www.cnblogs.com/liangbowen/p/17577222.html)。 妙妙题。单杀了，来写篇题解。 下文中 $ans_u$ 表示从 $u$ 点出发 ......

[洛谷链接](https://www.luogu.com.cn/problem/AT_abc218_d)&[Atcoder](https://atcoder.jp/contests/abc218/tasks/abc218_d) 本篇题解为此题较**简单做法**及**较少码量**，并且码风优良，请放心 ......

[洛谷链接](https://www.luogu.com.cn/problem/AT_abc215_d)&[Atcoder 链接](https://atcoder.jp/contests/abc215/tasks/abc215_d) 本篇题解为此题较**简单做法**及**较少码量**，并且码风优良， ......

## A. Desorting ### Problem [题目](https://codeforces.com/problemset/problem/1853/A) ### Sol & Code 若序列一开始无序答案为 $0$ 若有序即 $a_1\leq a_2 \leq \dots \leq a_ ......

题目链接 Card Collector - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 思路 将每一行、每一列转化为点，第i行第j列的卡牌转化为i->j+m（m为行数）的有向边。 总共会抽取m+n（m为行数，n为列数）张牌，每个点的出度为1。结果图为基环森林； 那么题目就转化为求最 ......

## [牛客小白月赛47](https://ac.nowcoder.com/acm/contest/62254 "牛客小白月赛47") ## [A. 牛牛的装球游戏](https://ac.nowcoder.com/acm/contest/62254/A "A. 牛牛的装球游戏") ### 标签 ` ......

[洛谷链接](https://www.luogu.com.cn/problem/AT_abc180_d)&[Atcoder 链接](https://atcoder.jp/contests/abc180/tasks/abc180_d) 本篇题解为此题较**简单做法**及**较少码量**，并且码风优良， ......

VP战报：1h 过了 A,B,C,D 然后被 E 罚坐 1h rank：210th 题解只有 A-E ## A.Forbidden Integer ### 题目描述： 你需要构造一个正整数序列，满足： 1. 对于 $i$，$a_i\le k$ 且 $a_i\not=x$。 2. $\sum a_i= ......

# Toyota Programming Contest 2023#4（AtCoder Beginner Contest 311） ## [A - First ABC (atcoder.jp)](https://atcoder.jp/contests/abc311/tasks/abc311_a) * ......

题目中的式子转化一下即存在一位 $i$ 使得到 $i$ 时的后缀和存在 $X + Y + Z, Y + Z, Z$，再发现 $X + Y + Z\le 17$，考虑状压。 设 $f_{i, j}$ 为填了 $i$ 个数当前后缀和中存在的数的状态为 $j$（只存 $0\sim X + Y + Z$ 的 ......

[洛谷传送门](https://www.luogu.com.cn/problem/AT_abc311_g "洛谷传送门") [AtCoder 传送门](https://atcoder.jp/contests/abc311/tasks/abc311_g "AtCoder 传送门") 考虑一维怎么做。 ......

发现 $(i, j)$ 若为黑色则就会有一个 $(i, j)$ 为最高点的阶梯形的图形被染黑（阶梯形指对于 $1\le i\le x$ 第 $i$ 列第 $x - i + 1$ 行及以下都是黑色）。 那么能发现其实每个列只需要记录最高的黑色点行数即可，因为及其以下的点肯定都是黑色。 考虑设 $f_{ ......

可以想到枚举最小值同时算出包含其的最大矩阵和。 考虑枚举行的上下界，再枚举最小值然后求出最大的列的范围，因为 $a_{i, j}\ge 1$ 列的范围越广矩阵和也越大。 考虑如何算出列的范围，令第 $i$ 列在选中的行的范围内的最小值为 $mn_i$，则对于 $mn_i$ 的列 的范围 $[l, r ......