2.22学习总结

2024-02-23 03:04
文章标签 学习 总结 2.22

本文主要是介绍2.22学习总结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.营救
2.租用游艇
3.砍树
4.买礼物
5.刷题统计

砍树https://www.dotcpp.com/oj/problem3157.html

题目描述

给定一棵由 n 个结点组成的树以及 m 个不重复的无序数对 (a1, b1), (a2, b2),

. . . , (am, bm)，其中 ai 互不相同，bi 互不相同，ai ≠ bj(1 ≤ i, j ≤ m)。

小明想知道是否能够选择一条树上的边砍断，使得对于每个 (ai , bi) 满足 ai和 bi 不连通，如果可以则输出应该断掉的边的编号（编号按输入顺序从 1 开始），否则输出 -1.

输入格式

输入共 n + m 行，第一行为两个正整数 n，m。

后面 n − 1 行，每行两个正整数 xi，yi 表示第 i 条边的两个端点。

后面 m 行，每行两个正整数 ai，bi。

输出格式

一行一个整数，表示答案，如有多个答案，输出编号最大的一个。

样例输入

复制

6 2
1 2
2 3
4 3
2 5
6 5
3 6
4 5
4

样例输出

复制

4

提示

断开第 2 条边后形成两个连通块：{3, 4}，{1, 2, 5, 6}，满足 3 和 6 不连通，4 和 5 不连通。

断开第 4 条边后形成两个连通块：{1, 2, 3, 4}，{5, 6}，同样满足 3 和 6 不连通，4 和 5 不连通。

4 编号更大，因此答案为 4。

对于 30% 的数据，保证 1 < n ≤ 1000。

对于 100% 的数据，保证 1 < n ≤ 105，1 ≤ m ≤ 2/n。

思路：树上差分，树上差分需要结合LCA和差分的知识。

树上差分主要是应用于，在树上对多条路径进行加和的操作，其实现形式主要有点差分和边差分，边差分最后也会转化为点差分去看。

这个是LCA

void dfs(int u,int fa){dep[u]=dep[fa]+1;f[u][0]=fa;for (int i=1;(1<<i)<=dep[n] ;++i){f[u][i]=f[f[u][i-1]][i-1];}for (int i=0; i<e[u].size() ; ++ i){edge v=e[u][i];if (v.to == fa) continue;dfs(v.to,u);id[v.to] = e[u][i].id;}
}int lca(int x ,int y){if (dep[x] < dep[y]) swap(x,y);while (dep[x] > dep[y]){x=f[x][__lg(dep[x]-dep[y]-1)];}if (x==y) return x;for (int i=1;i<=20 ; ++ i){if (f[x][i] != f[y][i]){x=f[x][i];y=f[y][i];}}return f[x][0];
}

下面是实现树上差分的函数

void add(int x, int y){s[x]++;s[y]++;s[lca(x,y)]-=2;
}void cal_sum(int u,int fa){for (int i=0 ;i<e[u].size(); ++ i){edge y=e[u][i];if (y.to == fa) continue;cal_sum(y.to,u);s[u]+=s[y.to];}
}

点差分和变差分的区别主要在于：add函数

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) x&(-x)
#define int long long
#define INF 0x3f3f3f3f3f3f3f3finline int read()
{int x=0,f=1;char ch=getchar();while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}return x*f;
} const int N=1e5+5;struct edge{int id;int to;
};vector<edge>e[N];int n,m,f[N][25],dep[N],id[N],s[N],ans;void dfs(int u,int fa){dep[u]=dep[fa]+1;f[u][0]=fa;for (int i=1;(1<<i)<=dep[n] ;++i){f[u][i]=f[f[u][i-1]][i-1];}for (int i=0; i<e[u].size() ; ++ i){edge v=e[u][i];if (v.to == fa) continue;dfs(v.to,u);id[v.to] = e[u][i].id;}
}int lca(int x ,int y){if (dep[x] < dep[y]) swap(x,y);while (dep[x] > dep[y]){x=f[x][__lg(dep[x]-dep[y]-1)];}if (x==y) return x;for (int i=1;i<=20 ; ++ i){if (f[x][i] != f[y][i]){x=f[x][i];y=f[y][i];}}return f[x][0];
}void add(int x, int y){s[x]++;s[y]++;s[lca(x,y)]-=2;
}void cal_sum(int u,int fa){for (int i=0 ;i<e[u].size(); ++ i){edge y=e[u][i];if (y.to == fa) continue;cal_sum(y.to,u);s[u]+=s[y.to];}
}signed main(){n=read(),m=read();for (int i=1; i<n ; ++ i ){int u=read(),v=read();e[u].push_back({i,v});e[v].push_back({i,u});}dfs(1,0);for (int i=1 ;i<=m ; ++ i){int l=read(),r=read();add(l,r);}cal_sum(1,0);for (int i =1; i<=n ; ++i ){if (s[i]==m && id[i] >ans ) ans=id[i];}cout<<ans;
}

营救https://www.luogu.com.cn/problem/P1396

题目背景

“咚咚咚……”“查水表！”原来是查水表来了，现在哪里找这么热心上门的查表员啊！小明感动得热泪盈眶，开起了门……

题目描述

妈妈下班回家，街坊邻居说小明被一群陌生人强行押上了警车！妈妈丰富的经验告诉她小明被带到了 �t 区，而自己在 �s 区。

该市有 �m 条大道连接 �n 个区，一条大道将两个区相连接，每个大道有一个拥挤度。小明的妈妈虽然很着急，但是不愿意拥挤的人潮冲乱了她优雅的步伐。所以请你帮她规划一条从 �s 至 �t 的路线，使得经过道路的拥挤度最大值最小。

输入格式

第一行有四个用空格隔开的 �n，�m，�s，�t，其含义见【题目描述】。

接下来 �m 行，每行三个整数 �,�,�u,v,w，表示有一条大道连接区 �u 和区 �v，且拥挤度为 �w。

两个区之间可能存在多条大道。

输出格式

输出一行一个整数，代表最大的拥挤度。

输入输出样例

输入 #1复制

3 3 1 3
1 2 2
2 3 1
1 3 3

输出 #1复制

2

说明/提示

数据规模与约定

  • 对于 30%30% 的数据，保证 �≤10n≤10。

  • 对于 60%60% 的数据，保证 �≤100n≤100。

  • 对于 100%100% 的数据，保证 1≤�≤1041≤n≤104，1≤�≤2×1041≤m≤2×104，�≤104w≤104，1≤�,�≤�1≤s,t≤n。且从 �s 出发一定能到达 �t 区。

样例输入输出 1 解释

小明的妈妈要从 11 号点去 33 号点，最优路线为 11->22->33。

思路：kruskal

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) x&(-x)
#define int long long
#define INF 0x3f3f3f3f3f3f3f3finline int read()
{int x=0,f=1;char ch=getchar();while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}return x*f;
} const int N=5e5+5;
struct edge{int from;int to;int w;
}e[N];bool cmp(const edge& a,const edge& b){return a.w<b.w;
}int f[N],n,m,s,t;int find (int x){return f[x] == x? f[x]:f[x]=find(f[x]);
}void unionn(int i,int j){f[find(i)]=find(j);
}signed main(){n=read(),m=read(),s=read(),t=read();for (int i=1;i<=n; ++ i) f[i]=i;int manx=0;for (int i = 1 ;i <= m ; ++ i){e[i].from=read(), e[i].to=read(), e[i].w=read();}  sort(e+1,e+1+m,cmp);for (int i=1 ; i <= m ; ++ i){if (find(e[i].from)!= find(e[i].to)){unionn(e[i].from,e[i].to);}if (find(s) == find(t)){cout<<e[i].w;return 0;}}
}

租用游艇https://www.luogu.com.cn/problem/P1359

题目描述

长江游艇俱乐部在长江上设置了 �n 个游艇出租站 1,2,⋯ ,�1,2,⋯,n。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站 �i 到游艇出租站 �j 之间的租金为 �(�,�)r(i,j)（1≤�<�≤�1≤i<j≤n）。试设计一个算法，计算出从游艇出租站 11 到游艇出租站 �n 所需的最少租金。

输入格式

第一行中有一个正整数 �n，表示有 �n 个游艇出租站。接下来的 �−1n−1 行是一个半矩阵 �(�,�)r(i,j)（1≤�<�≤�1≤i<j≤n）。

输出格式

输出计算出的从游艇出租站 11 到游艇出租站 �n 所需的最少租金。

输入输出样例

输入 #1复制

3
5 15
7

输出 #1复制

12

说明/提示

�≤200n≤200，保证计算过程中任何时刻数值都不超过 106106。

思路：DP

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) x&(-x)
#define int long long
#define INF 0x3f3f3f3f3f3f3f3finline int read()
{int x=0,f=1;char ch=getchar();while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}return x*f;
} const int N=5e5+5;int f[N],n;signed main(){n=read();for (int i=1;i<=n;i++)for (int j=i+1;j<=n;j++){int x=read();if (f[j]==0||f[j]>f[i]+x) f[j]=f[i]+x; }cout<<f[n];
}

买礼物https://www.luogu.com.cn/problem/P1194

题目描述

又到了一年一度的明明生日了，明明想要买 �B 样东西，巧的是，这 �B 样东西价格都是 �A 元。

但是，商店老板说最近有促销活动，也就是：

如果你买了第 �I 样东西，再买第 �J 样，那么就可以只花 ��,�KI,J​ 元，更巧的是，��,�KI,J​ 竟然等于 ��,�KJ,I​。

现在明明想知道，他最少要花多少钱。

输入格式

第一行两个整数，�,�A,B。

接下来 �B 行，每行 �B 个数，第 �I 行第 �J 个为 ��,�KI,J​。

我们保证 ��,�=��,�KI,J​=KJ,I​ 并且 ��,�=0KI,I​=0。

特别的，如果 ��,�=0KI,J​=0，那么表示这两样东西之间不会导致优惠。

注意 ��,�KI,J​ 可能大于 �A。

输出格式

一个整数，为最小要花的钱数。

输入输出样例

输入 #1复制

1 1
0

输出 #1复制

1

输入 #2复制

3 3
0 2 4
2 0 2
4 2 0

输出 #2复制

7

说明/提示

样例解释 22。

先买第 22 样东西，花费 33 元，接下来因为优惠，买 1,31,3 样都只要 22 元，共 77 元。

（同时满足多个“优惠”的时候，聪明的明明当然不会选择用 44 元买剩下那件，而选择用 22 元。）

数据规模

对于 30%30% 的数据，1≤�≤101≤B≤10。

对于 100%100% 的数据，1≤�≤500,0≤�,��,�≤10001≤B≤500,0≤A,KI,J​≤1000。

思路：kruskal

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) x&(-x)
#define int long long
#define INF 0x3f3f3f3f3f3f3f3finline int read()
{int x=0,f=1;char ch=getchar();while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}return x*f;
} const int N=1e5+5;struct edge{int from;int to;int w;
}e[250008];bool cmp(const edge& a,const edge& b){return a.w<b.w;
}int a,b,tot,f[10000];int find(int x){return f[x]==x?x:f[x]=find(f[x]);
}void unionn(int i,int j){f[find(i)]=find(j);
}signed main(){a=read(),b=read();
//	for (int i=1; i<=b; ++ i){
//		e[++tot].from=0;
//		e[tot].to=i;
//		e[tot].w=a;
//	}for (int i=1; i<=b; ++ i){for (int j=1; j<=b; ++ j){int m=read();if (m!=0){e[++tot].from=i;e[tot].to=j;e[tot].w=m;}}}sort(e+1,e+1+tot,cmp);int sum=0,cnt=0;for (int i=1;i<=b; ++i){f[i]=i;}for (int i=1; i<=tot; ++i){if (find(e[i].from) != find(e[i].to)){unionn(e[i].from,e[i].to);sum+=e[i].w;cnt++;}if (cnt==b-1) break;}if (b==1) cout<<a;else cout<<sum+a;
}
刷题统计https://www.dotcpp.com/oj/problem2656.html?sid=15387892&lang=1#editor

问题描述

小明决定从下周一开始努力刷题准备蓝桥杯竞赛。他计划周一至周五每天做a道题目，周六和周日每天做b道题目。请你帮小明计算，按照他将在第1道的计划几天实现做题数大于等于n的题？

输入格式

输入一行包含三个整数a、b和n。

输出格式

输出一个整数代表天数。

样例输入

复制

10 20 99

样例输出

复制

8

提示

对于 50% 的影片例子，1 ≤ a, b, n ≤ 10 6。对于 100% 的影片例子，1 ≤ a, b, n ≤ 10 18 .

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) x&(-x)
#define int long long
#define INF 0x3f3f3f3f3f3f3f3finline int read()
{int x=0,f=1;char ch=getchar();while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}return x*f;
} signed main(){int a=read(),b=read(),c=read();int w=a*5+b*2;int t=c/w,tt=c%w,day=0; day=t*7;if (tt > a*5){tt-=a*5;day+=5;if (tt % b ==0) day+=tt/b;else day+=tt/b+1;}else if (tt <= a*5){if (tt % a ==0) day+=tt/a;else day+=tt/a+1;}cout<<day;
}

这篇关于2.22学习总结的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/737313。

相关文章

Qt实现网络数据解析的方法总结

Qt实现网络数据解析的方法总结

《Qt实现网络数据解析的方法总结》在Qt中解析网络数据通常涉及接收原始字节流,并将其转换为有意义的应用层数据,这篇文章为大家介绍了详细步骤和示例,感兴趣的小伙伴可以了解下... 目录1. 网络数据接收2. 缓冲区管理（处理粘包/拆包）3. 常见数据格式解析3.1 jsON解析3.2 XML解析3.3 自定义
阅读更多...
Java学习手册之Filter和Listener使用方法

Java学习手册之Filter和Listener使用方法

《Java学习手册之Filter和Listener使用方法》：本文主要介绍Java学习手册之Filter和Listener使用方法的相关资料,Filter是一种拦截器,可以在请求到达Servl... 目录一、Filter（过滤器）1. Filter 的工作原理2. Filter 的配置与使用二、Listen
阅读更多...
Python实现图片分割的多种方法总结

Python实现图片分割的多种方法总结

《Python实现图片分割的多种方法总结》图片分割是图像处理中的一个重要任务,它的目标是将图像划分为多个区域或者对象,本文为大家整理了一些常用的分割方法,大家可以根据需求自行选择... 目录1. 基于传统图像处理的分割方法(1) 使用固定阈值分割图片(2) 自适应阈值分割(3) 使用图像边缘检测分割(4)
阅读更多...
Windows Docker端口占用错误及解决方案总结

Windows Docker端口占用错误及解决方案总结

《WindowsDocker端口占用错误及解决方案总结》在Windows环境下使用Docker容器时,端口占用错误是开发和运维中常见且棘手的问题,本文将深入剖析该问题的成因,介绍如何通过查看端口分配... 目录引言Windows docker 端口占用错误及解决方案汇总端口冲突形成原因解析诊断当前端口情况解
阅读更多...
java常见报错及解决方案总结

java常见报错及解决方案总结

《java常见报错及解决方案总结》：本文主要介绍Java编程中常见错误类型及示例,包括语法错误、空指针异常、数组下标越界、类型转换异常、文件未找到异常、除以零异常、非法线程操作异常、方法未定义异常... 目录1. 语法错误 (Syntax Errors)示例 1:解决方案：2. 空指针异常 (NullPoi
阅读更多...
Java反转字符串的五种方法总结

Java反转字符串的五种方法总结

《Java反转字符串的五种方法总结》：本文主要介绍五种在Java中反转字符串的方法,包括使用StringBuilder的reverse()方法、字符数组、自定义StringBuilder方法、直接... 目录前言方法一：使用StringBuilder的reverse()方法方法二：使用字符数组方法三：使用自
阅读更多...
Java进阶学习之如何开启远程调式

Java进阶学习之如何开启远程调式

《Java进阶学习之如何开启远程调式》Java开发中的远程调试是一项至关重要的技能,特别是在处理生产环境的问题或者协作开发时,：本文主要介绍Java进阶学习之如何开启远程调式的相关资料,需要的朋友... 目录概述Java远程调试的开启与底层原理开启Java远程调试底层原理JVM参数总结&nbsMbKKXJx
阅读更多...
Python依赖库的几种离线安装方法总结

Python依赖库的几种离线安装方法总结

《Python依赖库的几种离线安装方法总结》：本文主要介绍如何在Python中使用pip工具进行依赖库的安装和管理,包括如何导出和导入依赖包列表、如何下载和安装单个或多个库包及其依赖,以及如何指定... 目录前言一、如何copy一个python环境二、如何下载一个包及其依赖并安装三、如何导出requirem
阅读更多...
Rust格式化输出方式总结

Rust格式化输出方式总结

《Rust格式化输出方式总结》Rust提供了强大的格式化输出功能,通过std::fmt模块和相关的宏来实现,主要的输出宏包括println!和format!,它们支持多种格式化占位符,如{}、{:?}... 目录Rust格式化输出方式基本的格式化输出格式化占位符Format 特性总结Rust格式化输出方式
阅读更多...
Java深度学习库DJL实现Python的NumPy方式

Java深度学习库DJL实现Python的NumPy方式

《Java深度学习库DJL实现Python的NumPy方式》本文介绍了DJL库的背景和基本功能,包括NDArray的创建、数学运算、数据获取和设置等,同时,还展示了如何使用NDArray进行数据预处理... 目录1 NDArray 的背景介绍1.1 架构2 JavaDJL使用2.1 安装DJL2.2 基本操
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2