搜索结果
查询Tags标签： LOJ，共有 29条记录-
[LOJ #3533] NOI2021 路径交点
[LOJ #3533] NOI2021 路径交点 这题反映出来的就是菜吧 当时就是没想出来。 我们可以想到的一点就是，路径的这个交点个数，其实就是逆序对个数。于是我们考虑 \(K = 2\) 的情况，就是这一层边的临接矩阵的 \(\text{Det}\)。 我们考虑一个事情就是假如一层的奇数答案是 \(…
2021/7/31 6:09:26 人评论 次浏览 -
Solution -「LOJ #138」「模板」类欧几里得算法
\(\mathcal{Description}\)Link.\(T\) 组询问，每次给出 \(n,a,b,c,k_1,k_2\)，求 \[\sum_{x=0}^nx^{k_1}\left\lfloor\frac{ax+b}{c}\right\rfloor^{k_2}\bmod(10^9+7) \] \(T=1000\)，\(n,a,b,c\le10^9\)，\(0\le k_1+k_2\le 10\)。 \(\mathcal{Solution}\)类欧模板题…
2021/7/15 9:06:21 人评论 次浏览 -
Solution -「LOJ #138」「模板」类欧几里得算法
\(\mathcal{Description}\)Link.\(T\) 组询问，每次给出 \(n,a,b,c,k_1,k_2\)，求 \[\sum_{x=0}^nx^{k_1}\left\lfloor\frac{ax+b}{c}\right\rfloor^{k_2}\bmod(10^9+7) \] \(T=1000\)，\(n,a,b,c\le10^9\)，\(0\le k_1+k_2\le 10\)。 \(\mathcal{Solution}\)类欧模板题…
2021/7/15 9:06:21 人评论 次浏览 -
LOJ#2369. 「BalticOI 2008」魔法石
题目链接 LOJ #2369. 「BalticOI 2008」魔法石 题目大意 一个字符串由 \(X\) 和 \(I\) 组成，定义两个串是相同的当且仅当一个串可以通过翻转（头尾倒过来）另一个串得到，我们取字典序较小的那个作为该串的表达方式，求在长度为 \(n\) 的串中，满足「 \(X\) 和 \(I\) 相邻…
2021/7/2 23:21:59 人评论 次浏览 -
LOJ #115. 无源汇有上下界可行流
#115. 无源汇有上下界可行流描述这是一道模板题。 n n n 个点，m m m 条边，每条边 e e e 有一个流量下界 lower(e) \text{lower}(e) lower(e) 和流量上界 upper(e) \text{upper}(e) upper(e)，求一种可行方案使得在所有点满足流量平衡条件的前提下，所有边满足流量限制。…
2021/6/5 10:24:35 人评论 次浏览 -
LOJ#515. 「LibreOJ β Round #2」贪心只能过样例(bitset)
内存限制：256 MiB时间限制：1000 ms标准输入输出 题目类型：传统评测方式：文本比较 上传者： nzhtl1477提交提交记录统计讨论测试数据题目描述一共有 nnn个数，第 iii 个数 xix_ixi 可以取 [ai,bi][a_i , b_i][ai,bi] 中任意值。设 S=∑xi2S = \sum{{…
2021/6/5 10:24:33 人评论 次浏览 -
LOJ#6342. 跳一跳(期望)
题意$n \leqslant 10^5$ Sol 随便推一推就好了吧。。 $f[i] = \frac{f[i] + f[i +1] + \dots f[n]}{n - i + 1} + 1$ 移一下项，然后化一化，就做完了。。 然而这题卡空间MMP#include<cstdio> #include<algorithm> #include<iostream> //#define int lo…
2021/6/5 10:24:28 人评论 次浏览 -
loj#2531. 「CQOI2018」破解 D-H 协议(BSGS)
题意 题目链接 Sol 搞个BSGS板子出题人也是很棒棒哦 #include<bits/stdc++.h> #define Pair pair<int, int> #define MP(x, y) make_pair(x, y) #define fi first #define se second #define int long long #define LL long long #define ull unsigned lon…
2021/6/5 10:22:59 人评论 次浏览 -
loj#6073. 「2017 山东一轮集训 Day5」距离(费用流)
题意 题目链接 Sol 我们可以把图行列拆开，同时对于行/列拆成很多个联通块，然后考虑每个点所在的行联通块/列联通块的贡献。 可以这样建边 从S向每个行联通块连联通块大小条边，每条边的容量为1，费用为\(i\)(i表示这是第几条边)。 从每个点所在的行联通块向列联通块连边…
2021/6/5 10:22:58 人评论 次浏览 -
loj#6074. 「2017 山东一轮集训 Day6」子序列(矩阵乘法 dp)
题意 题目链接 Sol 设\(f[i][j]\)表示前\(i\)个位置中，以\(j\)为结尾的方案数。 转移的时候判断一下\(j\)是否和当前位置相同 然后发现可以用矩阵优化，可以分别求出前缀积和逆矩阵的前缀积(这题的逆矩阵炒鸡好求) 这样就可以\(n*10^3\) 发现相邻两个矩阵只有一行不同，那…
2021/6/5 10:22:57 人评论 次浏览 -
loj#6073. 「2017 山东一轮集训 Day5」距离(树链剖分 主席树)
题意 题目链接 Sol 首先对询问差分一下，我们就只需要统计\(u, v, lca(u, v), fa[lca(u, v)]\)到根的路径的贡献。 再把每个点与\(k\)的lca的距离差分一下，则只需要统计每个点与\(k\)的lca深度。这个东西等价于所有的链与\(k\)到根的链的并。 树剖+主席树维护一下。这题的…
2021/6/5 10:22:49 人评论 次浏览 -
loj#6041. 「雅礼集训 2017 Day7」事情的相似度(SAM set启发式合并 二维数点)
题意 题目链接 Sol 只会后缀数组+暴躁莫队套set\(n \sqrt{n} \log n\)但绝对跑不过去。 正解是SAM + set启发式合并 + 二维数点/ SAM + LCT 但是我只会第一种qwq 首先一个性质是两个前缀的最长公共后缀就是他们再parent树上的LCA的len 那么我们考虑每个LCA的贡献。 把询问…
2021/6/5 10:22:48 人评论 次浏览 -
loj#2312. 「HAOI2017」八纵八横(线性基 线段树分治)
题意 题目链接 Sol 线性基+线段树分治板子题。。 调起来有点自闭。。 #include<bits/stdc++.h> #define fi first #define se second #define pb push_back #define bit bitset<B + 1> using namespace std; const int MAXN = 501, B = 1001, SS = 4001; …
2021/6/5 10:22:46 人评论 次浏览 -
Solution -「LOJ #6053」简单的函数
\(\mathcal{Description}\)Link.积性函数 \(f\) 满足 \(f(p^c)=p\oplus c~(p\in\mathbb P,c\in\mathbb N_+)\)，求 \(\sum_{i=1}^n f(i)\bmod(10^9+7)\)。 \(\mathcal{Solution}\)首先，考虑 \(f\) 的素数点值： \[f(p)=\begin{cases} 3,&p=2\\ p-1,&\text{otherw…
2021/4/14 18:25:17 人评论 次浏览
