- 2023-02-24【YBT2023寒假Day15 C】缺口一样(数论)(莫队)(根号分治)
缺口一样题目链接:YBT2023寒假Day15C题目大意给你一个序列,多次询问,每次问你一个区间这里面所有非空点集的最大公约数之积,对质数取模。思路首先质因子之间是独立的,考虑
- 2023-02-24【YBT2023寒假Day15 A】破烂衣裳(Burnside引理)(DP)(矩阵乘法)
破烂衣裳题目链接:YBT2023寒假Day15A题目大意有一个n个点的环,有k种颜色,一开始都没有颜色。每次你可以选择一个位置,把它染成k种颜色的其中一个,但是相邻的两个位置
- 2023-02-24【YBT2023寒假Day14 C】字符串题(SAM)(树链剖分)(线段树)
字符串题题目链接:YBT2023寒假Day14C题目大意对于一个字符串S定义F(S)是fail树上除了0点其它点的深度和。G(S)是S每个子串S'的F(S')之和。然后一个空
- 2023-02-24【YBT2023寒假Day14 B】二进制数(数位DP)(数学)
二进制数题目链接:YBT2023寒假Day14B题目大意问你[A,B]之间有多少个整数,满足它二进制表示下(不要前导0)子串00,01,10,11个数分别是a,b,c,d。其中A,B<=2^{100000},a
- 2023-02-24【YBT2023寒假Day14 A】切割蛋糕(计算几何)
切割蛋糕题目链接:YBT2023寒假Day14A题目大意给你一个圆,圆心在原点,每次有一条直线,切掉圆中不包含原点的部分。(直线给出的部分是它在于圆两个交点形成的线段的垂直平分
- 2023-02-22【YBT2023寒假Day12 C】树的计数 II(prufer)(结论)(数学)
树的计数II题目链接:YBT2023寒假Day12C题目大意给你一个长度为n的排列p,问你有多少个不同的有标号无根树,满足如果i,j有边那pi,pj也有边。思路首先可以把排列变
- 2023-02-22【YBT2023寒假Day12 B】仰望星空(DP)(线段树)(笛卡尔树)
仰望星空题目链接:YBT2023寒假Day12B题目大意有一个n*n的网格,第i列下面的ai个点都是障碍。然后又一些不是障碍的地方有特殊点,删掉它有费用。要你用最小费用使得
- 2023-02-22【YBT2023寒假Day12 A】我的世界(二分)(主席树)
我的世界题目链接:YBT2023寒假Day12A题目大意有n个数,每一秒每个数都会减小1,而且你可以选一个数让它减小x,小于0的数会变成0。给你s秒,问你s秒操作后所有数中
- 2023-02-21【YBT2023寒假Day11 B】催眠大师(费用流)
催眠大师题目链接:YBT2023寒假Day11B题目大意有一个n*n的棋盘,有一些位置有障碍。然后定义棋盘上两个位置能相互攻击当且仅当在同一行或同一列,且之间的所有位置都没有
- 2023-02-21【YBT2023寒假Day11 A】海妖沙龙(计算几何)
海妖沙龙题目链接:YBT2023寒假Day11A题目大意平面上有n个点,然后对于一个排列,如果按顺序走对于的点,会形成若干个线段组成的路径,然后你从前一个线段走到下一个线段端点
- 2023-02-20【YBT2023寒假Day10 C】娄居吉勾(点分树)
娄居吉勾题目链接:YBT2023寒假Day10C题目大意有一个n个点m条边的无向连通图,每个点至多在k个简单环上。然后有q个操作,标记一个没有标记过的点,或者给你一个点求
- 2023-02-20【YBT2023寒假Day10 B】随机游走(记忆化搜索)
随机游走题目链接:YBT2023寒假Day10B题目大意有n个点排成环,你一开始在1号点,每次可以等概率选择左边跳两格,左边跳一格,右边跳一格,右边跳两格。走到一个走过的点就停
- 2023-02-20【YBT2023寒假Day10 A】集合比较(数学)(启发式分裂)
集合比较题目链接:YBT2023寒假Day10A题目大意给你一个长度为n的排列p,定义两个大小为n不可重集合的比较方式是先比较各自第p1小的元素,如果相同比p2,以此类推。给
- 2023-02-08【YBT2023寒假Day9 B】买棉花糖(DP)(分治)
买棉花糖题目链接:YBT2023寒假Day9B题目大意有n个商店,每个商店有ci个物品,原价是ai,你在一个商店买的物品越多,下一个买的就越少,每次减少di块钱。然后有q次询问,
- 2023-02-08【YBT2023寒假Day8 C】图论题(图论)(并查集)(线段树合并)
图论题题目链接:YBT2023寒假Day8C题目大意给你一个无向图,然后你会一直操作直到无法操作,每次找出一个满足条件的三元组(a,b,c),满足a<b<c,a,b与a,c之间有边,b,c之间没
- 2023-02-08【YBT2023寒假Day8 B】期望题(期望DP)
期望题题目链接:YBT2023寒假Day8B题目大意给你一个n个节点的数,每个点有黑色或者白色。你一开始在1号点,一直进行下面的操作:如果点第一次到或者是黑色就把计数器加
- 2023-02-07【YBT2023寒假Day7 B】打怪兽(cdq分治)(斜率优化)
打怪兽题目链接:YBT2023寒假Day7B题目大意有n个怪,每个怪有攻击力和血量。你每次可以选一个怪打b的伤害,如果一个怪的血量小于等于0就死了。然后每次你打完之后所
- 2023-02-07【YBT2023寒假Day7 A】出题人(线段树优化DP)
出题人题目链接:YBT2023寒假Day7A题目大意有一个序列,你要把它分成若干份,每一份的值的和不超过m,而且每一段最大值的和最小。输出每段最大值和的最小值。思路考虑每次
- 2023-02-07【YBT2023寒假Day6 C】子串染色(SAM)(线段树)(启发式合并)
子串染色题目链接:YBT2023寒假Day6C题目大意对于一个s的子串t,把它在s中所有出现的位置包含的所有下标染黑,黑色连续段的数目是子串t的价值。然后给你一个k和一
- 2023-02-07【YBT2023寒假Day6 A】寄蒜挤河(计算几何)(线段树)
寄蒜挤河题目链接:YBT2023寒假Day6A题目大意有一些二维平面上的点,按顺序加入,每次加入一个点后,问你图上有多少个三元点对使得它们构成的三角形严格包含原点,就是原点不能
- 2023-02-04【YBT2023寒假Day5 C】路径计数(数学)(生成函数)
路径计数题目链接:YBT2023寒假Day5C题目大意有一个h*w的网格,你要从左上角走到右下角,每次可以向右或者向下,定义一条路径的分数是它经过的位置的权值和。每次会选择权
- 2023-02-04【YBT2023寒假Day5 B】全面沦陷(tarjan)
全面沦陷题目链接:YBT2023寒假Day5B题目大意给你一个有向图,问你有多少个点可以到达所有点。一个点x能到达一个点y当且仅当在原图有路径或在把边反向的图中有路径。
- 2023-02-03【YBT2023寒假Day4 C】樱桃莓莓(交互)(四毛子分块)(线段树)
樱桃莓莓题目链接:YBT2023寒假Day4C题目大意有一个黑盒操作满足交换律和结合律,有n个数,q次询问,每次选m个下标,你要计算所有不包含那m个下标的数进行黑盒操作之后的
- 2023-02-03【YBT2023寒假Day4 B】人人人数(数学)
人人人数题目链接:YBT2023寒假Day4B题目大意随机生成一个长度为m且每个元素都是1~n的整数单调不降序列,问你这个序列的众数的期望出现次数是多少。(随机是所有满足条
- 2023-02-02【YBT2023寒假Day4 A】网格染色(DP)(矩阵乘法)(DFT)
网格染色题目链接:YBT2023寒假Day4A题目大意有一个n*3的网格,你可以选恰好m个格子染成黑色。然后对于一个黑点,我们对它周围的\(8\)个点中的一些有限制不能是黑点,