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 0x3f3f3f3f3f3f3f3f
inline 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 0x3f3f3f3f3f3f3f3f
inline 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 0x3f3f3f3f3f3f3f3f
inline 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 0x3f3f3f3f3f3f3f3f
inline 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 0x3f3f3f3f3f3f3f3f
inline 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;
}
