摘要：
【洛谷5439】【XR 2】永恒（树链剖分，线段树） 题面 "洛谷" 题解 首先两个点的$LCP$就是$Trie$树上的$LCA$的深度。 考虑一对点的贡献，如果这两个点不具有祖先关系，那么这对点被计算的次数是$size[u] size[v]$次。否则具有祖先关系，假设$u$是$v$祖先，则是$si 阅读全文
posted @ 2019-07-01 17:30
小蒟蒻yyb
阅读(545)
评论(0)
推荐(0)
摘要：
【洛谷5437】【XR 2】约定（拉格朗日插值） 题面 "洛谷" 题解 首先发现每条边除了边权之外都是等价的，所以可以考虑每一条边的出现次数。 显然钦定一条边之后构成生成树的方案数是$2 n^{n 3}$。可以直接$purfer$序列算。 也可以发现每一条边的出现次数相等，树的总数是$n^{n 2} 阅读全文
posted @ 2019-06-30 21:52
小蒟蒻yyb
阅读(579)
评论(0)
推荐(0)
摘要：
【洛谷5438】【XR 2】记忆（数论） 题面 "洛谷" 题解 很好的一道题目。 我们首先把所有数的每个质因子的出现次数模二，也就是把最大的完全平方因子给除掉。然后剩下部分一样的就可以产生$1$的贡献，所以答案就是$r l+1$减去除掉完全平方因子之后不同的数的个数。 那么如果$l=1$，答案就是不 阅读全文
posted @ 2019-06-30 15:46
小蒟蒻yyb
阅读(509)
评论(0)
推荐(0)
摘要：
【UOJ 82】【UR 7】水题生成器（贪心） 题面 "UOJ" 题解 把$n!$的所有约数搜出来，这个个数不会很多。 然后从大往小能选则选就好了。 阅读全文
posted @ 2019-06-29 22:15
小蒟蒻yyb
阅读(329)
评论(0)
推荐(0)
摘要：
【LOJ 3146】[APIO2019]路灯（树套树） 题面 "LOJ" 题解 考场上因为$\text{bridge}$某个$\text{subtask}$没有判$n=1$的情况导致我卡了$3.5h$左右，然后这题就只能匆匆$rush$了一个$60$分暴力...... 考虑维护出每一个时刻的亮的灯的 阅读全文
posted @ 2019-06-27 22:56
小蒟蒻yyb
阅读(575)
评论(0)
推荐(0)
摘要：
【LOJ 3145】[APIO2019]桥梁（分块，并查集） 题面 "LOJ" 题解 因为某个$\text{subtask}$没判$n=1$的情况导致我自闭了很久的题目。。。 如果没有修改操作，可以克鲁斯卡尔重构树在线处理。或者按照边权排序离线并查集处理。 现在有修改操作，于是我们来分块。 我们对于 阅读全文
posted @ 2019-06-27 07:54
小蒟蒻yyb
阅读(646)
评论(0)
推荐(0)
摘要：
【LOJ 3144】[APIO2019]奇怪装置（数论） 题面 "LOJ" 题解 突然发现$LOJ$上有$APIO$的题啦，赶快来做一做。 这题是窝考场上切了的题嗷。写完暴力之后再推了推就推出正解了。。。 考虑$t1,t2$两个时刻，如果两个时刻的$(x,y)$相等的话，考虑是一种什么样的情况。 $ 阅读全文
posted @ 2019-06-26 20:35
小蒟蒻yyb
阅读(480)
评论(2)
推荐(0)
摘要：
【UOJ 76】【UR 6】懒癌（动态规划） 题面 "UOJ" 题解 神....神仙题。 先考虑如果是完全图怎么做。。。 因为是完全图，所以是对称的，所以我们只考虑一个有懒癌的人的心路历程。 如果只有一只狗有懒癌：第一天，看了看，似乎其他的狗都没有，但是村子里至少有一只狗有，然后就确定了。 如果有两 阅读全文
posted @ 2019-06-26 19:30
小蒟蒻yyb
阅读(682)
评论(2)
推荐(1)
摘要：
【UOJ 75】【UR 6】智商锁（矩阵树定理，随机） 题面 "UOJ" 题解 这种题我哪里做得来啊[惊恐]，，， 题解做法：随机$1000$个点数为$12$的无向图，矩阵树定理算出它的生成树个数，然后找到四张图不拼接直接放在一起，也就是找到四个图，假设其生成树个数是$f(G)$，那么就找到$f(G 阅读全文
posted @ 2019-06-26 11:10
小蒟蒻yyb
阅读(745)
评论(0)
推荐(1)
摘要：
【UOJ 74】【UR 6】破解密码 题面 "UOJ" 题解 发现这个过程是一个字符串哈希的过程。 把第一位单独拿出来考虑，假设这个串是$p+S$，旋转后变成了$S+p$。 其哈希值分别是：$p 26^{|S|}+hash(S)$和$hash(S) 26+p$。 那么$h[i] 26 h[i+1]= 阅读全文
posted @ 2019-06-26 09:20
小蒟蒻yyb
阅读(455)
评论(0)
推荐(0)
摘要：
AtCoder Grand Contest 017 A Biscuits 有$n$个数，问有多少个集合的数的和模$2$余$P$。 随便$dp$一下就好了。 cpp include include using namespace std; define ll long long inline int 阅读全文
posted @ 2019-06-26 08:45
小蒟蒻yyb
阅读(460)
评论(0)
推荐(0)
摘要：
【UOJ 62】【UR 5】怎样跑得更快（莫比乌斯反演） 题面 "UOJ" 题解 众所周知，$lcm(i,j)=\frac{ij}{gcd(i,j)}$，于是原式就变成了： $$\sum_{j=1}^n gcd(i,j)^{c d}i^dj^dx_j\equiv b_i$$ 于是我们就可以写成函数的 阅读全文
posted @ 2019-06-23 20:44
小蒟蒻yyb
阅读(610)
评论(0)
推荐(0)
摘要：
【UOJ 61】【UR 5】怎样更有力气（最小生成树） 题面 "UOJ" 题解 最最最暴力的想法是把所有边给处理出来然后跑$MST$。 考虑边权的情况，显然离线考虑，把么一天按照$w_i$进行排序，显然在这一天的可以连的所有点中，我们能连则连。 考虑把这一天的所有的限制给弄出来（也就是弄出限制的子图 阅读全文
posted @ 2019-06-23 15:38
小蒟蒻yyb
阅读(632)
评论(0)
推荐(0)
摘要：
【UOJ 60】【UR 5】怎样提高智商 题面 "UOJ" 题解 首先猜猜答案是$4 3^{n 1}$。即前面的选啥都行，后面的搞搞就行了。 而打表（看题解），可以知道答案就是这个，并且每个问题都是询问$A$的个数，选项都是$0$。 证明啥的不存在的。 cpp include include usi 阅读全文
posted @ 2019-06-22 19:58
小蒟蒻yyb
阅读(322)
评论(0)
推荐(0)
摘要：
【UOJ 51】【UR 4】元旦三侠的游戏（博弈论） 题面 "UOJ" 题解 考虑暴力，$sg[a][b]$记录$sg$函数值，显然可以从$sg[a+1][b]$和$sg[a][b+1]$推过来。 发现可以从$sg[a][b]$推到$sg[a][b+1]$的值很少，所以可以直接把这些值全部提前计算出 阅读全文
posted @ 2019-06-20 22:42
小蒟蒻yyb
阅读(360)
评论(2)
推荐(0)
摘要：
【UOJ 50】【UR 3】链式反应（分治FFT，动态规划） 题面 "UOJ" 题解 首先把题目意思捋一捋，大概就是有$n$个节点的一棵树，父亲的编号大于儿子。 满足一个点的儿子有$2+c$个，其中$c\in A$，且$c$个儿子是叶子，另外$2$个存在子树，且两种点的链接的边是不同的，求方案数。 阅读全文
posted @ 2019-06-19 22:50
小蒟蒻yyb
阅读(877)
评论(2)
推荐(0)
摘要：
【UOJ 49】【UR 3】轴仓库 题面 "UOJ" 题解 不难发现一定是每次找到离当前位置最近的一个箱子，然后把它搬过来。 那么如果我们能够确定起始位置，我们就可以二分从两侧多少距离搬箱子，判断一下时间就好了。 考虑起始位置，发现一定可以让起始位置有箱子，因为这东西本质上就是一个中位数的模型。 考 阅读全文
posted @ 2019-06-19 20:23
小蒟蒻yyb
阅读(262)
评论(0)
推荐(1)
摘要：
【UOJ 48】【UR 3】核聚变反应强度（质因数分解） 题面 "UOJ" 题解 答案一定是$gcd$除掉$gcd$的最小质因子。 而$gcd$的最小值因子一定是$a_1$的质因子。 所以预处理出$a_1$的质因子，个数不会超过$\log(a)$个，然后就可以直接暴力了。 时间复杂度$O(n\log 阅读全文
posted @ 2019-06-19 15:08
小蒟蒻yyb
阅读(300)
评论(0)
推荐(0)
摘要：
【UOJ 22】【UR 1】外星人（动态规划） 题面 "UOJ" 题解 一道简单题？ 不难发现只有按照从大往小排序的顺序选择的才有意义，否则先选择一个小数再去模一个大数是没有意义的。 设$f[i][j]$表示考虑了前$i$个数，模完之后是$j$的方案数。 转移的时候枚举这个数是模还是不模，如果不模的 阅读全文
posted @ 2019-06-19 10:32
小蒟蒻yyb
阅读(665)
评论(0)
推荐(1)
摘要：
【UOJ 21】【UR 1】缩进优化 题面 "UOJ" 题解 ~~想复杂了就跟我一样不会做了~~ 选定$x$之后，要求的变成了： $$\sum_{i=1}^n [\frac{a_i}{x}]+a_i\% x$$ 考虑怎么在枚举$x$的过程中动态算这个东西。 先考虑怎么算第一部分，即$\sum [\f 阅读全文
posted @ 2019-06-19 09:43
小蒟蒻yyb
阅读(336)
评论(0)
推荐(0)
摘要：
【UOJ 33】【UR 2】树上GCD（长链剖分，分块） 题面 "UOJ" 题解 首先不求恰好，改为求$i$的倍数的个数，最后容斥一下就可以解决了。 那么我们考虑枚举一个$LCA$位置，在其两棵不同的子树中选择两个点，那么贡献就是这两段的$gcd$。 那么发现要统计的东西类似于$u$的子树中，深度为 阅读全文
posted @ 2019-06-19 08:28
小蒟蒻yyb
阅读(824)
评论(0)
推荐(1)
摘要：
【UOJ 32】【UR 2】跳蚤公路（最短路） 题面 "UOJ" 题解 不难发现要求的就是是否存在负环。也就是我们只需要找到所有的负的简单环，很容易就可以想到维护路径上和$x$相关的内容，即维护一下$u$到$v$路径上，含有$kx$的路径的最小的$b$。这个可以用$Floyd$在$O(n^5)$的复 阅读全文
posted @ 2019-06-18 19:40
小蒟蒻yyb
阅读(781)
评论(1)
推荐(2)
摘要：
AtCoder diverta 2019 Programming Contest 2 看起来我也不知道是一个啥比赛。 然后就写写题解QWQ。 A Ball Distribution 有$n$个气球$k$个人，每个人至少要拿一个气球。问所有分配方案中拿走气球最多的那个人可以比最少的那个人多拿多少个。 阅读全文
posted @ 2019-06-17 20:21
小蒟蒻yyb
阅读(521)
评论(0)
推荐(1)
摘要：
【BZOJ4944】[NOI2017]泳池（线性常系数齐次递推，动态规划） 首先恰好为$k$很不好算，变为至少或者至多计算然后考虑容斥。 如果是至少的话，我们依然很难处理最大面积这个东西。所以考虑答案至多为$k$的概率，再减去至多为$k 1$的概率就是最终的答案。 发现要求的东西必须贴着底边，所以对 阅读全文
posted @ 2019-06-10 07:46
小蒟蒻yyb
阅读(443)
评论(0)
推荐(0)
浙公网安备 33010602011771号