<?xml version="1.0" encoding="utf-8" ?><rss version="2.0"><channel><title><![CDATA[张松超的博客]]></title><description><![CDATA[]]></description><link>https://blog.csdn.net/ZscDst</link><language>zh-cn</language><generator>https://blog.csdn.net/</generator><copyright><![CDATA[Copyright &copy; ZscDst]]></copyright><item><title><![CDATA[Codeforces Round #532 (Div. 2) （A，B，C，D，E，F）]]></title><link>https://blog.csdn.net/ZscDst/article/details/88848746</link><guid>https://blog.csdn.net/ZscDst/article/details/88848746</guid><author>ZscDst</author><pubDate>Wed, 27 Mar 2019 17:07:26 +0800</pubDate><description><![CDATA[A. Roman and Browser

n个数只有（1/-1），你可以选择一个位置b，然后把所有c位置的数删除，c=b+i*k ( i 可以为任意整数)，求的最大值

思路

直接暴力枚举b然后搞一遍就OK


#include &lt;bits/stdc++.h&gt;
using namespace std;
const int MAXN = 1e5 + 5;
int n, k, a[M...]]></description><category></category></item><item><title><![CDATA[Educational Codeforces Round 62 (Rated for Div. 2) (A,B,C,D,E)]]></title><link>https://blog.csdn.net/ZscDst/article/details/88797870</link><guid>https://blog.csdn.net/ZscDst/article/details/88797870</guid><author>ZscDst</author><pubDate>Mon, 25 Mar 2019 17:13:41 +0800</pubDate><description><![CDATA[A. Detective Book

题意

有一本侦探小说共n页，每一页都会有一个问题，第 i 页的答案在第 a[i] 页。有个人再看这本书，他读书有个习惯，必须把所有的问题都找到答案，问他几天能看完这本书？

题解

定义MAX为前缀的最大值，统计有几个位置MAX = a[i] 即可。


#include&lt;bits/stdc++.h&gt;
using namespace std;
c...]]></description><category></category></item><item><title><![CDATA[牛客网 ~ 2018年湘潭大学程序设计竞赛G ~ 又见斐波那契 （矩阵快速幂）]]></title><link>https://blog.csdn.net/ZscDst/article/details/88310986</link><guid>https://blog.csdn.net/ZscDst/article/details/88310986</guid><author>ZscDst</author><pubDate>Thu, 07 Mar 2019 15:51:27 +0800</pubDate><description><![CDATA[题意

思路
显然就是矩阵快速幂，我们只需要构造6*6的矩阵使得
F[i−1]+f[i−2]+i3+i2+i+1F[i-1] + f[i-2] + i^3 + i^2 + i + 1F[i−1]+f[i−2]+i3+i2+i+1 乘一次可以转移到F[i]+f[i−1]+(i+1)3+(i+1)2+(i+1)+1F[i] + f[i-1] + (i+1)^3 + (i+1)^2 + (i+1) + ...]]></description><category></category></item><item><title><![CDATA[UVA ~ 712 ~ S-Trees（二叉树，二进制枚举）]]></title><link>https://blog.csdn.net/ZscDst/article/details/85951925</link><guid>https://blog.csdn.net/ZscDst/article/details/85951925</guid><author>ZscDst</author><pubDate>Sun, 06 Jan 2019 21:33:31 +0800</pubDate><description><![CDATA[题意
给出一棵满二叉树，每一层用一个xix_ixi​的01变量来表示，xix_ixi​取0往左走，取1往右走。每个叶子结点有一个值（0或1），然后有一些询问，求每个询问到达的叶子结点的值。
多组测试数据，以n=0表示结束，每组先输入n表示有n层，然后输入从根到叶子每一层对应x几x_几x几​那个变量，然后输入叶子结点对应的值。
接下来输入Q次询问，每次询问输入一个长度为n的01串表示x1−&amp;amp;...]]></description><category></category></item><item><title><![CDATA[UVA ~ 673 ~ Parentheses Balance （栈，括号配对）]]></title><link>https://blog.csdn.net/ZscDst/article/details/85935731</link><guid>https://blog.csdn.net/ZscDst/article/details/85935731</guid><author>ZscDst</author><pubDate>Sun, 06 Jan 2019 16:51:08 +0800</pubDate><description><![CDATA[
题意
给定一串由()和[]组成的字符串。如果我们规定以下的字符串是合法的字符串：
(1) 空串是合法的字符串
(2) 如果A、B都是合法的，那么AB也是合法的字符串。
(3) 如果A是合法的，那么(A)和[A]都是合法的字符串。
也就是说，所有左右括号必须配对，且不能“切开括号”（如“[(])”或“([)]”）是不匹配的。
思路
直接拿栈模拟就OK，左括号入栈，右括号判断与栈顶是否匹配，匹配完最...]]></description><category></category></item><item><title><![CDATA[HDU ~ 6273 ~ Master of GCD （差分数组 + 快速幂）]]></title><link>https://blog.csdn.net/ZscDst/article/details/85253980</link><guid>https://blog.csdn.net/ZscDst/article/details/85253980</guid><author>ZscDst</author><pubDate>Tue, 25 Dec 2018 20:44:17 +0800</pubDate><description><![CDATA[
题意
T组测试数据，每组给出一个N和M，N表示有一个长度为N初始值全为1的序列，现在有M次操作，每次把[L,R]区间乘上x（x只可能是2或者3），问最终整个序列的最大公约数是多少？
题目PDF地址
思路
答案就是：22出现最小次数∗33出现的最小次数2^{2出现最小次数}* 3^{3出现的最小次数}22出现最小次数∗33出现的最小次数。
解释一下，第一个数被乘了2次2，4次3，第二个数被乘了3次...]]></description><category></category></item><item><title><![CDATA[POJ ~ 3263 ~ Tallest Cow（差分数组）]]></title><link>https://blog.csdn.net/ZscDst/article/details/85253589</link><guid>https://blog.csdn.net/ZscDst/article/details/85253589</guid><author>ZscDst</author><pubDate>Tue, 25 Dec 2018 20:14:45 +0800</pubDate><description><![CDATA[
题意
有N头牛，最高的是第i头，身高是H，现在有R组相对关系。每组相对关系有两个数A和B，表示A和B能相互看见，也就是他们中间的牛都比他俩低。输出所有牛的最大的可能身高。
思路
我们只要找到每个牛最大可能是第几高的就OK。
A和B可以相互看见，其实就是[A+1,B-1]区间的牛都比他俩低，也就是我们把这个区间的值都 -1即可。
很明显是在修改完之后在查询，直接用差分数组就OK。
==坑点：==相...]]></description><category></category></item><item><title><![CDATA[GYM ~ 101775J ~ Straight Master（思维，差分数组）]]></title><link>https://blog.csdn.net/ZscDst/article/details/85253125</link><guid>https://blog.csdn.net/ZscDst/article/details/85253125</guid><author>ZscDst</author><pubDate>Tue, 25 Dec 2018 19:41:21 +0800</pubDate><description><![CDATA[
题意
T组测试数据，每次给你一个长度为N的序列，每次可以选择一个长度3,4,5的区间将这个区间内的数都减一，问能否经过若干次操作后使得数组全变为0？
思路
首先将数组进行差分获得差分数组diff（diff[i]=a[i]-a[i-1]）。
diff[i]为+++就相当于以 i 为起点的区间有diff[i]个。diff[i]为−-−就相当于以 i 为终点的区间有diff[i]个。
对于区间长度如何...]]></description><category></category></item><item><title><![CDATA[洛谷 ~ P3948 ~ 数据结构 （差分数组）]]></title><link>https://blog.csdn.net/ZscDst/article/details/85233403</link><guid>https://blog.csdn.net/ZscDst/article/details/85233403</guid><author>ZscDst</author><pubDate>Mon, 24 Dec 2018 14:52:29 +0800</pubDate><description><![CDATA[思路
直接差分数组搞一搞就OK了。因为前面的查询和修改掺杂在一起的询问很少，所以对于那些询问我们暴力去查询就OK。在final询问之前求一个符合要求的前缀和就可以O(1)输出了。
#include &amp;lt;bits/stdc++.h&amp;gt;
using namespace std;
const int MAXN = 8e4 + 5;
typedef long long LL;
int n, opt...]]></description><category></category></item><item><title><![CDATA[洛谷 ~ P1083 ~ 借教室 （差分数组 + 二分）]]></title><link>https://blog.csdn.net/ZscDst/article/details/85174817</link><guid>https://blog.csdn.net/ZscDst/article/details/85174817</guid><author>ZscDst</author><pubDate>Fri, 21 Dec 2018 21:35:03 +0800</pubDate><description><![CDATA[

思路
很容易想到暴力的写法，对于一个订单来说，直接从第一天到最后一天都减去d[i]即可，每个订单复杂度为O(n)，总的复杂度为O(n*m)明显超时。
可以发现如果前x个订单不符合要求，那么往后一定不符合，这个性质使得我们可以使用二分来求答案。
我们每次二分一个答案，对于当前答案x，我们需要判断前x个订单是否可以符合要求。如果每一个订单都去暴力去减的话，那么依旧会超时。对于区间减法的操作很容易想...]]></description><category></category></item><item><title><![CDATA[HDU ~ 1556 ~ Color the ball （差分数组）]]></title><link>https://blog.csdn.net/ZscDst/article/details/85172015</link><guid>https://blog.csdn.net/ZscDst/article/details/85172015</guid><author>ZscDst</author><pubDate>Fri, 21 Dec 2018 20:21:52 +0800</pubDate><description><![CDATA[
思路
差分数组模板题。
学习链接
#include &amp;lt;bits/stdc++.h&amp;gt;
using namespace std;
const int MAXN = 1e5 + 5;
int n, a[MAXN];
int main()
{
    while (~scanf(&quot;%d&quot;, &amp;amp;n) &amp;amp;&amp;amp; n)
    {
        memset(a, 0, si...]]></description><category></category></item><item><title><![CDATA[洛谷 ~ P2458 [SDOI2006] ~ 保安站岗（树形DP，最小支配集变形）]]></title><link>https://blog.csdn.net/ZscDst/article/details/85169749</link><guid>https://blog.csdn.net/ZscDst/article/details/85169749</guid><author>ZscDst</author><pubDate>Fri, 21 Dec 2018 19:18:23 +0800</pubDate><description><![CDATA[

注意他看守的是通道端点（即树中的点）
思路
看起来很像是最小点覆盖或最小支配集。但是最小点覆盖是去覆盖边的；最小支配集，一个点只可以被支配集中的一个点支配。而本题，需要支配点，但是一个点可以被多个点去支配，所以本题是最小支配集的一个变形。
dp[u][0/1/2]dp[u][0/1/2]dp[u][0/1/2]表示以u为根的子树上的点全部被控制的答案。
dp[u][0]dp[u][0]dp[u...]]></description><category></category></item><item><title><![CDATA[UVA ~ 1218 ~ Perfect Service （树形dp，最小支配集）]]></title><link>https://blog.csdn.net/ZscDst/article/details/85074794</link><guid>https://blog.csdn.net/ZscDst/article/details/85074794</guid><author>ZscDst</author><pubDate>Tue, 18 Dec 2018 19:09:33 +0800</pubDate><description><![CDATA[
题意

补充
本题是多组输入输出，每组先输入N，然后输入N-1条边，然后在输入一个flag，flag=-1表示结束。
dp[u][2]=min(dp[u][2],dp[u][1]−dp[v][2]+dp[v][0]);dp[u][2] = min(dp[u][2], dp[u][1] - dp[v][2] + dp[v][0]);dp[u][2]=min(dp[u][2],dp[u][1]−dp...]]></description><category></category></item><item><title><![CDATA[UVA ~ 1292 ~ Strategic game （树的最小点覆盖）]]></title><link>https://blog.csdn.net/ZscDst/article/details/85004551</link><guid>https://blog.csdn.net/ZscDst/article/details/85004551</guid><author>ZscDst</author><pubDate>Fri, 14 Dec 2018 15:29:24 +0800</pubDate><description><![CDATA[
题意

对于图G=(V,E)来说，最小点覆盖指的是从V中取尽量少的点组成一个集合，使得E中所有的边都与取出来的点相连。也就是说，设V‘是图G的一个顶点覆盖，则对于图中的任意一条边(u,v)，要么u属于集合V’，要么v属于集合V‘。在V‘中除去任何元素后V’不在是顶点覆盖。

输入有多组数据，每组先输入N，表示N个结点（0~n-1），然后N行输入这个N个结点的信息，每行第一个数字表示第i个结点的编...]]></description><category></category></item><item><title><![CDATA[洛谷 ~ P2014 ~ 选课 （树形背包）]]></title><link>https://blog.csdn.net/ZscDst/article/details/85002210</link><guid>https://blog.csdn.net/ZscDst/article/details/85002210</guid><author>ZscDst</author><pubDate>Fri, 14 Dec 2018 13:34:06 +0800</pubDate><description><![CDATA[
思路
树形背包的模板题。加一个虚拟的0结点然后选m+1个科目就OK。
sz[u]sz[u]sz[u]表示以uuu为根的这棵子树的节点数目
dp[u][j]dp[u][j]dp[u][j]表示uuu以uuu为根节点的子树，选取jjj门课且必须选自己的最优解。
dp[u][j]=max(dp[u][j−k]+dp[v][k])，(j:min(m,sz[u])−&amp;amp;gt;2)(k:1−&amp;amp;...]]></description><category></category></item><item><title><![CDATA[HDU ~ 4745 ~ Two Rabbits （区间DP，环形序列的最长回文子序列）]]></title><link>https://blog.csdn.net/ZscDst/article/details/84989839</link><guid>https://blog.csdn.net/ZscDst/article/details/84989839</guid><author>ZscDst</author><pubDate>Thu, 13 Dec 2018 15:47:48 +0800</pubDate><description><![CDATA[
题意
有两只兔子和一个N块石头组成的环，他们在这个环跳，A顺时针跳，B逆时针跳，有一个要求他们两个每时每刻必须站在相同质量的石头上，跳过的石头不能再跳，两个人的起点任意（可以相同），求两只兔子步数之和的最大值？
思路
问题就相当于：环形序列的最长回文子序列。环形序列，其实我们把原串往后复制一段就OK了。
dp[i][j]dp[i][j]dp[i][j]表示[i,j][i,j][i,j]区间的最优...]]></description><category></category></item><item><title><![CDATA[HDU ~ 4632 ~ Palindrome subsequence（区间DP，容斥，回文子序列个数）]]></title><link>https://blog.csdn.net/ZscDst/article/details/84979655</link><guid>https://blog.csdn.net/ZscDst/article/details/84979655</guid><author>ZscDst</author><pubDate>Wed, 12 Dec 2018 21:21:59 +0800</pubDate><description><![CDATA[
题意
T组测试数据，每组给你一个序列，问这个序列有多少个回文子序列，mod104+7mod\quad 10^4+7mod104+7
思路
dp[i][j]dp[i][j]dp[i][j]表示[i,j][i,j][i,j]区间有多少个回文子序列
①s[i]!=s[j]s[i]!=s[j]s[i]!=s[j]，通过容斥可得dp[i][j]=dp[i+1][j]+dp[i][j−1]−dp[i+1][...]]></description><category></category></item><item><title><![CDATA[POJ ~ 3280 ~ Cheapest Palindrome（区间DP，变为回文子序列最小代价）]]></title><link>https://blog.csdn.net/ZscDst/article/details/84978927</link><guid>https://blog.csdn.net/ZscDst/article/details/84978927</guid><author>ZscDst</author><pubDate>Wed, 12 Dec 2018 20:29:47 +0800</pubDate><description><![CDATA[
题意
给你长度为N一个字符串，和M个字符，对于每个字符有两种操作：增加或删除，各有一个权值，问将这个串变为一个回文串的最小花费是多少？
思路
dp[i][j]dp[i][j]dp[i][j]表示将[i,j][i,j][i,j]区间变为回文串的最小花费
那么状态转移很容易想到:
①如果s[i]==s[j]s[i]==s[j]s[i]==s[j]，那么dp[i][j]=dp[i+1][j−1]dp[...]]></description><category></category></item><item><title><![CDATA[Codeforces ~ 1083A ~ The Fair Nut and the Best Path（树形DP，树的直径）]]></title><link>https://blog.csdn.net/ZscDst/article/details/84977135</link><guid>https://blog.csdn.net/ZscDst/article/details/84977135</guid><author>ZscDst</author><pubDate>Wed, 12 Dec 2018 18:07:19 +0800</pubDate><description><![CDATA[

题意
先输入N表示一棵有N个结点的树，然后输入N个点的点权，然后输入M条边。要求一条链，使得链上的∑\sum∑点权和-∑\sum∑边权和最大，输出这个最大值。
思路
显然是树的直径？
dp[u]表示当前到u的最长链，那么ans=max(dp[u]+dp[e.v]−e.w)ans = max(dp[u]+dp[e.v]-e.w)ans=max(dp[u]+dp[e.v]−e.w)，dp[u]=m...]]></description><category></category></item><item><title><![CDATA[HDU ~ 2476 ~ String painter（区间DP，好题）]]></title><link>https://blog.csdn.net/ZscDst/article/details/84960582</link><guid>https://blog.csdn.net/ZscDst/article/details/84960582</guid><author>ZscDst</author><pubDate>Tue, 11 Dec 2018 19:40:44 +0800</pubDate><description><![CDATA[
题意
现在有两个字符串A，B，现在有一种操作是可以将A的某一段全变为同一个字符，问将A变成B最少需要多少次操作？
思路
可以发现是区间DP，如果考虑直接将A变为B，A和B有的字符相同有的不同不太好DP。
我们可以分两步来，先计算出来把一个空串刷成B的花费，然后在计算把A变为B的花费就比较好计算了
首先看第一步：
定义dp[i][j]dp[i][j]dp[i][j]为把[i,j][i,j][i,j...]]></description><category></category></item></channel></rss>