题解

原题链接：CF1900D，题意不多赘述。 首先可以将 \(a\) 数组排序，并且枚举中间的那个数 \(a_i\)。那么答案就是 \(\sum_{j=1}^{i-1} \gcd(a_j,a_i)\times (n-i)\)。重点在于求前面的 \(\gcd\)。可以用欧拉反演，但是也可以不用，因为我不会 ......

题意：有一个二维平面直角坐标系，给定一串向某个方向移动 \(1\) 个单位的操作。 有 \(q\) 个询问，对于每个询问给定 \(x,y,l,r\)，问如果倒着做 \(l\) 到 \(r\) 这段区间中的操作，是否会经过 \((x,y)\)。 ds 题。先预处理出 \(sx_i,sy_i\) 表示执 ......

原题链接：P3959 乍一看，感觉像是一道图论的最短路这类的题，但是细想发现用图论似乎不可做。再看到这道题的数据范围 \(n<=12\)，立马就可以想到用状压 \(DP\)，因为数据范围很状压/。 思路 设计状态 首先来考虑状态的设计。如果按状压 \(DP\) 的套路来设的话，设 \(dp_{i,j ......

原题链接：Group Projects 题意 有 \(n\) 个学生，每个学生有一个能力值 \(a_{i}\) 。现在要把这些学生分成一些(任意数量的)组，每一组的“不和谐度”是该组能力值最大的学生与能力值最小的学生的能力值的差。求所有不和谐度之和不超过 \(k\) 的分组方案总数。 思路 根据题目 ......

原题链接：Partition into Groups PS：这是今天上午NOIP模拟赛的T3。 题意 N个小朋友，每个小朋友最多有3个敌对小朋友， 问是否能把他们分成两组，使得这N个小朋友最多只有一个敌对小朋友在一组。 思路 考场上想肯定与二分图有关，最后没想出来，打了15分暴力就走了（最后还只有1 ......

原题链接：CF575A 前言 今天模拟赛考到了这道题，最近正好在学习矩阵，于是就来写了这道题，发现这道题是矩阵快速幂好题。 题意 题意不多赘述，大概就是一个广义斐波那契数列的升级版，可以修改 \(m\) 个系数。 思路 因为题目是求斐波那契数列的第 \(k\) 项，显然用矩阵去维护。又因为题目说了， ......

原题链接：Tautonym Puzzle 前言 这道题是一道很有趣的构造题。我认为这道题的重点在于对题目要求的转化与转化过程中细节的处理。（有些细节问题也困惑了我很久）。 题意 构造一个字符串 \(S\) ，使 \(S\) 的所有子序列中，恰好有 \(N\) 个好串。 好串：一个字符串能分成两个相同 ......

原题传送门：mit 前言 这道题是今天模拟赛T1，赛时只有 \(60\) 分。还有一位巨佬这道题保龄了。 题意 给定一个正整数 \(n\)，将 \(n\) 拆分成 \(k\) 个数之和。（\(k\) 为任意正整数） 求：\(k\) 个数的乘积最大是多少？乘积的期望是多少？ 思路 首先看第一个问题。易 ......

原题链接：P1903 题意 对于一个序列，维护两个操作： 将 \(a_{x}\) 改为 \(p\)。 求 \(l\) 到 \(r\) 中有多少个不同的数 思路 这道题本来是带修莫队的板子的，但是我是使用分块做的。 具体思路挺板的...但是这道题其实有个 \(trick\)。就是我们先预处理记录 \( ......

题意 给定一个数 \(n\)，要求将 \(n\) 表示成一些 \(4^{k}\) 的数之和或差的形式，要求用的数最少，求方案数。 思路 首先看到这道题的数据范围 \(n\le10^{1000}\)，又是求方案数，所以想到用数位 DP。因为每一个数都是 \(4\) 的次幂，显然我们需要讲原数转化为 \ ......

原题链接：P7532 前言 这道题是今天 NOIP 模拟赛的 T1，赛时只有 5 分。 题意 简化一下题意，即在一个 \(n\times n\) 的方阵中，求出有多少个满足条件的连通块，使得： 同一行或列的两点中间没有空 连通块内全是草 可以发现，其实连通块就是一个凸多边形。 思路 很显然，这道题是 ......

原题链接：CF1901E，树形 dp + 神奇分类讨论。 很容易想到树形 dp。难点在于如何转移以及统计答案，需要大量分讨。 父亲（及其以上）和自己组成连通块，不缩。(只保留自己并且往上传递) 连通块中只有自己一个（记录答案） 一个儿子和自己组成连通块，且自己作为根节点，不和父亲收缩（记录答案） 一 ......

题意 简述一下题意。给定一张图，每条边是双向的。给定一个数\(b\)，求一个最小\(ans\)和一条从\(1\)到\(n\)的路径，使边权和\(<=b\)，点权最大值\(<=ans\)。 思路 看到求点权最大值最小，想到二分。又要让边权和最小，想到最短路。具体来讲，二分一个\(mid\)，对于每个\ ......

Link 华中师范大学2023新生赛 H 龙 Question 有 \(m\) 个宝石孔，有 \(n\) 个宝石，每个宝石可以提升 \(a_i\) 点战斗力 每次镶嵌一个宝石，被选中的宝石会 随机 选择一个宝石孔进去，如果这个孔原来有宝石，则原来的宝石会被损坏 你可以任意决定镶嵌宝石的顺序，她想知道 ......

Link 华中师范大学2023新生赛 D 身无彩凤双飞翼 Question 给出一个 \(n\times m\) 的网格，网格上有一些障碍，问最少添加多少障碍才能使 \((1,1)\) 和 \((n,m)\) 不连通 Solution 我好像用了一种和标答不一样的写法 我们先对图 bfs 一次，如果 ......

Link CF1905 B Begginer's Zelda Question 给出一棵树，每次能把一条路径压缩成一个点，求最少几次把树压缩成一个点 Solution 贪心的想，路径肯定越长越好，所以肯定是以一个儿子节点为起点，以一个儿子节点为终点，儿子节点合并了儿子到根的父节点也合并了，每次合并两 ......

Link CF1905 A Constructive Problems Question 有一个 \(N\times M\) 的矩阵，你需要建造一些房子，把这个矩阵填满 当一个 \(2\times 2\) 的正方形左上和右下有房子时，左下和右上房子会自动生成 当一个 \(2\times 2\) 的正 ......

CodeForces-1913A Rating Increase 依题意模拟。 提交记录：Submission - CodeForces CodeForces-1913B Swap and Delete 交换免费就是能任意重排，从头开始尽量填相反的，剩下只能删去了。 提交记录：Submission ......

CodeForces-1905A Constructive Problems 发现沿着对角线放就行了，答案是 \(\max(n+m)\)。 提交记录：Submission - CodeForces CodeForces-1905B Begginer's Zelda 最优操作每次删两个叶子（除了最后一 ......

problem Farmer John 的牧草地可以看作是一个\(N×M\)（\(2≤N≤10^9, 2≤M≤2⋅10^5\)）的正方形方格组成的二维方阵（想象一个巨大的棋盘）。对于 \(x∈[1,N],y∈[1,M]\)，从上往下第 \(x\) 行、从左往右第 \(y\) 列的方格记为 \((x, ......

题目链接 给你一个 01 矩阵，求满足第一行、最后一行、第一列、最后一列均无 0 的最大子矩阵面积。\(n,m<=200\)。 不难想到对于每个点，预处理出，向其上下左右最大限度扩展。这种方法类似于单调栈的预处理。 预处理后，以每个点为矩阵左上角，向右下枚举矩阵右上角。此时我们已经确定了这个矩阵的第 ......

\(\text{By DaiRuiChen007}\) Contest Link A. Building 4 Problem Link 题目大意 给 \(2n\) 个数对 \((a_i,b_i)\)，构造一个非降序列 \(c_i\) 满足 \(\forall 1\le i\le n,c_i\in\{ ......

题目链接：http://codeforces.com/problemset/problem/762/E 题目大意： 一共有 n 个电台，对于每个电台 i 有三个参数： \(x_i\), \(r_i\), \(f_i\),分别指它的一维坐标、作用半径和频率。如果两个电台的频率差值在 k 内，并且它们的 ......

鸣谢 cinccout。赛时两次看出了我的错误/bx。 闲话：在我看过的所有人的做题过程中，大家都不约而同的把 棋子数量相同时答案相同 当作了第一发（。但是很可惜，这个结论是错误的。 样例已经给出了当棋子数量为 \(2\) 的答案，在此我们略去讨论。 对于棋子数量为 \(1\) 答案也很明显是后手必 ......

赛时队友把这题丢给我说他们去写 B，然后我成功成为了战犯。 首先考虑一个朴素的暴力，建出一个类似线段树的结构。然后每次合并两个儿子节点，操作次数为 $n\log n$，大约需要 1e7 次操作，不能通过。 这时候有一个思路，如果一个区间里的东西比较满，就会让它很慢。但是如果区间比较满，那么重复位置的 ......

传送门：https://atcoder.jp/contests/agc065/tasks/agc065_b 考虑 $dp$ 从 $Q$ 得到 $P$ 的过程个数。每次当我们插入 $i$ 的时候，我们要保证 $[1,i]$ 中所有数在新的 $Q$ 中的相对位置关系和在 $P$ 中相同（因为之后它们的相 ......

传送门：https://atcoder.jp/contests/agc065/tasks/agc065_a 为了方便理解，我们把要求的东西乘一个 $-1$，再把答案序列倒过来；也就是说，我们现在要求 $min_{A'}^{A'为A的排列}(\sum_{i=1}^{N-1}((A_{i+1}-A_{i ......

题目链接 点击打开链接 题目解法 很有思维难度的一道题 首先考虑简化操作（或者说用一种比较好的方法表示） 假设我们选择交换的位置为 \(x\)，不难发现，操作等价于交换 \(sumxor\) 和 \(x\) 于是，有解的条件就好判了，即 \(\{b_i\}\subseteq \{a_i\}\bigc ......

来个可能有点麻烦但不用动脑子的暴力做法。 直接设 \(f_{i,j}\) 表示有 \(i\) 个人时，第 \(j\) 个人幸存的概率。 显然有 \(f_{1,1}=1\)。 对于 \(i > 1\)，分类讨论容易得到： \[f_{i,j}= \begin{cases} \frac{f_{i,n}}{ ......

题目传送门 前置知识 排列组合 | 卢卡斯定理 解法 记 \(m=r-l+1,0 \le k \le n-1\) ，枚举长度 \(i\) ，等价于求 \(\sum\limits_{j=1}^{m}x_j=i\) 的非负整数解的数量。接着推式子就行。 \(\begin{aligned} \sum\li ......