题解at_agc 022 agc

CF689 Codeforces Round 361 (Div. 2) CF689A link CF689A题意 题目描述 迈克在海滩游泳时不小心将手机放入水中。他买了一个带有老式键盘的手机。键盘只有十个数字大小的键，位于以下方式： 1 2 3 4 5 6 7 8 9 0 联系人与他的旧手机一起消失 ......

题目链接 点击打开链接 题目解法 暴力并查集 \(merge\) 肯定不可行 对于限制是 \(O(n^2)\) 的，查询却是 \(O(n)\)，所以考虑均衡复杂度 可以用倍增的思想求解 令 \(fa_{i,j}\) 为 \([i,i+2^j-1]\) 的并查集数组，记录的是祖先的下标 这样限制不难做 ......

题意： 思路： 考虑修改同种字符： 如果要将其修改变大，修改最左侧的字符一定最优。 证明：将一个字符修改变大，自身的贡献可能增加或减少，其左侧的字符的负贡献一定增加，正贡献一定减少。考虑一左一右的两个同种字符，分别将其变大，其自身带来的贡献是相等的，但是修改靠右的字符，只会使左侧更多的字符的负贡献增 ......

题意： 维护一棵树，初始有一个编号为 $ 1 $ ，点权为 $ 1 $ 的根节点，后续进行 $ n $ 次操作，操作分为两种： $ + $ $ v_i $ $ x_i $ ：表示添加一个点权为 $ x_i $ $ (x_i \in $ { $ -1，1 $ } $ ) $ 的节点，并使其与点 $ v ......

题目链接 点击打开链接 题目解法 先考虑朴素的 \(dp\) 不难发现有两个断点 \(x,y\) 是重要的，即 \([1,x]\) 在第 \(1\) 行，\([x,y]\) 在第 \(2\) 行，\([y,n]\) 在第 \(3\) 行 不妨枚举断点 \(y\)，然后统计最优的 \(x\) 令 \( ......

题意： \(T\) \((\)\(1\) \(\le\) \(T\) \(\le\) \(10^4\)\()\) 组询问：是否存在一个满 \(k\) (\(k\) \(\ge\) \(2\)\()\) 叉树节点数恰好为 \(n\) \((\)\(1\) \(\le\) \(n\) \(\le\) \ ......

本篇题解参考 @djwj223，但是本人太弱了，对着代码看了 INF 年才看懂。因此写一篇具体讲解实现方面的题解。在此先表示感谢。 思路 考虑最终的答案圆会是怎样的。第一种是半径达到了 \(R\) 的上界，不能继续扩充。显然这种情况可以把圆移动一下使某个点在圆上，以此进行计算。第二种是楼上所说的与两 ......

[国家集训队] middle 题目分析 代码如下。 #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; const int MAXN=2e4+10; in ......

题目链接 点击打开链接 题目解法 首先考虑一个朴素的 \(dp\) 令 \(f_i\) 表示以 \(i\) 结尾的合法子串的个数 为了不重不漏，我们令 \(le_i\) 表示以 \(i\) 为右端点，离 \(i\) 最近的偶回文串的左端点，然后不难得到转移为 \(f_i=f_{le_i-1}+1\) ......

ISCTF 逆向题解用一个晚上的时间看了看ISCTF，有的题还蛮难的(毕竟得嘎嘎猜出题人想法)CrackMewinhex打开exe，修改标识头PFX为UPX然后放进UPXshell里面试试脱了，放进ida，直接反编译得到flagEasyReexeinfo看看这个是什么64位，放进ida反编译得到一段 ......

Link ICPC2022Xian L Tree Question 给出一个根为 \(1\) 的树，需要将树分成几个块每个块，一个块中的节点需要满足以下条件中的一个： 对于所有的 \(u,v \in S,\ u \neq v\) ，满足 \(u \in subtree(v)\) 或 \(v \in ......

好久没写一整场 CF 或者 AT 的题解了，所以写一篇。 C 有点意思的题。 考虑先放横再放竖，若确定所有横的位置，那么每列独立。所以记 \(f_i\) 表示第 \(i\) 列最多放多少个，考虑放一个横对 \(f_i\) 的影响。 若 \(n\) 为奇数，那么第一行放满显然最优。若某时 \(A>1\ ......

题目链接 点击打开链接 题目解法 首先 \(O(n^3)\) 的 \(dp\) 是显然的，令 \(f_{i,j,k}\) 为第 \(i\) 步在 \(j\)，当前等级为 \(k\) 的 \([i,n]\) 步获得钱数的期望，转移枚举出边即可 一个很妙的优化是：贡献都是 \(k^2\) 的形式，所以我 ......

题目链接 点击打开链接 题目解法 弱化题目 考虑一个常用的转化（更多用于期望）：枚举答案，将 \(=\) 变成 \(\le\) 或 \(\ge\) \(\sum\limits_{i=1}^mi\times c(x=i)=\sum\limits_{i=1}^mc(x\ge i)\) 枚举 \(i\)， ......

Codeforces Round #731 (Div. 3) 在家打了好久COD和战雷，偶尔也得学习一下，要不然感觉时间都浪费了，游戏玩多了也腻，保持适当学习才能爽玩游戏。申请完了也不想做太难的题了，那么就来一场div3保持一下思维敏捷度吧。 A. Shortest Path with Obstac ......

常规，但不常规。 思路来自 @gyh. 思路 BIT 优化计数。 本来考虑的是对 LIS 进行计数，得到一个对 \([]\) 形式的值套三层求和的方式，然后再瞪眼找优化方法，但是没有发现什么好的处理方法，于是只能考虑转换计数方法。 考虑通过每个位置对答案的贡献计数。假设某个位置 \(x\) 被一个合 ......

题目链接 点击打开链接 题目解法 首先第二个条件等价于同一种权值红蓝交错填 可得不考虑第三个条件的方案数为 \(2^{cntcol}\)，其中 \(cntcol\) 为出现过的颜色数量 考虑红蓝是等价的，所以 \(p>q\) 的方案数 \(=\) \(p<q\) 的方案数 所以我们只需要计算 \(p ......

1900D - Small GCD 给定序列 \(A\)，定义 \(f(a, b, c)\) 为 \(a, b, c\) 中最小的次小的数的 \(\gcd\)，求： \[\sum_{i = 1}^n \sum_{j = i + 1}^n \sum_{k = j + 1}^n f(a_i, a_j, ......

更好的阅读体验 SP19543 GSS8 - Can you answer these queries VIII fhq + 二项式定理。提供一个不太一样的思路。默认下标从 \(1\) 开始。 首先插入删除，区间查询，想到可以平衡树维护或者离线下来做线段树。本文中是用的是 fhq，好写一些。 \(k ......

题目传送门 思路： 按题意算出总分。 如果已经过了分数线，输出，结束程序。 否则开始循环，如果这道题已经全部对了，输出。 否则，判断可不可以过分数线，输出。 Code： #include<bits/stdc++.h> using namespace std; int n,score,a[105],w ......

Link CF1901 B Chip and Ribbon Qustion 初始有 \(n\) 个格子，刚开始每个格子都是 \(0\) ，Monocarp 刚开始在一号格子中，并使得 \(a[1]+1\)，每一轮，Monocarp 可以进行两个操作 操作 1 ，Monocarp 移动到下一个格子， ......

标签：DP \(B^+\) 阅读须知：本题解较为详细地讲述的该题解法的思路和来龙去脉，但篇幅较长，请耐心阅读。 Step 1 从题面获取信息 我们考虑，因为最大值最小，所以我们首先想到二分答案。 然后我们又看到 \(k \leq 17\) 这个限制，所以会想到可能是关于一个 \(2^k\) 之类的复 ......

Link ABC330 C Minimize Abs 2 Question 给定一个整数 D 求 \(|x^2+y^2-D|\) 的最小值，\(x,y\) 为非负整数 Solution 同时枚举 \(x,y\) 显然是不切实际的，考虑折半枚举 枚举 \(x^2\) 然后寻找接近 \(D-x^2\) ......

Link ABC330 E Mex and Update Question 给一个数组 \(a\)，有 \(Q\) 次修改 每次把 \(a_i\) 改成 \(x\) 问每次修改后，不在 \(a\) 数组中的最小非负数时多少 Solution 记录每个 \(a_i\) 出现的次数 \(num\) 每个 ......

SP1557 GSS2 - Can you answer these queries II 更好的阅读体验 扫描线。把询问挂在右端点上，扫描右端点，纵轴仍为序列维。 对于这种出现多次的数只算一次的，记 \(pre_i\) 表示 \(i\) 这个值上一次的出现位置，套路化的可以强制让出现多次的在 \( ......

Link UVA11275 3D Triangles Question 给你三维空间中的两个三角形，请判断它们是否有公共点。 Solution 如果在三维空间中相交，那么，肯定有一个三角形的某一条边穿过了另外一个三角形 Code #include<bits/stdc++.h> using names ......

Link CF1900 D Small GCD Question 定义 \(f(x,y,z)=\gcd(a,b)\) ，其中 \(a,b\) 为 \(x,y,z\) 中较小的那两个数 给出数组 \(a\)，求 \[\sum\limits_{i=1}^n \sum\limits_{j=i+1}^n \ ......

更好的阅读体验 很有意思的一道题。 设 \(f_i\) 表示第 \(i\) 根线的答案，首先有一个关键结论：任意两根相邻的线答案只差一定小于 \(1\)。原因显然，可以在无限远的地方加一根线来构造。该结论可以扩展一下，对于距离为 \(d\) 的两根线，答案之差不会超过 \(d\)。 考虑进行倒着加线 ......

题目传送门 思路： 首先我们要学习一下 \(KMP\) 算法，不会的可以看这个大佬的文章 那么我们就直接开始讲思路了。 针对于每一位，\(kmp\) 算法已经预处理出了一个对应 \(kmp\) 数组的单元，映射着如果此位失配，它可能的最靠后的一个重新开头是哪一个。 让我们举一个例子：假如让 \(aa ......

Link CF1900 C Anji's Binary Tree Question 给出一个树，每个节点上有一个字母 L/R/U ，从 \(1\) 号根节点开始，L 表示接下来走到左节点，R 表示接下来走到右节点，U 表示接下载走到父节点 问，最少修改几个节点上的字母使得从根节点走到叶子节点 Sol ......