AGC

开始重新板刷 AGC。别惦记着你那 b 多项式了！然后发现我做题量太少了。 现在思维强度不太上档次，T1 都能挂一个星期。 都干嘛呢？看了一圈，洛谷没人提交（除了 H_Kaguya 写了个左偏树），vjudge 也没人交题，真都写 APIO 呢？那咋 T1 没人交？ ## [AGC013A] Sor ......

> 给定 $n$ 个点的树，求其点分树的最小可能的深度。 > > $n\leq 10^5$。 第一个想法是，直接枚举分治中心，然后分裂成若干个连通块，递归下去。这就是个状态数是连通块子图数量的 DP，模拟赛可能能写个记忆化骗个分啥的，正解就不用想了。 我们发现这样正常做完全没思路。我们必须转化，我们 ......

### [AGC001] #### A.[BBQ Easy](https://www.luogu.com.cn/problem/AT_agc001_a) 由于最大数肯定要和一个比自己小的数搭配保留该数，不如选择保留次大数，如此递归即解。因此将序列排序后输出序号为奇数的数即可。 #### B.[Mys ......

# [AGC040B] Two Contests 挺难的。首先有一个搞笑的想法，最长的一个区间单独划分一个集合，可扩展性不是很强。 猜一下最后可能是怎样的，我写了个按照 $l$ 排序取前缀后缀，然后再结合上面的乱搞一下，只过了一半的点，不妙。 但是前缀后缀的思路还可以沿用，注意到写出来的式子里面有 ......

[[AGC049D] Convex Sequence](https://www.luogu.com.cn/problem/AT_agc049_d) > 给定整数 $n$ 和 $m$，问有多少个长为 $n$ 的非负整数数列 $A$，满足以下条件： > > - $A_1+A_2+\ldots+A_n = ......

好可怕。 AtCoder 的一贯风格，先找合法序列的充要条件，然后 DP 计数。 首先把数组排序，这个显然。 先找显然的必要条件。首先 $b_i \in [i,2n - i]$，这个比较显然。 然后发现加数很不好考虑，我们考虑倒过来删数。每次删两个数，不难发现中位数只会不变或向左 / 向右移动一位。 ......

好久之前模拟赛就考过的题，今天才写） 首先发现我们跳跃的次数只有 $\log V$ 次，我们设跳了 $i$ 次后的时刻为第 $i$ 时刻，且最后一个时刻为 $t$。发现每一时刻，我们能够到达的绿洲形成了若干个连续段。不难发现，当时刻 $0$ 的时候连续段数量大于 $t + 1$ 时一定全部都无法到达 ......

好。 首先考虑怎么计算方案数。我们考虑按照 $a_i$ 从小往大选，设排序后的下标为 $b_i$，那么容易得出方案数为： $$ s = \prod_{i=1}^n (a_{b_i} - i + 1) $$ 我们设 $c_i = a_{b_i} - i + 1$，这代表着某个数的选择方案数。 然后考虑 ......

【关键字】 AGC、applinking、崩溃 【问题描述】 开发者反馈在应用中集成了AGC的applinking服务，在打开app时遇到了一些问题。具体如下所述： 在接入app linking后，从浏览器中访问短链接，能正常唤起app, 但app启动后就崩溃了，崩溃日志如下： ​ 配置如下： 1. ......

$\mathtt{Description}$： 给定 $n$ 和一个长度为 $2^n$ 的数组 $A$ (从 $0$ 标号). 有一个初始为 $0$ 的变量 $x$ . 不断操作, 每次操作以 $\frac {A_i}{\sum_{j=0}^{2^n-1} A_j}$ 的概率将 $x$ 变成 $x\ ......

每次碰到折线计数的题都不会做啊！怎么回事。 首先考虑将问题转换成在一个 $n \times m$ 的网格上走，从 $(n, m)$ 到 $(0, 0)$。首先最优策略肯定是哪个多选哪个，放到这个图上来说就是对于 $y=x$ 这条直线下面的点都向左选，上面的都向下选，直线上方的点可以任意选。我们钦定向 ......

~~想了一会然后看题解，翻到日文题解然后又关了，然后突然会了，怎么回事~~ 第一眼生成函数！做不了。 考虑经典拆贡献方法，把平方的贡献变成从区间中选两个数的方案数。这样我们可以用一个 DP 来计数。 设 $f_{i, j}$ 表示到了第 $i$ 格，已经选了 $j$ 个数的方案数。如果没有限制，那么 ......

笑了，题意转换的思路大致都是对的，不知道为啥猜成与题解结论完全相反的结论了。 首先考虑将这个过程看做是一棵满 $k$ 叉树，其中有 $n + m$ 个叶子，$n$ 个叶子为 $0$，$m$ 个叶子为 $1$。不难发现，如果一个 $1$ 的深度为 $x$，那么它对最后的数造成的贡献为 $\frac{1 ......

​ 【关键字】 AGC、质量、数据分析 【问题描述】 开发者反馈在应用中集成了AGC的相关服务，在查看平台数据时遇到了一些问题。具体如下所述： 我发现平台的App卸载量每个月都非常高，卸载量/新下载量近80%，很异常，所以想要咨询两个问题： 1、中国的电商行业平均的卸载率 benchmark 是多少 ......

本来想写一个有关思维过程的题解，写出来却成了这样一个怪胎，大家当个乐子看。 最近回顾了一下 Picks loves segment tree IX，然后终于会做这题了，其实两题在思维上有很大的相似之处。 核心思想是划分阶段的问题。 分析一下 $+1$ 的操作，应该怎么考虑： 看作 bitxor 一段 ......

T1签到题。 [AGC030B] Tree Burning 高桥湖是周长为 $L$ 的一个首尾相接的圆，圆上整点标为$0, 1, 2, ..., L-1$. 在湖边有 $N$ 颗树，分别在距离起点顺时针数 $X_1, X_2,...,X_n$ 的位置上。保证位置 $0$ 没有树。 高桥君初始在位置 ......

感觉之前那样所有比赛都写在一个页面里没有一点趣味性。于是之后每做一套都写一篇。 之前做到 10 就没做了，现在直接从 30 开始做。 A 直接算，简单。 B 有一个一眼想到的贪心：直接顺时针逆时针做。但是很显然是错了。但是猜一个结论：只有最开始会固定一个方向地走。写了一发然后就对了。 这个感觉就很对 ......

a,b是签到题。 [AGC020C] Median Sum 一个集合由N个整数组成，请求出它的非空子集和的中位数。（$N<=2000$ $A_i<=2000$） 发现所有的子集和是关于所有数的和对称的。即有 $X$ 则有 $\sum{A_i} - X$，于是通过背包优化的bitset算出所有能拼出的 ......

$$也想养老鼠捏$$ 先把当前要解决的点旋转到位置 $n$，问题不变。求 $n$ 次即可。 我们先来看两个没有结果的解法。 一就是一 我们先考虑暴力 $dp$，设 $dp_{i,mask}$ 表示当前已经安放了 $i$ 个奶酪，被喂饱的老鼠的集合为 $mask$ 的概率。容易发现 $i$ 其实就是 ......

~~abcd都是签到题~~ [AGC021E] Ball Eat Chameleons 有 $n$ 只变色龙，一开始都是蓝色。现在你喂了 $k$ 次球，每次指定一只变色龙吃下你指定颜色的球。 一只变色龙从蓝色变成红色当且仅当它吃的红球比蓝球多； 一只变色龙从红色变成蓝色当且仅当它吃的蓝球比红球多。 ......

尝试考虑 $n=1,n=2,n=3$ 的必败必胜条件，寻找一些结论，但是发现即使是 $n=3$ 胜负情况已经有些不可描述了，说明我们必须尝试转化问题的形式。 注意到操作是全局减，常见的转化是差分，但是差分后的操作仍然没有优秀的性质。 继续思考，可以得到一个恰当的转化：注意到游戏结束当且仅当最大值 $ ......

abcd签到题，暂且不提。 [AGC002E] Candy Piles 桌上有 $n$ 堆糖果，第 $i$ 堆糖果有 $a_i$ 个糖。两人在玩游戏，轮流进行，每次进行下列两个操作中的一个: 将当前最大的那堆糖果全部吃完 将每堆糖果吃掉一个 吃完的人输，假设两人足够聪明，问谁有必胜策略？ 输出 Fi ......

首先观察这个奇怪的子树为 $1$ 或 $-1$ 的限制。 看不出来性质，润了。 我们不如直接把 $A$ 树和 $B$ 树拆开，变成两棵树，然后在树上留一下匹配的性质。 第一，我们对着样例构造一下，发现似乎有解的样例都有 $abs(X_i)\le 1$ 的解。 这就提示我们猜用 $-1,0,1$ 就够 ......

首先，我们来思考我们要构造的是什么。 我们要构造的是一个无论怎样操作字典序都会变小的序列，且这个序列的字典序是最小的。 然后考虑字典序会变大的条件。 如果字典序变大了，那么一定是在前 $i-1$ 位不变的前题下，$i$ 位的变大了。那么变大的一定是从后面来的。 而我们考虑所有的数对 $(a_i,a_ ......

首先，我们来证明一个引理： 若最优解中，最终串中的字符 $j$ 在最早来自原串中的字符 $i$（显然，$i\le j,s_i=t_j$），则称 $j$ 的匹配是 $i$，则在所有的匹配方案中，$t_j$ 会在全串存在匹配的前提下尽量选择 $|i-j|$ 最小的的 $s_i$ 进行匹配。 我们可以运用 ......

AGC质量是真的高啊 [AGC001A] BBQ Easy 史努克在参加一个BBQ派对， 他要准备N组食物， 他有2N的食材， 需要两两组成一个食物， 食物的价值是两食材中较小的那个。 问最大总价值是多少 签到题。 点击查看代码 #include<bits/stdc++.h> using names ......

【关键字】 AGC、插件、gradle 【问题描述】 开发者反馈在应用中集成了AGC的相关服务，在引入AGC插件时遇到了一些问题。具体如下所述： 目前最新的AGC插件版本com.huawei.agconnect:agcp:1.8.0.300只适配到了gradle 7.0+，想咨询什么时候会适配gra ......

人类智慧。 答案显然具有可二分性，考虑如何check。 我们使用调整法，不妨设 $x_n<y_m$ （反着做同理），一开始我们令 $x_i=1,y_i=+\infty$。每次我们期望让 $x$ 不断变大，$y$ 不断变小，不断将它们调整到当前的上下界。具体的，每次令 $x_i=\max {x_i, ......

[AGC007A] Shik and Stone 有一个纵 $ H $ 行，横 $ W $ 列的格子状棋盘。开始时，棋盘左上角的格子有一个马（不是象棋意义的马）。Shik 将会操纵它上下左右移动，从而到达右下角的格子。此时，马能够经过同一个格子多次（含左上角和右下角的格子）。 给出 $ H $ 行字 ......

不难的题，但是突然就不会分析复杂度了！脑子出了些什么问题。 首先考虑题目中要求一条边恰好经过两次，那么也就是说每进入一个子树，那么就必须把子树内的所有点探索完后再去另一个子树，那么这个问题就显然是可以递归处理的了。 具体来说，对于每一个子树 $u$，都存在若条路径 $u \to v$，然后当子树合并 ......