如果有写的不好的文章欢迎评论，我会在有时间的时候重写一篇更好的。

M_sea的博客

——どうか悔いることなく 明日へ続く道 歩いて——

洛谷1587 [NOI2016]循环之美

LuoguLOJ分析可以发现，$k$ 进制分数 $\frac{x}{y}$ 是纯循环的当且仅当 $\gcd(y,k)=1$。证明可以点这里。另外为了避免算重，我们只统计最简分数。那么我们要求的东西就是（设 $l=\min(n,m)$）这样子直接枚举约数递归下去算即可；当 $k=1$ 时无法继续往下递归，但此时相当于要求 $\mu(i)$ 的前缀和，杜教筛即可。代码// ===========...

  • M_sea
  • 2020 年 06 月 09 日
  • 暂无评论

    • 洛谷4094 [HEOI2016/TJOI2016]字符串

    LuoguLOJ分析考虑二分答案 $mid$，则我们需要判定是否存在一个 $p\in[a,b-mid+1]$，满足 $\operatorname{lcp}(suf(p),suf(c))\geq mid$。既然有 LCP，可以考虑后缀数组，则 $\operatorname{lcp}(suf(p),suf(c))\geq mid$ 相当于 $\min_{i=rk_p+1}^{rk_c}heigh...

  • M_sea
  • 2020 年 06 月 09 日
  • 暂无评论

    • 洛谷1117 [NOI2016]优秀的拆分

    LuoguLOJ分析设 $L_i$ 表示以 $i$ 为左端点的 AA 串的数量，$R_i$ 表示以 $i$ 为右端点的 AA 串的数量，则答案为考虑计算 $L_i$ 和 $R_i$。暴力就是 $\mathcal{O}(n^2)$ 枚举并用哈希 $\mathcal{O}(1)$ 判断，这样子可以拿 95 分。考虑枚举 A 的长度 $l$，然后把所有是 $l$ 的倍数的位置标成关键点，则每个 A...

  • M_sea
  • 2020 年 06 月 09 日
  • 暂无评论

    • 洛谷4590 [TJOI2018]游园会

    LuoguLOJ分析发现题目中那个 LCS 的限制不好处理，考虑建一个自动机来解决这个问题。假设我们已经建出了自动机，我们就可以设 $f_{i,j,k}$ 为前 $i$ 个字符，已经转移到自动机的 $j$ 节点，已经匹配到了 NOI 的第 $k$ 位的方案数，然后根据 $k$ 转移即可。现在考虑如何建这个自动机。考虑求两个串的 LCS 的过程，即设 $g_{i,j}$ 表示第一个串匹配到 $...

  • M_sea
  • 2020 年 06 月 07 日
  • 4 条评论

    • CF1292E Rin and The Unknown Flower

    CodeforcesLuogu分析首先查一下 CC、CH、CO、HO、OO。这样子我们就能确定 $[2,n-1]$ 中所有字符（没有确定的位置一定是 H）。此时如果 $1$ 没有确定，则它不可能是 C；如果 $n$ 没有确定，则它不可能是 O。这样子只有 $4$ 种情况，做 $3$ 次长度为 $n$ 的查询即可。这样子总花费是 $1.25+\frac{3}{n^2}$ 的，当 $n\geq ...

  • M_sea
  • 2020 年 06 月 07 日
  • 暂无评论

    • LOJ6044 「雅礼集训 2017 Day8」共

    LOJ分析树相等于一个左部点是深度为奇数的点、右部点是深度为偶数的点的二分图。首先需要在 $n-1$ 个点中选出 $k-1$ 个作为深度为奇数的点（$1$ 的深度一定为奇数）。将深度为奇数的点作为左部点、深度为偶数的点作为右部点，两部分间两两连边，则问题变为求生成树个数。考虑 Prufer 序列，则左部点出现了 $n-k-1$ 次、右部点出现了 $k-1$ 次，故生成树个数为 $k^{n-k...

  • M_sea
  • 2020 年 06 月 06 日
  • 暂无评论

    • LOJ6045 「雅礼集训 2017 Day8」价

    LOJCF 原题分析感觉很像最小权闭合子图。为了方便把所有费用取负。考虑这样的连边方式源点向每种药连容量为 $+\infty+p_i$ 的边。每种药向所需的药材连容量为 $+\infty$ 的边。每种药材向汇点连容量为 $+\infty$ 的边。拿最小割减去所有 $+\infty+p_i$ 的和即为答案（因为取了负）。下面是正确性理解：首先可以发现，第二种的边是不会割的，如果割了换成第三种边...

  • M_sea
  • 2020 年 06 月 06 日
  • 暂无评论

    • 洛谷4364 [九省联考2018]IIIDX

    LuoguLOJ分析把所有难度从大到小排序，然后从小到大给每个节点选一个难度。对于每个节点，我们至少要保证未选的难度中有 $sz$ 个 $\geq$ 它选的难度。设 $f_i$ 表示 $[1,i]$ 中有多少个难度可以填，则所有满足 $\min_{j=i}^n\{f_j\}\geq sz$ 的难度 $i$ 都可以被当前节点选择。显然我们选最靠右的位置会最优。假设这个位置是 $p$，则我们需要...

  • M_sea
  • 2020 年 06 月 05 日
  • 暂无评论

    • 洛谷3746 [六省联考2017]组合数问题

    LuoguLOJ分析考虑要求的东西的组合意义，为从 $nk$ 个物品中选出 $t$ 个物品的方案数，其中 $t\bmod k=r$。考虑 DP。设 $dp_{i,j}$ 表示前 $i$ 个物品，选出的物品数量模 $k$ 为 $j$ 时的方案数。显然有转移直接矩阵快速幂即可。需要注意的是 $k=1$ 时转移矩阵是 $[2]$。代码// =============================...

  • M_sea
  • 2020 年 06 月 05 日
  • 暂无评论

    • CF814E An unavoidable detour for home

    CodeforcesLuogu分析显然对于合法的图，满足不在最短路树上边连接的点在同一层。设 $f_{i,j}$ 表示前 $i$ 个点，$[i-j+1,i]$ 中的点在同一层时的方案数，$g_{i,j,k}$ 表示这一层有 $i$ 个点，上一层有 $j$ 个度数为 $2$ 的点、$k$ 个度数为 $3$ 的点时从上一层往这一层连边和上一层内部连边的方案数。$f$ 的转移不难得到：枚举上一层的...

  • M_sea
  • 2020 年 06 月 05 日
  • 暂无评论