搜索结果
查询Tags标签： Luogu，共有 83条记录-
Luogu P2445 [SDOI2005]动物园
全网好像就洛谷COGS还有几个不知名的网站有这个题边做边玩做了一天最近效率极其低下给下我的思路从每个给出的信息开始搜给出的信息包含了某个动物在时间后到达的位置注意动物们可以停住不动所以不一定是一定在准确的时间到达只要最近能走到就可以那么从给出的这个点开始搜…
2022/10/25 23:25:05 人评论 次浏览 -
[Luogu]SP2128题解
[Luogu]SP2128 KROW 题意 共有 \(t\) 个 \(n \times m\) 的由 .、x、o 组成的字符矩阵。设矩阵中连续 \(k\) 格为 x 小 A 加一分，连续 \(k\) 格为 o 小 B 加一分。 正文 最坏时间复杂度：\(\mathcal{O}(tnmk)\) 算法：暴力 此题我第一眼看就知道很水（尽管我调试了半天）…
2022/9/14 23:19:04 人评论 次浏览 -
【luogu CF633H】Fibonacci-ish II（莫队）（线段树）（矩阵乘法）
Fibonacci-ish II 题目链接：luogu CF633H 题目大意 给你一个序列，每次问你一个区间，把里面的数拿出来去重排序，第 i 个位置乘上斐波那契数列第 i 项之后所有数的和。 思路 这题卡常。 （而且好像能暴力优化草过去但是写的是标算）首先看着数据范围会主观思考 \(\sqrt{…
2022/9/4 23:25:23 人评论 次浏览 -
【luogu P5056】【模板】插头dp（插头DP）（分类讨论）
【模板】插头dp 题目链接：luogu P5056 题目大意 有一个 n*m 的网格，每个格子要么必须铺线，要么必须不铺。 然后问你有多少个铺发使得形成一个闭合回路。 思路 快乐插头 DP 模板题。 首先默认都会插头 DP，其实不会也没啥，其实就是你压你当前处理的位置跟没处理的分界线…
2022/9/2 23:24:57 人评论 次浏览 -
跑路
P1613 跑路 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)题意：如果两点之间有边连接那么边为1，然后如果两点之间有2^n长度的路径，那么他们距离就变为1 dp数组标记i到j有无2^p的距离的边，如果有，其dis值更新为1 第一次floyd如果i到k有距离p-1，k到j有距离p-1的边，那…
2022/8/28 23:53:49 人评论 次浏览 -
【luogu SP7685】FLWRS - Flowers（DP）（容斥）
FLWRS - Flowers 题目链接：luogu SP7685 题目大意 给你模数 m，问你有多少个长度为 n 的排列满足相邻两个差不为 1。 思路 首先一个简单的想法是容斥。 那有 \(n\) 对相邻的不满足，就乘上 \((-1)^n\)。 考虑如何统计，首先考虑不看数，就看每个位置是否会不满足。 于是能…
2022/8/27 23:53:06 人评论 次浏览 -
【luogu AT2377】Blue and Red Tree（思维）（STL）（启发式合并）
Blue and Red Tree 题目链接：luogu AT2377 题目大意 给你一棵树，每次你可以选一条路径，删掉其中的一条边，然后把路径两断点编号在另一个一样点数的图上连边。 然后给你一个要求的树形态，问你是否有方案能让你连出要求的树。 思路 发现不太能下手，考虑一些至少有的条…
2022/8/26 6:23:28 人评论 次浏览 -
【luogu AT2366】Prefix Median（DP）
Prefix Median 题目链接：luogu AT2366 题目大意 给你一个长度为 2n-1 的序列，你可以任意排序它们，问你有多少个不同的 b 数组。 b 数组的第 i 位为 a 数组 1~2i-1 区间的数的中位数。 思路 考虑 \(b\) 的限制，你考虑 \(b_i\) 跟 \(b_{i-1}\) 的区别。 就是每次加入两个…
2022/8/24 23:26:35 人评论 次浏览 -
【luogu CF1710C】XOR Triangle（数位DP）
XOR Triangle 题目链接：luogu CF1710C 题目大意 给你一个数 n，要你求有多少个满足条件的 a,b,c 使得它们两两异或得到的三个值可以得到一个非退化三角形。 其中 a,b,c 值域在 0~n 之间。 思路 考虑要满足三个数任意放要： \(a\oplus b+a\oplus c>b\oplus c\) 然后考虑…
2022/8/15 6:25:20 人评论 次浏览 -
luogu P2261 [CQOI2007]余数求和 (数论分块)
这题要推一下式子，注意涉及到取模的式子都要尽量展成减去下取整的形式。 注意，这里求和符号是求到n，因此分块里面 l 的范围就是l<=n，然后对于n大于k的情况需要特判一下。1 #include "bits/stdc++.h"2 using namespace std;3 typedef long long LL;4 LL…
2022/7/28 6:53:58 人评论 次浏览 -
题目Luogu-P1311 选择客栈
题目链接 题目很好理解1.暴力 60分 根据题面不难想到O(n2)的暴力，对b数组做一个最小值st表，然后暴力枚举两个端点，看区间最小值是否小于等于p即可 // Problem: P1311 [NOIP2011 提高组] 选择客栈 // Contest: Luogu // URL: https://www.luogu.com.cn/problem/P1311 //…
2022/7/24 23:22:43 人评论 次浏览 -
luogu P4547 [THUWC2017]随机二分图
题面传送门 首先根据期望的线性性，我们可以求出每一个完美匹配出现的概率然后求和即为完美匹配个数的期望。 显然的，我们可以设\(dp_{a,b}\)表示左部点选择了\(a\)集合内的点，右部点选择了\(b\)集合内的点在完美匹配中的概率。加入\(op=0\)的边以后，分这条边出现和不出…
2022/7/16 23:49:13 人评论 次浏览 -
SD2022 第二轮省队集训
day 1 T1 https://www.luogu.com.cn/problem/P7163 \(f(u,0/1,0/1/2)\) 表示走完 \(u\) 的子树，\(u\) 的子树全都开启，\(u\) 是关闭/开启，\(u\) 内部有 \(0/1/2\) 个路径端点，的最小路径长度 然后转移的时候要加入 \(u\) 的一个儿子 \(v\) 端点的个数就是背包，然后考…
2022/7/16 23:46:28 人评论 次浏览 -
luogu P5064 [Ynoi2014] 等这场战争结束之后
题面传送门 按秩合并并查集写错复杂度假掉以为自己被卡常卡了好久。 首先这种撤销题看上去就是把操作树建立出来然后dfs变成加入与撤销。 然后我们考虑对值域分块，这样看上去求\(k\)小值会可做一些。 首先我们需要确定每个询问在哪个块，这并不困难。我们考虑在dfs时用并…
2022/7/9 23:51:38 人评论 次浏览 -
Luogu-P8114 [Cnoi2021]六边形战士
题目链接 题解 方法一 考虑将这个东西看成立方体。相当于在一个 \(a\times b\times c\) 的长方体里堆积，每一层必须堆积在墙角的方案数。 这个东西实际上相当于 \(c\) 个人从 \((a,b)\) 走到 \((0,0)\) ，路径可以重叠但不能穿过，路径总数。 这个问题考虑LGV引理，但是L…
2022/7/9 23:24:04 人评论 次浏览
