ARC

题意 给定一个序列，每次操作 \(swap(p_i, p_{(i + p_i) mod N})\)。 求将她变得有序的方案。 Sol 我们考虑对于一个位置不断的操作，发现最后一定会变成 \(0\)。 我们设她为 \(p_x\)。 考虑操作 \(p_{x - 1}\)。 发现当 \(p_{x - 1} ......

https://atcoder.jp/contests/arc168/tasks/arc168_b 不会博弈，但是会乱搞 首先直接判断-1的情况 然后我们直接考察最大值能不能取到 假设存在一个数ai \(a_1\oplus a_2 ...\oplus(a_i-x)\oplus...a_n\)=max ......

题目链接 好题。 如果 \(1\) 和 \(n\) 一直联通，开始即结束。 如果 \(n\mod 4=1\)，那么 \(\frac 12x(x+1)+\frac12(n-x)(n-x+1)\) 为偶数。 如果 \(n\mod 4=3\)，那么 \(\frac 12x(x+1)+\frac12(n-x ......

题目链接 看到严格选 \(k\) 个，不难想到 WQS二分。定义 \(f(x)\) 为分成 \(x\) 段，最多有多少个超过 \(S\) 的。然后你会发现他不是凸的。因为他有很多平段，比如把两个很小的合并不改变答案。 换个方向？ 考虑定义 \(f(x)\) 为有 \(x\) 个超过 \(S\) 的段 ......

Link ARC66 D Interval Counts Question 给定正整数 \(n\) 和长度为 \(n\) 的序列 \(x_i,y_i\) 保证 \(x_i\) 单调递增，你需要构造 \(m\) 个去年 \([L_i,R_i]\) ，\(m\) 有你指定，使得每个 \(x_i\)恰好被 ......

Link ARC166 C LU RD Marking Question 给一个 \(n\) 行 \(m\) 列的网格，它的所有网格线上共有 \(n(m+1)\) 条竖边，有 \((n+1)m\) 条横边 有如下两中操作 选一个上面和左边的网格线没有被涂黑的格子，并涂黑着两条线 选一个下面和右边的网 ......

Link ARC166 A Replace C or Swap AB Qustion 给出两个长度相同的由 \(A，B，C\) 组成的字符串 \(X\) 和 \(Y\) 。 需要使用一些操作使得 \(X\) 和 \(Y\) 一样 将 \(X\) 中的 \(C\) 换成 \(A\) 将 \(X\) 中 ......

有点意思的简单题。 答案有可二分性。合并两段，显然仍然合法。 考虑如何 check。因为答案可以被二分，我们尝试求恰好 \(x\) 段就行了。 恰好，这是 wqs 二分的内容。如何设计一个与 \(x\) 有关的凸函数呢？ 这个函数大概是 \(\sum_{i=1}^x w(l_i, r_i)\) 的形 ......

题解 前言 个人认为官方题解写得最为详细、干净、清楚，如果有意向阅读外文版的题解的话，还是推荐去读一读： Editorial - AtCoder Regular Contest 117 本文属于转载（？），有一些自己的思考过程，希望有帮助。 题意 有多少个长度为 \(2N\) 的序列 \(A\) 满 ......

纪念一下第一次补完 ARC 的所有题。 本题解介绍 \(2 log\) 做法，需要卡常才能过。 感谢 @Rainbow_qwq 大佬的耐心讲解，拜谢拜谢拜谢。 首先注意到每次操作是前后缀修改，自然想到维护差分数组。 假设当前操作到了 \(a_i\)，那么差分数组的 \(a_i\) 这位加 \(2\) ......

比赛链接:arc168 A 题意： 读入一个由<和>构成的字符串，在最开始，最后，字符之间可以填上任意数字，任意两个相邻数字之间必须满足字符代表的大小关系。求问最后填入的数字组成的数组最少有多少对逆序对。 题解： 签到。 <可以不去考虑，因为不会对答案造成影响。 >如果不是在连续段内，也可以不去考虑 ......

考虑一次询问怎么做： 我们想求的答案就是 每次减时为 \(0\) 的位置个数之和（这些位置会与 \(0\) 取 \(\max\) 从而使答案变大） + \(\sum (m-2\times a_i)\)（所有操作的总和）。 考虑维护 \(y\) 的差分数组，分析一次操作 \([1,x]\) 减 \(1 ......

Description 给定 \(n\) 个点，\(m\) 条边的有向图，图中的任意一条有向边满足 边起点的编号小于边终点的编号。每个点有点权，但其中有些点的点权未知。 你需要找到一种给未知点权值的方案，使得 所有 \(1\to n\) 的路径点权和的最大公因数最大，或者告知答案可以无限大。输出这个 ......

简要题意 给定一个长度为 $n$ 的序列 $a$，将 $a$ 划分为 $k$ 个连续段，最大化满足连续段中元素和 $\geq s$ 的连续段数。 题解 首先发现是恰好 $k$ 个连续段，这种类型的题套路地考虑 wqs 二分，然后你会惊喜的发现这玩意不是凸的，我的思考也就卡在这里了。 正确的做法是观察 ......

开坑，主推红题和铜牌题，来源乱七八糟，目前一部分来自学校给的。 一眼秒了标绿，想了很久或是接受了提示标蓝，看了题解或者认为题很难标红。意义重大标星。很主观（然后发现其实基本上大多数题都不会，狠狠地难过了）。 以后有时间可能会开始板刷 ARC，现在，还是，慢慢来吧。 upd-2023-10-30：和 ......

题意 给定 \(N\) 个带有若干洞的节点，其中第 \(i\) 个点上有 \(d_i\) 个洞。 先可以在两个不同的节点的洞之间连边，一个洞最多连一条边，求使得最终形成的图是一棵树的方案数，对 \(998244353\) 取模。 洞之间相互区分，两个方案不同当且仅当存在一条边在两个方案中的连的洞不同 ......

题目描述： 给出一个大小为 \(N\) 的可重集 \(A=\lbrace\ A_1,A_2,\dots,A_N\ \rbrace\)。 你可以执行若干次如下操作（也可以不执行）。 将两个 \(x\) 合并成一个 \(x+1\)。 输出最终可能的集合个数对 \(998244353\) 取模的结果。 数 ......

题目简述 输入两个字符串 \(S\) 和 \(T\)，将他们进行如下操作： 将 \(S\) 字符串的第一位删掉，放在任意一位。 问最少多少次以后可以让 \(S\) 和 \(T\) 相等。 思路简述 看到这个题目以后，第一个想到的就是搜索，暴力搜一遍。但是仔细想来倒也不用这么麻烦，只需要特判一下就可以 ......

题意 给定一个 \(N\) 个点，\(M\) 条边的简单无向图，每个节点有两个值 \(A_i\) 和 \(B_i\)。 现对于每个节点，均可以选择花费 \(A_i\) 的代价将其删去或保留节点。若一个节点被删除，那么所有与其向连的边也会被删除。 定义一个极大联通块的权值为联通块内所有节点的 \(B_ ......

内容来自 DOC https://q.houxu6.top/?s=在ARC（自动引用计数）下，IBOutlets 应该是强引用（strong）还是弱引用（weak）？ 我正在使用 ARC（自动引用计数）专门为 iOS 5 进行开发。在这种情况下，指向 UIView（及其子类）的 IBOutlet 应 ......

多测，求值 \[\sum_{i=1}^{n}\Big[a+\lfloor\frac{i}{b}\rfloor=c+\lfloor\frac{i}{d}\rfloor\Big] \]\(1\le T\le 2\times 10^5\)，\(1\le n\le 10^9\)，\(1\le a,b,c,d ......

题目描述： 给定一张图。求将这张图分成两个完全子图后，最少会有多少条边的端点属于同一个完全子图。 数据范围： \(1\leq n\leq 700\) 思路； 发现这个 \(n\) 的范围非常小，所以他支持 \(n^2\) 的做法。 然后我们思考怎么转换一下这个问题。显然如果是完全子图的话，就不是很方 ......

题意 有一个商店和 \(N\) 名员工，其中第 \(i\) 名员工在第 \(1 \sim A_i\) 天工作，在第 \(A_i + 1 \sim 2 \times A_i\) 休息，接下来每 \(A_i\) 天改变一次状态。 每一天你都可以选择一名来上班的员工并为其颁一个奖，求使得每名员工都获得至少 ......

题意 给定一张有向图，询问将每条有向边反向过后整个图的强连通分量的个数是否发生改变。 数据范围：$n\le 1000,m\le 200000$。 思路 分类讨论，讨论强连通分量是增加了还是减少了，假设修改的边是 $u\to v$。 强连通分量减少 因为只修改了一条边，所以强连通分量减少的情况肯定是 ......

前言 ARC119F 好厉害，是没见过的自动机 DP。 正文 [1] 分析 主要分析一下为什么这么写。 [2] 状态设计 [3] 自动机状态转移 感觉状态设计中最难的就是如何处理带 \(O\) 的。 见参考资料。 [4] 代码 还没写。写ing 这是自动机的初始化（有点麻烦）。 int to[Kin ......

AtCoder-ARC116_C Multiple Sequences 朴素 DP 是设 \(f_{i,j}\) 表示第 \(i\) 个位置填 \(j\) 的方案数，时间复杂度 \(O(n^2\log V)\)。 考虑求出元素都不同序列个数，再根据长度乘组合数，这样长度是 \(O(\log V)\) ......

首杀问号题，虽然没有问号题的难度，但是至少是自己想出来的。 对于操作一和二，我们直接用分一个数组记录下来，\(O(nq)\)。 对于操作三，我们思考怎么样通过上面记录的信息处理答案。发现对于一个矩形，只要确定了 \(x+y\) 的值，\(x-y\) 的值就是一个区间，因为矩形的约束可以变成 \(2\ ......

题意 给定一个 \(N\) 个点 \(M\) 条边的简单无向联通图 \(G\)。每个边有红和蓝两种颜色，初始时每条边均是红色。 现在通过移除 \(G\) 中的一些边来获得一个新的无向图 \(G^{\prime}\)，求在所有的 \(2^M\) 种方案中有多少种方案可以使得 \(G^{\prime}\ ......

题目描述 一个全部为 \(0\) 的数组 \(a\) 。给01数组 \(b\) 和 \(q\) 个操作，每个操作 \(l_i,r_i\) ，即将 \(a\) 的 \([l_i,r_i]\) 全部赋值为 \(1\) ，你可以选一些操作，不要一些操作，求最后 \(a\) 和 \(b\) 最少有多少位不同 ......

题意 给定一张由 \(N\) 个点和 \(M\) 条边组成的简单无向图 \(G\)，定义一个无向图是好的当且仅当这张图满足以下条件： \(1\) 号节点和 \(N\) 号节点不联通 图中不存在重边和自环 现有两人轮流采取操作，每轮操作如下： 选择两个点 \(u, v\)，将边 \((u, v)\) ......