搜索结果
查询Tags标签： Luogu，共有 83条记录-
luogu P2304 [NOI2015] 小园丁与老司机
题面传送门 非常码农的二合一题。 首先第一问看上去非常simple。因为只能往左，往右，和往上走(包括左上，上，右上)，往上走显然是没有后效性的。而往左和往右因为每一层最多1000个，所以直接枚举从上一层跑过来的地方转移即可，时间复杂度\(O(1000n)\) 然后第二问只要按…
2022/6/27 23:27:24 人评论 次浏览 -
luogu P7737 [NOI2021] 庆典
题面传送门 感觉写起来真吃屎一样的，变量名多的离谱。 首先这个是一个连通性问题那就先缩点。 然后考虑题目中的性质有啥用，也就是说一个点如果有两个入度，那么断掉其中一个对于答案没有影响。那么我们就得到一棵外向树。 问题来了，断掉哪一个。 考虑缩点的时候scc代表…
2022/6/25 23:32:20 人评论 次浏览 -
luogu P7115 [NOIP2020] 移球游戏
题面传送门 首先大概有一个人口普查的40分做法： 考虑对每一种颜色单独做，主要就是将每根柱子上的球都拿到最上面。 先数出这根柱子上有多少个我们现在要拿的球，然后从另外一个柱子上拿出等量的球放在空柱子上，之后我们从当前柱子一个一个往外拿球，如果这个球是我们当…
2022/6/13 23:22:05 人评论 次浏览 -
luogu P5492 [PKUWC2018]随机算法
题面传送门 考虑到这样做得到的图的性质，不难发现对于一个点，要么是最大独立集里面的点，要么周围有至少一个点在最大独立集内。 可以发现如果我们限定了当前最大独立集里面是什么点，那么其余的点都会被限定在一个固定的集合里面，且完全包含最大独立集，直接dp可以得到…
2022/5/27 1:20:06 人评论 次浏览 -
luogu P5666 [CSP-S2019] 树的重心
其实上想清楚了也是挺好写的一道题。 首先直接算实在太蠢了。还要考虑一棵树有两个重心的情况。可以考虑对于每个点算贡献。也就是算每个点作为重心出现了几次。 那么也就是要在一个子树内断一条边，考虑除了这颗子树之外的子树的大小的最大值\(\max\)，最后肯定不能小于\…
2022/5/1 23:21:09 人评论 次浏览 -
学习方法
今天把前几天未看完的一个公众号文章看完了，我认为他讲的挺有道理的，特此分享。 这篇文章是讲的提高自己的深度思考能力的五个方法。先归纳，对于自己正在准备的竞赛来说我感觉是在恰当不过的了，在作一道题目的时候，自己应该先把题意给看懂，总结出要求，有什么自己马…
2022/4/21 23:16:35 人评论 次浏览 -
Luogu P3723 [AH2017/HNOI2017]礼物 （卷积 FFT）（紫）
https://www.luogu.com.cn/problem/P3723
2022/4/17 23:17:47 人评论 次浏览 -
刷(shui)题记录2022.4
[ABC247-F] Cards \(\Rightarrow \rm AT\) 链接 转化问题，将每一张牌看成一条边 \((P_i,Q_i)\) ，问题就转化成若干个环的答案积，每一个环的答案都是选择若干边，使得所有点都至少存在一条边被选择的方案。考虑断环为链，可以发现可以用 \(\rm dp\) 解决，设 \(f_x(n,0/…
2022/4/11 23:18:28 人评论 次浏览 -
luogu P3649 [APIO2014]回文串
题面传送门 结合manacher的拓展过程以及复杂度证明可以知道，一个序列的本质不同回文串是\(O(n)\)个，并且每次拓展时会出现一个可能本质不同的字符串。 那么就把这个回文串扔到SAM上查出现次数就好了。时间复杂度\(O(n\log n)\) 如果这样那也就不会有这篇题解了。 但是问…
2022/3/27 23:23:32 人评论 次浏览 -
【luogu CF1654F】Minimal String Xoration（倍增）
Minimal String Xoration 题目链接：luogu CF1654F 题目大意 给你一个长度为 2^n 的字符串 s，然后你要选一个在 0~2^n-1 中的数 k，使得变换得到的字符串 t 字典序最大。 变换操作为 t[i]=s[i⊕k]，输出 t 这个字符串即可。 思路 考虑设 \(f(i,j)\) 为 \(k=i\)，处理了前…
2022/3/26 23:26:39 人评论 次浏览 -
Luogu P5897 [IOI2013]wombats
Luogu P5897 [IOI2013]wombats 为了统一记号，下文设矩形的行数为 \(n(\le 5000)\)，列数为 \(m(\le 200)\)，更新次数为 \(U(\le 500)\)，查询次数为 \(Q(\le 2\times 10^5)\)。 最暴力的想法是每一次查询时直接DP，时间复杂度为 \(\mathcal O(Qnm^2)\)。这显然过…
2022/3/9 6:17:33 人评论 次浏览 -
【luogu P4512】【模板】多项式除法
【模板】多项式除法 题目链接：luogu P4512 题目大意 给你一个 n 次多项式 F(x) 和 m 次多项式 G(x)，要你求出多项式 Q(x),R(x) 使得 Q(x) 为 n-m 次多项式，R(x) 项数小于 m，然后 F(x)=Q(x)*G(x)+R(x)。 思路 考虑到如果没有余数就是直接多项式求逆，但是有余数，所以问…
2022/3/5 6:17:17 人评论 次浏览 -
【luogu P6577】【模板】二分图最大权完美匹配（KM算法）
【模板】二分图最大权完美匹配 题目链接：luogu P6577 题目大意 一个二分图，有一些带权边，保证有完美匹配。 求一种最大匹配的方案使得匹配边的边权和最大。 思路 KM 算法的模板题。 它有一定的针对性：一定要是带权的完美匹配。 然后我们定义每个点有一个顶表（一个值）…
2022/2/28 9:21:37 人评论 次浏览 -
【YBT2022寒假Day2 B】【luogu CF809D】模糊序列 / Hitchhiking in the Baltic States（平衡树优化DP）（fhq-Treap）
模糊序列 / Hitchhiking in the Baltic States 题目链接：YBT2022寒假Day2 B / luogu CF809D 题目大意 给你一个序列，然后每个位置有可以选的数的范围。 然后要你找到对于所有可能的序列它严格上升子序列的最大长度。 思路 很明显的 DP。 考虑列方程，发现数的范围很大，…
2022/2/7 6:12:33 人评论 次浏览 -
Luogu P7279 光棱碎片
Luogu P7279 光棱碎片 首先可以差分将限制转化为 \((a_{r_1}\oplus a_{r_2})+(r_1-l_1+1)\le k\)。 将 \(\texttt{SAM}\) 建出来后对于每个本质不同子串的 \(\text{endpos}\) 考虑。设点 \(x_1,x_2\) 分别对应原序列中 \(r_1,r_2\) 在 \(\texttt{parent tree}\) 上…
2022/2/6 23:45:26 人评论 次浏览
