zhangxixi的博客

一道求导题：1004T3 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133560750 需要知识: (xn)′=nxn−1(x^n)'=nx^{n-1}(xn)′=nxn−1 (sinx)′=cosx(sinx)'=cosx(sinx)′=cosx [f(g(x))]′=f′(g(x))×g′(x)[f(g(x))]'=f'(g(x))\times g'(x)[f(g(x))]′=f′(g(...

与值域有关的问题（非权值线段树）——运用分块：1004T1 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133560662 区间小于等于某值 区间加 显然同时涉及区间和值域，不能用log级ds来做，常见套路就是上分块 这题是个复合题，后面就是个组合数 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535...

组合数与莫队——组合数前缀和 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133559588 用莫队求组合数是一种常见套路 莫队求 S(n,m)=∑i=0m(ni)S(n,m)=\sum_{i=0}^m\binom n iS(n,m)=∑i=0m​(in​) S(n,m+1)S(n,m+1)S(n,m+1) 直接做个差，然后就相当于加上 (ni+1)\binom n {i+1}(i+1n​) 求 S(n+1,m)S(n+1,m)S(n+1,m) 会麻烦点，...

抓住普通情况变量猜结论：ARC136C 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133525236 假如不是环，我们求的就是上升的量。那么我们可以先大胆猜一波，环形结果就是上升的量。 然而我们在非环的情况是在前面补了0的，我们这里不能补0，我们就只能对最大值取max 1234n=read(); for(i=0; i<n; ++i) a[i]=read(), m=max(m, a[i]); for(i=0; i<n; ++i) k+=max(...

善于拆约束条件+合并相关项+DS维护：0928T2 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133521713 http://cplusoj.com/d/senior/p/SS230928B 老套路了 考虑枚举0和2 m+j+min(fam−gaj,fbm−gbj)\large m+j+min(fa_m-ga_j,fb_m-gb_j) m+j+min(fam​−gaj​,fbm​−gbj​) 然后拆一下min，再分情况讨论一下，移项合并相同的 以其中一...

贪心找性质+dp表示+矩阵表示+线段树维护：CF573D 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133437456 比较套路的题目 首先肯定贪心一波，两个都排序后尽量相连。我一开始猜最多跨1，但其实最多跨2，考虑3个人的情况： 我们发现第3个人没了，所以可以出现跨2的情况 然后直接上dp，由 i−1,i−2,i−3i-1,i-2,i-3i−1,i−2,i−3 转移过来。 然后这显然可以拿矩阵表示。 然后显然可以拿线段树维护。 后面三部分都是比较套路...

图论+博弈论上dp：CF536D 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133364509 此题其实比较板，只是我没看出来 首先肯定要跑个最短路，然后发现可以离散化把值域缩小 然后 nnn 很小，直接暴力列个 n2n^2n2 dp。 转移要注意的是必须从大往小dp。从小到大会产生后效性。 然后拿个双指针优化下转移就行。 123456789101112131415161718192021222324252627282930313233343536373...

博弈论（奇偶考虑法）+计数+DP（判定转dp）：CF838C 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133362167 首先题目有博弈，先分析一波最优策略（步骤：分析性质）。 两个人，所以显然考虑奇偶考虑法+递归考虑。 首先删就是使子问题-1，重新排列是在当前子问题里的。 一个串的排列是有限的，所以这里就可以上奇偶考虑法。如果有偶数种串，则必然是后手先“被迫“进入子问题（要算上初始情况） 考虑假设法：我们可以先假设进入子问题： 必赢。先手进！ ...

拆贡献与期望本质：CF1392H 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133355060 题目问牌数，但其实题面有另一个很明显的东西叫轮数 而如果我们每一轮单独考虑，其对应的期望牌数是确定的。 我们肯定会大胆考虑直接用期望牌数乘期望轮数，但为什么对？ 每轮牌数乘上前 i−1i-1i−1 轮未结束的的概率，后面的概率是第 iii 轮恰好结束的前缀和，而我们再求个和就是期望轮数。 考虑每一轮的期望牌数。首先肯定会抽到一种鬼牌，所以必然+1。然后考虑经典...

贪心+二分+DP+矩阵快速幂：CF461E 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133316261 https://codeforces.com/contest/461/problem/E 第一步：捕捉题目信息 四种字符 →\to→ 矩阵 n≤1018→n\le 10^{18}\ton≤1018→ 矩阵快速幂 →\to→ dp 最小值最大 →\to→ 二分 第二步：分析性质 sss 未知？那如果已知怎么做，肯定是每次暴力选最长的。 ...