摘要：
题意分析 首先 要求起点终点不连通 再结合数据范围 就是最小割了 首先我们可以建一个图出来 如果$x$可以到$y$的话 那么我们就从$x$向$y$连一条代价为$h[x] h[y]+1$的边 代表不联通的代价 可是如果存在以下情况呢 如果我们选择切断$c$到$d$的边的话 实际上我们也切断了$a$到$ 阅读全文
posted @ 2019-04-02 15:05
tcswuzb
阅读(162)
评论(0)
推荐(0)
摘要：
题意分析 就是让你求 $$\sum_{i=1}^{|S|}val[i][gcd(a[i],x)=y]$$ 那么接下来就是化简式子 $$\sum_{i=1}^{|S|}val[i][gcd(\frac{a[i]}{y},\frac{x}{y})=1]$$ $$\sum_{i=1}^{|S|}val[i 阅读全文
posted @ 2019-04-01 18:54
tcswuzb
阅读(526)
评论(0)
推荐(0)
摘要：
题目链接 题意分析 首先存在树上的删边连边操作 所以我们使用$LCT$维护 然后考虑怎么维护答案 可以发现 对于一条链 我们编号为$1,2,3,...,n$ 那么期望就是 \(\frac{a_1* 1* n+a_2* 2* (n-1)+a_3* 3* (n-2)+...+a_n* n* 1}{\fr 阅读全文
posted @ 2019-03-31 17:23
tcswuzb
阅读(277)
评论(0)
推荐(1)
摘要：
"题目链接" 题意分析 受到了$olinr\ \ julao$的影响 写了匈牙利算法 首先 我们对于每一个人 从高到低枚举志愿 如果当前志愿的老师有剩余的话 那么我们就选 否则的话 我们看看谁的那个志愿选了这个老师 我们跑匈牙利算法 看看是否更优 如果当前可以在接受范围内匹配上的话 我们就选择 否则 阅读全文
posted @ 2019-03-30 22:12
tcswuzb
阅读(283)
评论(0)
推荐(0)
摘要：
"题目链接" 题意分析 首先$1→2$的每一天路径上不可以存在环 所以我们先来一个$Tarjan$找环 然后如何确定$1$到$2$的路径上存在环呢 我们先正向边$1→2$跑一次 然后反向边$2→1$跑一次 全部都标记到的点就是会经过的点 如果有一个点位于环上 就是$inf$ 否则的话 正常的拓扑$d 阅读全文
posted @ 2019-03-30 18:49
tcswuzb
阅读(240)
评论(0)
推荐(0)
摘要：
"题目链接" 题意分析 我们令$dp[i][j][k]$表示当前区间$[i,j]$最小价格为$k$的最大收益 那么状态转移方程就是 $$dp[i][j][k]=max\{dp[i][pos 1][x]+dp[pos+1][j][y]+cnt[pos][k] k\}$$ $$x,y≥k$$ $cnt[ 阅读全文
posted @ 2019-03-30 15:53
tcswuzb
阅读(304)
评论(0)
推荐(1)
摘要：
"题目链接" 题意分析 首先 我们肯定会贪心的走从根节点到叶子结点最长的一条链 首先没有过剩的就好办了 但是有的话 我们就一边往下走 一边走分支 分支上每一个点平均走过两次 所以我们把剩下的除以$2$即可 CODE: cpp include include include include inclu 阅读全文
posted @ 2019-03-30 15:25
tcswuzb
阅读(181)
评论(0)
推荐(0)
摘要：
"题目链接" 题目链接 这道题建出模型之后就是一个树形图 首先我们不考虑有向边的关系 而是直接考虑树形$dp$ 关键是怎么个树形$dp$ 我们维护$dp[u][i]$表示当前$u$节点在已经遍历的子树中拓扑序排名为$i$的情况数 那么接下来就是经典的做法 合并$u$和子树$v$ 我们假设当前$u$已 阅读全文
posted @ 2019-03-30 06:26
tcswuzb
阅读(216)
评论(0)
推荐(0)
摘要：
题意分析 首先$\%\%\%\%olinr$以及花_Q$julao$当场切题 然后就是怎么求 $$max(|a A|,|b B|)=max(a A,A a,B b,b B)$$ 我们令$x_1=(a+b)/2,x_2=(A+B)/2,y_1=(a b)/2,y_2=(A B)/2$ $$max(x_ 阅读全文
posted @ 2019-03-29 20:13
tcswuzb
阅读(177)
评论(0)
推荐(0)
摘要：
"题目链接" 题意分析 题意精简一下就是 求所有连续区间和的异或和 由于涉加到计算区间和 所以我们先跑一个前缀和 然后 由于涉及到了位运算 我们很自然地联想到了拆位 对于当前我们枚举到了第$k$位 我们到了第$i$个数$s_i$ 如果$s_i$当前这一位是$1$ 1.存在$s_j(ji$ 那么也可以 阅读全文
posted @ 2019-03-29 19:42
tcswuzb
阅读(167)
评论(0)
推荐(0)
摘要：
题目链接 题意分析 \(olinr\) : 序列自动机+一系列的鬼畜操作 相信我 你们没人能切 \(lzxkj\) : $2^m+vector+$暴力二分 跑得比你正解还快 首先一看$m≤5$ 直接$2^m$枚举所有的子序列 然后我们用一个$vector$把匹配序列中的权值相同的位置存入一个$vec 阅读全文
posted @ 2019-03-28 18:21
tcswuzb
阅读(263)
评论(0)
推荐(0)
摘要：
题意分析 题目链接 这里借鉴了$Youngsc$以及$hzwer$的思路 首先由于涉及到了区间异或最值的问题 所以我们需要使用到$01Trie$树 这里贴一道板子题 然后对一个位置$x$ 我们维护四个位置$l_1,l_2,r_1,r_2$ \(l_1\) 从$x$往左数第一个大于$x$的位置 \(l 阅读全文
posted @ 2019-03-28 18:06
tcswuzb
阅读(149)
评论(0)
推荐(0)
摘要：
"题目链接" 题意分析 题意 给你一棵树 每一次都会删除一个叶子节点 同时树上存在一些有向边$(a,b)$ 必须满足$a$在$b$之前删除 问每一个节点作为根节点时是否存在合法的删边情况 使得跟、根节点被最后一个删除 换根$dp$ ？ $No$ ！ 首先有向边必定形成一个或者多个$DAG$ 所以先判 阅读全文
posted @ 2019-03-28 06:30
tcswuzb
阅读(288)
评论(0)
推荐(0)
摘要：
"题目链接" 题意分析 首先我们可以得出计算公式 $$s_i=\prod_{k=1}^i(1 p_k)$$ $$f_i=\sum_{k=1}^i\frac{p_k}{1 p_k}$$ 那么 $$ans(i,j)=\frac{s_r}{s_{l 1}}{f_r f_{l 1}}$$ 强行枚举 $O(n 阅读全文
posted @ 2019-03-27 19:50
tcswuzb
阅读(302)
评论(0)
推荐(0)
摘要：
"题目链接" 题意分析 神题呀 ! ! ! 首先在线好像没有什么办法 所以考虑离线 我们把询问按照右端点排好序 假设说我们已经维护出了$ans(i,j)=ans[i]$ 那么显而易见的是 $$ans[i]=min\{ans[k]\}(i≤k include include include inclu 阅读全文
posted @ 2019-03-27 15:58
tcswuzb
阅读(291)
评论(0)
推荐(0)
摘要：
"题目链接" 题意分析 首先我们令答案为$dp[n][k]$ 经过观察可以发现答案是存在积性的 $$dp "n][k] dp[m][k]=dp[n m][k" ==1)$$ 那么为根据质数的唯一分解定理 $x=p_1^{a_1}p_2^{a_2}......p_n^{a_n}$ 然后我们分别计算出$ 阅读全文
posted @ 2019-03-27 06:12
tcswuzb
阅读(174)
评论(0)
推荐(0)
摘要：
"题目链接" 题意分析 我们仔细分析一下 发现题目要求用最多$k$条路径实现最小权覆盖 首先由于最小路径覆盖针对的是有向图 但是这是一个无向图 所以我们面向对象编程 我们维护一个数组$d[i][j]$ 表示$i,j$之间的最短距离 由于是$n≤150$ 所以我们可以使用$floyed$求 同时由于我 阅读全文
posted @ 2019-03-26 19:17
tcswuzb
阅读(216)
评论(0)
推荐(0)
摘要：
"题目链接" 题意分析 一句话题意就是 : 让你选出$(k+1)$条不相交的链 使得这些链的边权总和最大 (这些链可以是点) 我们考虑使用树形$DP$ $dp[i][j][0/1/2]$表示以$i$为根的子树选出$j$条链 并且$j$的度数是$0/1/2$的最大总和 那么我们使用树上背包进行转移 $ 阅读全文
posted @ 2019-03-25 11:28
tcswuzb
阅读(182)
评论(0)
推荐(0)
摘要：
"题目链接" 题意分析 当前等级为$x$的魔法书会对等级在$[x,inf]$的所有人造成$y$的影响 所以除了求平均值之外 就是 区间修改区间求和 需要使用 动态开点 + 标记永久化 需要注意的是 当前点为空的话 需要返回 目标区间长度 下放标记值 CODE: cpp include include 阅读全文
posted @ 2019-03-24 21:46
tcswuzb
阅读(308)
评论(0)
推荐(0)
摘要：
"题目链接" 题意分析 这个题其实不是期望 就是一共有$C_{2n}^m$种情况 每一种情况选择$k$张牌 然后求最大攻击值的总和 我们考虑 当前抽出了选出了$i$张强化牌 $m i$张攻击牌 首先 可以肯定的是 能出强化牌就尽量出强化牌 我们去枚举$i$ 如果$i include include 阅读全文
posted @ 2019-03-24 21:46
tcswuzb
阅读(229)
评论(0)
推荐(0)
摘要：
"题目链接" 题意分析 首先 $[u,v]$在树上是一条深度递增的链 那么我们可以使用倍增找 $x$的祖先当中深度最大的值大于$x$的点 然后维护一个$pre$ 重新建树 这样从$x$到根节点 权值严格递增 我们在这个新树上维护好深度以及倍增数组 然后再去倍增找到 最近的权值 z的点 如果不存在或者 阅读全文
posted @ 2019-03-24 21:44
tcswuzb
阅读(266)
评论(0)
推荐(0)
摘要：
"题目链接" 题意分析 $$\sum_{i=1}^n\sum_{j=1}^mμ^2(gcd(i,j))$$ $$=\sum_{i=1}^n\sum_{j=1}^m\sum_{d=1}^{min(n,m)}μ^2(d)[gcd(i,j)==d]$$ $$=\sum_{d=1}^{min(n,m)}μ^ 阅读全文
posted @ 2019-03-24 21:37
tcswuzb
阅读(342)
评论(0)
推荐(0)
摘要：
"题目链接" 题意分析 由于要么学文科要么学理科 我们考虑用 最小割 解决问题 关键是怎么建图~~网络流的唯二难点~~ 首先我们考虑没有集体加成的时候 由$S$向$(i,j)$建边权为$art_{i,j}$的边 然后由$(i,j)$向$T$建边权为$science_{i,j}$的边 这样的跑出最大流 阅读全文
posted @ 2019-03-24 21:36
tcswuzb
阅读(217)
评论(0)
推荐(1)
摘要：
写在之前 李超线段树 简称$LCT$ 正式开始 李超线段树主要用于维护这样一类问题 有两个操作 1.插入一条直线(k,b) $y=kx+b$ 2.给出一个值$x$ 求$x=k$与这些直线交点中纵坐标的最大值 我们可以使用$CDQ$分治或者平衡树维护 但是这里有了一种玄学鬼畜的数据结构 李超线段树 $ 阅读全文
posted @ 2019-03-24 21:35
tcswuzb
阅读(410)
评论(0)
推荐(2)
摘要：
"题目链接" 题意分析 首先这道题不可以使用简单的贪心来做 根据$DP$ 我们令$dp[i]$表示当前到了$i$一共做了$dp[i]$次合并 $pre[i]$表示当前合并到了$i$后序列末尾的数 那么$$dp[i]=min\{dp[j]+i j,sum[i] sum[j]≥pre[j]\}$$ 可惜 阅读全文
posted @ 2019-03-24 21:33
tcswuzb
阅读(186)
评论(0)
推荐(0)
摘要：
"题目链接" 题意分析 我们根据前缀异或和的性质可以知道 例如说原序列 $a_1,a_2,a_3,a_4,...,a_n$ 那么前缀异或和之后是 $s_1,s_2,s_3,s_4,...,s_n$ 我们每一次访问区间$[l,r]$ 那么就是求$s_{l 1}\ xor\ s_r$ 很显然的是 我们知 阅读全文
posted @ 2019-03-24 21:32
tcswuzb
阅读(277)
评论(0)
推荐(0)
摘要：
"题意分析" 题意分析 神题呀 这题让你求$n$个结点的树当中有所少个联通块是与$m$个节点的树同构的 首先 我们对于$m$ 枚举根节点 然后 ? ? ? 树上哈希 ~~鄙人也震惊到了~~ 我们对于当前节点 搜出所有的儿子后 把儿子的哈希值$sort$一遍(防止重复) 然后暴力合并 同时我们对于形态 阅读全文
posted @ 2019-03-24 21:31
tcswuzb
阅读(285)
评论(0)
推荐(0)
摘要：
"题目链接" 题意分析 啥 ? ? ? $FFT$做字符串匹配 可是就是这样 我们定义匹配函数 我们定义$A$是匹配串 $B$是被匹配串 我们当前到达$B$串的$x$位置 $$P(x)=\sum_{i=0}^{m 1}[A(i) B(x m+i+1)]$$ 那么如果$P(x)=0$的话 是不是就是匹 阅读全文
posted @ 2019-03-24 21:30
tcswuzb
阅读(161)
评论(0)
推荐(0)
摘要：
"题目链接" 题意分析 这是一道树上斜率优化题 首先 $$dp[i]=min\{dp[j]+(dis[i] dis[j]) p[i]+q[i]\}(j∈Pre_i)$$ 那么就是 $$p[i]=\frac{dp[i] dp[j]}{dis[i] dis[j]}$$ 我们根据$p[i]$递增可知 我们 阅读全文
posted @ 2019-03-24 21:30
tcswuzb
阅读(299)
评论(0)
推荐(0)
摘要：
"题目链接" 题意分析 ~~自己树形DP果然是弱到家呀~~ 这是一道赤果果的树形$dp$问题 我们这样设状态 $cdy[now][i]$ 表示当前的以$now$为根子树我们已经覆盖并且又向上覆盖了$i$层的最小代价 ($0$时包括$now$) $wzy[now][i]$ 表示当前的$now$向下$i 阅读全文
posted @ 2019-03-24 21:28
tcswuzb
阅读(200)
评论(0)
推荐(0)
摘要：
"题目链接" 题意分析 给你一个字符串 让你求$1 n$长度下的字符串的中字典序最小并且最靠左的字符串的开头位置 我们考虑先建出$SA$ 然后考虑对于一个字符串后缀排序之后 我们可以发现 第二个后缀还可以更新长度为$1$的子串 所以我们考虑使用二分 求刚好可以满足的位置 然后我们再使用$RMQ$求这 阅读全文
posted @ 2019-03-24 21:27
tcswuzb
阅读(147)
评论(0)
推荐(0)
摘要：
"题目链接" 题意分析 我们考虑将已经维护好了$2∽n$的数列现在考虑插入最小值 然后现在插入最小值$1$ 现在我们使用$dp(i,j)$表示前$i$个数一共存在$j$个前缀最大值的方案数 我们如果放在开头 那么贡献就是$dp(i 1,j 1)$ 如果放在别的位置就是$dp(i 1,j)$ 所以 $ 阅读全文
posted @ 2019-03-24 21:24
tcswuzb
阅读(237)
评论(0)
推荐(0)
摘要：
"题目链接" 题意分析 要求$k$种颜色恰好出现$S$次 也就是出现$S$次的颜色恰好有$k$种 我们可以发现$lim=max\{k\}=min(\frac{n}{s},{m})$ 我们可以容斥一下 就是 出现$S$次的颜色至少存在$k$种 那么 $$dp[k]=C_m^kC_{n}^{ks}(m 阅读全文
posted @ 2019-03-24 21:18
tcswuzb
阅读(223)
评论(0)
推荐(0)
摘要：
也不知道写一些什么了 凑和着写写吧 最近十分的￥#&(^ ……#%!*%￥^#$# Day -1 上午考了一场试 就\(TM\)考了60分 好不容易积攒起来的信心啊~~~~~~ 就这么垮了~~~ 下午每一个人把考前注意事项好好的说了一下 大抵都是什么 1.不开\(long\ \ long\)见祖宗 阅读全文
posted @ 2019-03-24 21:16
tcswuzb
阅读(501)
评论(1)
推荐(4)
浙公网安备 33010602011771号