qbxt

11.8 突然被通知要去济南。 当天是很特殊的一天： zsc 请假。 wxy 生日。 jbk 值日班长，明天要写积累素材。 第二天我们组打扫卫生。 lzc 中午去校北门拿秋裤，晚上要在班里讲《我的未来》。 我在玩方舟。 于是乎只剩下不到一个小时的时间，我们要收拾好行李从校到达济南。 急急忙忙地赶到宿 ......

Day2 \(100+96+60+70=326,rk1\) T1 签到题 暴力 T2 莫比乌斯反演题 首先容易想到枚举最大公约数是多少，不妨设枚举的 \(\gcd=g\) ，则我们可以开一个桶 \(b_i\) 表示 \(i\) 倍数的数有多少个 对于每个固定的 \(g\) 答案为 \(\large ......

小葱觉得糖很好吃，现在要把糖卖掉。现在小葱的\(N\)位顾客形成了一棵\(N\)个点的树，小葱可以把糖卖给所有叶子节点上的人。但是，小葱不希望卖太多的糖，所以小葱会做\(K\)次操作。每次操作小葱会等概率选一条边，将两边的顾客合并成一个新顾客，并将原来连到这两个顾客的边全部连接到这个新顾客上。（除了 ......

小葱想要吃糖，小葱将拿出来的N颗糖排成一排，第\(i\)颗糖的美味值为\(a_i\)。小葱很喜欢吃糖，所以小葱会从\(N\)颗糖选择不超过\(K\)段不相交的区间的糖果吃掉。但是小葱同学不希望别人吃到和他美味度差不多的糖，所以对于一颗没被吃掉的糖，小葱希望这颗糖美味度比他吃的糖的美味度最大值还大或者 ......

小葱将买来的糖放进了冰箱冷藏，但是小葱想吃糖了，小葱希望把自己想吃的糖从冰箱里面拿出来。具体来说，小葱同学的冰箱是一棵\(N\)个点的树，每个点有一颗糖，第\(i\)个点的糖的美味值是\(a_i\)。小葱每次取糖会从根节点出发，指定一个目标节点\(p\)，走到\(p\)点并且把这条路径上的所有糖取走 ......

考虑经典的俄罗斯方块游戏，二维平面上有若干个积木，他们会受重力的影响下落并堆叠。注意，积木只会竖直下落，如果下落过程中碰到了别的积木那么就会停下。例如下图： 不同颜色的块代表了不同的积木，这些积木下落之后会形如下图： 积木的形状可以任意的，可能跟传统的俄罗斯方块有一些不同，比如下图： 这张图中的积木 ......

小K很喜欢摸鱼，但他不幸地来到卷王大学学习。他的学习生活可以抽象化成一个如下的过程：一个学期一共有\(n\)天，每一天上午上完课之后，老师会布置\(k_i\)个作业，他们的ddl是\(d_{i,1},d_{i,2},...,d_{i,k_i}\)，一个ddl是\(d\)的作业需要在第\(d\)天的2 ......

T2 倍增+换根即可，但赛时难写 赛时想得线段树二分，也可 from:https://www.cnblogs.com/fox-konata/p/17742669.html 回头一看老师代码，发现换根换的非常神奇，长见识了 方法0： 第一次思考，以为要记录走排名为 \(a_x\) 和 \(a_x+1\ ......

Day6 \(100+30+100+0,rk3\) ，考成这样还能 \(rk3\) ，好怪啊 虽然但是 \(T3\) 是在 \(oeis\) 上找的，虽然写了随机数但还是运气好过掉了 \(T2\) 应该是写寄了吧，感觉自己做法并没有什么问题 T1 比较典的题，并查集维护下一个没被删的点即可 复杂度 ......

本帖涉及以下内容： 超长内容 感性理解 思路引导 屑排版 恶意卖萌 Day4 没考，因为感觉题全是码农题，感觉有点烂 T1 \(lcm(a,b,c) = lcm(lcm(a,b), c)\) ，直接暴力算就好了 然后你就 \(Wa\) 了 因为答案要取模， \(lcm(a,b,c) \mod P \ ......

Day0 晚上玩恐怖游戏好吓人 \(QwQ\) Day1 rk4 有小奖品 T1 没什么好说的 T2 原题 给定一个等差数列，求他的各项乘积，你只需要输出其对 \(1145141\) 取模的结果。 具体的，每组给定 \(d,n,a\) 分别表示公差，长度，首项，你需要求出 \(\prod_{i=0} ......

原题 一条路径上有 \(n\) 个位置，有三种元素：\(slime\)，\(npc\)，\(player\)。 \(slime\) 初始会向右移动，\(npc\) 初始会向左移动，所有元素移动速度是相同的：\(1\) 单位距离每 \(1\) 单位时间。 元素的移动遇到边界会改变初始移动方向，并继续移 ......

原题 一行人，共有 \(n\) 个人，排成一排，在等待你发放矿泉水。 你会发放 \(m\) 轮矿泉水，第 \(i\) 次，你会给前 \(a_i\) 个人发放矿泉水，然后你会发放 \(b_i\) 瓶矿泉水。 具体的，你每次会一瓶一瓶的发矿泉水，每一轮发放 \(b_i\) 次。 每次，你会把矿泉水给最需 ......

原题 给定一个等差数列，求他的各项乘积，你只需要输出其对 \(1145141\) 取模的结果。 具体的，每组给定 \(d,n,a\) 分别表示公差，长度，首项，你需要求出 \(\prod_{i=0}^{n-1} (a+i\times d) \mod 1145141\)。 非常降智好的一道题，赛时往根 ......

原题 小 P 准备了一次预测活动，每个参与活动的人都可以在 PPP 队获胜，GGG 队获胜和平局三种结果中选择自己要预测的一种。如果第 \(i\) 个人预测正确，那么小 P 需要付给他 \(a_i\) 元，否则他需要给小 P 付 \(b_i\) 元。小 P 目前已经收到了 \(n\) 个人报名参加活 ......

# Day 1 ## 有向无环图 - 一种特殊的有向图，没有任何环，简写为 DAG。 - 对于这种图，我们就有“拓扑序”。 ![image](https://img2023.cnblogs.com/blog/3064197/202307/3064197-20230709084636701-85243 ......

有向无环图 有向无环图是一种特殊的图，其最大的意义在于能够拓扑排序。 拓扑排序是指给这个图的 $n$ 个点排序，使得所有 $x \rightarrow y$ 的边 $x$ 点都在 $y$ 前面。 求最短路是 $O_{(n + m)}$ 的，也可以在这张图上做 DP。 拓扑排序 考虑维护一个入度为 $ ......

洛谷P4460 n<20,试试状压 设 $dp[i][j]$ 表示状态为i,最后一个点为j（当前在点j）。 枚举当前点为i，要转移的点为k 转移：$ dp[i|(1<<k-1)][k]+=dp[i][j] $ 还需要判断一下三点连线在不在同一条直线上。 代码： #include<bits/stdc+ ......

DFS 生成树 对于任意一棵 DFS 生成树，其必定只有返祖边，没有横叉边，在求割点和强联通分量上方便很多。 最小生成树 求法：https://www.cnblogs.com/yifan0305/p/17363255.html 严格次小生成树、非严格次小生成树。 最短路问题 Floyd 求最短路、最 ......

数学知识 现有奇数个人，两两间可能认识或不认识，请证明永远存在一个认识偶数个人的人。 将其转化成更强的问题: 给定一张奇数个点的图 $G$ ，证明度数为偶数的点的个数为 奇数。 继续考虑它的相反的问题: 给定一张奇数个点的图 $G$ ，证明度数为奇数的结点的个数为偶数 考虑所有点的度数和，由于一条边 ......