搜索结果
查询Tags标签： LOJ，共有 29条记录-
LOJ#535「LibreOJ Round #6」花火 题解
题面 如果只能交换相邻两项，那么答案就是排列的逆序对数。 现在我们就是要求交换两个数，使得交换后的排列逆序对数最少。 不难发现我们一定不会交换满足 \(i<j,h_i<h_j\) 的 \((i,j)\)，因为这样只会让逆序对变多。 考虑怎么刻画减少的逆序对：\((i,j)\)； 满足 \…
2022/7/27 23:23:17 人评论 次浏览 -
LOJ #3534. 「NOI2021」庆典
提交记录 题目叙述 给定一个 \(n\) 个点 \(m\) 条边的有向图，满足如果 \(x\) 到 \(w\) 右边，并且 \(y\) 到 \(w\) 也有边，那么就一定有边 \(x\) 到 \(y\) 或者 \(y\) 到 \(x\) 。每次给出 \(k\) 条边 \(a_i\rightarrow b_i\) 表示这次询问新加入的边（不一定这样做之后…
2022/7/20 23:25:20 人评论 次浏览 -
LOJ #6089. 小 Y 的背包计数问题
题面传送门 奇妙的思维(技巧?)题。 发现每个物品有\(i\)个，体积为\(i\)，对于\(i>\sqrt n\)的物品来说，这个个数的限制是相当于没有的。所以相当于完全背包。 前面\(O(\sqrt n)\)个可以暴力多重背包算方案数。 考虑后面\(n\)个最多选择\(O(\sqrt n)\)个。所以可以设…
2022/4/9 23:19:27 人评论 次浏览 -
Loj#10159.旅游规划
Loj#10159.旅游规划 题目说的很明确了，问点是否在最长路径上，记录最长次长以及最长转移的位置。 怎么判断点在最长路径上，只要最长次长和向上走三者中较大的两个的和为最长路就能说明在最长路径上。 代码显然好写。 /* Knowledge : Rubbish Algorithm Work by :Gym_nas…
2022/3/26 23:26:25 人评论 次浏览 -
loj#6518-「雅礼集训 2018 Day11」序列【整体二分,dp,线段树】
正题 题目链接:https://loj.ac/p/6518题目大意 一个长度为\(n\)的序列\(a\)，你可以花费\(1\)的代价让一个数\(+1\)或者\(-1\)，给出\(m\)个限制形如第\(k\)个数要是区间\([l,r]\)的最大/最小值。 求满足所有限制的最小代价 \(1\leq n\leq 5000,1\leq a_i\leq 10^5\)解题思…
2022/3/25 23:23:07 人评论 次浏览 -
LOJ #6499. 「雅礼集训 2018 Day2」颜色
突然想起来这个题，作为总结写个题解。 考虑这个问题比区间数颜色强很多，那么要不然就离线，要不然在线考虑非 polylog 的做法。 颜色数信息比较难合并，考虑用 bitset 来记录颜色，合并就是 bitset 的按位或。 在线做法：四毛子，分成 \(w\) 个块以及它们的颜色 bitset，…
2022/2/12 23:48:08 人评论 次浏览 -
LOJ #3511. 「USACO 2021 US Open Platinum」United Cows of Farmer John
LOJ #3511. 「USACO 2021 US Open Platinum」United Cows of Farmer John 乍一看, 感觉题目一点也不可做. 但仔细想想又感觉有些蹊跷. 首先这种计算序列上元组 \((i,j,k,...)\) 对数的题要么是 cdq 分治, 要么是枚举左/右端点计数. 这道题可以考虑后者. 枚举右端点, 设右端…
2021/10/28 23:40:24 人评论 次浏览 -
LOJ #3511. 「USACO 2021 US Open Platinum」United Cows of Farmer John
LOJ #3511. 「USACO 2021 US Open Platinum」United Cows of Farmer John 乍一看, 感觉题目一点也不可做. 但仔细想想又感觉有些蹊跷. 首先这种计算序列上元组 \((i,j,k,...)\) 对数的题要么是 cdq 分治, 要么是枚举左/右端点计数. 这道题可以考虑后者. 枚举右端点, 设右端…
2021/10/28 23:40:24 人评论 次浏览 -
Loj #6284. 数列分块入门 8
Description Loj传送门 Solution 个人认为是 \(Loj\) 上这几道分块题中比较好的一道题。 对于这道题，我们对于每一块打一个 \(lazy\) 标记，表示当前块是否被完整赋过值，即全部赋值为 \(c\)。 修改时，整块的直接修改 \(lazy\) 标记，两头多余的部分暴力修改原数组。 注…
2021/10/9 23:05:49 人评论 次浏览 -
Loj #6284. 数列分块入门 8
Description Loj传送门 Solution 个人认为是 \(Loj\) 上这几道分块题中比较好的一道题。 对于这道题，我们对于每一块打一个 \(lazy\) 标记，表示当前块是否被完整赋过值，即全部赋值为 \(c\)。 修改时，整块的直接修改 \(lazy\) 标记，两头多余的部分暴力修改原数组。 注…
2021/10/9 23:05:49 人评论 次浏览 -
AcWing 352/loj 10131. 「一本通 4.4 例 2」暗的连锁
Description 给定一棵 \(n\) 个点的树，还有 \(m\) 条非树边，问有多少种方法使得仅砍去一条树边和一条非树边使得这个图分成不相连的两（或更多）部分。 每次如果先砍去主要边后已经砍成两半，则仍要再砍一条附加边。 Solution 一看这数据范围，暴力组合肯定不可行。 思考…
2021/8/4 23:08:20 人评论 次浏览 -
AcWing 352/loj 10131. 「一本通 4.4 例 2」暗的连锁
Description 给定一棵 \(n\) 个点的树，还有 \(m\) 条非树边，问有多少种方法使得仅砍去一条树边和一条非树边使得这个图分成不相连的两（或更多）部分。 每次如果先砍去主要边后已经砍成两半，则仍要再砍一条附加边。 Solution 一看这数据范围，暴力组合肯定不可行。 思考…
2021/8/4 23:08:20 人评论 次浏览 -
LOJ题目板刷
[LOJ#6030]. 「雅礼集训 2017 Day1」矩阵 考虑由于是覆盖，那么我们肯定要先做出来一个全是 1 的行，然后把其他的列全都覆盖啥的。 我们考虑计算把第 \(i\) 行全改成 \(1\) 需要的次数。 那么就是设这行有 \(cnt\) 个 \(0\)，考虑原先有没有一行的第 \(i\) 个是 \(1\) ，…
2021/8/4 23:08:03 人评论 次浏览 -
LOJ题目板刷
[LOJ#6030]. 「雅礼集训 2017 Day1」矩阵 考虑由于是覆盖，那么我们肯定要先做出来一个全是 1 的行，然后把其他的列全都覆盖啥的。 我们考虑计算把第 \(i\) 行全改成 \(1\) 需要的次数。 那么就是设这行有 \(cnt\) 个 \(0\)，考虑原先有没有一行的第 \(i\) 个是 \(1\) ，…
2021/8/4 23:08:03 人评论 次浏览 -
[LOJ #3533] NOI2021 路径交点
[LOJ #3533] NOI2021 路径交点 这题反映出来的就是菜吧 当时就是没想出来。 我们可以想到的一点就是，路径的这个交点个数，其实就是逆序对个数。于是我们考虑 \(K = 2\) 的情况，就是这一层边的临接矩阵的 \(\text{Det}\)。 我们考虑一个事情就是假如一层的奇数答案是 \(…
2021/7/31 6:09:26 人评论 次浏览
