_Wflower-CSDN博客

原创 [记忆化DFS]NOIP2017Day1T3 逛公园题解

解题分析题面网上肯定找得到，不贴了……仍然填大坑ing……当初在考场上看到了此题，由于发现k≤50k\le50k≤50，所以自然要在kkk上搞事情。设f[i][j]f[i][j]f[i][j]表示到达i点此时的路径总长度比最长路长j的题解，初始最短路求一趟，然后转移……转移……我又写了个spfa神奇转移骗走60分……这道题可以考虑拓扑+DP转移，然而也可以记忆化DFS转移，由于记忆化DFS...

2018-11-06 21:06:27 282

原创 [状压DP]NOIP2017Day2T2 宝藏题解

题目大意给出一个无向图，一开始选中一个点进行扩展成一棵树，初始节点深度为0，每次建边的代价为子节点到父节点的距离乘上子节点的深度，求最小建边代价。 n≤12n\le12n≤12解题分析见nnn那么小肯定想到状压DP了，然后用二进制枚举状态，可以用f[S]f[S]f[S]表示状态为SSS（0为不在树上，1为在树上），但是需要乘上子节点的深度，那么如何枚举？考虑加一维f[i][S]f[i][S]...

2018-11-06 19:25:02 247

原创 [BFS]Codeforces 906C Party题解

题目大意给出一个nnn个点eee条边的无向联通图，每次可以选中一个点，将这个点和它相邻的点缩成一个点，求最少需要多少次才能把图缩成一个点。解题分析首先要发现，以不同的顺序选中同样的点的结果其实是相同的，所以我们关注的就是选出哪些点，又由于n≤22n\le22n≤22，所以可以考虑二进制枚举选出的点集S，然后是结论：如果S内点联通，且任意一个S外点都至少与一个S内点相连，那么S合法。那么这...

2018-11-05 19:39:25 300

原创 [DP]hihoCoder #1147 时空阵题解

题目大意给出一个nnn个点的图，现允许任意两点之间建立长度为1的无向边（不允许重边），问有多少种建图方案满足1到nnn的最短路距离为KKK。n,K≤100n,K\le100n,K≤100解题分析很妙的DP！可以考虑对这个图进行分层，第iii层上所有点的最短路距离都为iii，那么1在第0层，nnn就在第KKK层，每一层都只能与上一层或这一层中的节点相连。设f[i][j][k]f[i][j][k...

2018-11-02 20:43:25 279

原创 [复杂度分析]HDU4473 Exam 题解

题目大意定义f(x)=∑a=1+∞∑b=1+∞[ab∣x]f(x)=\sum_{a=1}^{+\infty}\sum_{b=1}^{+\infty}[ab|x]f(x)=∑a=1+∞∑b=1+∞[ab∣x]，求∑i=1nf(i)\sum_{i=1}^nf(i)∑i=1nf(i)，n≤1011n\le10^{11}n≤1011解题分析嗯……转化一道就是求abc≤nabc\le nabc≤...

2018-11-02 11:17:40 161

原创 [数位DP]BZOJ 3131 [Sdoi2013]淘金题解

题目大意有一个大小为N∗NN*NN∗N的矩阵，一开始矩阵内每一个数都是1，每一次变换后坐标为(i,j)(i,j)(i,j)内的数会累加到(f(i),f(j))(f(i),f(j))(f(i),f(j))，其中f(x)f(x)f(x)为各位数的累积（如果f(x)=0f(x)=0f(x)=0，那么直接消失）。问一次变换后矩阵内前KKK大的数之和。N≤1012,K≤106N\le10^{12},K\...

2018-11-02 09:17:05 173

原创 [Manacher+离线+线段树]2015计蒜之道初赛第三场商品推荐走马灯题解

题目大意给出一个长度为nnn的序列，多次询问一个区间[L,R][L,R][L,R]内所有回文子串的权值和。解题分析涉及到回文字符串的题目立刻脑回路想到Manacher，那么这题可以考虑从回文中心入手，然后又发现这道题支持离线操作，所以可以离线询问，然后分析每一个回文中心的影响。那么对于一个询问，会存在回文中心是先碰到左端点还是先碰到右端点，所以可以分成两半分别处理，对于左半区间，肯定会先碰...

2018-10-29 16:25:27 193

原创 [最短路+拓扑]BZOJ 2750 [HAOI2012]Road

题目大意给出一个有向图，求有向图上每条边被多少不同的最短路通过。n≤1500,e≤5000n\le1500,e\le5000n≤1500,e≤5000解题分析签到题？反正并不难，就对于每个点先求最短路，然后取出所有dst[x]+w[j]==dsd[son[j]]dst[x]+w[j]==dsd[son[j]]dst[x]+w[j]==dsd[son[j]]对跑出来的图进行拓扑排序，正着做一...

2018-10-25 20:42:17 208

原创 [DFS序+树状数组+nim游戏]BZOJ 2819 nim 题解

[DFS序+树状数组+nim游戏]BZOJ 2819 Nim 题解题目大意给出一棵带点权的树，多组询问树上一条链上的所有点的点权作为nim游戏的初始石子数，问是否存在必胜策略，带修改。N,Q≤500000N,Q\le500000N,Q≤500000解题分析如果看过我那篇上了两次又删了两次的2017暑假集训日记的话~~（虽然我觉得应该没人记得82695518）~~，应该知道我对于这道题的无...

2018-10-24 20:59:54 246

原创 [DP]BZOJ 1939 [Croatian2010] Zuma 题解

[DP]BZOJ 1939 [Croatian2010] Zuma 题解题目描述祖玛游戏是这样的：有一列nnn个有颜色的珠子，如果触碰连续KKK个同色的珠子，那么它们就会消失，其余的珠子按照原来顺序接在一起。现在你每次可以发射任意颜色的珠子，发射在任意位置（开头、结尾以及任意两个之间）。注意，如果有连续kkk个或更多同色的珠子，你可以不立即消去他们，详见样例 3。问最少需要几发可以消掉所...

2018-10-23 20:20:35 271

原创 [KMP]BZOJ 4974 [Lydsy1708月赛]字符串大师题解

题目大意给出一个长度为n的字符串，求这个字符串的所有前缀的最小循环节，现在反过来，给出所有前缀的最小循环节，求字典序最小的字符串。(N≤100000)(N\le100000)(N≤100000)解题分析最小循环节=i-nxt[i]那么可以求出nxt数组。求出来了又如何？如果Nxt[i]已知，注意nxt[i]的定义是s[1…nxt[i]]=s[i-nxt[i]+1…n]，那么明显s[i]...

2018-10-18 19:05:45 236

原创 [欧拉函数]BZOJ 2818 Gcd 题解

题目大意见题面。解题分析一开始我还以为很麻烦，然后才发现是数论水题。思想很简单，之前用过的套路gcd(i,j)=p =&gt;gcd(i/p,j/p)=1gcd(i,j)=p\ =&gt; gcd(i/p,j/p)=1gcd(i,j)=p =>gcd(i/p,j/p)=1所以就是枚举素数p，然后就是求[1,n/p]中互质的数对个数，不难发现就是...

2018-10-14 20:34:12 189

原创 [欧拉函数]HDU 2824 The Euler function 题解

题目大意求∑i=LRφ(i)\sum_{i=L}^R \varphi(i)∑i=LRφ(i)解题分析水题，前缀和构造，注意空间不要爆示例代码题目传送门#include<cstdio>using namespace std;typedef long long LL;const int maxn=3000005;int s,t,p[maxn];bool vs[max...

2018-10-14 14:26:20 173

原创 [二分+交互]Codeforces#415 (Div. 1) 809B. Glad to see you! 题解

题目大意交互题，在[1,n]中选出k个数，每次你可以给出一次询问a,b，回复为如果∣a−x∣≤∣b−y∣|a-x|\le|b-y|∣a−x∣≤∣b−y∣满足，那么回复"TAK"，负责回复"NIE"，其中x,y是K个数中分别与x,y距离最近的数。求60次询问内得到K个数中任意的两个。解题分析第一道交互题多次查找的话想到二分之类的话，这里有个比较妙的技巧，每次给出(mid,mid+1)，然后判...

2018-10-12 14:29:32 199

原创 [BFS序+线段树]HDU 5957Query on a graph 题解

题目大意给出一个n个点n条边的图，有两种操作：1.Uptate x k d 将所有距离x距离不超过k的所有节点加d2.Query x k 统计所有距离x距离不超过k的所有节点n≤105,0≤k≤2n\le 10^5,0\le k \le 2n≤105,0≤k≤2解题分析基环树常用套路：将整个环当做一个根节点，然后建树。然后用BFS建树的时候可以得到一个进队列的顺序，称之为BFS序（相...

2018-10-12 09:44:13 217

原创 [Manacher+贪心]BZOJ 3790 神奇项链题解

[Manacher+贪心]BZOJ 3790 神奇项链题解本题有权限题目描述Description母亲节就要到了，小 H 准备送给她一个特殊的项链。这个项链可以看作一个用小写字母组成的字符串，每个小写字母表示一种颜色。为了制作这个项链，小 H 购买了两个机器。第一个机器可以生成所有形式的回文串，第二个机器可以把两个回文串连接起来，而且第二个机器还有一个特殊的性质：假如一个字符串的后缀和...

2018-10-08 20:59:05 437

原创 [莫队]BZOJ 4542 [Hnoi2016]大数题解

题目大意给出一个长度为NNN的数字串和一个素数ppp，MMM组数据求一段子串内为ppp倍数的子串个数。解题分析先假设ppp不为2和5，那么对于一个ppp的倍数xxx和一个位数为LLL的数字yyy，那么有x mod p=0x\ mod\ p=0x mod p=0y mod p=zy\ mod\ p=zy mod&nbsp...

2018-10-07 20:28:04 170

原创 [二分+DP]BZOJ1181 [CROATIAN2009]IZBROI选举题解

题目大意在地区选举中有nnn个政党争夺mmm个议会席位，总共有VVV张票数，其中已经有一些票已经投出，议会席位的分配方式如下：设viv_ivi为第iii个政党的票数，第iii个政党有SiS_iSi个席位，初始所有政党都没有席位，先把投票数小于5%5\%5%的政党剔除，每次把席位给vi/(Si+1)v_i/(S_i+1)vi/(Si+1)最大的政党，问每个政党能得到的席位数的最大和最小值。...

2018-10-03 15:27:26 335

原创 [DP](计蒜之道2016程序设计大赛初赛第六场)微软的员工福利题解

[DP] (计蒜之道2016初赛第六场) 微软的员工福利题解题目大意给出一个nnn个节点的有根树，每个点可以赋予给定的两个值v[i][0/1]v[i][0/1]v[i][0/1]其中之一，这棵树的权值就是所有节点的值，但是对于每个非叶节点节点iii而言，如果在它和它所有儿子节点中最大值与最小值的差大小为xxx，那么需要在树的权值中扣除i∗666∗⌈x1000⌉i*666*\lceil\fra...

2018-09-24 20:58:09 251

原创 [二分+2-SAT]POJ 2749 Building roads 题解

[二分+2-SAT]POJ 2749 Building roads 题解题目大意给出nnn个谷仓和2个中转站的坐标，要求每个谷仓都必须连且只连接其中一个中转站，有k1k1k1对谷仓由于某种原因不能连在同一个中转站，还有k2k2k2对谷仓由于另某种原因一定要连载同一个中转站，平面上两点路径等于两点的曼哈顿距离，问所有谷仓连接后所有两个谷仓的最长路的最小值是多少。解题分析“连且只连接其中一个中...

2018-09-17 21:49:31 185

原创 [二分+半平面交]POJ 3525 Most Distant Point from the Sea 题解

题目大意给出一个nnn条边的凸多边形，求这个凸多边形离边界最远的点与边界之间的距离，n≤100n≤100n\le100题目分析这道题有多种写法，这里为其中一种方法，对于凸多边形上一点到边界的距离肯定是取所有边到点的距离中取最小值，最小取最大？二分！我们可以尝试二分查找答案x验证。对于每条边界，都要有一部分是与边界距离大于等于x的，这些点在一起构成了一个小的凸多边形，或者可以说，构成...

2018-09-13 20:04:21 166

原创 [并查集]LibreOJ#10067 构造完全图题解

题目大意见题目……解题报告完全不会做啊…… 从边入手这道题. 把每条边所连的左右两个点分别看做一个集合，左边集合和右边集合所要连的边数是（cnt[i]*cnt[j]-1）。但我们要连的边权是多大？不能比当前的边还小，所以边权就为（当前边的边权+1），我们可以贪心的去解决，把边从小到大排序，并查集一下就行了，当然还得加上原始边的边权。全是抄的……...

2018-09-10 21:10:38 541

原创 [AC自动机+DP]BZOJ1030 (JSOI2007)文本生成器题解

题目大意给出n个模板串，如果在一个文本中至少存在一个模板串，那么这个文本就是合法的，求长度为m的文本的合法方案数模10007后的结果。解题报告AC自动机+DP的经(mo)典(ban)题。用模板串建AC自动机，f[i][j]f[i][j]f[i][j]表示文本串长度为iii，在AC自动机上匹配到节点jjj的方案数，注意别走到单词节点，而且如果fail[x]fail[x]fail[x]...

2018-09-07 21:42:45 176

原创 [AC自动机]BZOJ4327 JSOI2012 玄武密码题解

题目大意给出nnn个文本串|s||s||s|和1个模板串|S||S||S|，问对于每个文本串能与模板串匹配的最长前缀长度。∑|s|≤107,|S|≤107,n≤105∑|s|≤107,|S|≤107,n≤105\sum|s|\le10^7,|S|\le10^7,n\le10^5解题报告对nnn个文本串建立AC自动机，然后将模板串放到AC自动机上匹配，对于匹配到的点就沿着它的fa...

2018-09-06 19:15:51 207

原创 AC自动机

简介AC自动机，全称Aho-Corasick自动机，适用于存在多个模板串的字符串匹配问题，如果没有AC自动机，你可能需要对n个模板串分别求一趟KMP，但是复杂度过高，而AC自动机可以一次匹配，效率更优秀。实现KMP是在字符串上线性匹配，而AC自动机则在字符串的集合上匹配，什么东西可以把一大堆字符串吧、放一起存储？Trie!所以AC自动机其实就是在Trie上生成KMP的失配函数。...

2018-08-30 15:07:35 1031

原创 [Trie树]BZOJ 1590 [Usaco2008 Dec]Secret Message 秘密信息题解

[Trie树]BZOJ 1590 [Usaco2008 Dec]Secret Message 秘密信息题解题目大意给出nnn个01字符串a和mmm个字符串b，求对于每个字符串b，有多少个字符串aaa满足lcp(a,b)=min(a,b)lcp(a,b)=min(a,b)lcp(a,b)=min(a,b)（lcp为最长公共前缀，min取长度较短的那个字符串），n,m≤105n,m≤10...

2018-08-28 14:52:06 276

原创 2-SAT

定义2-SAT问题如下：给出nnn个集合，每个集合内有两个元素（例如：truetruetrue和falsefalsefalse），要求每个集合内必须取且只能取一个元素，并且给出一些限制条件，例如选iii就不能选jjj，求一种合法方案。分析首先如果集合iii中有两个元素，那么可以把它们标号为2∗(i−1)2∗(i−1)2*(i-1)和2∗(i−1)+12∗(i−1)+12*(i-1)...

2018-08-28 11:18:05 1318

原创 [贪心+并查集+堆]HDU6326(2018多校训练赛第三场 Problem H)Monster Hunter 题解

一种好像之前做过这道题的感觉，然后发现……没用。题目大意你现在正在打一个游戏”Monster Hunter“，游戏中你在一个有nnn个节点的地图上，一共有n−1n−1n-1条双向边相连，初始时你在节点1上，初始HP值为XXX，节点2,3,…,n各有一个怪兽，要消灭第iii个怪兽需要aiaia_i点HP，在消灭第iii个怪兽之后又可以得到bibib_i的HP，消灭第iii个怪兽需要先把他和你...

2018-08-27 10:12:41 526

原创 [Trie+贪心]BZOJ 4567 [Scoi2016]背单词题解

题目大意给出nnn个字符串，要求给这nnn个字符串编号1~n，使其代价和最小。对第iii个字符串编号为viviv_i，代价的计算方式如下：1.如果存在字符串jjj满足jjj是iii的后缀，且vi<vjvi<vjv_iiii的代价为n2n2n^2 2.如果字符串iii没有对应的后缀，那么代价为viviv_i 3.如果存在字符串jjj满足jjj是iii的后缀，而且没有vi&...

2018-08-25 16:54:36 186

原创 [Manacher]BZOJ 2160 拉拉队排练题解

题目大意给出一个长度为n的字符串，求它前k长的回文子串长度乘积。n≤106,k≤1012n≤106,k≤1012n \le10^6,k\le10^{12}解题报告某神犇曾经说过：“ 水水博客有利身体健康。” 所以这题就是Manacher裸题，因为如果[L,R]是回文子串，那么[L+1,R-1]也是回文子串。所以前缀和统计就行了。#include<cstdio>#...

2018-08-24 22:18:22 152

原创 [KMP]BZOJ 3620 似乎在梦中见过的样子题解

题目大意给出一个字符串，求它有多少个子串满足可以拆成三个子串A+B+AA+B+AA+B+A，其中|A|≥k,|B|≥1|A|≥k,|B|≥1|A|\ge k,|B|\ge1解题报告O(n2)O(n2)O(n^2)过,真是……前缀和后缀相同，KMP……那么这道题枚举左端点L，对后缀进行失配处理，建一棵fail数（把每个点向它的失配点连边，可以构造出一棵树），那么如果子串[L,...

2018-08-24 16:15:19 478

原创 [KMP]UOJ#5. 【NOI2014】动物园题解

题目大意多组数据，每次给出一个长度为nnn的字符串，求它的∏ni=1(num[i]+1)&nbsp;Mod&nbsp;1000000007∏i=1n(num[i]+1)&nbsp;Mod&nbsp;1000000007\prod_{i=1}^n(num[i]+1)\ Mod\ 1000000007num[i]num[i]num[i]的定义为：对于字符串长度为i的前缀子串中，前缀等于后缀且前...

2018-08-24 11:09:16 985

原创 [DP]HDU6415(2018多校训练赛第九场 Problem A) Rikka with Nash Equilibrium 题解

题目大意给出一个n∗mn∗mn*m的网格，现要在网格中填入1，2，……，n∗mn∗mn*m，如果一个格子数比同行同列的数都大，那么就说这个格子占领了这行这列，求只有一个格子占满一行一列的方案数。解题报告因为n∗mn∗mn*m是最大的，所以他肯定占领一行一列，所以这样的话我们就必须保证其他的数都不能同时占领一行一列了。如果我们随便把n∗mn∗mn*m放在某个格子上，接下来放n∗m...

2018-08-23 23:55:23 224

原创 [模拟(绝对值)]HDU6435(2018多校训练赛第十场 Problem J) CSGO 题解

题目大意在玩CSGO的你有nnn把枪和mmm个弹匣，每把枪有一个威力SmiSmiS_{mi}，每个弹匣也有一个威力SsiSsiS_{si}，但是由于这个游戏神(che)奇(dan)的设定，所以枪和弹匣可能会出现一些奇妙的效果来增强威力，具体来说，每把枪和每个弹匣都有kkk个参数性x[1],x[2],..,x[k]x[1],x[2],..,x[k]x[1],x[2],..,x[k]，而一把枪和一...

2018-08-23 16:08:04 232

原创 [字符串hash+DP]HDU4622 Reincarnation 题解

题目大意给出字符串s，多组询问子串中本质不同子串个数。解题报告典型的后缀树/后缀自动机模板题，然而都不会，所以直接用hash。考虑枚举出一个子串出现在[L,R]，那么如果没有重复，所有包含着这个子串[L,R]的区间答案+1，但是如果出现了重复，那么就需要-1。但之前处理的时候有些区间已经去过重了，不能误删，这里可以在之前处理的时候用hash存储每个相同长度的子串，然后如果找到重...

2018-08-23 14:36:35 202

原创 [莫队]HDU6333(2018多校练习赛第四场 Problem B)【Harvest of Apples】题解

题目大意求f(n,m)=∑mi=0Cinf(n,m)=∑i=0mCnif(n,m)=\sum_{i=0}^{m}C_n^i，多组数据。解题分析上莫队。如果已经求出了f(n,m)f(n,m)f(n,m)，那么如何求出f(n+1,m)f(n+1,m)f(n+1,m)和f(n,m+1)f(n,m+1)f(n,m+1)呢？f(n,m+1)=f(n,m)+Cm+1nf(n,m+1)...

2018-08-21 11:34:22 157

原创莫队算法

莫队算法前言当初我问ZigZagK什么是莫队算法时，他给了我一个神犇的眼神，飘了一句：“就是一个高级的暴力。”当时我彻底凌乱，后来翻了下他的Blog，发现……神犇都喜欢把话都说的很简洁……实现莫队算法，就是当你处理一个区间问题时，已经知道了[L,R]的答案，求[L’,R’]，那么如果可以通过较快的复杂度得到[L+1,R],[L-1,R],[L,R+1],[L,R-1]的答案...

2018-08-21 10:52:50 147

原创【字符串+哈希】BZOJ 2795 [Poi2012]A Horrible Poem 题解

(传送门)题目大意见题面……解题分析贴结论：一个字符串的最小周期等于这个字符串的长度-border的长度但这道题是多组询问，所以不能用KMP，此时又出现了这么一个定理：如果这个字符串的一个周期为x，则[L,R-x]=[L+x,R] ([]表示子串位置)而且很明显循环节的长度是字符串的一个因子。所以线性筛O(n−−√n\sqrt n)找出所有因子，然后哈希判断一...

2018-08-04 23:54:29 273

原创【线性模方程】BZOJ 1407 [Noi2002]Savage 题解

题目大意nnn个人在mmm个点的环上，每个人初始在点cicic_i，能活LiLiL_i秒，每秒会向后走pipip_i步，求出最小的mmm使得任意两个人在有生之年都不会在一个点上相遇。解题分析转化一下这题，如果两个人i,ji,ji,j在第xxx天相遇了，说明什么？ci+x∗pi≡cj+x∗pj(Mod m)ci+x∗pi≡cj+x∗pj(Mod m)c_i+x...

2018-08-02 23:38:47 125

原创【最大流】BZOJ 1066 [SCOI2007]蜥蜴题解

（传送门）题目大意已知n只跳跃距离为D的蜥蜴被困在石柱林中，它们可以通过在石柱上跳跃来逃脱，但每个石柱都有一个通过的限制，问最少有多少只蜥蜴最终困在石柱林中。解题分析ans可以转换成总蜥蜴数-最大逃脱蜥蜴数。每个石柱明显说有通过的限制，那么网络流建模，每个石柱拆点，流量限制为通过限制，建立超级源和超级汇，等等… 总之不错的网络流建模题。解题代码#incl...

2018-07-27 08:29:16 152

空空如也

空空如也