又在摸鱼的大熊猫很勤奋努力

分类

题解(38)

/ 注册

TA的专栏 36篇文章 0人订阅

36篇文章 1214人学习

全部文章（共10篇）

Closest Equals

分析当我们看到区间的多次查询时，首先想到的可能就是离线了我们尝试将查询的区间右端点排序那么我们在向右移动指针时如果前边出现了这个值那么就可以将Pre[i]更改为i-Pre[i]因为我们现在还没有扩展到右边的点所以我们可以直接区间查询的最小值线段树即可因为我们需要将数值作为下标，所以需要离散化一次 ...

YJYX

2020-09-15

3 684

Present

分析由于我们需要求出最后序列最小值最大所以我们直接可以想到二分答案经验告诉我们，我们需要先考虑比较特殊的数列位置从最左边开始考虑若果当前不成立，那么我们将他加到成立为止并是以当前位置为起点的向后加1所以我们需要的是区间修改，单点查询可以的树状数组当然更可以的差分可以证明这种贪心是绝对最优的需要注意...

YJYX

2020-09-15

3 720

Telephone Lines

分析本题主要就是一个转化当我们看到数据范围，就可以大胆猜测较高复杂度的算法因为维护最大值比较麻烦我们考虑用二分答案限制最大值然后就可以顺理成章的想出将的路径长度标为1跑一个最短路如果最后的Dist[T]那么这就是一个可行的解以此二分即可求得答案代码 //P1948 #include <io...

YJYX

2020-09-12

4 660

道路和航线

分析本题给出的道路和航线其实就是单向道路和双向道路所以我们直接正常建边就可了由于题目保证了不存在环，那么就绝对没有负环情况但因为有负边，所以我们需要用SPFA所以我们直接套板子即可当然，这里我们使用SPFA的优化（slf优化或者 lll优化）（机房大佬说想要不一样就要Tarjan缩点+Dijks...

YJYX

2020-09-10

3 681

网格图

分析由于所以我们可以直接考虑较为大胆的算法直接枚举，将其暴力直接转移需要注意的就是，每次的转移方向需要判断一下当时，我们只能转移相同方向上的方案由于空间问题，我们最好使用滚动数组转移时间复杂度：代码 //Newcoder 16735 #include <iostream> #inc...

YJYX

2020-09-09

4 1051

Working out

吐槽本人感觉题目十分有坑。。。就是因为没有理解真正的题意。。。两人只能相遇一次从下边上来的人只能从上边出这个点，从左边进来的人只能从右边出这个点分析因为我们需要两个人走对角线，并且复杂度允许所以我们可以直接从4个顶点暴力DPDP[1/2/3/4][i][j]表示从某个顶点到的最大权值和...

YJYX

2020-09-08

3 633

摆渡车

前言作为NOIP-J的T3，这道题在一定程度上是会有区分度的。。。比如说这道题就有一堆解法：剪枝优化状态斜率优化DP 的神级DP 某位大佬说的算法但我这里就主要讲一下斜率优化DP吧，相信大部分都是这种做法吧分析我们考虑枚举设DP[i]表示在时回到人大附中的最少总时间Pre[i]表示及之...

YJYX

2020-09-07

4 783

Tree

分析首先，此题需要加点和查询操作我们可以想到倍增但由于对于祖先的选择有要求所以我们需要修改对于倍增数组的表示Anc[i][j]表示从点向上走个满足要求的点之后，到达的点Sum[i][j]表示从点向上走个满足要求的点得权值之和这样我们就可以查询了至于插入操作我们需要先求出此点祖先中第一个满足要求的祖...

YJYX

2020-09-07

3 600

选择客栈

分析由于我们需要求出符合要求的，但感觉比较繁琐所以我们考虑求补集，即不符合要求的发现，不符合要求，当且仅当：两个客栈位于两个的客栈之间所以，我们类似一个滑动窗口向右滑动，记录各种颜色的个数当遇到满足要求的客栈时，立马统计答案即可最后用总方案数不符合要求的方案数即可代码 //P1311 #incl...

YJYX

2020-09-07

3 934

Newcoder IOI周赛18-普及组 D 能量水晶

分析排序之后可以证明，枚举最后无法凑出的数然后统计答案一定是OK的比它值小的必须选所以可以直接暴力背包背出方案数暴力加上答案即可时间复杂度：代码 //Newcoder 18 D #include <iostream> #include <cstdio> #include ...

YJYX

2020-09-06

3 588