zhangxixi的博客

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15552903.html 题目链接 首先先预处理，把连续方块合一，变成 P2135 方块消除。 没错这题是双倍经验 设 dp(i,j,k)dp(i, j, k)dp(i,j,k) 为区间 [i,j][i, j][i,j] 内后面与 a[j]a[j]a[j] 相同颜色的方块有 kkk 个，然后分两种情况考虑。 直接把 [i,j−1][i, j-1][i,j−1] 裁掉，于是 dp(i,j,k)=dp(i,j−1,0)+(b[j]+k)2dp(i,...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15552685.html 题目链接 明显是道期望dp，设 fi=Ei→i+1f_i=E_{i\rightarrow i+1}fi​=Ei→i+1​。表示从第 iii 层到第 i+1i+1i+1 层的期望步数。 所以 Ex→y=∑i=xyfiE_{x\rightarrow y}=\sum_{i=x}^yfiEx→y​=∑i=xy​fi，即从第 xxx 层走到第 yyy 层的总期望步数。 现在推 fxf_xfx​, 设 dxd_xdx​ 为 xxx ...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15552456.html 题目链接 看到什么价值的什么喜爱度的明显是背包。 然而题目还要考虑小明的感受，所以弄个二维费用背包。 设 dp(i,j,k)dp(i, j, k)dp(i,j,k) 为前 iii 道菜，用 jjj 元，且小明的喜爱程度为 kkk 时小红的最大喜爱度。 如果不选，则 dp(i,j,k)=dp(i−1,j,k)dp(i, j, k)=dp(i-1, j, k)dp(i,j,k)=dp(i−1,j,k)。 如果选，则 dp(i...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15552404.html 题目描述 小明和小红还剩下N天的假期，小明可以安排旅行的计划。如果连续X天旅游，小明需要花旅行费用PXX元；如果连续X天不旅游，小明需要请小红吃饭，花费为Q*X元。（P,Q都是输入的常数） 请你帮小明写一个程序，计算出假期里他至少需要花费多少元。 只会贪心做法… 首先可以明确一点，在天数相同的情况下，吃饭天数连不连续不重要，旅行天数能分开就分开。 于是我们可以直接枚举吃饭天数 iii，剩下的 n−in-in−i 天旅游...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15551910.html 之前打atcoder时不会这个东西，下大分，现在赶快补 仅用于个人备忘 坐标系中三角形面积求法 已知三角形三点坐标为 A(x1,y1),B(x2,y2),C(x3,y3)A(x_1, y_1),B(x_2, y_2), C(x_3, y_3)A(x1​,y1​),B(x2​,y2​),C(x3​,y3​) 则三角形面积为： S△ABC=∣(x2−x1)(y3−y1)−(x3−x1)(y2−y1)∣2S_{\triangl...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15551902.html 此文章只是给自己看到，当作一个备忘录 一元二次方程求根公式 形如： ax2+bx+c=0(a≠0)ax^2+bx+c=0\quad(a\ne0) ax2+bx+c=0(a=0) 可得： x=−b±b2−4ac2a(△=b2−4ac⩾0)x=\frac{-b\pm\sqrt{b^2-4ac}}{2a}\quad(\vartriangle=b^2-4ac\geqslant0) x=2a−b±b2−4ac​​(△=b2−4a...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15551853.html 线性筛/欧拉筛的应用 线性求 ipi^pip 若 iii 是质数，则我们用快速幂求 ipi^pip。 若 iii 不是质数，则在欧拉筛里，必然可以用最小的质数 p1p_1p1​，使得 p1×j=ip_1\times j=ip1​×j=i，于是我们就可以得到结论： ip=(p1×j)p=p1p×jpi^p=(p_1\times j)^p=p_1^p\times j^p ip=(p1​×j)p=p1p​×jp 线性求欧拉...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15551802.html 卡特兰数 博客园的 LaTeX\LaTeXLATE​X 好容易炸啊 设 f(1)=1f(1)=1f(1)=1，则 ： f(n)=∑i=0n−1(f(i)×f(n−i−1))f(n)=\sum_{i=0}^{n-1}(f(i)\times f(n-i-1)) f(n)=i=0∑n−1​(f(i)×f(n−i−1)) 当然，也有两个通用公式： f(n)=C2nnn+1f(n)=\frac{C_{2n}^n}{n+1}\\ f...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15551651.html 测试一下这个博客园的功能（图片好像只能在洛谷上看，有时间就改） manacher 算法总结 题目大意 给定一字符串，求其最长回文串长度 方法对比 暴力效率：O(n3)O(n^3)O(n3)，优化后为O(n2)O(n^2)O(n2) manacher效率：O(n)O(n)O(n) 算法思想 回文串有两种：奇回文与偶回文 分类讨论太麻烦，主要是我不会，于是我们就统一为奇回文 如何统一 例： abbab 偶回文：abba 奇...