首页 > 其他分享 >那些你不要的模板

那些你不要的模板

时间:2023-07-21 14:12:39浏览次数:28  
标签:lfloor le 不要 rfloor 那些 right frac binom 模板

打 qoj 板子赛打的。

有的是会的,只是之前没写过。

就题论题,所以写的不一定是正解。

回文自动机

题意

对于 \(S\),记 \(c_S(T)\) 表示 \(T\) 在 \(S\) 中的出现次数。对所有回文串 \(T\),求 \(\max_T(c_S(T) \cdot |T|^2)\)。

对于所有数据,\(|S| \leq 10^6\)。

题解

经典结论:本质不同回文子串只有 \(O(n)\) 个。

Manachar 的同时动态维护一下字典树,使用树上倍增快速找 \(k\) 级祖先,就好了。

最后树上差分,枚举每个串,计算贡献即可。

区间本质不同子串

题意

给定字符串 \(S\),\(q\) 次询问,每次给出 \(l,r(1 \leq l \leq r \leq |S|)\),你需要求出 \(S[l:r]\) 本质不同的子串数量。

对于所有数据,\(1 \leq |S| \leq 2 \times 10^5, 1 \leq q \leq 2 \times 10^5\)。

题解

建出后缀树,对 \(l\) 从大往小扫描线。

动态维护一下每条边最新归属于哪个后缀,容易发现就是对一个点到根的路径染色,使用 LCT 的均摊即可维护。

拿一个 BIT 计算一下贡献,总复杂度 \(O(n\log^2n+q\log n)\)。

正则二分图匹配

题意

给定一个正则二分图 \(G=(X,Y,E)\),其中 \(|X|=|Y|=n\) 且每个点的度数均为 \(d\),请你求出一个其完美匹配。

对于 \(100\%\) 的数据,保证 \(n\times d\le 2\times 10^6\)。

题解

我们打乱所有左部点,然后逐个枚举左部点作为起点,每次步步随机走出一条增广路,消掉增广路的环之后直接增广这条增广路。

可以证明复杂度期望是 \(O(n\log n)\) 级别的。

边三联通分量

题意

给出 \(N\) 个点 \(M\) 条边的无向图,第 \(i\) 边是 \((a_i,b_i)\)。求出其所有边三连通分量。

\(1 \leq N \leq 2\times 10^5\),\(1 \leq M \leq 2 \times 10^5\),\(0 \leq a_i, b_i < N\)。

题解

首先拉出一颗 Tarjan 生成树出来。我们给每条非树边一个 \(2^{64}\) 范围内的随机哈希值,然后在树链上异或上这个哈希值。这样每条非树边的哈希值对应了一个集合。

我们取出所有对应非树边集合大小 \(\ge2\) 的边(哈希值不为 \(0\) 且不与任意一个非树边的哈希值相等),可以使用排序或者哈希表给出每种集合的边集。

容易发现同一个非树边边集这些对应的所有树边一定均在原生成树上一条根到叶子的链上,我们取出这样的最深和最浅的边,把最深的边的儿子节点和最浅的边的父亲节点使用一条新边连通。最后每个由新边组成的联通块即为一个边三连通分量。

正确性证明:两个点同属一个边三等价于这两个点之间割的大小 \(\ge3\),所以我们直接找出所有割的大小 \(\le2\) 的对即可。割边本身即为割的大小 \(=1\),如果一个树边对应非树边集合大小 \(=1\) 则直接割掉这个树边和非树边即构成一个 \(=2\) 的割。剩下的割 \(=2\) 的情况即为割掉两条对应非树边集合相同的树边,容易验证我们上面这么干是对的。

有源汇有上下界最小费用最大流(随机数据)

题意

给定一张 \(n\) 个点 \(m\) 条边的有向图,其中源点为 \(s\) 点,终点为 \(t\) 点。每条边有起点 \(a_i\),终点 \(b_i\),流量下界 \(l_i\),流量上界 \(u_i\),费用 \(c_i\)。

现在,你需要找到一个从 \(s\) 到 \(t\) 的流,满足每个点的流量平衡与每条边的流量上下界,且在流量最大的情况下费用尽可能小。

对于所有数据,保证 \(1 \le n \le 1\,000\),\(1 \le m \le 5\,000\),\(1 \le s,t \le n\),\(s \ne t\)。

对于所有数据,保证 \(1 \le a_i, b_i \le n\),\(a_i \ne b_i\),\(1 \le l_i \le u_i \le 10^6\),\(-10^6 \le c_i \le 10^6\)。

特别地,保证本题的数据通过以下方式随机生成:

  1. 选定 \(n\),\(m\),\(s\),\(t\) 的值,不保证 \(n,m,s,t\) 随机生成。
  2. 通过以下方式生成一张 \(m\) 条边的有向图 \(G\):
    1. 选定参数 \(k_1, k_2\),满足 \(0 \le k_1, k_2\) 且 \(k_1 + k_2 \le n\)。
    2. 进行 \(k_1\) 次:
      • 均匀随机选择 \(1 \le a \le n\) 且 \(a \ne s\),添加边 \(s \to a\)。
    3. 进行 \(k_2\) 次:
      • 均匀随机选择 \(1 \le a \le n\) 且 \(a \ne t\),添加边 \(a \to t\)。
    4. 进行 \(m-k_1-k_2\) 次:
      • 均匀随机地选择 \(1 \le a, b \le n\) 且 \(a \ne b\),添加边 \(a \to b\)。
  3. 对于每条边,均匀随机地选择其费用 \(c_i \in [-10^6, 10^6]\)。
  4. 对于每条边,选择一个 \(\Delta_i \in [1, 10^6]\),不保证 \(\Delta_i\) 随机生成
  5. 随机进行以下过程若干次:
    1. 选择一个值 \(\delta \in [1, 10^6]\),不保证 \(\delta\) 随机生成。
    2. 从 \(s\) 开始 dfs 整张图,每次均匀随机地选择一个出边。
    3. 如果最终到达了点 \(t\),则将 \(s \to t\) 路径上所有边的 \(l_i\) 增加 \(\delta\)。
    4. 特别地,若存在边的 \(l_i\) 超过了 \(10^6 - \Delta_i - \delta\),则放弃本轮操作。
  6. 随机进行以下过程若干次:
    1. 选择一个值 \(\delta \in [1, 10^6]\),不保证 \(\delta\) 随机生成。
    2. 均匀随机地选择一个顶点 \(x\)。
    3. 从 \(x\) 开始 dfs 整张图,每次均匀随机地选择一个出边。
    4. 如果最终回到了点 \(x\),则将走过的路径上所有边的 \(l_i\) 增加 \(\delta\)。
    5. 特别地,若存在边的 \(l_i\) 超过了 \(10^6 - \Delta_i - \delta\),则放弃本轮操作。
  7. 令每条边的 \(u_i = l_i + \Delta_i\)。
题解

上下界网络流!

我们考虑加一条 \(t\rightarrow s\),\(+\infty\) 容量,\(0\) 费用的边,转换成无源汇上下界循环费用流。

增加超级源汇,钦定正权边初始流 \(l\),负权边初始流 \(r\),添加附加边来退流,对超级源汇之间跑最小费用最大流。

如果附加边没有流满则无解。

否则我们再在原始源汇间跑一次流,计算出本轮的流量和费用,将费用和上次的费用相加即为总费用。

类欧几里得算法

题意

给出 \(T\) 组询问,每组用 \(n, a, b, c, k_1, k_2\) 来描述。对于每组询问,请你求出

\[\sum_{x = 0} ^ {n} x ^ {k_1} {\left \lfloor \frac{ax + b}{c} \right \rfloor} ^ {k_2} \]

对 \(1000000007\) 取模。

对于 \(100 \%\) 的数据,\(T = 1000, 1 \le n, a, b, c \le {10} ^ 9, 0 \le k_1 + k_2 \le 10\)。

题解

首先我们拆成组合数的形式。

\[\sum_{i=1}^ni^x{\left\lfloor\frac{ai+b}{c}\right\rfloor}^y=\sum_{t_1,t_2}(-1)^{x+y-t_1-t_2}{x\brace t_1}{y\brace t_2}\sum_{i=1}^ni^{\overline{t_1}}{\left\lfloor\frac{ai+b}{c}\right\rfloor}^{\overline{t_2}} \\=\sum_{t_1,t_2}t_1!t_2!(-1)^{x+y-t_1-t_2}{x\brace t_1}{y\brace t_2}\sum_{i=1}^n\binom{i+t_1-1}{t_1}\binom{\left\lfloor\frac{ai+b}{c}\right\rfloor+t_2-1}{t_2} \]

然后

\[\sum_{i=1}^n\binom{i+x-1}{x}\binom{\left\lfloor\frac{ai+b}{c}\right\rfloor+y-1}{y} \\=\sum_{i=1}^n\binom{i+x-1}{x}\sum_{j=1}^{\left\lfloor\frac{ai+b}{c}\right\rfloor}\binom{j+y-2}{y-1} \\=\sum_{j=1}^{\left\lfloor\frac{an+b}{c}\right\rfloor}\binom{j+y-2}{y-1}(\sum_{i=1}^n\binom{i+x-1}{x}-\sum_{i=1}^{\left\lfloor\frac{jc-b-1}{a}\right\rfloor}\binom{i+x-1}{x}) \\=\binom{\left\lfloor\frac{an+b}{c}\right\rfloor+y-1}{y}\binom{n+x}{x+1}-\sum_{j=1}^{\left\lfloor\frac{an+b}{c}\right\rfloor}\binom{j+y-2}{y-1}\binom{\left\lfloor\frac{jc-b-1}{a}\right\rfloor+x}{x+1} \]

然后考虑怎么令 \((a,b)\leftarrow(a\bmod c,b\bmod c)\)。

\[\sum_{i=1}^n\binom{i+x-1}{x}\binom{\left\lfloor\frac{ai+b}{c}\right\rfloor+y-1}{y} \\=\sum_{i=1}^n\binom{i+x-1}{x}\binom{\left\lfloor\frac{(a\bmod c)i+(b\bmod c)}{c}\right\rfloor+\left\lfloor\frac ac\right\rfloor i+\left\lfloor\frac bc\right\rfloor+y-1}{y} \\=\sum_{i=1}^n\binom{i+x-1}{x}\sum_t\binom{\left\lfloor\frac{(a\bmod c)i+(b\bmod c)}{c}\right\rfloor+t-1}{t}\binom{\left\lfloor\frac ac\right\rfloor i+\left\lfloor\frac bc\right\rfloor+y-t-1}{y-t} \\=\sum_t\sum_{i=1}^n(\binom{i+x-1}{x}\binom{\left\lfloor\frac ac\right\rfloor i+\left\lfloor\frac bc\right\rfloor+y-t-1}{y-t})\binom{\left\lfloor\frac{(a\bmod c)i+(b\bmod c)}{c}\right\rfloor+t-1}{t} \\=\sum_t\sum_qf_{q,x,y-t,\left\lfloor\frac ac\right\rfloor,\left\lfloor\frac bc\right\rfloor}\sum_{i=1}^n\binom{i+q-1}{q}\binom{\left\lfloor\frac{(a\bmod c)i+(b\bmod c)}{c}\right\rfloor+t-1}{t} \]

其中 \(f_{q,x,y,a,b}\) 满足

\[\sum_{0\le q\le x+y}f_{q,x,y,a,b}\binom{i+q-1}{q}=\binom{i+x-1}{x}\binom{ai+b+y-1}{y} \]

具体做法是把关于 \(i\) 的多项式展开,然后反复试减。

这样每轮是 \(O(k^4)\) 的,看上去可能有点卡常,需要松一松。不过事实上由于实际计算量能除个 \(4!\) 左右的数,所以并不算太卡常。

标签:lfloor,le,不要,rfloor,那些,right,frac,binom,模板
From: https://www.cnblogs.com/myee/p/template-practise.html

相关文章

  • 线段树--区间最大值模板
    Smiling&Weeping----你是我绕过的山河错落,才找到的人间烟火ProblemDescriptionThereisasequence a oflength n.Weuse ai todenotethe i-thelementinthissequence.Youshoulddothefollowingthreetypesofoperationstoth......
  • C++ 模板编程技术解析
    一、函数模板函数模板实现通用函数,根据传递类型进行编译时实参推导:template<typenameT>Tadd(Ta,Tb){returna+b;}intmain(){intx=1,y=2;doublem=1.5,n=2.5;intz=add(x,y);doublep=add(m,n);return0;}这里te......
  • html 数据可视化大屏展示模板源码分享(第一期)
    1、angular+echart.js统计数据图表读取投屏数据大屏2、生意参谋大数据可视化HTML模板3、大数据可视化展板通用模板4、基于echarts实现的销售统计数据可视化大屏模板5、新能源车联网综合大数据平台6、厅店效能大屏监控看板7、东海省交通大数据分析平台8、基于echarts......
  • 小旋风超级模板站群788套整站html5模板(已经过xxfseo处理)免费下载
    这784套整站模板来源于市面上的html5英文模板,经过机器处理(替换、过滤、精简、压缩)后,生成的。适用于超级模板站群。本来是1千多套的,删除了后台模板、单页模板。剩下784套不错的模板。整站多页面模板。----------------------------------------------------------------------使......
  • LCT 模板
    以P3690为例。#include<iostream>#defineUP(i,s,e)for(autoi=s;i<e;++i)namespaceLCT{//}{{{structNode{ Node*ls,*rs; Node*fa; intsum,val; boolrev; Node();}nil_,*nil=&nil_;Node::Node(){fa=ls=rs=nil;}voidpushup(......
  • 痞子衡嵌入式:恩智浦i.MX RT1xxx系列MCU启动那些事(10)- 从Serial NAND启动
    大家好,我是痞子衡,是正经搞技术的痞子。今天痞子衡给大家介绍的是恩智浦i.MXRT1xxx系列MCU的SerialNAND启动。最近越来越多的客户在咨询i.MXRT1xxx从SerialNAND启动的事情,让这个本来比较冷门的启动设备突然火热起来。据痞子衡的了解,其实客户主要目的是在应用里基于......
  • 工控的要不要学python
    工控的要不要学Python引言工业控制(Industrialcontrol)是一门涉及到控制系统、自动化和机械工程的学科。工业控制系统是用于监控和控制生产过程的系统,其中包括传感器、执行器、控制器和人机界面等组件。在过去的几十年中,工业控制系统一直采用传统的编程语言,如C、C++和ladderlog......
  • 建站新手福利:免费网页模板大合集,快速打造专业网站!
    今天给大家带来的网站模板素材,网站类型丰富,包含户外旅行、餐饮、个人网站等等,可以学习和参考其中的布局排版和配色。 ⬇⬇⬇点击获取更多设计资源https://js.design/community?category=design&source=bky&plan=bbqbky772   1、设计公司&工作室相信大家都希望拥有属......
  • 上传jrxml模板进行JasperReport解析导致任意代码执行RCE
    JasperReport是一个强大、灵活的报表生成工具,能够展示丰富的页面内容,并将之转换成PDF、HTML、XML等格式。该库完全由Java写成,可以用于在各种Java应用程序,包括J2EE,Web应用程序中生成动态内容。JasperReports附带了报表编译器,可以在报表表达式内部使用Groovy脚本语言或JavaScript编......
  • 关于go语言常量的那些事
    相对于变量,常量是恒定不变的值,多用于定义程序运行期间不会改变的那些值。常量的声明和变量声明非常类似,只是把var换成了const,常量在定义的时候必须赋值。const常量名[数据类型]=value项目实战常见场景数据类型可以忽略不写,Golang编译器会⾃动推断出数据类型。在使⽤......