月嫂网站模板关于网站建设的意义

当前位置： 首页 > news >正文

月嫂网站模板,关于网站建设的意义,博客 软件 wordpress,如何建设高校网站本文涉及的基础知识点 本博文代码打包下载 C二分查找 C图论 [蓝桥杯 2022 国 A] 环境治理 题目描述 LQ 国拥有 n n n 个城市#xff0c;从 0 0 0 到 n − 1 n - 1 n−1 编号#xff0c;这 n n n 个城市两两之间都有且仅有一条双向道路连接#xff0c;这意味着任意两…本文涉及的基础知识点 本博文代码打包下载 C二分查找 C图论 [蓝桥杯 2022 国 A] 环境治理 题目描述 LQ 国拥有 n n n 个城市从 0 0 0 到 n − 1 n - 1 n−1 编号这 n n n 个城市两两之间都有且仅有一条双向道路连接这意味着任意两个城市之间都是可达的。每条道路都有一个属性 D D D表示这条道路的灰尘度。当从一个城市 A 前往另一个城市 B 时可能存在多条路线每条路线的灰尘度定义为这条路线所经过的所有道路的灰尘度之和LQ 国的人都很讨厌灰尘所以他们总会优先选择灰尘度最小的路线。 LQ 国很看重居民的出行环境他们用一个指标 P P P 来衡量 LQ 国的出行环境 P P P 定义为 P ∑ i 0 n − 1 ∑ j 0 n − 1 d ( i , j ) P\sum \limits{i0}^{n-1} \sum \limits{j0}^{n-1} d(i,j) Pi0∑n−1​j0∑n−1​d(i,j) 其中 d ( i , j ) d(i,j) d(i,j) 表示城市 i i i 到城市 j j j 之间灰尘度最小的路线对应的灰尘度的值。 为了改善出行环境每个城市都要有所作为当某个城市进行道路改善时会将与这个城市直接相连的所有道路的灰尘度都减少 1 1 1但每条道路都有一个灰尘度的下限值 L L L当灰尘度达到道路的下限值时无论再怎么改善道路的灰尘度也不会再减小了。 具体的计划是这样的 第 1 1 1 天 0 0 0 号城市对与其直接相连的道路环境进行改善第 2 2 2 天 1 1 1 号城市对与其直接相连的道路环境进行改善 …… 第 n n n 天 n − 1 n - 1 n−1 号城市对与其直接相连的道路环境进行改善第 n 1 n 1 n1 天 0 0 0 号城市对与其直接相连的道路环境进行改善第 n 2 n 2 n2 天 1 1 1 号城市对与其直接相连的道路环境进行改善 …… LQ 国想要使得 P P P 指标满足 P ≤ Q P \leq Q P≤Q。请问最少要经过多少天之后 P P P 指标可以满足 P ≤ Q P \leq Q P≤Q。如果在初始时就已经满足条件则输出 0 0 0如果永远不可能满足则输出 − 1 -1 −1。 输入格式 输入的第一行包含两个整数 n , Q n, Q n,Q用一个空格分隔分别表示城市个数和期望达到的 P P P 指标。 接下来 n n n 行每行包含 n n n 个整数相邻两个整数之间用一个空格分隔其中第 i i i 行第 j j j 列的值 D i , j ( D i , j D j , i , D i , i 0 ) D{i,j} (D{i,j}D{j,i},D{i,i} 0) Di,j​(Di,j​Dj,i​,Di,i​0) 表示城市 i i i 与城市 j j j 之间直接相连的那条道路的灰尘度。 接下来 n n n 行每行包含 n n n 个整数相邻两个整数之间用一个空格分隔其中第 i i i 行第 j j j 列的值 L i , j ( L i , j L j , i , L i , i 0 ) L{i,j} (L{i,j} L{j,i}, L{i,i} 0) Li,j​(Li,j​Lj,i​,Li,i​0) 表示城市 i i i 与城市 j j j 之间直接相连的那条道路的灰尘度的下限值。 输出格式 输出一行包含一个整数表示答案。 样例 #1 样例输入 #1 3 10 0 2 4 2 0 1 4 1 0 0 2 2 2 0 0 2 0 0样例输出 #1 2提示 【样例说明】 初始时的图如下所示每条边上的数字表示这条道路的灰尘度 此时每对顶点之间的灰尘度最小的路线对应的灰尘度为 d ( 0 , 0 ) 0 , d ( 0 , 1 ) 2 , d ( 0 , 2 ) 3 d(0, 0) 0, d(0, 1) 2, d(0, 2) 3 d(0,0)0,d(0,1)2,d(0,2)3 d ( 1 , 0 ) 2 , d ( 1 , 1 ) 0 , d ( 1 , 2 ) 1 d(1, 0) 2, d(1, 1) 0, d(1, 2) 1 d(1,0)2,d(1,1)0,d(1,2)1 d ( 2 , 0 ) 3 , d ( 2 , 1 ) 1 , d ( 2 , 2 ) 0 d(2, 0) 3, d(2, 1) 1, d(2, 2) 0 d(2,0)3,d(2,1)1,d(2,2)0。 初始时的 P P P 指标为 ( 2 3 1 ) × 2 12 (2 3 1) \times 2 12 (231)×212不满足 P ≤ Q 10 P \leq Q 10 P≤Q10; 第一天 0 0 0 号城市进行道路改善改善后的图示如下 注意到边 ( 0 , 2 ) (0, 2) (0,2) 的值减小了 1 1 1但 ( 0 , 1 ) (0, 1) (0,1) 并没有减小因为 L 0 , 1 2 L{0,1} 2 L0,1​2 所以 ( 0 , 1 ) (0, 1) (0,1) 的值不可以再减小了。此时每对顶点之间的灰尘度最小的路线对应的灰尘度为 d ( 0 , 0 ) 0 , d ( 0 , 1 ) 2 , d ( 0 , 2 ) 3 d(0, 0) 0, d(0, 1) 2, d(0, 2) 3 d(0,0)0,d(0,1)2,d(0,2)3 d ( 1 , 0 ) 2 , d ( 1 , 1 ) 0 , d ( 1 , 2 ) 1 d(1, 0) 2, d(1, 1) 0, d(1, 2) 1 d(1,0)2,d(1,1)0,d(1,2)1 d ( 2 , 0 ) 3 , d ( 2 , 1 ) 1 , d ( 2 , 2 ) 0 d(2, 0) 3, d(2, 1) 1, d(2, 2) 0 d(2,0)3,d(2,1)1,d(2,2)0。 此时 P P P 仍为 12 12 12。 第二天1 号城市进行道路改善改善后的图示如下 此时每对顶点之间的灰尘度最小的路线对应的灰尘度为 d ( 0 , 0 ) 0 , d ( 0 , 1 ) 2 , d ( 0 , 2 ) 2 d(0, 0) 0, d(0, 1) 2, d(0, 2) 2 d(0,0)0,d(0,1)2,d(0,2)2 d ( 1 , 0 ) 2 , d ( 1 , 1 ) 0 , d ( 1 , 2 ) 0 d(1, 0) 2, d(1, 1) 0, d(1, 2) 0 d(1,0)2,d(1,1)0,d(1,2)0 d ( 2 , 0 ) 2 , d ( 2 , 1 ) 0 , d ( 2 , 2 ) 0 d(2, 0) 2, d(2, 1) 0, d(2, 2) 0 d(2,0)2,d(2,1)0,d(2,2)0。 此时的 P P P 指标为 ( 2 2 ) × 2 8 Q (2 2) \times 2 8 Q (22)×28Q此时已经满足条件。 所以答案是 2 2 2。 【评测用例规模与约定】 对于 30 % 30\% 30% 的评测用例 1 ≤ n ≤ 10 1 \leq n \leq 10 1≤n≤10 0 ≤ L i , j ≤ D i , j ≤ 10 0 \leq L{i,j} \leq D{i,j} \leq 10 0≤Li,j​≤Di,j​≤10对于 60 % 60\% 60% 的评测用例 1 ≤ n ≤ 50 1 \leq n \leq 50 1≤n≤50 0 ≤ L i , j ≤ D i , j ≤ 1 0 5 0 \leq L{i,j} \leq D{i,j} \leq 10^5 0≤Li,j​≤Di,j​≤105对于所有评测用例 1 ≤ n ≤ 100 1 \leq n \leq 100 1≤n≤100 0 ≤ L i , j ≤ D i , j ≤ 1 0 5 0 \leq L{i,j} \leq D_{i,j} \leq 10^5 0≤Li,j​≤Di,j​≤105 0 ≤ Q ≤ 2 31 − 1 0 \leq Q \leq 2^{31} - 1 0≤Q≤231−1。 蓝桥杯 2022 国赛 A 组 F 题。 二分查找多源最短路 Check(mid)多源最短路计算最短路(int)再计算其和sum(long long)。返回sum Q。 二分类型寻找首端。 参数返回[0,107] 如果Check(ans)不成立返回-1。 cur[i][j]记录mid后城市i到城市j之间的灰尘度。 max(mat[i][j]-mid/N2-(imid%N)-(jmid%N),L[i][j]) 代码 核心代码 #include iostream #include sstream #include vector #includemap #includeunordered_map #includeset #includeunordered_set #includestring #includealgorithm #includefunctional #includequeue #include stack #includeiomanip #includenumeric #include math.h #include climits #includeassert.h #includecstring#include bitset using namespace std;templateclass T int vectorT Read(int n,const char pFormat %d) {vectorT ret(n);for(int i0;in;i) {scanf(pFormat, ret[i]); }return ret; }templateclass T int vectorT Read( const char* pFormat %d) {int n;scanf(%d, n);vectorT ret;T d;while (n–) {scanf(pFormat, d);ret.emplace_back(d);}return ret; }string ReadChar(int n) {string str;char ch;while (n–) {do{scanf(%c, ch);} while ((\n ch));str ch;}return str; } templateclass T1,class T2 void ReadTo(pairT1, T2 pr) {cin pr.first pr.second; }templateclass T int class CFloyd { public:CFloyd(int n, const T INF 1000 * 1000 * 1000) :m_INF(INF){m_vMat.assign(n, vectorT(n, m_INF));for (int i 0; i n; i) {m_vMat[i][i] 0;}}void SetEdge(int i1, int i2, const T dis, bool bDirect false){m_vMat[i1][i2] min(m_vMat[i1][i2], dis);if (!bDirect) {m_vMat[i2][i1] m_vMat[i1][i2];}}vectorvectorT Dis(){auto vResMat m_vMat;const int n m_vMat.size();for (int i 0; i n; i){//通过i中转for (int i1 0; i1 n; i1){if (m_INF vResMat[i1][i]){continue;}for (int i2 0; i2 n; i2){//此时m_vMat[i1][i2] 表示通过[0,i)中转的最短距离vResMat[i1][i2] min(vResMat[i1][i2], vResMat[i1][i] vResMat[i][i2]);//m_vMat[i1][i2] 表示通过[0,i]中转的最短距离}}}return vResMat;};vectorvectorT m_vMat;//结果串const T m_INF; };templateclass INDEX_TYPE class CBinarySearch { public:CBinarySearch(INDEX_TYPE iMinIndex, INDEX_TYPE iMaxIndex) :m_iMin(iMinIndex), m_iMax(iMaxIndex) {}templateclass _PrINDEX_TYPE FindFrist(_Pr pr){auto left m_iMin - 1;auto rightInclue m_iMax;while (rightInclue - left 1){const auto mid left (rightInclue - left) / 2;if (pr(mid)){rightInclue mid;}else{left mid;}}return rightInclue;}templateclass _PrINDEX_TYPE FindEnd(_Pr pr){INDEX_TYPE leftInclude m_iMin;INDEX_TYPE right m_iMax 1;while (right - leftInclude 1){const auto mid leftInclude (right - leftInclude) / 2;if (pr(mid)){leftInclude mid;}else{right mid;}}return leftInclude;} protected:const INDEX_TYPE m_iMin, m_iMax; };class Solution { public:int Ans(vectorvectorint mat, vectorvectorint L, int Q) {const int N mat.size();auto Check {auto cur L;for (int i 0; i N; i)for (int j 0; j N; j) {cur[i][j] max(cur[i][j], mat[i][j] - mid / N * 2 - (i mid% N) - (j mid% N));}CFloydint floyd(N);floyd.m_vMat.swap(cur);auto res floyd.Dis();long long ans 0;for (const auto v : res) {ans accumulate(v.begin(), v.end(), 0);}return ans Q;};auto ans CBinarySearchint(0, 1e7).FindFrist(Check);return Check(ans) ? ans : -1;}};int main() { #ifdef _DEBUGfreopen(a.in, r, stdin); #endif // DEBUGint N,Q; cin N Q;vector vectorint mat(N), L(N);for (int i 0; i N; i) {mat[i] Readint(N);}for (int i 0; i N; i) {L[i] Readint(N);}auto res Solution().Ans(mat, L, Q);cout res std::endl; #ifdef _DEBUG Out(mat, mat);Out(L, L);printf(,Q%d;, Q); #endif return 0; }单元测试 vectorvectorint mat, L;int Q;TEST_METHOD(TestMethod11){mat { {0,2,4},{2,0,1},{4,1,0} }, L { {0,2,2},{2,0,0},{2,0,0} }, Q 10;auto res Solution().Ans(mat, L, Q);AssertEx(2, res);}扩展阅读 我想对大家说的话工作中遇到的问题可以按类别查阅鄙人的算法文章请点击《算法与数据汇总》。学习算法按章节学习《喜缺全书算法册》大量的题目和测试用例打包下载。重视操作有效学习明确的目标 及时的反馈 拉伸区难度合适 专注闻缺陷则喜(喜缺)是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛失败反思成功 成功反思成功 视频课程 先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。 https://edu.csdn.net/course/detail/38771 如何你想快速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程 https://edu.csdn.net/lecturer/6176 测试环境 操作系统win7 开发环境 VS2019 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用C实现。