ARC

题目传送门 前置知识 贪心 | 构造 解法 对于任意一个未加入序列 \(P\) 的数 \(x<A_{i}(1 \le i \le k-1)\)，如果其放在了 \(A_{i}\) 的前面，会导致最长上升子序列长度加一，从而不符合题目要求。因此我们需要把 \(x\) 放在 \(A_{i}\) 后面，同理 ......

ARC169 前言 学校晚饭后不让来机房，时间卡的很死。基本赶不上赛时 AtCoder，更不能谈 codeforces 了。这就导致到现在一场 ARC 没参加过。 于是今天 VP 了一下，A题很水十分钟碾过去了，B题先想到了一个假贪心，答题思路不变稍微改改改成 dp 就可以了。C 题写的比B还快，比 ......

题意 给定 \(k\) 和一个排列 \(P'\)，问有多少个排列 \(P\) 以最少步数交换相邻两个元素来进行收敛，最终的排列可能是 \(P'\)，一个排列是收敛的当且仅当对于每一个数，在该数前且比这个数大的数的个数不超过 \(k\) 个。 思路 考虑正向的让一个排列收敛，我们设在第 \(i\) 个 ......

萌萌构造题，随便构造构造就做出来了。似乎跟官方题解思路一样。 首先解决以下问题：给定一个质数 \(P\)，构造一个每个数在 \(0\sim P-1\) 的大小为 \(P^2\times P^2\) 的矩阵，满足不存在 \(x_1\ne x_2,y_1\ne y_2\) 使得 \(a_{x_1,y_1 ......

分析 注意到本题在放完盘子之后就是一个简单的 Nim 问题，所以考虑每个背包会放到哪个盘子。由于放完盘后谁执先手与 \(n\) 的奇偶性有关，于是分类讨论。 如果 \(n\) 是奇数，放完后后手先取硬币，他肯定会尽量让异或和不为 \(0\)（Nim 的玩法），那么他有一个必胜策略：不管先手取哪个背包 ......

Solution 首先判掉 \(k\nmid m\) 时显然无解的情况。 然后考虑倒着做，往序列上加，那么有显然的 \(dp\)，记 \(f_{i,j}\) 表示考虑前 \(i\) 个位置，总共做了 \(j\) 次操作的方案数，转移的时候将区间加操作钦定在最后一个位置统计，暴力枚举操作的数量即可转移 ......

ARC133D Range XOR 题目链接：【ARC133D】 Range XOR 非常好数位 dp。 思路 根据异或的前缀和，我们可以把式子化成这样。 \[\sum_{i=l}^r\sum_{j=i}^r [s_j\oplus s_{i-1}==v] \]然后先去掉 \(l \leq r\) 的 ......

题意 将 \(1\dots n\) 依次加入一个双端队列，然后再一个一个弹出，要求得到的第 \(k\) 个数是 \(1\)，求得到的排列有多少种。 做法 我们首先考虑 \(n = k\) 的问题。经过简单的转化不难发现，我们实际上是在数有多少个长度为 \(n-1\) 的排列可以被划分成两个上升子序列 ......

赛时冲了两个多小时没冲出来，想得断断续续，导致没想到如何处理奇偶。 思路 根据限制条件一，可以知道最后的图一定是两个连通块，其中一块包含 \(1\)，另一块包含 \(n\)。因为此时再想连边就必须连通两个块，使其不合法了。 每次操作都是新增一条边，那么到最后的边数是多少呢？假设其中一个连通块有 \( ......

很有意义很有思维量的图论题。（摸了好久做出来了，很有感觉） 本文的「环」均指简单环，「路径」均指简单路径。 初步 考虑这个「存在一条三种颜色的路径」这个限制其实是很弱的，首先的感觉就是我们随便画出一些连通图，随便选择三条边，基本都能找到一条经过这三条边的路径。 于是我们考虑将难以描述的弱限制单步容斥 ......

[ARC101E] Ribbons on Tree Luogu ARC101E 题目描述 给定一个大小为 \(n\) 的树，保证 \(n\) 为偶数且小于 \(5000\) 您需要给树上的点两两配对，对于一组对子 \((u,v)\)，在树上将 \(u\to v\) 的路径染色，定义一个配对方案合法当 ......

更好的阅读体验 [ARC150F] Constant Sum Subsequence 很有意思的题。 设 \(nex_{i,j}\) 表示位置 \(i\) 后面的最小的满足 \(k>i\wedge a_k=j\) 的 \(k\)，则问题可以抽象为： \[f_i=\max_{j=1}^inex_{f_ ......

ARC134C The Majority link：【ARC134C】 The Majority 小清新数学题。（反正我做不出来） 简要题意 有\(K\)个箱子，编号为\(1\)到\(K\)的箱子。起初，所有箱子都是空的。 史努克有一些球，球上写着\(1\)到\(N\)的整数。在这些球中，有\(a_ ......

我沉迷 ARC 的样子就像沉迷 Arc 做 ARC D 题被骗的样子就像在推病女却 ptt-- 刷 ARC 刷不动的样子就像在 Arc 爬白复生爬了几百年还是没爬到 为什么我好像会这道 ARC 的每一步，但却做不到？为什么我锁屏练习觉得病女喷嚏门 AE 绿魔王全都很会，但是分推不了一点？ 谁来教我打 ......

题目链接 题目链接（AT） 题目链接（Luogu） 解题思路 简单贪心，由于每个格子始终不超过 \(9\) 个史莱姆，因此对于每四个格子 \(a_{i-1,j},a_{i+1,j},a_{i,j-1},a_{i,j+1}\)，我们只需要减去 \(\min(a_{i-1,j},a_{i+1,j},a_ ......

ARC157 A. XXYYX 观察一些性质。注意到 \(\texttt{XY}\) 和 \(\texttt{YX}\) 会产生当且仅当 \(\texttt{X}\) 和 \(\texttt{Y}\) 的连续段交错，因此 \(|b-c|=1\)。然后特判掉 \(a\neq 0,b=0,c=0,d\n ......

在 HL 群里吃瓜，顺手写一篇题解。 第一眼必定是数位 dp，可是这会使原题难度反而升高了。相对而言，我们要是枚举前缀 \(1\) 的长度，然后寻找对答案有贡献的区间，此问题是很容易的。同时我们不难发现，前缀 \(1\) 长度为 \(l\) 的所有有贡献的数字即为 \(\forall i\in[l, ......

[ARC168A] <Inversion> 之前打了，忘了，懒得想了，咕。 $\texttt{Code}$ #include<bits/stdc++.h> using namespace std; #define int long long #define il inline #define re ......

[ARC169A] Please Sign 每个点会一直一直给它的父节点加，所以深度越深的点影响越大，统计出每个深度的点权和，从深到浅判断正负，有正负就输出答案，全都没有就是 \(0\)。 $\texttt{Code}$ #include<bits/stdc++.h> using namespace ......

ARC167D 看到排列并且有 \(i\gets a_i\)，就可以直接建出图来，显然是若干个不相干的环。 如果不求字典序最小，就可以直接不在同一个环中的 \(i,j\) 直接交换就可以了，因为它要求了最小化操作数。如果求字典序最小，直接从前往后扫一遍，可以用 set 维护不在这个环中且 \(j>i ......

ARC105E 正向考虑是很难的，从结果入手，发现最后一定是分别包含 \(1\)，\(n\) 的两个完全图。 考虑表示出这两个人一共加了多少边：\(\frac{n(n-1)}{2}-m-x(n-x)\)，\(x\) 表示点 \(1\) 所在集合的大小。 由于是判断先手还是后手必胜，所以只需看结果对 ......

最后更新时间 2023/12/22 温馨提示 右下角有展开目录索引的功能。 由于是做题记录，所以作为题解的话可能有些地方的表达不是特别好，请见谅。 [ARC104C] Fair Elevator \(2n\) 个位置，要不重复地填 \(2n\) 个数，所以可以发现题目中给的区间里面带 \(-1\) ......

[ARC107F] Sum of Abs 发现点数比较少，考虑最小割 我们最大可能的答案为 \(\sum|b_i|\) ，现在考虑减去多余答案 首先点可以不选，于是拆点，之间边权为 \(a_i+|b_i|\) 钦定割完之后，和 \(S\) 连通的点最终取正数，和 \(T\) 连通的点最终取负数，于是 ......

NOIP 模拟赛原题，赛时还是没切。 正解奇偶性。 考虑最终不能走的时候是什么情况，当且仅当图中只剩下两个联通块了。设其中一个联通块的点数为 \(k\)，那么另一个的点数为 \(n - k\)。所以两人一共的操作次数为 \(sum = \frac{n \times (n-1)}{2}-m-k \ti ......

原题链接：ARC168B 题意：有 \(n\) 堆石子，每堆有 \(a_{i}\) 个。每人每次可以取走其中一堆中的 \(x(1 \le x \le k)\) 个。求出一个最大的 \(k\) 使得先手必胜。无解输出 \(0\)，\(k\) 可以取无限大输出 \(-1\)。 一个经典 Nim 游戏的结 ......

题意： 给出三个数 \(n,m,q\)。 你有一个长度为 \(n\) 的序列 \(a\)，初始全为为 \(0\)，你有三种操作： 操作 \(1\)：给出 \(l,r,v\)，让区间 \([l,r]\) 对 \(v\) 取 \(\min\)。 操作 \(2\)：给出 \(l,r,v\)，让区间 \([ ......

题目跳转 Fake_Solution 前言 [warning]: 本题解的做法是错法，但是正确概率贼高。离谱的是正确率还可以叠加。 正解是记搜，时间复杂度可以证明。正解看文末。 思考 众所周知一个公式： \[a\times b=\operatorname{lcm}(a,b)\times \gcd(a ......

题面 考虑一张竞赛图 \(G\)，其中有 \(N\) 个节点，节点编号为 \(1,2,\dots,N\)，且 \(G\) 满足： 对于 \(G\) 中的所有边 \(u\to v\)，恰好有 \(M\) 条边满足 \(u<v\)。 设 \(f(G)\) 表示图 \(G\) 中的强连通分量数量。请你求出 ......

考虑假设已知括号序列 \(s\)，如何求出 \(p,q\)。 对于求 \(p\)，考虑从 \(s_1\) 到 \(s_n\) 逐个往里放，如果能放就直接放，肯定不劣，否则就从后面抽最近的左括号放过来，然后继续放。不难证明不存在更优方案，对于 \(q\) 同理。 接下来我们发现，如果 \(p\) 中存 ......

不妨将棋盘黑白染色，并将黑色格子上的数取反。对应地，把操作修改为将某个 \(2 \times 2\) 区域地黑格子 \(-x\)，白格子 \(+x\) 后答案与原问题相同。于是我们考虑这个新问题的解（不难发现新问题和原问题的解集是一一对应的）。 对于新问题，修改显然不会影响行或列的和。实际上只要对应 ......