生不逢时6878 loj
loj 数列分块
1 操作涉及区间加法,单点查值。 对于每个块维护一个 \(ad\) 数组表示这个块每次修改增加的值的和,在修改 \(l\) ~ \(r\) 区间时,如果 \(l,r\) 在同一个块,那直接暴力修改。否则对于 \(l\) ~ \(R_{bel_l}\) 和 \(L_{bel_r}\) ~ \(r\) ......
LOJ2294 银河英雄传说 题解
Question LOJ2294 银河英雄传说 Solution 算是带权并查集一个比较典的题目了 定义 \(d[x]\) 表示战舰 \(x\) 与 \(fa[x]\) 之间边的权值,在路径压缩把 \(x\) 的 \(fa[x]\) 修改为根节点时,把 \(d[x]\) 更新成从 \(x\) 到树根 ......
#LOJ10000. 活动安排
可以把题目中的活动看成一个个的区间,那么多的区间可能有相交的,我们要找出不相交且最多的区间 想要区间数量最多化,可以贪心的从区间末开始计算,从区间最小的开始记 #include<bits/stdc++.h> using namespace std; const int N=1e3+10; struc ......
LOJ-3033/QOJ-4896/南外集训 2023.12.26 T3 Alice、Bob 与 DFS
恶魔的低语,会送来天堂的福音。 题意 有一个 \(n\) 个点的有向无环图,第 \(i\)(\(1 \le i \le n\))个点有 mi 条有序的出边 \(e_{i,1}, e_{i,2}, . . . , e_{i,m_i}\)。每个点要么是黑点,要么是白点。有 \(k\) 个程序,第 \(i ......
LOJ #3353. 「CEOI2020」象棋世界
题面传送门 什么缝合怪( 以下默认判掉一步走到。 Section 1: P 容易发现不会改变纵坐标,简单判断即可。 Section 2: R 两步,两种方案。 Section 3: Q 因为 \(n\geq m\),所以直走两种方案,先斜着走再竖着走两种方案是一定有的。 以下默认其先往左下走,往右下 ......
LOJ6039 「雅礼集训 2017 Day5」珠宝
LOJ 传送门 显然枚举物品做背包没有前途,于是我们把体积相等的物品捆绑在一起。 设 \(f_{i, j}\) 为考虑完体积 \(\in [1, i]\) 的物品,背包容量为 \(j\) 的最大值。可以贪心求出 \(g_{i, j}\) 为选 \(j\) 个体积为 \(i\) 的物品的价值最大值。 ......
LOJ3405 「2020-2021 集训队作业」Gem Island 2
LOJ 传送门 组合计数神题。下文的 \(m\) 指原题面中的 \(d\),\(k\) 指原题面中的 \(r\)。 考虑最后每个人得到的宝石数量的序列 \(s_1, s_2, \ldots, s_n\),考虑这种方案的出现次数。首先要在 \(m\) 次操作中分别选 \(s_i - 1\) 次给第 \ ......
loj144&145 dfs序+树状数组/线段树
[https://loj.ac/p/144](loj144) [https://loj.ac/p/145](loj145) 两题非常相似,一题的权值修改是在点上的,一题的权值修改是在整棵子树上的。 首先我们要了解dfs序,并记录每个节点的子树大小sz,对于一个节点,在dfs序上sz长的区间全都是他的 ......
LOJ2763/JOI2013Final 现代豪宅
题面 Link 说实话这题看懂题面就做出来一半了,所以本题不提供简化题面 分析 题目描述很具有迷惑性,我们发现其实所谓“房门”的一系列操作,其实就是人物只能竖着走或者横着走。相当于我们要从左下角出发,一开始只能竖着走,图中分散着一些“节点”,人物只能在“节点”上才能改变方向,并付出一单位代价。 于是 ......
LOJ #6040. 「雅礼集训 2017 Day5」矩阵
题面传送门 不会线性代数🤡!又被 ZJ 薄纱了! 首先我们考虑如果确定了 \(A\) 矩阵,怎么计算 \(B\) 矩阵的个数。 好像有点困难,不妨先考虑 \(C\) 全零的情况。考虑 \(B\) 的一列,将其设成未知数,则最后的答案就是形如 \(\sum A_{i,j}b_{j}=0\) 这样 \ ......
题解 LOJ3483【[USACO21FEB] Counting Graphs P】
题解 P7418【[USACO21FEB] Counting Graphs P】 problem Bessie 有一个连通无向图 \(G\)。\(G\) 有 \(N\) 个编号为 \(1\ldots N\) 的结点,以及 \(M\) 条边(\(1\le N\le 10^2, N-1\le M\le ......
LOJ #6878. 生不逢时
题面传送门 原题不卡常,但是被某个出题人搬到校内 OJ 上开了 2s 1024MB,怎么回事呢? 首先我们可以把回文改写成 \(x\operatorname{xor} x^R=0\),这样只需要维护 \(x\) 的下 \(\frac{m}{2}\) 位即可。 考虑一个常见的套路,将 \([l,r]\ ......
题解 P6878 [JOI 2020 Final] JJOOII 2
好久没写题解,水一篇。 题意 题意显然。 分析 看到这道题,我们就应该进行一个小贪心,对于最左边某一字符,直到最右边的这一字符,我们不会在中间删除同样的字符,不然则可以保留这一字符,将两边往内缩。 也就是说,我们确定了最左边的 J 后,那么留下最后一个 J 必然是当前这个 J 的后面的第 \(K-1 ......
loj2737. 「JOISC 2016 Day 3」电报
最终形态一定是 \(n\) 个点形成的一个大环。 故每个点的入度一定为 \(1\),我们考虑保留每个点入度中 \(c_i\) 最大的边,剩下的删除,此时原图一定变成一堆链加一些环。 对于环,我们是需要拆开的,此时我们可以枚举环上每个点,考虑将其反悔,反悔代价为环边代价减去其次大入边(最大入边一定为环 ......
[LOJ6698] 一键挖矿
一键挖矿 弱化版(?):CF562F 将矩阵扩展一个单位(长宽均加1),把当前存在的格子染色。 可以发现当且仅当恰好存在4个有1个格子被染色,不存在有3个格子被染色的2x2矩阵时满足题意。 枚举右端点 r,设 g(l) 表示选择 [l,r] 时有多少个上述矩阵。 可以发现 g(r)=4,且对于 x\ ......
[LOJ3626/QOJ4889] 愚蠢的在线法官
考虑这个矩阵长啥样,首先显然 \(A\) 不能重复否则答案是 \(0\)(有两行两列相同)。 把 \(A\) 重标号为 DFS 序的顺序,那么行列式的值不改变,因为交换 \(A_i,A_j\) 相当于同时交换两行两列。 考虑把权值 \(v\) 做树上差分,令 \(B_u=v_u-v_{fa(u)}\ ......
LOJ3658/QOJ4921 匹配计数
考虑对每种方案,设其交点数为 \(t\),我们就给答案加上 \((-1)^t\)。这样算出来的是偶 - 奇的方案数,加上总的方案数再除以二就是答案了。总的方案数可以简单算出,这里略过。 考虑一条边对奇偶性的贡献。发现如果这条边是 \((u,v)\) 其中 \(u<v\),那么 \([u+1,v-1] ......
LOJ2831
JOISC2018 Construction 题目链接 Statement 给定 $n$ 个点,初始时 $i$ 号点的权值为 $c_i$。 接下来进行 $n-1$ 次加边操作,每次连接一条边 $(u,v)$,保证此时 $u$ 与 $1$ 号点连通,$v$ 与 $1$ 号点不连通。 对于每一次加边,求 ......
LOJ 6479 [ICPC World Finals 2017] 小小水管工 Son of Pipe Stream 题解
更好的阅读体验 题意 原题链接 给出 \(n\) 个城市和 \(m\) 条双向管道,以及两个实数 \(v\) 和 \(a\)。有两种液体,分别是水和 Flubber(下面简写为 W 和 F)。\(1\) 号和 \(2\) 号城市分别生产 Flubber 和水,并通过管道流入 \(3\) 号城市。对于 ......
Solution -「LOJ #3310」丁香之路
首先有两个前置技巧:1) 两点间的最短距离就是直接连接两点的边的长度;2) 遍历一个子图的最小花费是最小生成树的边权之和乘二。原问题让我们找出一条最短且必经过钦定边的 \(( s, i )\) 路径,那么我们先将 \(\lang s , i \rang\) 连上,问题就变成了找出一条最短且必经过钦定 ......
题解 LOJ2549【[JSOI2018] 战争】
problem 给你两个平面凸多边形 \(A,B\),\(Q\) 次询问,每次询问是一个向量 \(\vec v\),回答 \(A\) 与 \(B + \vec v\) 是否有交。\(n,Q \leq 10^5\)。 solution 观察闵可夫斯基和(Minkowsky sum)的定义,若将这个运算 ......
题解 LOJ6738【王的象棋世界】
problem 一个 \(R\times C\) 的棋盘,你有 \(Q\) 组询问,每次询问国王走 \(R-1\) 步从 \((1,a)\) 到达 \((R,b)\) 有多少种方案。你只需要输出答案对 \(998244353\) 取模的结果。\(2\le C\le 10^5, C\le R\le 1 ......
LOJ#6515. 「雅礼集训 2018 Day10」贪玩蓝月题解
题目链接 #6515. 「雅礼集训 2018 Day10」贪玩蓝月 - 题目 - LibreOJ (loj.ac) 分析 一个朴素的想法就是模拟这个过程,当询问时做一遍01背包,但这样明显会超时 想象这样一个例子:当两次询问中间夹着一次插入操作 第二次进行01背包,明显只需要在第一次的基础上对新插入 ......
loj3175. 「IOI2019」排列鞋子
[原题](https://loj.ac/p/3175) 做这题时一定不要被ioi吓到,因为这题非常非常降智 结论1:从左到右便利一遍,对于一个$x$和前面最左边第一个没被匹配的$-x$匹配,一定是最优的 证明显然,发现交叉和包含一定不优 于是我们对于每一个$x$可以得到与它匹配的鞋子$b_x$ 但问 ......
loj3362
~~因为某 hhz 曾经往 XJOI 模拟赛搬了这题,然后现在我要给模拟赛讲题,所以滚回来补题了~~。 观察 $1$:对于一个形如 `WWBB` 的子图,如果当前匹配是 $(1,4)(2,3)$,我们换成 $(1,3)(2,4)$ 总更优。 观察 $2$:满足观察 $1$ 的情况,可以被描述为,假设 ......
loj#508. 「LibreOJ NOI Round #1」失控的未来交通工具
https://loj.ac/p/508 贼牛逼的题目。想了两天才想明白。网上大多数题解都讲得很烂啊。 对于部分分的情况,我相信是较为容易想到的。因此,我只会阐述正解的思考过程及一些证明。 首先,考虑路径这东西太泛了。能否将其特殊化、具体化。 先观察一些性质。 1. 对于一个环,我们可以走若干圈,会 ......
LOJ 10115. 「一本通 4.1 例 3」校门外的树
## [$LOJ \ 10115$. 「一本通 4.1 例 3」校门外的树](https://loj.ac/p/10115) ### 一、题目描述 校门外有很多树,学校决定在某个时刻在某一段种上一种树,保证任一时刻不会出现两段相同种类的树,现有两种操作: - $K=1$,读入 $l,r$ 表示在 $ ......
LOJ 10117 简单题
## [$10117$. 「一本通 $4.1$ 练习 $2$」简单题](https://loj.ac/p/10117) #### 题目解析 区间修改+单点查询,用树状数组维护差分数组,从而记录每个点反转的次数。最后单点查询点反转的次数%2即为应得值。 ### $Code$ ```cpp {.line ......
LOJ #6040「雅礼集训 2017 Day5」矩阵
给定 $01$ 矩阵 $C$,求有多少个 $01$ 矩阵的有序对 $(A,B)$ 满足 $A \times B \equiv C \pmod 2$。 $n \leq 2 \times 10^3$。 先考虑如果知道了 $A$ 怎么做。考虑把 $C$ 和 $A$ 写成若干行向量的组合 $c_1 \sim ......