题解atcoder agc 004

A - Range Flip Find Route 可以发现，一条路径的最小操作数等于路径上有多少 # 的块，令 \(f_{i,j}\) 表示到 \((i,j)\) 的最小操作次数，直接 DP 就行了。 注意路径上一个 \(1\) 的块会被算两次，需要除以 \(2\)。 #include<iostr ......

CF 是没题考了吧，每场都出二进制拆位。 思路 首先我们可以二分 \(r\)，因为 \(r\) 越大，按位与一定只会小于等于 \(r\) 小的情况。 那么，我们可以用 \(num_{i,j}\) 记录 \(a_j\) 第 \(i\) 位的二进制情况。 如果我们对 \(num_{i,j}\) 做一个前 ......

前言 赛时代码可能比较难看。 A 判定 \(a\) 中是否有 \(k\) 即可。 赛时代码 B 奇怪的构造题。 令 \(a_1=1,a_2=3\)，其他项由上一项加一开始枚举判定可行性即可，可以简单证明时间复杂度为 \(O(n)\)。 赛时代码 C 容易发现当 \(x\in \left[\dfrac ......

目录题目链接思路分析代码 题目链接 P4819 思路分析 首先考虑这道题的连通性。容易发现这种类型的题目会容易产生环形的状态转移。假设我们知道了其中的一个点是否是黑白点，那么我们就可以知道所有点是否是黑白点。容易陷入一个误区：我们只能通过一个点知道他所相邻的最直接的点，如何确定相邻的点的状态？注意本 ......

Codeforces Round 742 Div2 A-D题解 A. Domino Disaster 这题就是说给出一些2x1 tile，然后给出2xn的第一行构造，问第二行 这个刚开始想着是啥dp，一看那么多人过了果断改思路，发现这题就是个模拟题，就是把U换成D，D换成U，L和R不影响，然后输出就 ......

AtCoder Beginner Contest 318 A - Full Moon (atcoder.jp) 以\(M\)为首项,\(P\)为公差,看\(1 \sim N\)里包含了多少项的个数 #include<bits/stdc++.h> using i64 = long long; usin ......

水题。 发现根据限制 \(M_{i,j}=M_{j,i}\) 可以知道除了主对角线上的点，其他的点都是成对出现的。也就是说如果有一条要求的 \(a_i\) 为奇数，那么至少有一个 \(c_i\) 在主对角线上。 记 \(S=\sum\limits_{i=1}^{k} (a_i\equiv 1\pmo ......

CF1791G2 Teleporters (Hard Version) 题解 题目大意 题意挺清楚的，给个传送门吧。 分析 比较简单的贪心题，很容易就能看出来是贪心，也很容易就能看出来贪什么。 我没做简单版（Teleporters (Easy Version)），但是我去看了一眼。那个也非常简单，不 ......

T1 derby 你考虑直接贪心进行匹配即可，就是说对于每一个 \(1\) 去匹配最大的 \(0\) #include<bits/stdc++.h> using namespace std; int n,m; vector<int> A[2],B[2]; int main(){ freopen("d ......

Preface 这场前三题是上周四写的，今天课有点多本来想着把最近两场CF的博客先写下的 但后面发现还有CCLCC的杂谈没写，写完发现由于晚上要上课没时间了，只能先把这场先写一下 A - Sum equals LCM 设\(n=\prod_{i=1}^k p_i^{c_i}\)，不难发现令\(A_1 ......

2023-09-26 题目 难度&重要性(1~10): 题目来源 luogu 题目算法 组合数学 解题思路 前置知识 范德蒙德卷积公式：\(\sum\limits_{i=0}^kC_{n}^{i}\times C_{m}^{k-i}=C_{n+m}^k\)。 至于证明请看此篇文章。 Sol 我们这道 ......

在 \(V\times V\) 的平面上，\(n\) 次修改，每次给定 \(x,y,v\)，令 \(a,b\) 为不超过 \(x,y\) 的最大的 \(2\) 的整数次幂，则所有 \((x+pa,y+qb)(p,q为自然数)\) 都加上 \(v\)，最后有 \(m\) 次单点询问一个位置的值。 \( ......

## _Description_ 有一个长度为 $n$ 的 ```01```字符串 $s$，其中部分位置已给出，在 ```?```的位置处需填入一个 ```1```或 ```0```。 一个填充方案是好的，当且仅当存在 $m$ 个不同的 $i$ 满足 $1\le i ......

题意 若非负数列 \(A\) 中任意 \(i(2 \leq i \leq N-1)\) ，都有 \(2A_i \leq A_{i-1} + A_{i+1}\)，则称 \(A\) 为凸数列。 问长为 \(N\) ，且数列中所有项的和为 \(M\) 的凸数列有多少个，答案对 \(10^9+7\) 取模。 ......

P8074 SVEMIR \(Solution\) ： 这道题目乍一看感觉好难... 因为有绿色的加持，再加上一进题目就看见了头疼的三维坐标，不知道的还以为需要用到什么非常高大上的知识来解决这道题，其实只需要用到最小生成树就行了。 不会最小生成树的请出门左转：P3366 【模板】最小生成树 然后来仔 ......

CF1106D 题解 暑期学校军训第一天模拟赛的题，相对而言比较简单 题意： 题意其实很简单，就是有一个无向图，需要你从\(1\)号节点出发，然后一次遍历所有的点，输出其中字典序最小的遍历 思路 说说思路吧，这题既然要遍历图上所有点，那首先就会想到 \(\texttt{BFS}\) 或 \(\tex ......

Sequence Growing Hard 不难发现设合法的条件为第 k 位后,需满足 \(k\in[1,n)\)\(A_{i,k+1}\leq A_{i+1,k}\) 或 k=n。 对于连续相等的一段,在任意位置放得到的 A_{i+1} 相同需去重。 以上两种方式体现为,在末尾放 x,放一段不降序 ......

CF1863 题解 A 条件很简单：如果总共的 '+' 号加上开始上线人数不到 \(n\) 人，就不可能。实时记录人数，如果某一时刻大于等于 \(n\) 人在线上，就一定是。剩余情况则可能。 #include<bits/stdc++.h> using namespace std; int main( ......

RobinChenRobinChenRobinChenRobinChenRobinChenRobinChenRobinChenRobinChenRobinChenRobinChenRobinChenRobinChenRobinChenRobinChenRobinChenRobinChenRobinC... ......

CF1872 题解集，包含 CF1872B The Corridor or There and Back Again，CF1872C Non-coprime Split，CF1872D Plus Minus Permutation。 ......

@目录Description前置芝士SolutionCode Description 构造一类矩形： 先构造矩形 \(M_1=\begin{bmatrix}1\end{bmatrix}\)。 对于 \(i\geq1\)，\(T_{i+1}\) 从 \(T_i\) 构造而来，方法为在最右侧和最下侧插入 ......

1.最长路程 考虑一个简单的85分做法：维护若干条链的集合\(S\)。 每次从\(S\)中取出\(3\)条链，设他们的一个端点（任意取）为\(a,b,c\)。 查询\((a,b)\)，如果联通则合并\((a,b)\)对应的链。 如果不连通则查询\((b,c)\)，如果联通则合并\((b,c)\)对应 ......

CF1106D 题解 暑期学校军训第一天模拟赛的题，相对而言比较简单 题意： 题意其实很简单，就是有一个无向图，需要你从\(1\)号节点出发，然后一次遍历所有的点，输出其中字典序最小的遍历 思路 说说思路吧，这题既然要遍历图上所有点，那首先就会想到 \(\texttt{BFS}\) 或 \(\tex ......

main函数如下： int __cdecl main(int argc, const char **argv, const char **envp) { int v4; // [rsp+Ch] [rbp-4h] BYREF init(argc, argv, envp); puts("EEEEEEE ......

[JOISC 2014] 電圧 题解 赛时都想到了我也不知道为啥自己没敢写 首先题意可以转化为，我们去掉一个边后，剩下的图可以黑白染色，同时保证去掉的边两端的点颜色相同，问这样的边数。换句话说，去掉一条边后，剩下的图应该是一个二分图。 然后我们很容易想到线段树分治来处理这种问题。每次只有一条边被删掉 ......

题目大意 有 \(n\) 个杯子，第 \(i\) 个杯子里装有 \(W_i\) 升水，且有 \(n\) 对正整数 \(l_i,r_i\)。Yuri 和 Muri 两人在玩一个游戏：两人轮流进行操作，最先不能进行操作者输。 一次操作定义为：操作者选择一个杯子 \(i\)，从中喝掉 \(x_i\) 升水 ......

原题连接 可以发现集合对称差就是异或运算。 每个点都记一个长度为值域的 bitset，每一位都表示根到他有没有奇数个这个数字。 那么 \(a_x\) 改为 \(v\) 的修改就变成了修改子树的所有点的 bitset，每次将子树中所有点的第 \(a_x\) 位取反，再将第 \(v\) 位取反。 查询就 ......

AT_abc321_f [ABC321F] #(subset sum = K) with Add and Erase 题解 题目大意 现在有一个空箱子。给你两个数 \(Q, K\)，然后给你 \(Q\) 行，每一行代表一个操作： \(+ x\)，即向箱子里加一个权值为 \(x\) 的小球。 \(- ......

AtCoder-ABC321A 321-like Checker 依题意判断。 提交记录：Submission - AtCoder AtCoder-ABC321B Cutoff 枚举 \(a_n\)，依题意模拟即可。 提交记录：Submission - AtCoder AtCoder-ABC321C ......

A 从低位到高位判断是否递增就行了。 B 直接暴力枚举。 C 深搜一下，答案最多 1023 个，然后要开 long long !!! D 从小到大枚举 a 的同时从大到小枚举 b，然后前缀和优化一下就行了。 E 考虑把这棵树分成两部分，分界线为从 1 到 n 的路径。 然后在路径上从下往上dp出长为 ......