shyyhs

题解

DP专题(52) 图论(4) 多校补题(2) 数据结构(27) 数论(4) 日记(14) 未归档(38)

/ 注册

全部文章 / 题解（共329篇）

前天我们写了数独II(dfs),今天来一个推箱子(bfs)--恶心

同样又得写170行的纯代码,还是十分不适应的QAQ.优先我们得保证箱子的移动步数最小,然后我们得保证人的移动步数最少,再然后又得优先NSWE.首先我们对箱子进行bfs,枚举方向的时候优先NSWE.然后取人步数最少的方案.每次进行移动的时候对人进行bfs,bfs到的必定是最短距离,我们用seq存下它的...

BFS

2020-05-28

1 922

数独(2)--即将要写一个200多行的代码..为自己壮胆+写完后的题解来自专栏

和数独1差不多--dancing link算法等会学完会有博客的QAQ,下面是爆搜解法.数独1的代码也就1百多行QWQ,数独2也才200多行,可惜蒟蒻代码打的少,导致码力十分弱,所以写下博客为自己壮胆QAQ.数独2题目是:请你将一个16x16的数独填写完整，使得每行、每列、每个4x4十六宫格内字母A...

dfs

2020-05-26

4 722

一个比较难的贪心--写法以及扩展来自专栏

在一个x轴上给你n个点,以及他们的坐标要你找k段使得2*k个点相连,然后求他们相连段的总距离.这是个贪心问题,至于证明我就不证明了..有点复杂,直接说结论吧.就是选了一段后,旁边的那两段就不会选了,我们就要造一个新的段为a[left]+a[right]-a[id].然后插入集合里面去.代表多连接了一...

贪心

2020-05-22

3 589

[CQOI2009]中位数图

是个还行的思维题.跟我昨天出的题差不多.样例解释:4724572435724316思路找下这个值所在的位子,记录为0,把小于它的计为-1,把大于它的计为1.然后就是用个map记录,把当前记录为0,因为必须要经过这个点,所以map只能记录前面的数.然后中间的那个数不是太好处理,单独拿出来处理一下.代码...

思维题

2020-05-21

0 705

k-size字符串来自专栏

这题很简单..就是切分连通块.把a看成一个联通块,把b看成一个连通块.题目就是要你切k-2刀分成k块.然后由连通块的定义可知肯定是对半分,然后代码就是这样--(把ans放到外面调bug,服了 #include <bits/stdc++.h> using namespace std; ty...

2020-05-18

3 1137

双端对列来自专栏

这是一篇关于蓝书的题解..因为我觉得这个题目比较好,其实蓝书的题目都挺好的,但是这个特别好,就先拿它当题解呐.其实数据结构中的一些容器越学越会发现它的神奇之处.比如双端队列.下面是题目讲解..题目描述:达达现在碰到了一个棘手的问题，有N个整数需要排序。达达手头能用的工具就是若干个双端队列。她从1到N...

双端队列

2020-05-08

1 845

Codeforces div2 c~e 来自专栏

题意:给定n个节点的有根树，根是1号节点。你可以选择k个节点将其设置为工业城市，其余设置为旅游城市。对于一个工业城市，定义它的幸福值为工业城市到根的路径经过的旅游城市的数量。你需要求出所有工业城市的幸福值之和的最大可能值。注意工业城市到工业城市不计幸福值..那么怎么计算幸福?肯定我选这个的时候后面的...

2020-04-16

3 891

codeforces Three Blocks Palindrome题解来自专栏

先看看数据范围,1≤t≤104,1≤n≤2⋅105,1≤ai≤200注意到ai很小是吧?那么我们就可以dp[i][j]预处理它们的值i到当前j位子有多少个.然后暴力就没了..3个for 200n的复杂度 #include<bits/stdc++.h> #define ios ios_ba...

2020-04-14

0 942

关于dij算法的理解.. 来自专栏

因为本人很弱没学过dp,试图用dp写最短路,结果算法写出来复杂度应该大概有n^2,本人对算法复杂度又不是很敏感.所以就炸了,呜呜呜 void dfs1(ll x) { vis1[x]=1; // cout<<1<<endl; for(ll i=0;i&l...

2020-04-14

2 785

黑白树题解来自专栏

先给大家看看样例的图.思路:从最底下开始考虑,消耗了其价值肯定要走完,然后没消耗的就要保留到现在消耗1能造成的最大价值.下面的代码有注释.大家看看就懂了,不懂私聊~ #include<bits/stdc++.h> #define ios ios_base::sync_with_stdio...

2020-04-11

2 926