1 

题目描述

给出每个节点的两个儿子节点，建立一棵二叉树（根节点为 11），如果是叶子节点，则输入0 0。建好树后希望知道这棵二叉树的深度。二叉树的深度是指从根节点到叶子结点时，最多经过了几层。

最多有 10^6106 个结点。

输入格式

无

输出格式

无

输入输出样例

输入 #1复制

7
2 7
3 6
4 5
0 0
0 0
0 0
0 0

输出 #1复制

4

还剩一个测试点过不了emmm，我目前的代码暂时ac了80.目前还没找到问题在哪。

#include<bits/stdc++.h>
using namespace std;
int n;
struct Tree
{int root;int deep;struct Tree * left;struct Tree * right;
}T[1000000];
struct Tree * Creat(int n)
{struct Tree * head;for(int i=1;i<=n;i++){int a,b;cin>>a>>b;if(i == 1){head=&T[i];//因为T【】是个结构体数组元素，而不是指针，所以不能直接head=T【】，而应该head=&T【】if(a==0&&b==0)//特判一手空树{T[i].deep=0;T[i].left=NULL;T[i].right=NULL;return head;}T[i].deep=1;}if(a==0)T[i].left=NULL;else{T[i].left=&T[a];//加&的原因同上T[a].deep=T[i].deep+1;}if(b==0)T[i].right=NULL;else{T[i].right=&T[b];//加&的原因同上T[b].deep=T[i].deep+1;}}return head;
}
int main()
{cin>>n;//初始化for(int i=1;i<=n;i++){T[i].root=i;}struct Tree * head;//创建根结点，便于使各个结点练起来head=Creat(n);//建树int m=T[1].deep;for(int i=1;i<=n;i++){if(T[i].deep>m)m=T[i].deep;}cout<<m;return 0;
}

后来用了dfs的方法，原来我一开始理解的题意是对的，然后想着想着又理解错了，然后又回到正道来了，害。

ac代码：

#include<bits/stdc++.h>
using namespace std;
int n,ans;
struct Tree
{struct Tree * left;struct Tree * right;
} T[100000];
void dfs(struct Tree * x,int deep)//当前结点和深度
{ans=max(ans,deep);if(x->left!=NULL)dfs(x->left,deep+1);if(x->right!=NULL)dfs(x->right,deep+1);
}
int main()
{cin>>n;for(int i=1; i<=n; i++){int a,b;cin>>a>>b;if(a!=0)T[i].left=&T[a];elseT[i].left=NULL;if(b!=0)T[i].right=&T[b];elseT[i].right=NULL;}dfs(&T[1],1);//根结点深度为1cout<<ans;return 0;
}

后来在原来ac80的代码的基础上进行了修改，也过了，就是发现自己其实把问题复杂化了。

#include<bits/stdc++.h>
using namespace std;
int n;
struct Tree
{struct Tree * left;struct Tree * right;int deep;
} T[1000000];
struct Tree * Creat(int n)
{struct Tree * head;for(int i=1; i<=n; i++){int a,b;cin>>a>>b;if(i == 1){head=&T[i];//因为T【】是个结构体数组元素，而不是指针，所以不能直接head=T【】，而应该head=&T【】if(a==0&&b==0)//特判一手空树{T[i].deep=0;T[i].left=NULL;T[i].right=NULL;return head;}T[i].deep=1;}if(a==0)T[i].left=NULL;elseT[i].left=&T[a];//加&的原因同上if(b==0)T[i].right=NULL;elseT[i].right=&T[b];//加&的原因同上}return head;
}
void dfs(struct Tree * x,int s)
{if(x->left!=NULL){x->left->deep=s+1;dfs(x->left,s+1);}if(x->right!=NULL){x->right->deep=s+1;dfs(x->right,s+1);}}
int main()
{cin>>n;struct Tree * head;//创建根结点，便于使各个结点练起来head=Creat(n);//建树dfs(head,1);int m=T[1].deep;for(int i=1; i<=n; i++){if(T[i].deep>m)m=T[i].deep;}cout<<m;return 0;
}

2

题目描述

明天就是母亲节了，电脑组的小朋友们在忙碌的课业之余挖空心思想着该送什么礼物来表达自己的心意呢？听说在某个网站上有卖云朵的，小朋友们决定一同前往去看看这种神奇的商品，这个店里有 nn 朵云，云朵已经被老板编号为 1,2,3,...,n1,2,3,...,n，并且每朵云都有一个价值，但是商店的老板是个很奇怪的人，他会告诉你一些云朵要搭配起来买才卖，也就是说买一朵云则与这朵云有搭配的云都要买，电脑组的你觉得这礼物实在是太新奇了，但是你的钱是有限的，所以你肯定是想用现有的钱买到尽量多价值的云。

输入格式

第一行输入三个整数，n,m,wn,m,w，表示有 nn 朵云，mm 个搭配和你现有的钱的数目。

第二行至 n+1n+1 行，每行有两个整数， c_i,d_ici​,di​，表示第 ii 朵云的价钱和价值。

第 n+2n+2 至 n+1+mn+1+m 行 ，每行有两个整数 u_i,v_iui​,vi​。表示买第 u_iui​ 朵云就必须买第 v_ivi​ 朵云,同理，如果买第 v_ivi​ 朵就必须买第 u_iui​ 朵。

输出格式

一行，表示可以获得的最大价值。

输入输出样例

输入 #1复制

5 3 10
3 10
3 10
3 10
5 100
10 1
1 3
3 2
4 2

输出 #1复制

1

说明/提示

• 对于 30\%30% 的数据，满足 1≤n≤100；
• 对于 50\%50% 的数据，满足  1≤n,w≤10^3，1≤m≤100；
• 对于 100\%100% 的数据，满足 1≤n≤10^4，0≤m≤5×10^3。

很容易看出来就是并查集加0/1背包。

一个集合算一个物品，目前拥有的钱为 背包总容量，其中该集合的总价格为背包质量，该集合的总价值为物品价值。

因为一开始用的是二维dp数组（一维的滚动数组还不太理解所以不怎么用），时间超限了ac60，我就改成了一维滚动数组，结果直接答案错误。。还不知道具体原因，目前的代码是这样子的。

#include<bits/stdc++.h>
using namespace std;
int n,m,w;//n：云朵数目，m：搭配数，w：钱（即背包容量）
int f[10000];//父亲数组
int dp[10000];
int v[10000],d[10000];//v:价格（即物品质量）d：价值
int findd(int x)
{if(f[x]==x)return f[x];elsereturn f[x]=findd(f[x]);
}
void hb(int x,int y)
{if(findd(x)!=findd(y))f[findd(x)]=findd(y);
}
int main()
{cin>>n>>m>>w;//初始化并查集for(int i=1;i<=n;i++){        f[i]=i;cin>>v[i]>>d[i];}for(int i=1;i<=m;i++){int a,b;cin>>a>>b;hb(a,b);}for(int i=1;i<=n;i++){if(findd(i)!=i)///这里很关键{v[findd(i)]+=v[i];v[i]=0;//把该云朵的价格加到其所在集合老大里面，原本的就清零d[findd(i)]+=d[i];d[i]=0;//同上}}//0/1背包for(int i=1;i<=n;i++){for(int j=w;j>=1;j--)//滚动数组{if(j>=v[i])dp[j]=max(dp[j],dp[j-v[i]]+d[i]);}}cout<<dp[w];return 0;
}

----------------------------------------------------------------------------------------------------------------

 原来是这样子，我每个数组范围多加个0就过了！！！！

所以ac代码就是以上贴出来的代码每个数组范围多加个0。

（他要是显示的是运行错误而不是答案错误就好嘛！！）

----------------------------------------------------------------------------------------------------------------

3

题目背景

小明在 A 公司工作，小红在 B 公司工作。

题目描述

这两个公司的员工有一个特点：一个公司的员工都是同性。

A 公司有 NN 名员工，其中有 PP 对朋友关系。B 公司有 MM 名员工，其中有 QQ 对朋友关系。朋友的朋友一定还是朋友。

每对朋友关系用两个整数 (X_i,Y_i)(Xi​,Yi​) 组成，表示朋友的编号分别为 X_i,Y_iXi​,Yi​。男人的编号是正数，女人的编号是负数。小明的编号是 11，小红的编号是 -1−1。

大家都知道，小明和小红是朋友，那么，请你写一个程序求出两公司之间，通过小明和小红认识的人最多一共能配成多少对情侣（包括他们自己）。

输入格式

输入的第一行，包含 44 个空格隔开的正整数 N,M,P,QN,M,P,Q。

之后 PP 行，每行两个正整数 X_i,Y_iXi​,Yi​。

之后 QQ 行，每行两个负整数 X_i,Y_iXi​,Yi​。

输出格式

输出一行一个正整数，表示通过小明和小红认识的人最多一共能配成多少对情侣（包括他们自己）。

输入输出样例

输入 #1复制

4 3 4 2
1 1
1 2
2 3
1 3
-1 -2
-3 -3

输出 #1复制

2

说明/提示

对于 30 \%30% 的数据，N,M \le 100N,M≤100，P,Q \le 200P,Q≤200；

对于 80 \%80% 的数据，N,M \le 4 \times 10^3N,M≤4×103，P,Q \le 10^4P,Q≤104；

对于 100 \%100% 的数据，N,M \le 10^4N,M≤104，P,Q \le 2 \times 10^4P,Q≤2×104。

思路： 知识点：并查集。

因为一个公司全是男人一个公司全是女人，所以配对一定是两个公司各取一人。

配对的人都要是小明和小红的朋友，所以在小明所在的公司找与小明祖先结点相同的人数，在小红所在的公司找与小红祖先结点相同的人数。

又因为情侣配对是一男一女，所以选择min（与小明是朋友的男性，与小红是朋友的女性）即可。

要注意的问题是，女性是用负数代表，而数组不存在负数下标，此时我们只需要把女性编号转化为正数即可，但不能直接取绝对值否则会和男性编号重合，我们应该绝对值女性编号再加上一个n，n即男性最大编号，就可以巧妙地使编号都是正数且不重合了。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,p,q,numm,numh;
int f[1000000];
int findd(int x)//找祖宗（并查集必写函数）
{if(f[x] == x)return x;elsereturn f[x]=findd(f[x]);//压缩路径
}
void hb(int x,int y)//合并集合（并查集必写函数）
{int fx=findd(x);int fy=findd(y);if(fx!=fy)f[fx]=fy;
}
int main()
{cin>>n>>m>>p>>q;for(int i=1;i<=n+m;i++)//不要忘了！！初始化并查集f[i]=i;//起初自己就是自己的老大for(int i=1;i<=p;i++)//根据提给信息合并小集合{int a,b;cin>>a>>b;hb(a,b);}for(int i=1;i<=q;i++)//处理全是女人的公司{int a,b;cin>>a>>b;//因为女性是用负数代表，而数组不存在负数下标a*=-1;b*=-1;//所以先把a，b变为正数a=a+n;b=b+n;//再加上n避免和男人编重合hb(a,b);}for(int i=1;i<=n;i++){if(findd(i)==findd(1))//如果是与小明是朋友的男性numm++;}for(int i=n+1;i<=n+m;i++){//n+1到n+m才是女人f数组if(findd(i)==findd(1+n))//如果是与小红是朋友的女性numh++;     //小红的编号是-1，转化为重合正数为-1*-1+n即1+n。}int ans=min(numm,numh);//短板效应，最终结果取决于少的那一方cout<<ans;return 0;
}

4

题目背景

AA地区在地震过后，连接所有村庄的公路都造成了损坏而无法通车。政府派人修复这些公路。

题目描述

给出A地区的村庄数NN，和公路数MM，公路是双向的。并告诉你每条公路的连着哪两个村庄，并告诉你什么时候能修完这条公路。问最早什么时候任意两个村庄能够通车，即最早什么时候任意两条村庄都存在至少一条修复完成的道路（可以由多条公路连成一条道路）

输入格式

第11行两个正整数N,MN,M

下面MM行，每行33个正整数x, y, tx,y,t，告诉你这条公路连着x,yx,y两个村庄，在时间t时能修复完成这条公路。

输出格式

如果全部公路修复完毕仍然存在两个村庄无法通车，则输出-1−1，否则输出最早什么时候任意两个村庄能够通车。

输入输出样例

输入 #1复制

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

输出 #1复制

5

说明/提示

N \le 1000,M \le 100000N≤1000,M≤100000

x \le N,y \le N,t \le 100000x≤N,y≤N,t≤100000

很开心，完全靠自己做出来的，中途的错误通过n个地方断点找出来了，最后迎来ac！！

#include<bits/stdc++.h>
using namespace std;
int n,m;
int f[110000];
int x[110000],y[110000],t[110000];
int findd(int x)//找祖宗
{if(f[x]==x)return f[x];elsereturn f[x]=findd(f[x]);
}
void hb(int x,int y)
{if(findd(x)!=findd(y))f[findd(x)]=findd(y);
}
void quicksort(int l,int r)
{int i,j,mid,p;mid=t[(l+r)/2];i=l;j=r;while(i<=j){while(t[i]<mid)i++;while(t[j]>mid)j--;if(i<=j){p=t[i];t[i]=t[j];t[j]=p;//交换p=x[i];x[i]=x[j];x[j]=p;p=y[i];y[i]=y[j];y[j]=p;i++;j--;}}if(l<j) quicksort(l,j);if(i<r) quicksort(i,r);
}
bool check()
{int v=findd(1);for(int i=1; i<=n; i++){if(findd(i)!=v)return false;}return true;
}
int main()
{cin>>n>>m;//初始化！for(int i=1; i<=n; i++)f[i]=i;int tmax=-1;for(int i=1; i<=m; i++){cin>>x[i]>>y[i]>>t[i];if(t[i]>tmax)tmax=t[i];}quicksort(1,m);int k,time=1;for(k=1; k<=m;){if(t[k] == time){hb(x[k],y[k]);if(check()==true){cout<<time;return 0;}k++;}elsetime++;}cout<<-1;return 0;
}

目录

1 

题目描述

输入格式

输出格式

输入输出样例

2

题目描述

输入格式

输出格式

输入输出样例

说明/提示

3

题目背景

题目描述

输入格式

输出格式

输入输出样例

说明/提示

4

题目背景

题目描述

输入格式

输出格式

输入输出样例

说明/提示

5 

题目描述

输入格式

输出格式

输入输出样例

---

 

题目描述

在JSOI2005夏令营快要结束的时候，很多营员提出来要把整个夏令营期间的资料刻录成一张光盘给大家，以便大家回去后继续学习。组委会觉得这个主意不错！可是组委会一时没有足够的空光盘，没法保证每个人都能拿到刻录上资料的光盘，又来不及去买了，怎么办呢？！

组委会把这个难题交给了LHC，LHC分析了一下所有营员的地域关系，发现有些营员是一个城市的，其实他们只需要一张就可以了，因为一个人拿到光盘后，其他人可以带着U盘之类的东西去拷贝啊！

可是，LHC调查后发现，由于种种原因，有些营员并不是那么的合作，他们愿意某一些人到他那儿拷贝资料，当然也可能不愿意让另外一些人到他那儿拷贝资料，这与我们JSOI宣扬的团队合作精神格格不入！！！

现在假设总共有N个营员（2<=N<=200），每个营员的编号为1~N。LHC给每个人发了一张调查表，让每个营员填上自己愿意让哪些人到他那儿拷贝资料。当然，如果A愿意把资料拷贝给B，而B又愿意把资料拷贝给C，则一旦A获得了资料，则B，C都会获得资料。

现在，请你编写一个程序，根据回收上来的调查表，帮助LHC计算出组委会至少要刻录多少张光盘，才能保证所有营员回去后都能得到夏令营资料？

输入格式

先是一个数N，接下来的N行，分别表示各个营员愿意把自己获得的资料拷贝给其他哪些营员。即输入数据的第i+1行表示第i个营员愿意把资料拷贝给那些营员的编号，以一个0结束。如果一个营员不愿意拷贝资料给任何人，则相应的行只有1个0，一行中的若干数之间用一个空格隔开。

输出格式

一个正整数，表示最少要刻录的光盘数。

输入输出样例

输入 #1复制

5
2 3 4 0
4 5 0
0
0
1 0

输出 #1复制

1

 

这道题，因为是题目中关系是单向的，而我们之前使用的常规的并查集都是双向的关系，所以我就一直在思考怎么实现这种单向的关系，”如果A愿意把资料拷贝给B，而B又愿意把资料拷贝给C，则一旦A获得了资料，则B，C都会获得资料“有点难处理，因为不直接合并会遇到把原先关系覆盖的问题。后来看到了一个题解，我发现他用到了之前自学了但还没有用上过的一个算法----Floyd-Warshall算法，觉得特别巧妙，正好能巧妙地解决题目说的“如果A愿意把资料拷贝给B，而B又愿意把资料拷贝给C，则一旦A获得了资料，则B，C都会获得资料”，我们知道，弗洛伊算法通常用于解决任意两点之间最短路径的问题。那么我们可以转化一下概念，把意愿关系转化为单向路径问题，因为"A愿意给B，B愿意给C就相当于A愿意给C“相当于”A地点能通往B地点，B地点能通往C地点，相当于A地点可以通往C地点“，这两者是本质是一样的，那么我们就可以用Floyd算法来遍历能”通路“的两个人。

之前是在这一天学习了Floyd-Warshall算法但是没有用上。(9条消息) 2022.1.14学习_m0_62742402的博客-CSDN博客

 参考了用二维标记数组来记录谁是否愿意借给谁拷贝的方法。妙哉妙哉！

即：will【i】【j】=1：代表 i 愿意借给 j 拷贝，反之，等于0代表不愿意。

因为题目只给出了每个人愿意给谁的信息，所以我们要记得先初始化will数组元素为0，但是因为全局变在未声明的时候默认元素为0，我们也可以不初始化（因为系统的默认恰好帮我们达到了初始化目的），但是也可以在主函数初始化一下使得代码更好理解，可读性更强。

#include <bits/stdc++.h>
using namespace std;
int will[210][210];//will意愿数组元素的值取1或0表示一个人是否愿意给另外一个人拷贝
int f[210],n;
int main()
{cin>>n;//memset(will,0,sizeof(will));  //初始化，起初大家之间都没有意愿//因为will数组是全局变量，是可以不初始化的//初始化父亲数组for(int i=1; i<=n; i++)f[i]=i;int x;for(int i=1; i<=n; i++)while(cin>>x && x!=0)//每一行数据个数不确定，输入0代表结束will[i][x]=1;  //表示第i个人愿意给第x个人拷贝//Floyd-Warshall把意愿关系转化为单向路径问题for(int k=1; k<=n; k++)for(int i=1; i<=n; i++)for(int j=1; j<=n; j++)if(will[i][k] == 1 && will[k][j] == 1)//如果i愿意给k，k愿意给j，则相当于i愿意给jwill[i][j]=1;for(int i=1; i<=n; i++)//遍历意愿数组for(int j=1; j<=n; j++)if(will[i][j])f[j]=f[i];  //不能直接合并，因为该题的关系是单向的，要f【拷贝人】=f【愿意给他拷贝的人】，即所有他愿意给拷贝的人认他为老大int ans=0;for(int i=1; i<=n; i++)if(f[i]==i)ans++;  //处理完以后，f【x】=x的人需要给一个光盘cout<<ans;return 0;
}

----------------------------------------------------------------------------------------------------------------------------

学习c++（bilibili）和看书《大话数据结构》

----------------------------------------------------------------------------------------------------------------------------