文章归档

首先不同的地图最多只有16种了，每张地图可以组合的格式是 $2^{16}$ ,因为同一种地图变成全 $1$ 的步骤是一样的，那么我们可以这么抽象，把一种不同的地图状态看成二进制的某一位,把一些地图的组合看成是一个点，要求的是最小花费，我们可以用全 $1$ 的地图作为起点，向外拓展可以到达的点，那么就可以使用最短路求解。 具体的：令 $dis[x]$ 表示到达 $x$ 这个地图状态的最小花费 , $x$ 在第 $i$ 位是 $1$ 代表的就是代表有第 $i$ 张地图。我们可以定义 $trans[bit][S]$ 表示 当前有的地图集合是 $S$ 进行 $bit$ 操作时变成的状态集合 $S^{\prime }$ . $bit$ 是题目给的一行，一列等等的操作，具体是把 $2\times 2$ 的格子从左到右，从上到下设为 $1,2,4,8$ ，那么比如说对上面一行操作，那就是一张地图的二进制表示异或上 $3$

考虑一个序列最中间的左括号和右括号，如果这两个交换那么序列是不合法的，由此可以猜测确定操作序列唯一确定的条件。利用一种抽象的前缀和，把左括号看成 $1$ ,右括号看成 $-1$ ,对于一个左括号，如果和一个右括号中间的有一个前缀和是 $<2$ 的,那么操作序列就可以唯一确定，每次枚举左括号位置，计算合法方案数求和即可.

传送门：https://codeforces.com/gym/105851

总得来说，思路就是先找到，$L[i]$ 和 $R[i]$ ,左右第一个满足偏序条件的索引，即 $L[i]=j,s.t.j<i\&\&x[j]>=x[i]\&\&y[j]>=y[i]$ , $R[i]$ 同理。找到之后，考虑每个位置$i$ 能为区间 $[l,r]$ 产生的贡献，我们发现把询问 $[l,r]$ 看成二维平面的点，那么 对于 $i$ ,产生的贡献的区域就是 $[L[i]+1,i]\times [i,R[i]-1]$ ,贡献为1。

一个经典的套路，二分答案+check,检查是否可行也是经典的转化，把符合条件的变成1，不符合条件的置0，现在问题就变成了一个01序列可以用中位数代替3个数,让0尽量消去，1尽量多。

• 多走长度的偶数部分可以忽略,我可以通过在一个点来回走都掉这一部分
• 设 $x$ 是我要走的长度，题目条件转化为 $x\in [k\cdot l,k\cdot r]$ ,那么我们的答案就是最小的 $k$

一副除去大小王的扑克牌，初始两人各拿五张，你知道自己的牌，可以换 掉其中的若干张牌并加注同等数量的筹码，最终总点数大的一方胜并赢得 全部筹码，问最大收益的期望。

分享一下 单$log$ 做法 代码，本质上就是找离我左边最近的点和离我右边最近的点

期望具有线性性，可以将第一次选取的数为为 $i$ 的期望算出来，再把他们相加除以 $n$ 就是答案，问题转化为 对于第一次选取的数 $i$ 的期望长度怎么算， 对于一个 $k$ ,设 $f[i]$ 是以 $i$ 开始的期望长度，我们手模几个样例，发现如果选出来的数 $i\ge k$ ，$f[i]=1$ , 对于 $i<k$ ,$f[i]=1+\frac{1}{n-i}{\sum }_{j=i+1}^{n}f[j]$ ,如何理解相当于从 $i$ 开始已经长度为 1 了，我只能选择比 $i$ 大的数，对于 $[i+1,n]$ 每个数我有 $\frac{1}{n-i}$ 的概率选中它。因为期望具有线性性，所以求和相加除以平均数+1就是以 $i$ 开始的期望长度，但是这还不足以通过本题，如果每次跑一遍递推就是 $n^2$ 的复杂度，发现还可以优化，发现 $dp$ 式子好像是一个后缀和的形式，那么可以维护后缀和 $sum$ ,那么每次的递推不就变成了 $f[i]=1+\frac{1}{n-i}\cdot sum$, $sum=sum+f[i]=1+\frac{n-i+1}{n-i}sum$,我们要求的 $f[1]$ 已经被包含在最后的 $sum$ 里面，那么就不需要 $f$ 的递推了，只需要维护 $sum$ 即可，$sum$ 发现是一次函数复合. 设 $f=ax+b,g=cx+d$,$(f\circ g)(x)=f(g(x))=a(cx+d)+b$,写成映射形式就是 $(a,b)\circ (c,d)\mapsto (ac,ad+b)$ ,那么我们只要根据这个维护关于$sum$ 一次函数的嵌套即可$O(1)$求解，需要注意的是维护的嵌套顺序不对，需要求解上面映射的逆映射，这题卡空间，不清楚是否可以通过，不过可以提一嘴逆映射怎么求。 复合类似于于左乘矩阵，求逆也是类似的。具体的，现有一次函数复合 $F(x)=f_1(f_2(f_3(x)))$ ,现在我想得到 $f_1(x)$ ,那么我可以 $F\circ g(x)=f_1(f_2(f_3(g(x))))$ , 其中 $g(x)=f_3^{-1}(f_2^{-1}(x))f_3^{-1}是f_3的逆映射$ 该题还有一个细节，因为 $n$ 很大，需要线性求逆元

一道对次小生成树的考察，首先我们可以确定的是最小生成树肯定是其中一个答案，现在假设最小生成树的权值和 $cost(T)$ 是奇数,那么我们只要求偶数的答案即可，最小的偶数权值和 $cost(T^{\prime })$ 我们知道一定比 $cost(T)$ 大，那我们自然可以想到求严格次小生成树，但是求严格次小生成树只能保证一定比 $cost(T)$ 大，但是不能保证是偶数。我们回顾一下次小生成树的求法，考虑加入 $x-y$ 这一条边，会构成一个环，我们选取最小生成树上 $x-y$ 路径上权值最大的一条边，替换它，更新答案(如果要求严格的话这一步可能求出来的和最小生成树一样，那就要维护次大边，替换次大边) ,为了保证是偶数，我们不妨分开维护奇数和偶数，分别维护 $x-y$ 路径上奇数边权的最大和次大边，偶数边权的最大和次大边，那么每次尝试替换的时候，如果这条边是奇数，我就去查询最小生成树上偶数边权的最大和次大，偶数同理，那么本题即可解决. 这题还有一个corner case，有可能没有次小生成树或者最小生成树

套着数学外衣的字符串模拟题，首先，题目要求大于 $n$ 的最小的 $m$ 的倍数或者数字中出现 $m$

正难则反，考虑小于等于的个数不好考虑,我们可以用总数减去大于的情况

看网上题解很少，来写一份，这题个人觉得思维难度不是特别大，难度主要在于代码准确度,首先将问题转化成 $x$ 向 $f(x)$ 连边，这一步转化应该是比较容易想到的，通过手模样例，会有类似的灵感,那么 $n$ 个点 , $n$ 条边，会构成基环树森林，因为图没有保证连通所以会有多棵基环树，并且还会有自环(虽然这是trivial的) 然后我们考虑如何计算答案,题解中给出如下条件

将第二个条件转化成实际意义就是，两个点都需要通过移动进入环内并且，二者在环内的路径之差是环长的倍数,也就是最终会落在同一点,了解完需要的条件后我们需要计算答案，对于第二种条件，我们只关心能否走进环，并且路径差是环长倍数。所以我们对于相同环的长度进行合并处理，注意到环长最多只有 $\sqrt{n}$ 种(通过 $(1+2+3+....+x)=n$ 推导出来的)，将环上的点的深度定义为 $0$ , 环外面的点的深度依次递增,统计每个环长深度小于等于 $1$ 的点有多少, 深度小于等于 $2$ 的点有多少,这样子做下去即可

赛时磨了两个小时,模拟每一秒的变化就行了，模拟题要想清楚写这样思路比较清晰一些

题解是什么意思呢，首先我们需要知道的是，斐波那契数列可以用矩阵快速幂和矩阵乘法求解 $\left(\begin{array}{c}F(n+1)\\ F(n)\end{array}\right)=\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)\left(\begin{array}{c}F(n)\\ F(n-1)\end{array}\right)=M\left(\begin{array}{c}F(n)\\ F(n-1)\end{array}\right)$ $\left(\begin{array}{c}F(n+1)\\ F(n)\end{array}\right)=M^n\left(\begin{array}{c}1\\ 0\end{array}\right)$ 题解横着放也是一样的，根绝题解给出的例子，手模一下发现是对的，如何去理解? $T0$是一个单位阵$E$，$T1$和我上面写的矩阵相似,$E$和任何矩阵$A$相乘结果都是A，所以可以理解为$0$ 的贡献是 $E$ ,也就是没有，二进制$1$ 的贡献则是 $T1(M)$ 让斐波那契数列往下递推一次 然后题解那个从0 到 $2^m-1$ 的求和答案怎么算出来的呢? 我们需要注意到，$0——2^m-1$中, 二进制数 $1$ 的个数为 $0$ 的数有 $C_n^0$ 个 二进制数 $1$ 的个数为 $1$ 的数有 $C_n^1$ 个 二进制数 $1$ 的个数为 $2$ 的数有 $C_n^2$ 个 ...

记录一下为数不多的网络流

补题链接 看网上好像不怎么找不到代码,发一份出来

首先不考虑删除操作,那么插入元素这件事情就是DP(背包或者可达DP) 做的，设 $D{P}_i$ 为能否用S中的元素组合得到 $i$ 具体的转移式子为 $d{p}_i=d{p}_i|d{p}_{i-x}$,这样的时间复杂度是 $O(ns)$

看似解析几何实则DP，$\sout{被诈骗了}$,题目是说每次选择前面的所有未选择的点用最小的凸多边形覆盖，可以在二维平面平动和转动，问$y$轴累加最高多少,选择两个点会退化成线段，那么显然每次选择两个点更好,题目就变成了，n个点划分成若干线段，线段和 $max$ 是多少,显然DP $dp[i]=ma{x}_{j=1}^i(dp[j-1]+dis(p_i,p_j))$ $p_i$ ,$p_j$是两个点

最大值最小，对于套路化的题目来说一般先想二分?(不行试试DP?再试试网络流?),我们先试着二分答案$mid$，考虑如何检查, 题目说可以选择任一点为根，不好考虑我们不妨先选择1作为根节点 因为要让两个点的距离都尽可能的小,所以自然的选取两个节点的LCA会是第一直觉. 设两点间距离是$dis$ ,点x到 LCA 的距离是 $len$ ,首先显然的如果 $dis\le mid$随便选择一个点作为根都是可行的，否则, 对于x来说我们要找到它可以在mid步到达的节点(y同理) 如果$len\le mid$ 那就说明在x到LCA的路径内部就已经会走mid步,就是官方题解中的mid级子树内,否则我们找到距离y 的$dis-mid-1$节点，在这个节点到x之间，x走的步数都不超过mid.这样对于每一对点我们可以知道符合条件的节点是哪些，对这些节点取个交集即可，这里我采用了dfn序+差分求前缀和的方式

头一回用不是正解的方法做出来，也是比较极限，直接说做法就是二分+数位dp 数位$dp$ 求$1-n$出现多少含$4$的数字个数 $\sout{这纯纯板子了}$ 设 $f(x)$ 为$1-x$ 中含有4的个数，$f$ 关于 $x$ 单调递增(并非严格) ,题目要找的其实是 $x-f(x)=k$这样一个解,我们去二分 $x$，检查 $x-f(x)$ 和 $k$ 的大小关系 Specially ，我们需要注意 $x-f(x)$ 是一个一会儿单调递增，一会儿没有增量的一个函数，所以我们要找最小的符合上述方程的解

题目大意: $a,b,c$是每个人的衣服,相邻的人的衣服不可以相同,给定字符串,第$i$个位置代表第$i$个人的衣服,如果是问号则是待分配，$q$次询问,每次给定三个数x,y,z表示分别制作了x件a,y件b,z件c,问分配方案数

直接贴码了，注释可能有误，欢迎指出

$\sout{此为犟种的胜利，我太菜了呜呜呜}$ 分析: 首先发现的性质是如果是beautiful的话，他如果要继续拓展的话，只能是最小值-1 或者 最大值+1，那么我们可以固定最小值($i$)，每次去找它最大能拓展到哪里（记为$r$），那么最小值$i$对答案的贡献就是$r-i+1$，($[i],[i,i+1]....[i,i+1,r]$),那么只需要解决最后一个问题了，怎么找他最多能拓展到哪里?我们可以查询即将插入这个数位置的逆序对个数和顺序对个数，如果他在两个数组中的逆序对个数或者顺序对个数不一样那么就说明他们的相对位置是不同的，那么就是不可以插入的，这个可以用线段树做到，按照位置建线段树，因为插入的数是递增的所以找到的位置比他小的个数就是顺序对个数，找到的位置比他大的就是逆序对个数

题目大意: 每次操作会把区间内最大值除以2，q次询问，问[l,r]操作k次后的结果是什么

$\sout{虽然确实用dfn序计算贡献比递归调用好写也不饶，但谁让我是犟种呢}$

题目如下:

官方题解:

官方题解一如既往的简洁，$\sout{对于不会做的人要读懂真的挺难}$

一道数据结构体，差分+线段树，我从没有看见过的全新版本，不过据说挺常见的。线段树维护题目里询问的东西，是否一样，单调还有单峰，小细节挺多的。建线段树开始是从2开始的，因为差分的第一个元素是$a_1$，同理，询问的时候也要是$l+1$,更新只需要更新两个点即可，注意询问的区间范围，还有一点就是如果询问的区间长度是1的话直接特判掉。

本题需要的前置知识：hash/kmp+ACAM，解法很简单，没有什么好补充的，不过可以学习一下std的写法，构建fail树，再跑一遍dfs累积答案，这样的做法比较高效,不过我写kmp+ac自动机会TLE，估计可能是STL的锅，hash就快很多

总的来说就是对$\le lim$的$a_i$让它用第一种方式去更新,因为小的数更容易被更新,对于$>lim$的$b_i$用他们去更新$a_i$(第二种方式),因为大的数更容易更新别的数

做一些对官方题解的补充: 1.为什么问题可以转化为求$MEX\ge i$的连通块数量, 题目让我们求所有连通导出子图MEX之和,可能存在的答案有1,2......n,对于$i$,它的贡献是$MEX=i$的联通子图数量乘上MEX， 所以答案$ans={\sum }_{i=1}^{n}i\ast |MEX=i|$, 记$su{m}_i=|MEX=i|$ , 所以$ans={\sum }_{i=1}^{n}i\ast su{m}_i$,

大意 一个操作杆可以对k个红绿灯进行操作，操作杆上的一个字符对应一个红绿灯，操作包括+,-,0,问每种组合方案有多少种组合方式 +: red->green->yellow->red -:green->red->yellow->green

补题链接

官方题解

补充: $({\sum }_{u\in tre{e}_i}{a}_u{)}^2$ $={\sum }_{u\in tre{e}_i}{a}_u^2+2{\sum }_{x\in tre{e}_i,y\in tre{e}_i}{a}_x\ast a_y$ 可以用树状数组算出$\sum a_u^2$和$\sum a_u$,这样通过上述式子就可以求出$\sum a_x\ast a_y$即原文中的第二行

一开始和队友想出来的式子,$p_i$是$i$的因子数组 $ans[i]={\sum }_{i=1}^{k}ans[(i-p_i)/p_i]$ 一个$O(n\sqrt{n})$的dp显然是过不了的 然后想到了对每个数枚举倍数预处理因子的话计算的话,时间复杂度是$O(nlnn)$,因为是$\frac{n}{i}+\frac{n}{i+1}+....+\frac{n}{n}$约等于$nlnn$ 发现还是TLE,STL常数太大了，队友突然想到可以直接算 设当前数字是$i$,枚举倍数$j$,$ans[i\ast j]+=ans[(i\ast j-j)/j]+=ans[i-1]$, $ans[i-1]$已经算过了，可以进行转移,另外特殊处理因子是$i$本身的情况，$+1$即可

题目大意: 有m块钱，买花只能买花瓣数差值不超过1的花，有多少花瓣就花多少钱，问最多能买到多少花瓣

大意: MAD函数返回出现次数$\ge 2$的最大整数 $b_i$ = $MAD(a[1,2,...i])$ 每次操作把$a_i$进行上述操作，直到全变为0为止，对每次操作的数组进行求和，记为$sum$,问sum的大小

大意: 告诉除自己以外的相对位置，判断绝对位置是否有冲突 分析: 我们可以让相对位置连单向边，代表位置关系，如果有环就说明有冲突了，判环用拓扑排序即可

大意： $1\ast n$的地图有豆子和人，每个豆子每一秒可以往左或右移动一个单位长度，吃豆子不消耗时间，最短吃完所有豆子的时间

大意: 找两个不同的序列使得他们在mod 200的意义下相等 $2^8=256>200$，所以8个数构成的子序列必定有相同的子序列，状态压缩枚举min(8,n)的状态，如果第二次碰到某个数则输出yes，并输出序列

题意: 给定一棵树的遍历顺序，一个节点的子树遍历顺序是递增的，问这棵树的最小高度是多少

提交 题目大意 建一座桥要安装支架，支架之间的距离不能超过d(两个位置之间)，建支架的代价是$a_{ij}+1$ 问建连续相邻的k座桥的最小代价是多少

题意: 加边是所有点连通，没有重边和自环,问最小代价 加边规则：两点权值奇偶性相同代价为a,否则为b $-100\le a,b\le 100$

题意: 一个字符串$s$只有1,2,3,求最小的子串三者都包含. $0\le |s|\le 2e5$

题目大意： 每过一秒$a_i$或运算的范围往左和右扩展一个数,问经过$i$秒$a_i$是多少,刚开始$a_i=i$

题目大意: 一个人每月会有x的钱，m个月，每个月可以用钱换幸福值，问最多能获得幸福值多少,有多组测试

题目大意: 有三个面数给定的骰子，每次投出前进x+y+z(三个骰子投出的数字),开始位置在0点,问位置>n的期望步数？ 特别的,如果x==a&&y==b&&z==c会回到0点

题目大意: 给定以字符串，问从中选出任意多个数字可以得到多少不含前导零偶数(可以重复)

题目大意: 给你一个字符串，有q次询问，每次询问给一个区间l到r，问最少修改多少次使得区间内的字符串是好串 好串的定义:长度和自身相同的,拥有red子序列最多的字符串

题目大意: Def of 3-friendly：数字中只要子串mod 3==0即可,0也算 多组询问给定l ,r 问区间内有多少数满足条件

题目大意: 每天穿的衣服有数值val,从n天选m天使得val_max-val_min最小

题目大意: x从1号往n号点走t秒，秒之后y从n开始追x，y速度比x快

题目大意： 给定一棵树，对于每个点求包含该点的连通点集的数量

题目链接 题目大意 n头牛排队领礼物，每头牛有自己的ci，当它得到礼物后会插到倒数第ci个位置，问会有多少牛领不到礼物

题目描述: 你正在一个城市里旅游，这个城市里有n个景点，你需要从1号点出发，按顺序访问2号点、3号点...n−1号点、n号点并结束冒险，本来是这样的。 但是你感觉有些累，希望跳过其中的若干个点。设你跳过了k个点，则你跳过点的花费为： 若k=0，则花费为0。 若k>0，则花费为2k−1。 而你路上总花费为：对于未跳过的剩余点，相邻点的距离之和。 需要注意的是，你必须1号点出发，n号点结束，故1号点和n号点不允许跳过。 对于平面上两点ab，ab的距离是线段ab的距离，可以使用sqrt函数计算：sqrt((xa−xb)∗(xa−xb)+(ya−yb)∗(ya−yb))。 现在你希望跳过0个或者若干个点，使得自己的跳过景点的花费+路上总花费最小。请你输出一个三位小数表示你的答案。

题目大意:每个物品有自己的体积和价值，要求体积xi不超过m的情况下获得的最大价值W,(w,x特别大)

题目: 给你一棵根为1的有N个节点的树，以及Q次操作。 每次操作诸如: 1 x y：将节点x所在的子树的所有节点的权值加上y 2 x：询问x所在子树的所有节点的权值的平方和，答案模23333后输出

题目大意: n件物品每个物品有重量和价值,但所选物品的总重量并不是每件物品的重量和，而是所有所选物品的重量进行按位或运算的结果。

题目大意： 有一个排列p，对于i属于1-n,pi = pi+i,且pi要是质数 easy和hard不同就只有n的范围 1<=n<=1e6

大意: 要求除全 0 连续子数组外的每个连续子数组的平均数都大于等于 1,0最多有多少个

题目大意： 一个数组分三段，，第一段做异或运算，第二段做或运算，第三段做与运算，求三者和的最大值

题目大意： 有一个数组a，存在数组b，使ai = ai+bi，使得a有序（非递减），同时max{b1,b2,b3...}-min{b1,b2,b3...}要最小，求数组b

题目大意： 存在操作使得长度小于n的区间按非降序排列，问能否用一次操作使得整个数组非降序

题目大意 给定n个点，定义每个点的等级是在该点左下方（含正左、正下）的点的数目，试统计每个等级有多少个点。

题目大意 一个01串从第i个位置出发到第j个位置结尾且第j个位置为1的路径条数,只能从父亲走到儿子

题目大意: 一开始n个人已经有各自积分，经过m次比赛，问一号选手最高能排到第几名

学校里的题目，一开始我的想法使用while循环来解决，但我尝试用其他方法解决

我用递归写了一个程序但当我运行的时候输出的结果是错的，我一开始觉得是c+=1没运行后面我就把c+=1换了一个位置

然后还是错误的，我于是想看看每次运行的时候c的情况 结果发现最后的结果又会是对的，经过我的思考我发现了原因，因为print(c)这句话先执行了，c是之后加上去的，改成下面这样就没有问题了

今天我的一个同学给我发了个问题 学校里学python也没有多长时间，不是很会，经过我的思考，一开始我写成了这样

然后它出现了这样的问题：赋值前引用局部变量

当我写成这样时： 下面展示一些 内联代码片。