,,,

https://www.acgo.cn/contest/2204/detail?matchRoundId=2204&examId=40534&teamCode=1793944541884059648&openLevel=2

https://www.acgo.cn/application/1776484607864774656

https://www.acgo.cn/contest/2026/detail?matchRoundId=2026&examId=39081&teamCode=1661232050350374912&openLevel=2 邀请码：SHAi

4. 游戏的规则是，在你和小码君面前有 N 个数，同时将给出一个数 C ,要求你和小码君在这组数内找到两个数，满足 A−B=C 。找出的数对越多，你们的排名越高。 为了计算赢得比赛的可能性，你们打算先计算出所有满足此条件的数对的个数（不同位置的数字一样的数对算不同的数对）。 输入格式 第一行包含两个正整数 N 和 C 。 接下来的一行包含 N 个正整数，表示你将在这 N 个数中找数对。 输出格式 共一行，表示该串正整数中包含的满足 A−B=C 的数对的个数。 样例组 输入#1 复制 4 1 1 1 2 3 输出#1 复制 3 提示说明 对于 75% 的数据，1 ≤ N ≤ 2000。 对于 100% 的数据，1 ≤ N ≤ 2×10 5 ，0 ≤ a i ≤ 2 30 , 1 ≤ C ≤ 2 30 。 样例解释： 4 个数，分别为 1 1 2 3，总共有 3 对 A-B 的值等于 1。 这三对分别为 2-1、2-1、3-2（不同位置的数字一样的数对算不同的数对）

1.想要投稿超难50题的人可以关注@阿墨（创题）在自己的个人题单里创建名为”稿超难50题“的题单把需要投稿的题目放入题单里@阿墨（创题）每周日查看。

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 嗯嗯嗯额-_-

1.想要投稿超难50题的人可以关注@阿墨（创题）在自己的个人题单里创建名为”稿超难50题“的题单把需要投稿的题目放入题单里@阿墨（创题）每周日查看。 2..想要挑战超难50题的人可以关注@阿墨（创题）在他的个人题单挑战。

AC - Accepted（答案正确） WA - Wrong Answer（答案错误） TLE - Time Limit Exceeded（超出时间限制） RE - Runtime Error（运行时错误） CE - Compilation Error（编译错误） MLE - Memory Limit Exceeded（超出内存限制） OLE - Output Limit Exceeded（输出限制超出） PE - Presentation Error（格式错误）

STL库 包含很多数据结构，可以节省手搓的时间直接用： vector: 动态数组 queue: 队列 priority_queue: 优先队列 deque: 双向队列 set: 有序集合 multiset: 有序集合，但允许相同的元素 unordered_set: 无序集合 map: 字典，以键值对的方式储存数据 unordered_map: 无序的字典，通过哈希实现 bitset: 一种二进制数据结构，常用于加速位运算 倍增 一种基于指数增长模式的算法设计技术 典型例题：求a^b % (1e9+7), a<=1e9, b<=1e9 模板： ST表 一种用于解决区间最小/最大值的数据结构 模板： 矩阵快速幂 矩阵作为倍增的对象 矩阵类乘法的实现： 可以用来加速一些递推方程的计算，例如： 斐波那契数列的地推方程可以表示为：f[n]=f[n-1]+f[n-2] 使用矩阵可以表示为： [Fn+1Fn]=[1110]n⋅[11]\begin{bmatrix} F_{n+1} \\ F_n \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n \cdot \begin{bmatrix} 1 \\ 1 \end{bmatrix} [Fn+1 Fn ]=[11 10 ]n⋅[11 ] 其中 FnF_nFn 表示第 n 个Fibonacci数。 并查集 一种处理不相交集合的数据结构和算法 模板：

图 图是若干个给定的顶点，以及若干条连接两个顶点的边所构成的图形。这种图形通常用来描述 常用G(V,E)G(V,E)G(V,E)表示。某些事物之间的某种特定关系，用顶点代表事物，用连接两个顶点的边表示相应两个事物具有某种关系。 VVV为顶点集合，EEE为边集合。 图是图论的研究对象 顶点的个数叫做图的阶 相关定义 * 有向图的基图：忽略有向图所有边的方向得到的无向图 * 完全图：无向图中任何一对顶点之间都有一条边 * 有向完全图：有向图中任何一对顶点u和v都存在<u,v><v,u>两条有向边 * 稀疏图：边的数目相对少（远小于n(n−1)n(n-1)n(n−1)) * 稠密图：边的数目相对多（接近于完全图或有向完全图） * 平凡图：只有一个顶点的图 * 零图：边集合为空的图 * 自环：一个顶点连接到自身的边 * 重边：两个顶点之间有多条边 * 权值图：边带有全权值的图 * 简单图： 一种无向图或有向图，其中不存在自环与重边 * 多重图：一种无向图或有向图，其中存在自环与重边 * 路径：在图G(V,E)中从顶点viv_ivi 出发，沿着一些边经过一些顶点viv_ivi ,vp1v_{p1}vp1 ,vp2v_{p2}vp2 ,vp3v_{p3}vp3 ,……,vpmv_{pm}vpm 到达顶点vjv_jvj ，则称顶点序列{viv_ivi ,vp1v_{p1}vp1 ,vp2v_{p2}vp2 ,vp3v_{p3}vp3 ,……,vpmv_{pm}vpm ,vjv_jvj }为viv_ivi 到vjv_jvj 的一条路径 * 联通：若从顶点u至v有路径，则称顶点u，v是联通的 * 如果无向图中任意一对顶点都是连通的，则称此图为连通图 * 如果有向图中任意一对顶点都是互相连通的，则称此图为强连通图 树 * 树：一个不存在回路无相连通图 * 树是一种特殊的图 * 树是一种非线性的数据结构，是由n(n≥0)n(n\ge 0)n(n≥0)个节点组成的有限集合 当n==0n==0n==0时，称为空树；如果n>0n>0n>0，树有且只有一个根节点 * 树的前驱与后继：除根节点没有前驱外，其余每个节点都有唯一的一个前驱节点。每个节点可以有0或多个后继节点 * 节点的后继称为节点的的孩子，节点的之家前驱称为节点的父亲，有同一个父节点的不同节点互称兄弟 * 结点拥有的子树的数量叫做节点的度 树中节点的层次：树中根节点为第一层，根节点的孩子为第二层，以此类推…… 树中节点最大层次乘坐是的高度。 注意：有些题中根节点是第0层 树的存储 父亲表示法： 孩子表示法 特殊的树 二叉树（BT） 度数最大为2的树，即二叉树的节点最多有两个子节点，每个子节点分别被称为左孩子节点、右孩子节点， 每个子树分别被称为左子树、右子树 满二叉树：一棵深度为kkk且有2k+12^{k+1}2k+1个节点的二叉树 完全二叉树：若二叉树的高度为kkk，则共有kkk层，除第kkk层外，其他各层(1(1(1到(k−1))(k-1))(k−1))的节点数都达到最大个数， 且kkk层缺少的节点是从左到右并连续的，则称其为完全二叉树 二叉搜索树（BST） 二叉搜索树具有以下性质： * 若任意结点的左子树不空，则左子树上所有结点的值均不大于它的根结点的值。 * 若任意结点的右子树不空，则右子树上所有结点的值均不小于它的根结点的值。 * 任意结点的左、右子树也分别为二叉搜索树。

图论 图 是由若干个给定的顶点/以及若干条连接两个顶点的边所构成的图形 图 是 图论 的研究对象 图(graph)图(graph)图(graph):通常用 G(V,E)G(V,E)G(V,E)表示。VVV 为集合，EEE 为边集合。 > G(V,E)-->GraphGraphGraph VertexVertexVertex EdgeEdgeEdge 顶点的个数称为图的阶 路径 在图G(V,E)中从顶点viv_ivi 出发，沿着一些边经过一些顶点vp1v_{p1}vp1 ,vp2v_{p2}vp2 ,………………,vpmv_{pm}vpm 有向图 有向图：单向的 <1,5>为一对顶点构成的有序对（用尖括号括起来） 有向图的基图：忽略有向图所有边的方向，得到的无向图称为该有向图的基图。（无向图G为有向图的G1的基图） 完全图 一个n阶的完全图含有n∗(n−1)÷2n*(n-1) \div 2n∗(n−1)÷2条边。 完全有向图 有向图中任何一对顶点u和v，都存在<u,v>&<v,u>两条有向边。一个n阶的完全有向图含有n∗(n−1)n*(n-1)n∗(n−1)条边。 稀疏图 边的数目相对较小（远小于n∗(n−1)n*(n-1)n∗(n−1)). 稠密图 边的数量相对较多（接近于完全图或者有向完全图 平凡图 只有一个顶点的图 自环 一个节点连接到自身的边 重边 两个结点之间存在多条边。 带权图 边上有带权值的图 简单图（5） 一种无向图或有向图，其中不存在自环和重边。 多重图（5） 一种无向图或有向图，其中存在自环和重边。 连通 若从顶点u到v有路径，则称顶点u和v是连通的。 连通图 如果无向图中任意一对顶点都是连通的，称此图为连通图。 强连通图 有向图中，每一对顶点u和v，存在u<−>vu<->vu<−>v(双向奔赴)。 连通图和连通分量 如果在图G中，任意2个顶点之间都存在路径，那么称G为连通图（注意是任意2顶点）。上面那张城市之间的图，每个城市之间都有路径，因此是连通图。而下面这张图中，顶点8和顶点2之间就不存在路径，因此下图不是一个连通图，当然该图中还有很多顶点之间不存在路径。 上图虽然不是一个连通图，但它有多个连通子图：0,1,2顶点构成一个连通子图，0,1,2,3,4顶点构成的子图是连通图，6,7,8,9顶点构成的子图也是连通图，当然还有很多子图。我们把一个图的最大连通子图称为它的连通分量。0,1,2,3,4顶点构成的子图就是该图的最大连通子图，也就是连通分量。连通分量有如下特点： 1）是子图； 2）子图是连通的； 3）子图含有最大顶点数。 注意：“最大连通子图”指的是无法再扩展了，不能包含更多顶点和边的子图。0,1,2,3,4顶点构成的子图已经无法再扩展了。 显然，对于连通图来说，它的最大连通子图就是其本身，连通分量也是其本身。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 例题 有101010个顶点的无向图至少有（ ）条边边边才能确保是一个连通图。 解析：2个顶点需要1条边，3个顶点需要2条边，以此类推 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 树 n个V，n-1 个E 连通 当n==0时，称为空树。 二叉树 是一种度数为2的树 满二叉树： 定义：一个深度为k且有2k−12^k-12k−1个结点的树叫做满二叉树。 树中结点的最大层次称为树的（深度）高度； 完全二叉树 若二叉树的高度为kkk，则共有kkk层，除第kkk层外，其他各层(1 (k−1))(1~(k-1))(1 (k−1))的结点数都达到最大个数，且第kkk层缺少的结点是从右向左并连续的（存在的是从左到右），这就是完全二叉树。 注意:注意:注意:满二叉树也是完全二叉树的一种。 二叉搜索树 一种应用广泛的二叉树。

图和树 图(有向图，无向图，有向图的基图是无向图) 定义 > 图有若干节点和线组成 表示 > G(V,E) V顶点集合，E边集合 完全图 > 定义:无向图中任意两点都有相连 > 计算方法：1.n阶完全图有n*(n-1)/2条边 稀疏图（边数量相对少（远小于N*(N-1)））&&稠密图(接近完全图或有向完全图) 自环（自己链连接自己）&&重边（两点之间有多条边相连） 简单图 > 无向或有向图，无自环或重边 多重图 > 无向或有向图，有自环或重边 联通 > 从u到v有路径，则称u与v联通 连通图 > 无向图中任意两点相连 强连通图 > 有向图中，有从u到v的路径，也有从v到u的路径 路径 > 在图G(V,E)中， 树 定义 > 无向连通图中不存在回路 性质 > 有n个点，n-1条边 度 > 结点所拥有的子树的数量，为结点的度，度=0->叶子结点，度!=0->分支结点 前驱 后继 > 除根外，任意结点都有前驱结点 > 除叶子结点外都有后继结点 树的深度(高度) > 根为第一层，根的孩子为第二层，以此类推 二叉树（树的度数为2） > 两个子树，左子树（左孩子），右子树（右孩子） 满二叉树 > 有k层，且结点树为$ 2^k-1 $，即是一个标准的二叉树 完全二叉树 > 二叉树高度为k，除第k层以前是满的，第k层不完全，但第k层的结点是从左到右连续的 > ####二叉搜索树 > 根结点的左子树<根节点 > 根节点的右子树>根节点

AKSZ-第X课 图论 图分为有向图、无向图，有权图、无权图 图：G(V,E) V=顶集 E=边集 顶点的个数是图的阶 把几组具体的联系转变为抽象的模型就是图论模型 > G(V,E)G(V,E)G(V,E)=GraphGraphGraph VertexVertexVertex EdgeEdgeEdge 有向图的基础就是无向图。 每个顶点之间都有边相连就是完全图 > 完全图公式：边数=n∗(n−1)/2边数=n*(n-1)/2边数=n∗(n−1)/2 > 但如果有向，就不用除以二 稀疏图和稠密图是用来看边的密度 对于n=1e5 边数<=1e5就算稀疏图 自环是自己连自己，重边就是有完全一致的边 边上有数字就是有权值 简单图就是没有自环和重边，相反则是多重图 平凡图就是只有一个点，零图就是没路 路径 从V（j）出发到V（i）就是路径 长度就是边数 若u到v有路径，则称他们是联通的 如果谁到谁都有路，就是连通图，有向则称为强连通图 树 n个顶点，必须联通，n+e条边 **根节点（root）**绝对固定 度 就是子节点数量 度为零是叶子节点，否则叫分支节点，一整棵树的度是度的最大值 前驱、后继、兄弟 对于一个点，它的父节点就是它的前驱，子节点就是后继，同父节点的几个节点就是兄弟 树的输入 高度 高度就是根节点走到一个点所用的步数，+不+1看根节点深度 树中任意两个节点之间有且仅有一条简单路径 树的遍历 二叉树 每个节点都有两个子树 满二叉树 深度为k且有2k−12^k-12k−1个节点 完全二叉树 若二叉树高度为k，除第k层外，（1~（k-1））的节点数都达到最大个数，且第k层有的点是从左到右并连续的，这就是完全二叉树 二叉搜索树 所字数所有节点都小于根节点，右边则大于

rt，记忆化的本质就是 dpdpdp 思想，这种题都不用找方程，注意下细节就行了

rt，蒟蒻居然TLE了，一康数据发现#3、#4测试点 n = 1，#3 测试点中图仅仅包含1,#4 恰恰相反，只有1个0,所以可以加入以下特盘：

翻译 多米尼克设想了一个正整数p1，…，pn的数组。让我们将该数组的排序版本表示为q1，…，qn。 此外，他还设想了一系列允许的换人。如果一对（X，Y）是允许替换集合的成员，Dominik可以交换数组p中X和Y位置的数字。 Marin正在向Dominik Q提供查询，每个查询都属于以下类型之一： 交换A和B位置的数字。 将对（A，B）添加到允许的替换集合中。 马林可以给已经在允许换人范围内的一对（A，B）。 看看是否可以只使用允许的替换对数组进行排序？ 替换可以按任意顺序使用，并且每个替换可以进行任意次数。 如果从位置a的数字可以仅使用允许的字幕转移到位置B，那么我们调用一对链接的位置（a，B）。 让我们把链接到位置A的所有位置的集合称为A的云。 如果云中的每个位置j都可以使用一系列允许的替换来实现pj=qj，那么云就是好的。 你必须回答存在多少对不同的位置（A，B），使其保持： a.位置a和B没有链接。B.a的云不好，B的云也不好。c.如果我们将对（a，B）添加到允许的替换集，则a的云（通过链接a的云和B的云创建）变好。 请注意：对（A，B）和（B，A）被认为是同一对。 输入格式 输入的第一行包含整数N和Q（1≤N，Q≤1000 000）。 第二行输入包含N个整数p1、…、pn（1≤p1、…，pn≤1000 000）。 以下Q行中的每一行都包含以下格式的查询： ● 行中的第一个数字是集合{1,2,3,4}中的查询T的类型。 ● 如果查询T的类型是1或2，则后面跟着两个不同的整数A和B（1≤A，B≤N） 其表示取代（A、B）。 输出格式 对于每个类型为3或4的查询，在其单独的行中输出答案。 类型3的查询答案是“DA”（克罗地亚语表示是）或“NE”（克罗地亚文表示否），不带引号，类型4的查询答案为任务中的非负整数。 输入输出样例 输入#1. 复制 3 5 1 3 2 4. 3. 2 2 3 4. 3. 输出#1. 复制 1. 氖 0 DA 输入#2. 复制 5 5 4 2 1 4 4 3. 4. 1 1 3 3. 4. 输出#2. 复制 氖 1. DA 0 输入#3. 复制 4 10 2 1 4 3 3. 4. 1 1 2 3. 4. 2 2 3 2 1 2 4. 2 3 4 3. 输出#3. 复制 氖 2. 氖 1. 3. DA 说明/提示 在占总分50%的测试用例中，它将保持N，Q≤1000。 第一个测试用例的说明： 第一个查询的答案是1，因为位置对（2，3）满足所有给定的要求。 第二个查询的答案是NE（否），因为无法将数字2和3转移到 对应的位置，因为所允许的替换的集合是空的。 在第三个查询之后，我们将对（2，3）添加到允许的替换集合中。 第四个查询的答案现在是0，因为2和3已经链接，而第五个查询的回答 查询为DA（是），因为可以通过应用允许的替换（2，3）对数组进行排序。

#include <bits/stdc++.h> using namespace std; const int qmaxzie=1000000; int q[1000010]; int head,tail; void init(){ head=tail=0; } void push(int x){ tail=(tail+1)%qmaxzie; q[tail]=x; } void pop(){ head=(head+1)%qmaxzie; } int front(){ return q[(head+1)%qmaxzie]; } int beck(){ return q[tail]; } bool empty(){ return head==tail; } int size(){ return (tail+qmaxzie-head)%qmaxzie; } void clear(){ head=tail; } int main(){ init(); int n,k; cin>>n>>k; for(int i=0;i<n;i++){ push(i); } while(size()!=1){ for(int i=1;i<k;i++){ push(front()); pop(); } pop(); } cout<<front(); return 0; }

机翻(经过整理 遵照原文) 题目描述 贝西和农夫约翰喜欢山羊卡丁车比赛。这个想法与其他人喜欢的卡丁车比赛非常相似，只是卡丁车是由山羊拉的，支架是由附近的农田制成的。农田由NNN个草地和MMM条道路组成，每条道路连接一对草地。 贝西想用附近的农场做一道菜。农场是两个或两个以上草地的子集，其中的每一片草地都可以沿着一系列不同的道路到达另一片草地。 附近的农田可能包含多个农场。假设有KKK个农场。贝西想通过增加长度为XXX的KKK条道路来连接所有KKK个农场，从而形成一个山羊卡丁车环路。每个农场应该只参观一次，每个农场内必须穿过至少一条道路。 为了让赛道对参赛者来说有趣，赛道的总长度至少应该是YYY。贝西想知道所有这些有趣赛道的总赛道长度的总和。如果一条赛道上有两个相邻的草地（加上农场之间的道路后），而另一条赛道则不同。请注意，只有选择的道路，而不是山羊卡丁车将沿着这些道路行驶的方向。 输入格式 第一行输入包含NNN,MMM,XXX和YYY，其中1≤N≤15001≤N≤15001≤N≤1500,1≤M≤N−11≤M≤N−11≤M≤N−1以及0≤X,Y≤25000≤X,Y≤25000≤X,Y≤2500。 以下MMM条线中的每一条都描述了道路。线条的形式是：Ai,Bi,DiA_{i},B_{i},D_{i}Ai ,Bi ,Di ，意思是草地AiA_{i}Ai 和BiB_{i}Bi 与整数长度为DiD_{i}Di 的aroad相连(1≤Ai,Bi≤N1≤A_{i},B_{i}≤N1≤Ai ,Bi ≤N,0≤Di≤25000≤D_{i}≤25000≤Di ≤2500)。每个草地至少与一条道路相连，并且没有自行车道路。 在至少70%的测试用例中，还保证N≤1000N≤1000N≤1000和Y≤1000Y≤1000Y≤1000。 输出格式 输出一个整数，给出所有有趣音轨的音轨长度之和。由于轨道长度之和可能相当大，请打印长度之和的模109+710^9+7109+7。 说明/提示 此示例有6个可能的轨迹 1-->2-->4-->5->1（长度11） 1->2-->5->4->1（长度11） 2-->3-->4-->5-->2（长度12） 2-->3-->5-->4-->2（长度12） 1-->2-->3-->4-->5-->1（长度15） 1-->2-->3-->5-->4-->1（长度15） 答案是12+12+15+15=5412+12+15+15=5412+12+15+15=54，只将长度至少为121212的轨道相加。 请注意，对于这个问题，标准时间限制增加到每个测试用例3秒（对于Java和Python，每个用例6秒）。 AC助手回答 首先，这是一个组合优化问题，涉及到图论和最短路径的概念。我们需要找到所有可能的赛道组合，这些赛道的长度至少为YYY，并且每个农场被访问一次。这要求我们识别出所有的连通分量（即题目中的农场），然后在这些连通分量之间添加XXX长度的边，形成一个闭合的赛道。 1. 理解题目：确保你理解了题目的核心要求，即寻找满足条件的赛道，赛道的总长度至少为YYY，并且每个农场至少有一条内部道路。 2. 预处理数据：你需要先找出所有的连通分量（农场），这可以通过深度优先搜索（DFSDFSDFS）或广度优先搜索（BFSBFSBFS）来实现。在这个过程中，你需要记录下每个农场包含的节点数（即meadowsmeadowsmeadows的数量）。 3. 计算可能的赛道：对于每一对不同的农场，你可以添加一条长度为XXX的边。你需要计算所有可能的边对组合，并累加它们的长度。注意，每个农场只需要添加一次边，因为赛道需要回溯到起点。 4. 满足最小长度的赛道：你需要筛选出总长度大于等于YYY的赛道。对于每个可能的赛道，将其长度累加并取模109+710^9+7109+7 5. 优化计算：由于题目规模较大，直接暴力求解可能会超时。你可以考虑使用动态规划或者回溯法来减少重复计算。例如，可以先固定一个农场，然后尝试连接其他农场，这样可以减少计算量。 6. 处理样例：先从简单的样例开始，尝试手动构造解决方案，然后逐渐增加复杂度。对于这个特定的样例，你可以尝试画出图，并观察如何形成满足条件的赛道。 7. 编码和调试：将上述思路转换为代码，注意处理好边界情况和数据结构的效率。在编码过程中，可以使用单元测试来验证你的函数是否按预期工作。 请尝试根据这些提示去解决这个问题，如果遇到困难，再告诉我具体的问题，我会进一步提供帮助。记住，实践和思考是学习编程和算法的关键。