qbxt
【闲话】QBXT集训
11.8 突然被通知要去济南。 当天是很特殊的一天: zsc 请假。 wxy 生日。 jbk 值日班长,明天要写积累素材。 第二天我们组打扫卫生。 lzc 中午去校北门拿秋裤,晚上要在班里讲《我的未来》。 我在玩方舟。 于是乎只剩下不到一个小时的时间,我们要收拾好行李从校到达济南。 急急忙忙地赶到宿 ......
qbxt23国庆刷题Day2 题解
Day2 \(100+96+60+70=326,rk1\) T1 签到题 暴力 T2 莫比乌斯反演题 首先容易想到枚举最大公约数是多少,不妨设枚举的 \(\gcd=g\) ,则我们可以开一个桶 \(b_i\) 表示 \(i\) 倍数的数有多少个 对于每个固定的 \(g\) 答案为 \(\large ......
qbxt 突破营 Day7 T4
小葱觉得糖很好吃,现在要把糖卖掉。现在小葱的\(N\)位顾客形成了一棵\(N\)个点的树,小葱可以把糖卖给所有叶子节点上的人。但是,小葱不希望卖太多的糖,所以小葱会做\(K\)次操作。每次操作小葱会等概率选一条边,将两边的顾客合并成一个新顾客,并将原来连到这两个顾客的边全部连接到这个新顾客上。(除了 ......
qbxt 突破营 Day7 T3
小葱想要吃糖,小葱将拿出来的N颗糖排成一排,第\(i\)颗糖的美味值为\(a_i\)。小葱很喜欢吃糖,所以小葱会从\(N\)颗糖选择不超过\(K\)段不相交的区间的糖果吃掉。但是小葱同学不希望别人吃到和他美味度差不多的糖,所以对于一颗没被吃掉的糖,小葱希望这颗糖美味度比他吃的糖的美味度最大值还大或者 ......
qbxt 突破营 Day7 T2
小葱将买来的糖放进了冰箱冷藏,但是小葱想吃糖了,小葱希望把自己想吃的糖从冰箱里面拿出来。具体来说,小葱同学的冰箱是一棵\(N\)个点的树,每个点有一颗糖,第\(i\)个点的糖的美味值是\(a_i\)。小葱每次取糖会从根节点出发,指定一个目标节点\(p\),走到\(p\)点并且把这条路径上的所有糖取走 ......
qbxt 突破营 Day1 T4
考虑经典的俄罗斯方块游戏,二维平面上有若干个积木,他们会受重力的影响下落并堆叠。注意,积木只会竖直下落,如果下落过程中碰到了别的积木那么就会停下。例如下图: 不同颜色的块代表了不同的积木,这些积木下落之后会形如下图: 积木的形状可以任意的,可能跟传统的俄罗斯方块有一些不同,比如下图: 这张图中的积木 ......
qbxt 突破营 Day1
小K很喜欢摸鱼,但他不幸地来到卷王大学学习。他的学习生活可以抽象化成一个如下的过程:一个学期一共有\(n\)天,每一天上午上完课之后,老师会布置\(k_i\)个作业,他们的ddl是\(d_{i,1},d_{i,2},...,d_{i,k_i}\),一个ddl是\(d\)的作业需要在第\(d\)天的2 ......
再谈 qbxt2023国庆刷题 Day7 T2 树
T2 倍增+换根即可,但赛时难写 赛时想得线段树二分,也可 from:https://www.cnblogs.com/fox-konata/p/17742669.html 回头一看老师代码,发现换根换的非常神奇,长见识了 方法0: 第一次思考,以为要记录走排名为 \(a_x\) 和 \(a_x+1\ ......
qbxt2023国庆刷题 Day6 ~ Day7
Day6 \(100+30+100+0,rk3\) ,考成这样还能 \(rk3\) ,好怪啊 虽然但是 \(T3\) 是在 \(oeis\) 上找的,虽然写了随机数但还是运气好过掉了 \(T2\) 应该是写寄了吧,感觉自己做法并没有什么问题 T1 比较典的题,并查集维护下一个没被删的点即可 复杂度 ......
qbxt2023国庆刷题 Day4 ~ Day7
本帖涉及以下内容: 超长内容 感性理解 思路引导 屑排版 恶意卖萌 Day4 没考,因为感觉题全是码农题,感觉有点烂 T1 \(lcm(a,b,c) = lcm(lcm(a,b), c)\) ,直接暴力算就好了 然后你就 \(Wa\) 了 因为答案要取模, \(lcm(a,b,c) \mod P \ ......
qbxt2023国庆刷题
Day0 晚上玩恐怖游戏好吓人 \(QwQ\) Day1 rk4 有小奖品 T1 没什么好说的 T2 原题 给定一个等差数列,求他的各项乘积,你只需要输出其对 \(1145141\) 取模的结果。 具体的,每组给定 \(d,n,a\) 分别表示公差,长度,首项,你需要求出 \(\prod_{i=0} ......
qbxt 4219: npc与slime
原题 一条路径上有 \(n\) 个位置,有三种元素:\(slime\),\(npc\),\(player\)。 \(slime\) 初始会向右移动,\(npc\) 初始会向左移动,所有元素移动速度是相同的:\(1\) 单位距离每 \(1\) 单位时间。 元素的移动遇到边界会改变初始移动方向,并继续移 ......
qbxt 4220: 矿泉水
原题 一行人,共有 \(n\) 个人,排成一排,在等待你发放矿泉水。 你会发放 \(m\) 轮矿泉水,第 \(i\) 次,你会给前 \(a_i\) 个人发放矿泉水,然后你会发放 \(b_i\) 瓶矿泉水。 具体的,你每次会一瓶一瓶的发矿泉水,每一轮发放 \(b_i\) 次。 每次,你会把矿泉水给最需 ......
qbxt 4218: 等差
原题 给定一个等差数列,求他的各项乘积,你只需要输出其对 \(1145141\) 取模的结果。 具体的,每组给定 \(d,n,a\) 分别表示公差,长度,首项,你需要求出 \(\prod_{i=0}^{n-1} (a+i\times d) \mod 1145141\)。 非常降智好的一道题,赛时往根 ......
qbxt 4179 积木中赛(block)
原题 小 P 准备了一次预测活动,每个参与活动的人都可以在 PPP 队获胜,GGG 队获胜和平局三种结果中选择自己要预测的一种。如果第 \(i\) 个人预测正确,那么小 P 需要付给他 \(a_i\) 元,否则他需要给小 P 付 \(b_i\) 元。小 P 目前已经收到了 \(n\) 个人报名参加活 ......
暑假QBXT集训01
# Day 1 ## 有向无环图 - 一种特殊的有向图,没有任何环,简写为 DAG。 - 对于这种图,我们就有“拓扑序”。 ![image](https://img2023.cnblogs.com/blog/3064197/202307/3064197-20230709084636701-85243 ......
qbxt day3
有向无环图 有向无环图是一种特殊的图,其最大的意义在于能够拓扑排序。 拓扑排序是指给这个图的 $n$ 个点排序,使得所有 $x \rightarrow y$ 的边 $x$ 点都在 $y$ 前面。 求最短路是 $O_{(n + m)}$ 的,也可以在这张图上做 DP。 拓扑排序 考虑维护一个入度为 $ ......
2023 qbxt 笔记整理
洛谷P4460 n<20,试试状压 设 $dp[i][j]$ 表示状态为i,最后一个点为j(当前在点j)。 枚举当前点为i,要转移的点为k 转移:$ dp[i|(1<<k-1)][k]+=dp[i][j] $ 还需要判断一下三点连线在不在同一条直线上。 代码: #include<bits/stdc+ ......
qbxt day2
DFS 生成树 对于任意一棵 DFS 生成树,其必定只有返祖边,没有横叉边,在求割点和强联通分量上方便很多。 最小生成树 求法:https://www.cnblogs.com/yifan0305/p/17363255.html 严格次小生成树、非严格次小生成树。 最短路问题 Floyd 求最短路、最 ......