熠丶

题解

未归档(32)

/ 注册

做想做的事，见想见的人

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

[SCOI2009]游戏来自专栏

思路：dp+思维样例解释： <=10的素数都有 2,3,5,7所以可选的数为 2 3 5 7 4 9 8 选0个数（不选，即为原数列）方案数为1选1个数方案数为7选2个数所有方案为：（2,3）（2,5）（2,7）（4,3）（4,5）（3,5...

2020-09-18

1 1304

联合权值来自专栏

做法：DFS,树的深度优先遍历思路：距离为2的点对有两种：1.自己的儿子们之间2.自己的父亲和自己的儿子们对树进行一遍dfs后得出max和sum因为是求有序点对（dfs是从上到下，然而有序对也可以是从下往上），所以结果需要*2 代码 #include <bits/stdc++.h>...

2020-09-18

1 735

Present 来自专栏

做法：二分+差分思路：最小值最大化-->二分然后利用差分来进行二分操作，具体见check函数代码代码 #include <bits/stdc++.h> using namespace std; #define pb push_back #define mp(aa,bb) ma...

2020-09-17

1 677

Closest Equals 来自专栏

做法：RMQ+二分思路： 1.我们将相同的数作为一个区间存下来，将两个的坐标分别作为区间的左右端点。再把两个端点的差放在一个数组中，然后题目可以转化为数组区间找最小值。由此可以想到RMQst表2.因为存的左右端点是有序的，在每次询问时，我们可以二分查找，找到可以得出答案的范围。代码 #inclu...

2020-09-17

1 645

The XOR-longest Path(最长异或路径) 来自专栏

由题意可知这是一道经典的字典树模板将数的二进制表示看做一个字符串，就可以建出字符集为{0,1}的 trie 树。思路： 1.邻接表建树（链式前向星也行）2.先dfs求出每个点到root的异或值，记为a[i],则有u到v的异或值等于a[u]^a[v]3.u到root的路径与v到root的路径会有重叠...

2020-09-16

1 824

Telephone Lines 来自专栏

题意：求原点1到n的所有路中的第k+1长的路最小做法：邻接表优化的dijkstra+二分思路： 1.先找到二分所需要的边界条件l,r2.对于长度小于二分出的答案的线段，因为不需要付价钱，所以可以将其权值看作是0;同理，大于二分的值的路径，我们将长度看作1(意味着我需要使用1次免费的资格)3.跑d...

2020-09-12

2 701

道路和航线来自专栏

做法：SPFA+SLF 思路：出现了负权边,那么我们可以使用SPFA做法然后套用SPFA的板子，结果就t了最后2个点wwwhttps://ac.nowcoder.com/acm/contest/view-submission?submissionId=44977509&returnHome...

2020-09-11

0 633

Working out 来自专栏

思路：先设dp1,dp2,dp3,dp4[i][j]分别是从矩阵的四个顶点（以左上为起点顺时针，记为A,B,C,D）走到(i,j)的点数之和枚举两人可能相遇的点，求ans的最大值相遇点走法有两种可能性： 1：A->C可能是经过该点上方后走到该点下方，B->D是左到右 2：A-&g...

2020-09-08

0 549

选择客栈来自专栏

时间复杂度：思路： sum即统计pospos之前的颜色相同的旅店的个数pre是上一个颜色相同的旅店的位置cnt是该颜色旅店的总数我们可以维护一个pos(在i个旅店之前的最近的满足最低消费小于p的旅店) 那么我们统计一下在pos之前的颜色相同的旅店的个数加进答案 #include <bits...

2020-09-08

0 669

摆渡车来自专栏

做法：记忆化搜索思路： 1.小于等于当前时间点的人都要上车 2.当前时间没人就跳到下一个有人的时间点 3.考虑是不是要等待下一个人来再开车 #include <bits/stdc++.h> using namespace std; #define pb push_back #def...

2020-09-07

4 890