- 博客(152)
- 收藏
- 关注
RSS订阅
原创 acm-Polya计数定理
Polya定理目录轨道-稳定子定理Burnside 引理polya 引理轨道-稳定子定理对于一个置换群GGG，定义GGG作用于一个元素aaa代表取GGG中所有的置换对aaa作变换后能够得到的所有可能的结果构成的集合，这个集合中的所有元素也就构成了一个在GGG作用下形成的等价类。轨道-稳定子定理就是说对于任意一个元素aaa的等价类中元素个数×\times×对元素aaa施加GGG中的置换后元素aaa保持不变的置换个数=G=G=G中的总置换个数。Burnside 引理设ZiZ_iZi表示对iii元素进
2021-08-11 22:51:07
307
原创 acm-【平衡树】学习笔记(Splay,Treap,fhq Treap,替罪羊树,红黑树,avl tree,B树,B+树)
引言本文的写作目的主要是为了作者日后复习，也供浏览本文的群众以参考，若有不严谨之处欢迎在评论区指出。下面目录引言SplaySplaySplay又名伸展树，是一种比较常见的平衡树，它的核心操作主要是...
2021-02-18 21:29:55
962
原创 acm-【堆】学习笔记(二叉堆、左偏树、配对堆、斐波拉契堆、斜堆、STL)
引言本文主要针对作者本人复习使用，相关基础知识点不会讲述。目录引言二叉堆左偏树斜堆配对堆二项堆斐波拉契堆STL中的堆堆的应用二叉堆二叉堆是最普通的堆，能够实现push,poppush,poppush,pop等基本操作，下面以小根堆为例给出一种常见的实现。首先设置一个足够大的数组，我们将树的节点按照层次遍历的顺序从小到大依次放置在数组中，数组中的位置也对应是该节点的编号，如下图所示：上图是一个典型的二叉树，每个节点上标注的数字即是该节点的编号，容易发现对于一个节点uuu而言，它的儿子分别是2u,
2021-02-17 20:59:48
805
原创 acm-无向图三元环、四元环计数
三元环计数考虑对无向图的边进行定向，度数小的点连向度数大的点，如果度数相同则编号小的点连向编号大的点。然后再这张新图(有向图)中我们枚举所有点uuu，对于每个点uuu我们枚举它的出边对应的端点vvv，先给这些点打上标记，然后再枚举uuu的出边对应的端点vvv，枚举vvv的出边对应的端点www,如果www是标记点的话就找到一个三元环，每个三元环都一定只会被恰好枚举一次，因此找到一个三元环就++ans++ans++ans即可，注意枚举下一个uuu之前需要清空标记数组。考虑正确性，经过重定向后新图一定是一张
2021-02-02 15:20:25
1395
原创 acm-马拉车算法学习笔记
引言本文主要介绍马拉车算法的原理及相关应用，并给出经典习题原理马拉车(manacher)算法主要用于解决回文串问题，它能够O(n)O(n)O(n)求出一个字符串每个位置的hhh数组值，h[i]h[i]h[i]代表的是从字符串的第iii个位置开始向右延伸能够到达的最大长度使得s[i−h[i]+1∼i+h[i]−1]s[i-h[i]+1\sim i+h[i]-1]s[i−h[i]+1∼i+h[i]−1]是一个回文串。首先对字符串预处理，即再每个字符间加上一个不在字符集中的字符(比如#)。考虑维护一
2021-01-01 16:40:39
251
1
原创 acm-kmp学习笔记
引言kmp相关算法主要用于解决字符串的匹配问题，本文除了探讨最基础的kmp算法，还会介绍扩展kmp算法，以及kmp自动机，注意本文主要写给作者看，很多基础的东西都没有讲，写得也相对比较随意kmp相关算法引言一、kmp算法1、原理2、代码3、习题二、扩展kmp算法1、原理2、代码3、习题一、kmp算法1、原理kmp最核心的思想就是充分利用已知信息，这样就可以避免不必要的重复检查。具体地，我们考虑模式串与匹配串之间的关系，假设模式串s2s2s2当前匹配到第iii位(即将匹配)，匹配串s1s1s1
2021-01-01 11:59:03
193
原创 acm-排列组合学习笔记(更新中)
引言本文主要介绍排列与组合的相关知识点，以及重要的一些结论推论及其证明，会给出少量的例题，此外本文是建立在作者的需求上，故更多简单的内容不会涉及，默认读者已经拥有前置技能排列组合引言一、集合1.不可重集(1).普通排列(2).圆排列(3).组合2.可重集(1).排列[1].无限集[2].有限集(2).组合[1].无限集[2].有限集二、组合数(二项式系数)1.二项式定理(1).基本内容(2).推广2. 帕斯卡三角形3.组合数性质4.组合数取模及求解(1).Pascal打表法(批量)(2).公式法(单
2020-11-04 23:13:53
780
原创 acm-dp相关优化学习笔记(决策单调性)
引言本文暂时只介绍与决策单调性有关的优化。后面会陆续完善其他优化一、决策单调性优化1.四边形不等式[1].定义设w[i][j]w[i][j]w[i][j]是一个二元函数，若∀a≤b≤c≤d\forall a\le b\le c\le d∀a≤b≤c≤d满足w[a][c]+w[b][d]≥w[a][d]+w[b][c]w[a][c]+w[b][d]\ge w[a][d]+w[b][c]w[a][c]+w[b][d]≥w[a][d]+w[b][c](可以记作交叉大于等于包含)成立，那么称w[i][
2020-11-04 10:17:11
346
2
原创 acm-后缀树组学习笔记
引言本文主要介绍后缀数组的原理和一些典型例题后缀数组的实现基本原理后缀数组主要是考虑用一个数组存放字符串s的所有后缀，然后再给这些后缀排个序。然后利用这个数组我们可以解决许多奇妙的问题。首先是后缀的存放方式，显然不能真正地为每一个后缀开一个空间来存放，这空间不得爆炸…因此我们考虑用后缀的第一个字母所在的下标来代表这个后缀本身。这里sa[i]\mathbf{sa[i]}sa[i]来存放排好序的后缀，它代表的是排好序的后缀中的第i\mathbf{i}i个后缀的首字母下标，相应地为了操作方便还要设
2020-10-13 21:24:06
238
原创 acm-扫描线学习笔记
引言扫描线可以用于解决矩形求面积并，矩形求周长并的问题问题引入我们以洛谷的P5490 【模板】扫描线为例题来讲解扫描线的基础运用。先给出题面描述：扫描线的精髓在于用一根垂直于坐标轴的线去扫描平面上的对象，并在此过程中维护关于平行于该扫描线的方向上的一维的变量。具体就本题而言，我们可以设置一根平行于x轴而垂直于y轴的线条然后沿着y轴向上扫描矩形。当然，这根线上我们会始终维护一些量，本题中我们维护的是当前扫描线上与所有矩形的交集，显然是一根一根的线段，由于是求面积，我们维护的是这些交集线段的总
2020-10-09 12:12:27
594
原创 acm-Kruskal重构树学习笔记
引言Kruskal重构树主要用于解决在线查询问题，询问通常涉及的条件为边权小于某值。原理考虑利用Kruskal算法构建一个最小生成树，但在此过程中稍稍改动一下。Kruskal算法的过程主要是按照边权由小到大的顺序对边上的两点做合并操作。现在假设正在处理u−v\mathbf{u-v}u−v这条边，Kruskal重构树将不会直接在新图建立边u−v\mathbf{u-v}u−v，而是建立一个新的节点t\mathbf{t}t，然后让该节点连向u和v\mathbf{u和v}u和v各自连通块的根节点，并给t\
2020-09-30 09:57:21
376
原创 acm-线段树题型总结
引言线段树可以说是最频繁使用的数据结构，在各大比赛中总能看到它的身影，虽然原理简单，但出题的形式却千变万化。本文主要总结作者遇到过的各种线段树题型，以达到对线段树有更好的掌握的目的。例题分析例题一题目来源：Codeforces Round #665 (Div. 2)F题：Reverse and Swap题面：题解：本题在原来线段树的基础上进行适当的改造，首先是线段树的儿子不固定，由于要实现序列交换顺序的功能，因此儿子需要单独记录，以便进行swap。其次是懒标记的打法需要注意，共同点是两种
2020-08-22 11:04:13
201
原创 acm-网络流费用流典型例题解析
引言网络流费用流类型的题目一般的难点都在于建图，本文主要总结作者在做习题过程中也遇到的各种困难，以例题的形式进行讲解。关于网络流费用流的相关原理网上可以找到许多写得非常详细的博客，本文就不再次累述相关知识点，本文将给出更多的例题加以分析，熟悉如何把题目转化为图，如何巧妙建图。下面给出几个写得不错的博客加以参考。网络流费用流入门博客参考：https://blog.csdn.net/yjr3426619/article/details/82808303https://blog.csdn.net/x
2020-08-15 17:44:24
380
原创 acm-CDQ分治
引言CDQ分治主要用于解决一类分治过程中分治区间彼此存在互相影响的问题。这类问题最典型的就是三维偏序问题，本文主要从CDQ的核心思想出发，先分析基本问题，再给出难度更大的例题。CDQ的核心思想非常简单，就是先分治，再合并并且计算分治部分彼此之间的贡献，递归进行这个过程即可。与普通的分治算法唯一的区别在于计算合并的部分，CDQ在合并的时候，假设有两个区间，那么就需要计算这两个区间之间彼此的贡献，一般来说是计算左区间的所有元素对右区间的所有元素的贡献。具体怎么计算贡献呢？这取决于问题的描述，下面将以三
2020-08-14 18:23:16
212
原创 acm-矩阵树定理入门
引言矩阵树定理是主要为了解决生成树计数的问题，生成树计数分为无向图计数以及有向图计数。除此之外，变元矩阵树定理还能够求解生成树边权积的和。本文会先给出矩阵树定理的基本和扩展内容，然后给出关于定理的详细证明，最后是相关的习题及讲解。定理内容生成树计数无向图对于一般无向图而言，将图中的自环的边去除以后，计算出满足如下条件的基尔霍夫(Kirchhoff)矩阵：Li,j={i点度数,if i=ji与j连边数的相反数,if i≠j\mathbf{L_{i,j} =\begin{
2020-08-12 08:51:51
240
原创 acm-博弈论基础知识点详细总结(含证明推导分析)
引言本文主要介绍acm中有关博弈论的基础知识点，意在梳理博弈论学习的总体框架与基本逻辑，使读者和作者都能够对博弈论的思维方式有更深入的理解。博弈论：引言巴什博奕尼姆博弈及其扩展普通尼姆博弈anti-nim和游戏(反尼姆博弈)nim-k博弈其他扩展尼姆博弈SG函数及其应用威佐夫博弈斐波拉契博弈总结巴什博奕问题：有两个绝顶聪明的人在玩取石子游戏，假设最初有n个石子，每人可以轮流取1~m范围内的石子，如果没有石子可取就失败，问先手胜还是后手胜。巴什博奕属于博弈论中最基础的问题，但从该问题我们往往
2020-08-11 10:30:07
1604
原创 acm-根号分治在各个领域的应用
引言对于acm常有一些题目让人十分棘手，并且没有专门的算法来解决这些问题。这时候一般都最好从暴力着手来思考解决方案，而根号分治可以说是一种优雅的暴力。本文将通过例题的方式从各个领域来剖析根号分治的核心思想。图论例题一题目来源：2020上海高校程序设计竞赛暨第18届上海大学程序设计联赛夏季赛（同步赛）D题：旅行简化题意：给定一张n<=100000个点,m<=n+5000条边的有向图(随机生成)和q<=300000个询问，每次询问u点是否能够到达v点，能输出Good,否
2020-08-05 23:57:48
387
原创 acm-有向图中的最小平均权值回路
引言对于求解有向图的最小均值环的问题一般由两种做法：【二分均值+spfa判定负环】【公式法】，本文将对两种做法进行推导，并提供相应的例题和变式训练。以[Usaco2006 Mar]Milk Team Select产奶比赛为例题对两种方法进行介绍法一：二分均值+spfa判定负环设有向图中的所有回路的最小平均权值为ans，于是可以对ans进行二分处理，不过注意到当题目给出的条件中未明确要求环的权值非负的时候，ans可以是负数，这时候需要特殊处理。这里假设ans>=0，那么二分ans，每次对an
2020-08-05 00:56:59
561
1
原创 凌风 TEMU工具箱 抢仓 库存销售数据利润计算 选品监控采集上品 一网打尽
最近发现一款软件，无论是正在苦苦选品的temu新手商家还是日入万单的工厂大卖，都适合用这款软件，里面集合了智能抢仓、商品模板、ERP模块库存信息、大数据选品、跨境翻译、跨境日历等等非常丰富的功能，方便了每个商家经营自己的店铺，这里给出这个软件的安装教程和一些介绍，方便商家入门这款软件。
2024-03-05 16:46:44
1339
原创 【TEMU】凌风TEMU工具箱介绍，集合智能抢仓、TEMU选品、TEMU监控、TEMU库存管理，本地仓库管理、跨境翻译等功能....
(1) 事先 谷歌浏览器 登录https://seller.kuajingmaihuo.com/“拼多多跨境卖家中心”，保持登录状态。如果没有 会在软件页面单独登录一次。！！！目前支持在谷歌浏览器 360浏览器上登录拼多多商家后台一 :自动抢发货台模块该抢仓程序通过底层算法驱动，自动调节抢仓速度,间隔等,选择最优抢仓策略,无需商家繁琐设置，一键抢仓创建。助力商家掘金全球。
2024-03-05 15:21:35
2819
原创 按键精灵脚本分享 temu发货台
AutoHotkey提供了一种类似于编程语言的脚本语言，允许用户编写自定义的脚本来模拟键盘和鼠标操作，处理文本、文件和窗口操作等。
2023-08-09 10:35:01
2129
4
原创 python-配置文件库ConfigParser介绍
配置文件的格式：中括号“[ ]”内包含的为section。section 下面为类似于key-value 的配置内容，section内的每一项被称之为一个option。比如下面这份名为config.ini文件的内容就是一份典型的ConfigParser格式的文件案例。ConfigParser 是用来读取配置文件的包。使用ConfigParser需要引入对应的包。接下来可以了解一下这个库的常用方法。
2022-12-27 18:53:16
1052
原创 acm-(好题、神题)2020-2021 Winter Petrozavodsk Camp, Day 5 B.Lockout vs tourist
传送门简要题意：你和tourist一起比赛做题，你们两个每轮同时决策做哪道题，如果选择相同的题目，那么你不得分，比赛继续进行，如果选择了不同的题目，那么你能拿下你选择的这道题的全部分数，比赛结束，tourist想让你得分最少，你想让得分最多，问在双方均采取最优决策的情况下你的期望得分。这道题一看就非常难以下手，直接给出题解的神仙做法吧。首先tourist的决策一定是基于概率的，我们考虑给每个问题设置一个概率pip_ipi，代表touristtouristtourist有pip_ipi的概率在当前轮.
2021-09-15 20:06:54
1095
原创 acm-LuoGu P3348 [ZJOI2016]大森林(LCT神仙题)
传送门本题的做法非常神奇，原理的思想需要仔细体会才能理解，这里只陈述客观的做法，原因不解释(太难解释了。首先发现222号操作可以放到最后处理，其次000号操作可以认为是对所有的树进行一次统一的操作，因为222号操作不会询问不存在树上的点，而111号操作某个节点的时候需要与创建该节点的000号操作的范围取一下交集。考虑将操作离线处理，对于所有的111号类型的操作都建立一个虚点，假设编号是v1,v2,v3,...,vkv_1,v_2,v_3,...,v_kv1,v2,v3,...,vk，其中kk.
2021-05-29 22:58:20
217
原创 acm-Codeforces Round #596 Div1 E. To Make 1 (状压dp)
传送门这道题真是人类智慧题，难想~~首先如果最终能够得到1那么一定可以写成如下表达式:∑i=1naik−bi=1\sum_{i=1}^{n}a_ik^{-b_i}=1∑i=1naik−bi=1。不过难就难在这个式子反过来也是成立的，下面给出证明。设B=maxi(bi)B=max_i(b_i)B=maxi(bi)，那么有∑i=1naikB−bi=kB\sum_{i=1}^na_ik^{B-b_i}=k^B∑i=1naikB−bi=kB，然后可以证明的是一定有∑i=1n[bi=B]≥2.
2021-04-09 19:05:18
89
原创 acm-(欧拉路径、构造)Educational Codeforces Round 105 (Rated for Div. 2) F. Delete The Edges
传送门经过一番思索可发现如果要存在一种合法方案，图必须可以被划分成两个部分：G1G_1G1和G2G_2G2。其中G1G_1G1要求具有一条欧拉路径或欧拉回路，并且在欧拉路径(回路)的终点ttt处有一个以ttt为中心的菊花图G2G_2G2，G1G_1G1和G2G_2G2共同构成GGG。关键是如何找到G1G_1G1和G2G_2G2。考虑枚举ttt，对于每个ttt我们先考虑那些非临接点中有几个点的度数是奇数：若有两个及以上，那么显然ttt是不能作为G2G_2G2的菊花图中心点；若有一个.
2021-03-15 08:22:40
133
原创 acm-(异或、思维)Codeforces Round #705 (Div. 2) E. Enormous XOR
传送门首先给出结论：若l0=0,r0=1l_0=0,r_0=1l0=0,r0=1，那么答案就是111...1111...1111...1(长度为nnn)。否则若rrr为奇数或l+1≥rl+1\ge rl+1≥r，那么答案是rrr。否则(rrr为偶数并且l+1<rl+1<rl+1<r)答案是r+1r+1r+1。下面给出证明：第一种情况下我们可以找到长度为nnn的01111..101111..101111..1与1000..01000..01000..0串，两者异或就能得.
2021-03-07 09:46:49
468
原创 acm-Educational Codeforces Round 104 (Rated for Div. 2) F. Ones
传送门这题真是绝了，看半天题解没理解意思，但是一旦懂了就觉得题目也不算太难，主要是方法是真的不太好描述，这里打算用图片来解释原理。我们从高位向低位考虑，也就是说给最高位编号为111，次高位编号为222，以此类推…最低位编号为nnn，然后我们设dp[i][j][k]dp[i][j][k]dp[i][j][k]代表考虑了前iii位，我们确定了一些形如111...11111...11111...11的数，满足它们的长度都大于n−in-in−i，并且对于每个数而言我们先去掉它的长度为n−in-in−i的后缀，.
2021-02-19 23:03:14
211
原创 acm-(好题、网络流思想、spfa、负环判定、分数规划)LuoGu P3288 [SCOI2014]方伯伯运椰子
传送门本题是一道分数规划题目。建立新图，对于u,v,a,b,c,du,v,a,b,c,du,v,a,b,c,d，考虑从uuu到vvv连一条权值为b+db+db+d的边，代表扩大流量的额外花费，从vvv到uuu连一条权值为a−da-da−d的边，代表缩小流量的额外花费。注意到新图中的一个环恰好代表一组满足流量平衡的扩大/缩小扩大/缩小扩大/缩小操作。为什么流量平衡呢，我们考虑原图中环上的每个节点的情况，情况一如下：红色代表我们要操作的环的一部分，容易发现与这个节点关联的环上的这两条边都是扩流操作，满.
2021-02-02 20:49:15
123
原创 acm-(交互、bfs、dp)2018 ECNU Campus Invitational Contest E. Balance Reset
cf传送门vj传送门首先注意到ai<=100a_i<=100ai<=100，也就是每次最多花费100100100，然后由于每次可以充100100100，那么其实当前的余额可以维持在[0,100)[0,100)[0,100)的范围以内(第一次除外)。考虑余额到达某个状态uuu所需要的最少物品数，记作dp[u]dp[u]dp[u]，可以从状态000出发通过bfsbfsbfs更新出所有的可达状态以及其dpdpdp值。然后由于每个物品出现的概率都是12\frac 1221，我们每天都检查.
2021-01-23 22:40:04
193
原创 acm-(交互题、思维、二分、子序列、好题)2020 年 “游族杯” 全国高校程序设计网络挑战赛 B. Binary String
vj传送门本题实在是非常妙，首先二分求出000和111中数量较小的一个的数量，方便起见，假设000数量最少，设cnt0,cnt1cnt_0,cnt_1cnt0,cnt1分别表示000和111的数量。假设序列是如下形式：111...10111..10111..1.....111..10111...1111...10111..10111..1.....111..10111...1111...10111..10111..1.....111..10111...1，即假设第i−1i-1i−1个000与第iii.
2021-01-23 10:50:37
272
原创 acm-(欧拉回路、思维、好题)2020 ECNU Campus Online Invitational Contest E. Even Degree
cf传送门vj传送门容易发现跟欧拉回路有关联，考虑先求出每个连通块的欧拉回路，并记录在队列中，然后考虑将队首的边依次放入答案序列中，并与此同时记录每个点的度数变化，如果当前边的两个端点的度数都是奇数，那么从队尾取边，直到队列中只有一条边的时候，就停止，然后考虑下一个连通块的删边顺序。欧拉回路如何求解呢？考虑从任意一个点开始dfs，遍历过的边都删除掉(用前向星)，删除的方式就是改变h[u]h[u]h[u]的值即可，注意同一个点在dfs的过程中可能会多次访问，因此如果不删边会导致复杂度爆炸。#incl.
2021-01-22 23:05:11
185
原创 acm-(cdq分治、单调栈、好题)#2880. 「JOISC 2014 Day3」稻草人
原oj传送门vj传送门本题不太好讲述做法，大致上就是cdq分治的时候统计左半部分对右半部分产生的贡献，其中左半部分的点为左下角顶点，右半部分的点为右上角顶点。最开始的时候按照x坐标由小到大排序，cdq分治的过程中左右两半部分都分别按照从大到小的顺序排列，然后对左右两半部分分别维护一个单调栈，左半部分维护一个横坐标递减纵坐标递减的单调栈，右半部分维护一个横坐标递增纵坐标递减的单调栈。为什么要这样维护呢？先说说左半部分，如果当前点的横坐标大于栈顶的点，那么栈内的所有元素都不可能影响当前点对右半部分的点产.
2021-01-21 20:47:24
128
原创 acm-(树形dp)Educational Codeforces Round 52 (Rated for Div. 2) F. Up and Down the Tree
传送门设dp[u]dp[u]dp[u]表示以uuu为根节点的子树的答案，f[u]f[u]f[u]表示从以uuu为根节点的子树的根节点uuu出发按照题述规则遍历后能够回到uuu的父节点对应的遍历的叶子节点的最大数量。设md[u]md[u]md[u]表示uuu的子树中深度最小的节点，那么更新方程就是dp[u]=∑sonf[son]+maxson{dp[son]−f[son]}dp[u]=\sum_{son}f[son]+max_{son}\{dp[son]-f[son]\}dp[u]=∑sonf[son.
2021-01-20 23:43:31
90
原创 acm-(好题、kmp、思维、字符串)Good Bye 2020 G. Song of the Sirens
传送门设ans[i]ans[i]ans[i]表示www在sis_isi重复的次数，我们要求的其实就是ans[k]ans[k]ans[k]。设g[i]g[i]g[i]表示www在sis_isi中的重复次数，但是必须包含ti−1t_{i-1}ti−1。于是不难写出ans[i]=2ans[i−1]+g[i]ans[i]=2ans[i-1]+g[i]ans[i]=2ans[i−1]+g[i]，假设s[cur]s[cur]s[cur]是最小的满足len(scur)≥len(w)len(s_{cur})\.
2021-01-01 18:18:46
170
原创 acm-(思维、反面、01串)Educational Codeforces Round 101 (Rated for Div. 2) E. A Bit Similar
传送门考虑反面，要求构造一个串使得它和每个串有至少一位相同等价于构造一个串使得与所有长度为kkk的串取反后不同，其实只需要考虑这些串的最后20位即可，因为220>1e62^{20}>1e6220>1e6，也就是说当k≥20k\ge 20k≥20的时候总是存在一个长度为202020的串使得它跟所有的串反面不同，这也是我们需要找的串。由于要求串最小，那么除了最后202020位外我们可以让其它的位全是000，最后202020位直接从小到大暴力枚举看是否存在一个长度为kkk的串的末尾2020.
2020-12-29 21:53:17
190
原创 acm-(gcd、思维)第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（上海）L.Traveling in the Grid World
传送门当gcd(n,m)=1gcd(n,m)=1gcd(n,m)=1的时候，容易发现直接走直线即可，并且不会经过任何网格点，显然是一条最短路。当gcd(n,m)≠1gcd(n,m)\ne 1gcd(n,m)=1的时候，暴力枚举(0,0)(0,0)(0,0)向(n,m)(n,m)(n,m)连线的路径附近的整点，考虑将它们作为转折点，就像下图一样(标记红的点就是要枚举的转折点):那么为什么答案一定是出现在以这些红点中的某一个点为转折点的路径下呢？先考虑以一个点为转折点的最短路径的情况，设起点为A.
2020-12-24 11:58:53
334
原创 acm-(dp、优化)第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（上海）E.The Journey of Geor Autumn
传送门设dp[n]dp[n]dp[n]表示在kkk的情况下的答案，那么考虑nnn个数中最小的那个数的放置情况，显然只能放在前kkk个数中，于是枚举这个数的位置，那么更新方程就是dp[n]=∑i=1kdp[n−i]⋅Cn−1i−1⋅(i−1)!dp[n]=\sum_{i=1}^{k}dp[n-i]\cdot C_{n-1}^{i-1}\cdot (i-1)!dp[n]=∑i=1kdp[n−i]⋅Cn−1i−1⋅(i−1)!，这个方程的更新总复杂度是O(nk)O(nk)O(nk)，考虑变形一下，得到dp.
2020-12-24 08:47:40
403
原创 acm-(dp、思维、找规律)Codeforces Global Round 10 D. Omkar and Bed Wars
传送门先令′L′'L'′L′为000，′R′'R'′R′为111，然后本题就可以无脑dp，设dp[i][j][k][h][w]dp[i][j][k][h][w]dp[i][j][k][h][w]表示考虑到字符串第iii位，s[1]=j,s[2]=ks[1]=j,s[2]=ks[1]=j,s[2]=k，s[i−1]=h,s[i]=ws[i-1]=h,s[i]=ws[i−1]=h,s[i]=w的时候对应的最小改变字符数(使得前iii个字符合法，头尾不保证合法，在最后的时候对nnn特判)。方程有亿点点不好写.
2020-12-19 00:11:45
199
1
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人