题解atcoder agc 004

## A.New Palindrome ### 题目描述： 给你一个由小写字母组成的回文字符串，问你是否能在重排其之后构造出另一个与原串不同的回文字符串。 多测，$t \le 1000,2 \le |s| \le 50$ ### 题目分析： 考虑其实就是前 $\lfloor \frac{n}{2} ......

~~好像并没有**矩阵快速幂**的题解，那我来写一篇~~ ## 题目分析 ### 对于每两盏灯，只考虑右灯变化，分为四种情况： 左灯为 $1$，右灯为 $1$，右灯变为 $0$； 左灯为 $0$，右灯为 $0$，右灯不变，为 $0$； 左灯为 $1$，右灯为 $0$，右灯变为 $1$； 左灯为 $0 ......

思路前几篇题解都介绍了，这里着重介绍一个状态设计的小技巧。 在设计状态时，我们可能会碰到**状态数值过大，而dp数组内存的值较小**的情况。 例如在该题用 $dp_{l,r,t,0/1}$ 表示逆时针经过 $l$ 个，顺时针经过 $r$ 个，已经花费 $t$ 秒，所拿到的雕像个数，$0$ 表示当前在 ......

模拟赛做到的题，赛后看了 Y2hlbnlpa2Fp 的题解，感觉没讲清楚，这里做下补充，提供自己的理解。 ### 基本思路： 对每个 $A_i$ 的答案进行预处理，对于每个询问，只需要找到第一个到达的景点即可。 那么如何预处理每个点的答案呢？有一条很重要的性质：**最多转向 $\log{X}$ 次* ......

~~模拟赛做到的题，场上写贪心爆栈了qwq~~ 首先在首尾加上两个 $1$ 表示进出，将两段路中间的间隔作为传送门，恰好有 $2 \times N$ 个传送门，根据两段路的经过情况给传送门分类别： `00`：用 $N$ 表示，称为无用点，不到达该点。 `10`：用 $S$ 表示，称为起点，需要通过向 ......

## 前言 昨天考试考到过了，顺便叫发题解，我的做法有两个，一个 $O(n)$，一个 $O(n\log n)$。 ### $O(n\log mn)$ 的方法——三分 当时考试时就想到了，因为这次的答案是单谷函数，可以使用三分，跟二分差不多，就是找向左走上升还是向右走更优，然后 $O(n)$ 统计一下 ......

**[原题传送门](https://atcoder.jp/contests/abc262/tasks/abc262_e)** 感觉是一道不是很难想到但还是比较不错的题。 题目要求将k个点染成红色，那么我们不妨首先将所有点视为蓝色，然后一个一个地将红点加进去。 那么就从简单的入手，考虑最初只加入一个红 ......

# [ABC311] D~G 题解 ## D - Grid Ice Floor 搜索 题目的意思实际上是要求出所有可能到达的点，也就是说所有路径可达点的并。 基本上看清题目就会了，直接搜索每个点，每次枚举四个方向的时候直接冲到底，需要用数组去重贡献。 ```cpp void dfs(int x, i ......

[题目链接](https://www.luogu.com.cn/problem/P2149) 题意简述：求两条给定起点终点最短路的最长公共路径。 首先最长公共路径一定是两条最短路的公共最长链的部分。至少一定在两条最短路上。 考虑如何求出一条路径是否包含于一条最短路，只要路径 $x\rightarro ......

妙妙题。 ### 题意 给定 $F_0(x)=a_{(x-1)\bmod n +1}$。 $$ F_k(x)=F_{k-1}(x)-\sum\limits_{i=2}^n F_k(\lfloor\frac{n}{i}\rfloor) $$ 求 $F_k(m)$。 $1\le n\le 10^4,1\ ......

集体被大样例薄纱了。 ## T1 P1292 > 有两个容量分别为 $a$ 与 $b$ 的酒杯与一个容量无限的酒桶，有以下几种操作： > 1. 用酒桶将 $a$ 倒满； > 2. 将 $b$ 中的酒全部倒入酒桶； > 3. 将 $b$ 中的酒倒入 $a$，直到 $a$ 被装满或 $b$ 被倒空。 > ......

一个非常显然的事情是：总方案数即为每条边方案数之积。 树边已经确定，考察每条非树边 $(u,v)$ 可以怎么取。给定的树 $T$ 是唯一最小生成树，这意味着非树边 $(u,v)$ 要么不存在，要么权值大于 $T$ 上 $(u,v)$ 之间任意一条边的权值。设 $T$ 上 $(u,v)$ 间的最大边权 ......

打算只写点有意思的题。 ### D1J Easy problem I 注意到 $x_i$ 单增，所以一个数被减到负数之后，所有的操作都会将它减到负数，也就等价于乘 $-1$ 再相加。 使用一棵线段树维护所有数，将这些数分为两种，一种如上，一种是区间减。 最终所有数都会变为需要乘 $-1$ 再相加的数 ......

[Lnk](https://www.luogu.com.cn/problem/P4069) 首先树剖，然后变成在 $\text{dfn}$ 区间上插一个关于 $\text{dis}$ 的一次函数。这个很神奇，一般的李超树是，在 $x$ 轴区间上插入关于 $x$ 的一次函数。然而这里，$\text{d ......

[TOC] # 题目 [题目链接](https://www.luogu.com.cn/problem/P4200) # 解题思路 首先，此题有明显的插入、删除、查找，所以必须要使用平衡树。 考虑如何使用平衡树维护每个鸟的状态。发现很不方便，因为鸟的位置改变，整个平衡树的值都要修改。 考虑针对每个节点 ......

[原题传送门](https://www.luogu.com.cn/problem/P9507) ## 题目描述 Ghiță 有一个下标从 $0$ 开始的正整数序列 $S$。因为他是喀尔巴阡的国王，所以他想要构造一个节点编号为 $0,1,\ldots ,N-1$ 的二叉树，满足： - 树的中序遍历按节 ......

# A 发现只是单向变换 $(0\to 1)$，用两个变量维护位置最小值和最大值即可。 ```cpp #define int long long int n,q,maxn,minn=1e18+1,x; signed main(){ n=read(),q=read(); while(q--){ x=r ......

[题面](https://codeforces.com/problemset/problem/1857/B) ## 题目大意 给定 $T$ 组数据，每组数据一个自然数 $n$，可以多次选择第 $k$ 位数进行四舍五入，求出四舍五入后该数的最大值。 ## 分析思路 思想：**贪心**。 这里给定了两种 ......

好吧，作为一道绿题，我还是没能够自己做出来。 我做这道题时思路：利用并查集，对于 M 询问，如果不在同一集合则将两者所在集合合并，对于 C 询问 ，如果不在同一集合很好解决，如果在同一集合，我们需要解决的首要问题是如何计算出两者之间的数量 。 所以就从这道题出发，学习一下带权并查集吧！ **思路：通 ......

# A. Array Coloring 因为： 偶数+偶数=偶数 奇数+奇数=偶数 奇数+偶数=奇数 所以设 $s1$ 为奇数之和，$s2$ 为偶数之和 $s2$ 必定是偶数 如果奇数的个数为偶数，则 $s1$ 为偶数；否则是奇数 而在 $s1$ 为奇数时，即使拿一个奇数加到 $s2$ 里，那么也是 ......

## CF1030F 题解 [传送门](https://www.luogu.com.cn/problem/CF1030F) [更好的阅读体验](https://www.cnblogs.com/Xttttr/p/17615939.html) 简化题意：有 $n$ 个小球，每个小球在位置 $a_i$，移 ......

[洛谷博客链接](https://www.luogu.com.cn/blog/hanhan-zz/cf1477e-tai-hu-ai-di-song-fen-ti-ti-xie) 此篇未投洛谷题解，因为写得太菜了qwq。 # CF1477E&大户爱的送分题题解 （CF1477E为我出的校内模拟赛的一 ......

[洛谷博客链接](https://www.luogu.com.cn/blog/hanhan-zz/p8170-ti-xie) 这题跟 [P3826 [NOI2017] 蔬菜](https://www.luogu.com.cn/problem/P3826) 在外观上差不多，如果再深入观察一下，会发现跟 ......

# 题解背景 某一天上课时，老师在讲这道题，zxk 同学想出了一个非 dp 的**贪心**想法，但是在敲了 20 分钟后就很痛苦地离开了。 一位名为 zzn 的同学对此付出了实践，并给出了严谨的贪心证明，zxk 同学被他的黄金精神深深地感动了， 最后和 zzn 同学齐心协力在测试了 14 组毒瘤数据 ......

## [CF1239E](https://codeforc.es/contest/1239/problem/E) 给定 $2n$ 个数，将其重排成 $2\times n$ 的矩阵，最小化：从 $(1,1)$ 走到 $(2,n)$，只可向右下走的所有方案中，途径所有数的和的最大值。$n\le 25,| ......

# [AT_ABC307_G-Approximate Equalization](https://atcoder.jp/contests/abc307/tasks/abc307_g "ABC307_G") [没想到还有Approximate Equalization II ！！：AT_ABC313_ ......

## 题意 给定一棵树，对于每个节点 $u$，求 $\sum\limits_{v = 1}^{n} \operatorname{dist}(u, v) ^k$，其中 $\operatorname{dist(u, v)}$ 表示 $u, v$ 两点间的距离。 ## 题解 首先考虑化简算式中的 $k$ ......

# A 国家集训队 ## 题解 注意数据已经是有序的，~~我还搞了个排序，我是智障~~ 所以只需要将第5个人到第16个人的成绩都预设成300，再把前4个人的成绩都预设成0，再看有没有人能超过第4个人就行了 ## ac代码 ```c++ #include using namespace std; co ......

每次出题都出其不意 >群友蓝桥国三ac一道题 根据官方的视频题解整理 依据难度的划分 第五题：促销糖果 分析：从答案出发想吃K个糖果，必定有k个糖纸，考虑换购，则有一张糖纸是不可以换的（因为你必须至少要买一颗糖果）则换购的数量为（k-1）/减去换购的糖果则是买的糖果 package Li2209; ......

# CodeForces CF1846G 题解 - [CodeForces题目链接](https://codeforces.com/contest/1846/problem/G) - [洛谷题目链接](https://www.luogu.com.cn/problem/CF1846G) - 标准答案是 ......