3 _Wflower

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 7w+

[记忆化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

[状压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

[BFS]Codeforces 906C Party题解

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

2018-11-05 19:39:25

[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

[复杂度分析]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=1n​f(i),n≤1011n\le10^{11}n≤1011解题分析嗯……转化一道就是求abc≤nabc\le nabc≤...

2018-11-02 11:17:40

[数位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

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

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

2018-10-29 16:25:27

[最短路+拓扑]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

[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

[DP]BZOJ 1939 [Croatian2010] Zuma 题解

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

2018-10-23 20:20:35

[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

[欧拉函数]BZOJ 2818 Gcd 题解

题目大意见题面。解题分析一开始我还以为很麻烦,然后才发现是数论水题。思想很简单,之前用过的套路gcd(i,j)=p =>gcd(i/p,j/p)=1gcd(i,j)=p\ => 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

[欧拉函数]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

[二分+交互]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

[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

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

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

2018-10-08 20:59:05

[莫队]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

[二分+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

[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

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

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

2018-09-17 21:49:31

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 1024勋章
    1024勋章
    #1024程序员节#活动勋章,当日发布原创博客即可获得