AT_agc
AT_agc054_c 题解
题意 给定 \(k\) 和一个排列 \(P'\),问有多少个排列 \(P\) 以最少步数交换相邻两个元素来进行收敛,最终的排列可能是 \(P'\),一个排列是收敛的当且仅当对于每一个数,在该数前且比这个数大的数的个数不超过 \(k\) 个。 思路 考虑正向的让一个排列收敛,我们设在第 \(i\) 个 ......
AT_agc057_e 题解
AT_agc057_e [0] 约定 \(r_i = \sum\limits_{j = 1}^{m}[A_{i,j}\le k]\) \(r^{'}_i = \sum\limits_{j = 1}^{m}[B_{i,j}\le k]\) \(c_j = \sum\limits_{i = 1}^{n} ......
AT_agc034_e Complete Compress
原题链接 这里是用 set 实现的换根 DP,时间复杂度 \(O(n\log n)\)。 记 \(siz_x,g_x,f_x\) 分别为 \(x\) 及其子树中有多少个关键点,所有关键点到 \(x\) 的距离和,将关键点尽可能两两向上合并后到 \(x\) 的距离和(我愿意理解为是将 \(g_x\) ......
AT_agc038_c 做题笔记
题目链接 莫反好题,不仅仅是莫反,还有很多思维含量。 由于推式子过程太过于漫长了,所以我仅仅讲下大概。 题目是给你一个长度为 $n$ 的数组,请求出 $\sum\limits_{i=1}^n\sum\limits_{j=i+1}^n \operatorname{lcm}(A_i, A_j)$ 莫反通 ......
AT_agc019_b 题解
洛谷链接&Atcoder 链接。 题目简述 给定一个字符串 \(A\),可以选择区间 \([i,j]\) 翻转一次,求能得到多少本质不同的字符串。(\(A\) 的长度不超过 \(2 \times 10^5\))。 思路 首先解释本质不同的含义,即不完全相等的两个字符串(可能 \(A\) 是 \(B\ ......
AT_agc030_d [AGC030D] Inversion Sum 题解
# AT_agc030_d [AGC030D] Inversion Sum 题解 ## 题目大意 给你一个长度为 $n$ 的数列,然后给你 $q$ 次交换操作,你每次可以选择操作或者不操作,问所有情况下逆序对的总和。($n, q \le 3000$) ## 分析 很容易想到 $dp$,但是发现不好直 ......
AT_agc064_a题解
## [题面](https://www.luogu.com.cn/problem/AT_agc064_a) # 题目大意 给定一个正整数 $N$,要求构造一个序列。对于每一个在 $1$ 到 $N$ 之间的整数 $i$,序列中包含了 $i$ 个,并且将该序列首尾相接拼成环后,相邻两项之差大于等于 $1 ......
AT_agc022_a 题解
[洛谷链接](https://www.luogu.com.cn/problem/AT_agc022_a)&[Atcoder 链接](https://www.luogu.com.cn/remoteJudgeRedirect/atcoder/agc022_a) 本篇题解为此题**较简单做法**及**较少 ......
AT_agc017_b 题解
[洛谷链接](https://www.luogu.com.cn/problem/AT_agc017_b)&[Atcoder 链接](https://atcoder.jp/contests/agc017/tasks/agc017_b) 本篇题解为此题较**简单做法**,请放心阅读。 ## 题目简述 一 ......
AT_agc002_f [AGC002F] Leftmost Ball 思考--zhengjun
思维 + dp。 如果像题意那样先放球再染色的话不是很好做。 所以考虑有 $n$ 个白球,$n$ 种其他颜色的球各 $k-1$ 个。 那么限制就是说对于每个前缀,白球的个数 $\ge$ 其他颜色球的种数。 所以就可以设 $f_{i,j}$ 为放了 $i$ 个白球,$j$ 种颜色的 $k-1$ 个球的 ......
【大联盟】20230703 T2 开心的序列(sequence) 题解 AT_agc049_f 【[AGC049F] Happy Sequence】
恐怖 zak 将这题加强,出到模拟赛。直接把 $A_i,B_i\le 10^5, C_i\le 5$ 变成了 $A_i,B_i,C_i\le 10^9$。 非常恐怖。 ## 题目描述 [here](https://www.luogu.com.cn/remoteJudgeRedirect/atcode ......
AT_agc062_c [AGC062C] Mex of Subset Sum 思维妙妙题--zhengjun
思路比较巧妙。 首先排序。 考虑目前维护出 $a_{1 \sim i}$ 不能表示的数的集合 $S$。 考虑如何加入 $a_{i+1}$。 如果当前 $sum$ $$S'=S\cup [sum+1,a_{i+1}-1] \cup \{x+a_{i+1}|x\in S\}$$ - 若 $|S\cup ......
AT_agc062_b [AGC062B] Split and Insert 对自己的警告--zhengjun
做题时想出来的东西: - 时光倒流 做题时的思维定式: - 按照操作顺序,挨个算出拿几个数到最后 - 没有想到在原序列上进行区间 dp。 - 反复只想到从小到大划分区间,每个区间计算贡献,具有一定局限性 > 需要发现,在考虑不同的值的时候,选择哪些操作顺序是独立的 ### 代码 ```cpp #in ......
AT_agc062_a [AGC062A] Right Side Character 对自己的警告--zhengjun
自己推性质的能力是真的差。 - 如果最后一个字符是 `A`,那么答案就是 `A`(分为全是 `A` 和存在 `B` 两种情况证明即可) - 否则如果最后一个字符是 `B`,检查是否会变为以 `A` 结尾 - 如果原串为 `AA...ABB...B` 的话,答案为 `B` - 否则最后的 `B` 会不 ......
AT_agc009_c
# [Division into Two](https://www.luogu.com.cn/problem/AT_agc009_c) 一道 DP 好题。 题解代码最后一个 if 语句:由于到下一轮循环才用到,所以等价于 i 的时候知道了 s[i-1]-s[i-2]<b 推出只能取到 i-2(因为以 ......