好运莲莲_

分类

未归档(1) 题解(36)

/ 注册

全部文章（共68篇）

牛客—— Protecting the Flowers （贪心）

牛客—— Protecting the Flowers （贪心）题意：农夫有n头牛在破坏花朵，每头牛每分钟破坏d[i]朵花，农夫把这头牛运回牛棚的时间为t[i]（单程）,问如何运才能使得被破坏的花最少。思路：考虑贪心。其实贪心无非几种排序关键字，某单个数值，某些数值之加减乘除。对于本题，...

2020-05-27

0 591

#关于BFS的拓展（2）——双向广搜，A*

这两种都是BFS的优化方法。双向广搜相当于从起点和终点轮流进行扩展，最后如果两边各自有一个状态发生重复的话，说明这两个搜索过程相遇了，由此可以合并出起点到终点的最小步数。一般适用于最小步数模型，即把这个状态看做无向图的一个点。再有一个小优化就是每一次扩展时选择当前队列里元素个数较少的一方来扩...

2020-05-26

0 922

关于BFS的拓展（1）——多源BFS，最小步数，双端队列

矩阵距离（多源BFS）题意：给定一个01矩阵，求每个位置到所有1的最短曼哈顿距离。思路：朴素的做法是分别以每个1为起点遍历一遍，最后保留最小值，时间复杂度O（n^2）。在图论里，如果求所有点到最近起点的最短距离，可以建立一个虚拟源点，从虚拟源点往每个起点连一条边权为0的边，这时候再求一遍最...

2020-05-26

0 1265

Codeforces Round #644 (Div. 3)（A~G）

Codeforces Round #644 (Div. 3) A. Minimal Square 题意：给定一个矩形，长宽分别是a,b。求一个最小的正方形，使得其能够包含两个这样的矩形。求出其面积。思路：假设长是a，宽是b，考虑2b和a之间的大小关系即可。因为要可以包含两个矩形，所以不难推...

2020-05-25

1 580

牛客——中位数图（思维）

[CQOI2009]中位数图（思维）思路：感觉这个题很偏向思维，原谅本蒟蒻看了题解后才想明白。首先要考虑到的就是题目中的大小关系都只是一个相对的关系，所以大于b的数对答案的贡献都是一样的，小于b的数对答案的贡献都是一样的。不妨就设大于b的数的值为1，小于b的数的值为-1，等于b的数的值为0。...

2020-05-24

1 656

牛客——简单瞎搞题（bitsit优化DP）

UP:好像01的东西都会有些奇奇怪怪的优化，比如双端队列BFS就是一个很秀的算法。https://blog.csdn.net/weixin_45675097/article/details/106265696 前言：（bitset的学习）很容易看出来是背包问题，我们用dp[i] [j] 表示只由前...

2020-05-24

0 758

牛客——比赛（DP DFS 二进制枚举）

题意：给定每个题可以解出（独立和偷听）的概率，求解出0~12题的概率。思路：首先可以算出每个题解出的概率，即1-解不出该题的概率，即 ///计算独立的每道题解出来的概率 for(int i=1;i<=12;i++){ double tmp=(1-a[i])*(1-...

2020-05-24

0 653

牛客—— 算法周周练7（EAD）

算法周周练7 （EAD） E：数字比较思路：x,y范围都是1e9，而且还是计算次方，直接计算肯定是不行的。根据高中数学知识，可以两边同时取对数，就化成了比较ylogx和xlogy的大小。代码： ///ylogx和xlogy #include<bits/stdc++.h> typede...

2020-05-23

0 739

牛客——「土」秘法地震

牛客每日一题—— 「土」秘法地震题意：问有多少个大小为k*k的矩阵的元素之和至少为1 思路：因为矩阵的大小已经固定，我们可以直接枚举一下左上角的区间端点，这样就可以根据端点和矩阵大小得到右下角的端点。这时候如果再遍历区间的话，复杂度就是O（n^4），所以我们要想办法优化一...

2020-05-22

0 548

牛客——图的遍历（dfs染色）

题意：一次走两步问最少添加几条边可以完整的遍历整张图思路：考虑环的奇偶性。如果有奇环，那么从奇环的任意点出发，一定能够走完这个环。所以如果存在某个连通块是奇环，那么就只需要把剩下的连通块都连接到该连通块上即可，所需要的添加边数就是连通块数-1；如果不存在奇环的话，先要将某个连通块变成...

2020-05-21

0 1023