zhangxixi的博客

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15558415.html 题目链接 设 dp(i,j)dp(i, j)dp(i,j) 为前 iii 行放 jjj 个棋子的方案数， lenilen_ileni​ 为第 iii 行的列数。 类似背包的思想，每一行放或不放： dp(i,j)=dp(i−1,j)+dp(i−1,j−1)×(leni−(j−1))dp(i, j)=dp(i-1, j)+dp(i-1, j-1)\times(len_i-(j-1)) dp(i,j)=dp(i−1,j)+dp...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15558214.html 线性求逆元 当初做洛谷模板题的时候还没发现原来这就是线性求逆元，现在发现了才知道原来这么好用。 首先我们要求 [1,n](modp)[1,n]\pmod p[1,n](modp) 的逆元。 第一，我们知道： 1−1≡1(modp)1^{-1}\equiv1\pmod p 1−1≡1(modp) 现在我们要求 i(modp)i\pmod pi(modp) 的逆元，肯定的，我们可以把 ppp 拆分成： p=k×i+rp=k\...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15558203.html 题目链接 考虑每次都做一次拓扑排序。 如果所有节点未遍历，即存在环。 否则的话，如果结果唯一，即拓扑层数为 nnn，判断队尾层数是否为 nnn 即可。 否则结果不唯一。 由于最多只有26个字母，所以时间过得去。 —————————————————————————————————— 说一下我做题时的几个坑点： 每次做拓扑排序时不要修改入度。 输出的是最早能体现出的操作。 至于漏.: 什么的，推荐使用cp edi...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15558033.html 题目大意 我们称一个集合 S=(x1,y1),(x2,y2),…,(xk,yk)S={(x_1, y_1), (x_2, y_2), … , (x_k, y_k)}S=(x1​,y1​),(x2​,y2​),…,(xk​,yk​) 是好的，当且仅当把它们按照 yiy_iyi​ 降序排序后满足： 对于所有满足 3≤j≤k3 ≤ j ≤ k3≤j≤k 的 jjj，有 xj−2<xj<xj−1x_j−2 <...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15553942.html 题目链接 题外话： 这题应该没有蓝题难度吧，就是道树状数组模板题+一些小思维 利用前缀和思想，答案很明显为 rrr 之前的区间总数- lll 之前的区间总数，即 rrr 之前的左端点数目- lll 之前的右端点数目。分别用两个树状数组维护即可。 时间复杂度 O(nlog⁡2n)O(n\log_2n)O(nlog2​n)。 1234567891011121314151617181920212223242526272829...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：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...