J.Involutions 题解 令  为大小为  的集合对应的答案。 第  个点可以和前  个点之一配对，也可以形成不动点，因此有转移式 。 从组合数角度理解，分别考虑选取  个配对的贡献，则有 。 注意到  大于  的项会被消去，对剩余项运用 Lucas 定理可以得到 。 据此考虑暴力枚举前  项，发现在极端数据下运行时间约 4.7 秒，无法通过。 因此考虑循环展开，即一次枚举  与 ，此时运行时间缩小至一半，即 2.3 秒，可以通过本题。 Bonus：尝试利用循环展开通过 H. Color of Goods。 代码 #include<bits/stdc++.h> using ...

J.2D Travel 题解 首先注意到两维可以独立求解。 据此考虑离线处理。对于每一维，令位置集 为所有当前处于位置 的询问形成的集合，我们记录总偏移量 ，位置集偏移量 ，询问偏移量 和每个询问 所属的位置集 ，同时记录当前边界 与 。 接下来对于从 到 每一次操作，我们依次进行如下处理： 对于插入询问操作，我们将对应询问加入其所属的位置集 ，同时初始化其偏移量为 。 更新操作对应的边界 与 。 对于所有超出边界（即 或 cr&preview=true">）的位置集，我们将其与  或  合并。 对于查询询问操作，我们将询问  的位置更新为 ，同时将  的移动距离...

F.小橙的圈圈 题解 注意到竞赛图上的三元组  共有如下两类状态：  其中的第一类（即三元环）很难枚举，因此考虑枚举第二类三元组。 具体地，我们统计朝每个点  连边的点的总数 ，则在这些点中任取一对 ，都能唯一地确定一个第二类三元组 。 因此第二类三元组的总数为 。答案即为三元组总数  减去第二类三元组的总数。 代码 #include<bits/stdc++.h> using namespace std; typedef long long ll; int i,j,k,n,m,t; ll sd,res,in[5005]; int main(){ cin>>n>&g...

F.粉毛天堂 题解 BCIO  B：彩彩。 C：劈瓦。 I：“结果看见一屋子铺天盖地的二次元粉红色元气少女偶像，警察叔叔愣在那儿大半天，我另外三个朋友还在打游戏完全没反应过来”。 O：修哇。  FKNP  F：承认欲求 Monster 的背面。 K：波奇。 N：波奇。 P：结束乐队。  剩下的 猜的。 代码 AGHM BCIO DEJL FKNP

F.小红的基环树删边 题解 注意到基环树上的环产生两个分支路线，因此  到  的路径最多只有  条，暴搜枚举即可。 代码 #include<bits/stdc++.h> using namespace std; #define N 100050 int i,j,k,n,m,t,vis[N],f[N]; vector<pair<int,int> > v[N]; void dfs(int x,int dep){ if(x==n){ for(i=1;i<=n;i++)if(!vis[i])f[i]=min(f[i],dep); return; } for(a...

E.小A的任务 题解 本题的  版本做法与 CCPC 2023 网络赛 L 题 基本一致。 对于固定的询问 ，在完成前  个 A 类任务的情况下显然应选择  到  中前  小的数。 对应的结果可以将  离散化后用可持久化线段树  查询。 同时，对于固定的  和  ，当  逐渐增加时，由于  对应的  集合严格包含  对应的  集合，因此  对应的第  大也不大于  对应的第  大。即对任意 , ，有 ，即每个  对应的最优  存在决策单调性。 因此可以用决策单调性分治求解。时间复杂度 。 代码 #include <bits/stdc++.h> using namespace std...

E.S 老师的礼物 题解 None 的判断 首先将所有  与  连边，若连边后存在环或图的状态与  冲突则答案不存在。 否则，我们首先判断图的连通性。 将图上的点按  到  的顺序在数轴上一字排开，发现两个联通块能够合并，当且仅当两个联通块对应的区间有交。 证明: 令左侧联通块对应区间为 ，右侧联通块对应区间为 ，如果没有交（即 ），则右边的联通块均有 ，左边的联通块均有 ，不符合条件；如果有交，则可选取满足  且  的点对  并连接。 据此我们可以尝试将最右侧的联通块依次往左合并。具体地，我们从  到  维护指针 ，同时记录使得  最小的位置 ，若  指向其他联通块则连接 （联通块最右侧的点...

D 题数据怎么没有 a,b>0、c=0 的情况？ Hack 1： 0 5 0  Output: YES 4  解释： 所有神都是假神，因此问 b-1 个人就能排除所有情况。 Hack 2： 3 3 0  Output: YES 5  解释： 询问原神在哪个房间，再询问两遍其他房间（询问到原神房间时问假神也会回答 No），均为 No 则为真神，否则为假神。接下来依次排除每个人。 Hack 3： 1 2 0  Output: YES 3  解释： 至少问 3 次才能确认假神。 Hack 4： 1 1 0  Output: NO  解释： 至少有 3 个人才能确认假神。 补充 Hack 5： ...

F 现在是消消乐时间 题解 注意到小球的运动轨迹只有两种：从矩形的四个角之一射出，或者回到发射点进入循环。 接下来对两种情况分别讨论： 1.从某个角射出 令小球的初始位置为 ，射出时间为 ，则  为满足如下同余方程的最小正整数：  注意到方程的答案不超过 ，而当  取矩形的四个角时取得最大值 ，即 。 我们将网格线的交点按棋盘方式黑白染色，由于小球只能斜向移动，因此小球只能在同色点之间移动。 同时，一个方块恰好由一对同色点相连接，且每条边最多只被经过一次（经过两次即说明小球在出口处反弹），因此小球在  的时间内恰好能消除  个方块。 若想消除所有方块则有 ，解得 。 当  时由裴蜀定理可知方程...