ARC

Desc. Link. 你有 \(n\) 个朋友，他们会来你家玩，第 \(i\) 个人 \(1...A_i\) 天来玩，然后 \(A_i+1...2A_i\) 天不来，然后 \(2A_i+1...3A_i\) 又会来，以此类推; 每天你会选一个来玩的人，给他颁个奖，如果没人来玩，你就不颁奖。 你要给 ......

题意 给定一棵由 \(N\) 个节点组成的树，每个节点有黑白两种颜色。定义一个节点 \(u\) 为好的当且仅当路径 \(1 \leftrightarrow u\) 上的节点均为黑色的，反之为坏的。初始情况下所有点均为白色。 定义一次操作为选取一个坏的节点并将其染黑，求将全部节点均染为黑色的期望操作次 ......

写在前面的话 我从今年 \(7\) 月末开始断断续续地写 ARC 的题目，\(9\) 月中旬的时候已经做了少量的题了，还有许多 F 没写，一方面是因为我水平太差看不懂题解，另一方面是因为一种题写多了总是有一种无聊的感觉的。所以到此为止吧，把这些日子水的题放在这篇博客中吧，以后再写 ARC 的题大概会 ......

前置芝士 排列组合 分析 明显的贪心，第一问与此题思路相似，优先选择做时间少的，可以尽可能让后面的罚时尽量的小。 难点在第二问，第二问问的是有几种可能性，有个显然的结论： 相同做题时间的题目，位置调换答案仍然相同。 那么可以用 桶+排列组合 来解决： 用桶储存这个做题时间的出现次数 \(b_i\)， ......

题目大意 给定一个长度为 \(N\) 的序列 \(A\)，这个序列组成一个环。每次可以选择环上的一段都减去 \(1\)，求最少操作次数使得序列每个位置值均为 \(0\)。 思路 首先考虑一次操作会产生什么影响。 发现，会使得序列的最大值最多减 \(1\)，环的差分序列最多减 \(2\)。 那么我们设 ......

这是一个没有必要的复杂做法，但我考场上第一时间想到的就是这个做法。 分析 首先观察样例。发现答案有对称性，所以我们只需要求出 \(\left[2,k+1\right]\) 区间内的答案。又发现相邻两项答案是一样的，所以只需要处理其中奇数情况的答案。 推式子 设 \(f_s\) 表示点数和不为 \(2 ......

题意 给定一个长度为 \(N\) 的环，每次选取环上一段并使其中每个元素值均加 \(1\)。给定一个长度为 \(N\) 的序列 \(A\)，环上元素初始值为 \(0\)，求将环变为序列 \(A\) 的最少操作次数。 （\(1 \le N \le 2 \times 10^5, 1 \le A_i \l ......

2023-09-29 题目 [ARC059F] バイナリハック 难度&重要性(1~10):6 题目来源 luogu 题目算法 (纯)dp 解题思路 一道非常水的 dp 题。 先看数据 \(N\le 5000\)，考虑 \(O(n^2)\) dp。 对于题目的三个操作中，我们唯一需要仔细思考的就是对于 ......

洛谷连接&Atcoder 链接 题目简述 给定两个数 \(n\) 和 \(m\)，输出 \(\left\lfloor\frac{10^n}{m}\right\rfloor \bmod m\) 的值。 数据范围：\(n \le 10^{18},m \le 10^4\) 思路 首先看到数据范围还是很大的 ......

include <bits/stdc++.h> typedef long long valueType; typedef std::vector ValueVector; constexpr valueType MAXB = 31; int main() { std::ios::sync_with_ ......

ARC——run Adaptive Rotated Convolution for Rotated Object Detection (ICCV 2023)运行过程 Introduction This is the official implementation of the paper, Adap ......

题面 给定 \(N\) 个正整数对 \((a_i, b_i)\) 和两个初始为空的集合 \(S, T\)，你可以选择将每个数对的两个元素划分到两个不同的集合中。求 \[\max\operatorname{lcm}(\gcd\limits_{x \in S}x, \gcd\limits_{y \in ......

题意 给定正整数 \(N\)，求满足如下条件的正整数对 \((x, y)\) 的数量： \(1 \le x, y \le N\) \(x^2 - y\) 为完全平方数（\(0\) 也是完全平方数） （\(1 \le N \le 10^{12}\)）。 题解 因为 \(x^2 - y\) 为完全平方数 ......

Day \(4!\)。 首先容易找到周长为 \(2(w+1)\) 和 \(2(h+1)\) 的矩形，所以答案下界是 \(2(\max(w,h)+1)\)。 考虑按照整个矩形中心坐标，将矩形分成 \(4\) 个子矩形，观察到若有矩形完全包含于其中一个子矩形，则其周长必不超过 \(2\max(w,h)\ ......

D - Bracket Score 2 看了题解之后发现自己是弱智 如果能够猜到答案就是前n大-前n小，那么这题就解决了，直接用一个栈模拟匹配即可。 #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #inc ......

洛谷题目链接 ATcoder 题目链接 好题。（不过绝大部分题解全在瞎说） 看到 $n$ 个点 $n$ 条边且每个点只有一条出边很容易的想到基环树。 而最后每个连通块一定是一个基环树，那么统计连通块的数量就相当于统计基环树的数量。 既然有基环树，这种题绝对不能枚举然后求连通块数量，一定是枚举连通块求 ......

区间排序问题，主席树优化建图，最小字典序拓扑排序（priority_queue） problem 给定一个长度为 \(n*2\) 的序列，其中每种元素恰好出现了 2 次。 允许每次选择任意两个相邻的元素交换。 那么必定存在一个最小 \(k\)：使得 \(k\) 次交换以后所有相同的元素都是相邻的。 ......

Problem StatementFor an integer sequence $X=(X_1,X_2,\dots,X_n)$, let $X[L,R]$ denote the integer sequence $(X_L,X_{L+1},\dots,X_{R})$. You are given ......

这个题不是网络流。 problem 我们说一个集合 \(D\) 是一个好的集合，当不存在集合中的两个不同元素 \(a,b\) 使得 \(a\) 是 \(b\) 的约数。 给定 \(N\) 个整数的一个集合 \(S\)，值域均落在 \([1, 2*M]\) 内。 对 \(S\) 中的每个元素 \(A_ ......

arc165F 题目描述： 给定 \(n\) 和一个长度为 \(2n\) 的序列 \(a\)，满足 \([1,n]\) 每个数恰好出现两次。 每一次操作可以交换相邻的两个数，询问最少多少次操作可以使得序列 \(a\) 满足 \(\forall i\in[1,n]\ a_{2\times i}=a_{ ......

D - Substring Comparison simple 的好题捏！ 只考虑每两个串的第一个位置，假设这两个位置不同，那么可以定出一个大小关系。将所有大小关系建成一张图，如果这张图是个 DAG，那么就可以成立了，如果有环，说明环上的点都是一样的，因此可以将这些数缩成一个点，然后把对应的串往后移 ......

赛时：看不懂题，啊这！ 赛后：就这？ 题目描述 有一个简单相连的无向图，其顶点数为 \(n\)，编号为 \(1\) 至 \(n\)。图中有 \(m\) 条加权边，第 \(i\) 条边连接顶点 \(a_i\) 和 \(b_i\)，权重为 \(w_i\)。此外，连接两个顶点的简单路径的权重是简单路径中包 ......

题目描述： 给定 \(n\) 和一个长度为 \(2n\) 的序列 \(a\)，满足 \([1,n]\) 每个数恰好出现两次。 每一次操作可以交换相邻的两个数，询问最少多少次操作可以使得序列 \(a\) 满足 \(\forall i\in[1,n] \quad a_{2i} = a_{2i-1}\)。 ......

ARC165 A 猜的结论,质因数\(\ge2\) 感觉证明不难 #include<bits/stdc++.h> using namespace std; int t; int n; int main() { // freopen("date.in","r",stdin); // freopen(" ......

AT_arc165_d [ARC165D] Substring Comparison 题解 Links 洛谷 AtCoder Description 给定正整数 \(n,m\) 和 \(m\) 个形如 \((A_{i},B_{i},C_{i},D_{i})\) 的限制条件。 判断是否存在一个长度为 ......

AT_arc165_b [ARC165B] Sliding Window Sort 2 题解 Links 洛谷 AtCoder Description 给定正整数 \(n,k\) 和一个长度为 \(n\) 的整数 \(P\)，你需要选择一个长度为 \(k\) 的区间 \([l,l + k - 1]\ ......

前天的晚上打这道题，和同学一起想出了思路，开心。 题意描述 给你一个数 \(N\)，问你存不存在一个数列 \(A_1,A_2,\ldots,A_n(2 \le n)\) ，使得 \(\sum_{i=1}^n A_i=N\) 并且 \(\operatorname{lcm}(A_1,A_2,\ldots ......

题意翻译是假的，骗了我十分钟（恼）。 题目大意 给定两个正整数 \(k\) 和 \(m\)，需要求出有多少个正整数 \(n\) 满足 \(1 \leq n \leq m\) 且 \(n \equiv S_n(\operatorname{mod} k)\)。 （\(1 \leq m \leq 10^{ ......

D1a5y。 记录 \(x(1\le x\le n)\) 出现位置分别为 \(l_x,r_x(l_x< r_x)\)，讨论一下发现当两个数 \(x,y\) 满足 \(l_x<l_y,r_x<r_y\) 时操作后 \(x\) 一定出现在 \(y\) 前面，不然可以交换位置以达到更优步数。否则发现无论怎 ......

有点结论场的感觉了。 A 题面 简单题。证明一个结论，只要 \(n\not=p^q(p \text{是} n \text{的一个质因子})\)，都是有解的，反之无解。 先证明 \(n=p^q\) 无解，假定 \(n\) 分解为 \(p^a\times p^b(a\le b,a+b=q)\)，此时两数 ......