AcWing 1171. 距离（周三）
复习
前言
昨天的题比较难。我还不是很理解，主要是个别代码，感觉比较难理解。我再学一遍。今天把周一的题再写一遍，感觉周一的题应该还是比较理解的，就是并查集。
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+1e5+10;
int p[N];
int find(int x){
if(x!=p[x]){
p[x]=find(p[x]);
}
return p[x];
}
int main(){
for(int i=1;i<N;i++){
p[i]=i;
}
int n;
cin>>n;
for(int i=1;i<=n;i++){
int x;
cin>>x;
x=find(x);
cout<<x<<" ";
p[x]=x+1;
}
return 0;
}
能比较顺畅地写出来。周二的题现在更懂一些了。
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
vector<int> a[N];
int f[4][N];
int main(){
int n,m;
cin>>n>>m;
for(int i=0;i<n;i++){
int x;
cin>>x;
a[x%m].push_back(x);
}
memset(f,-0x3f,sizeof f);//取最大值，最开始取成负数，按道理说取成-1也行，有点奇怪了
f[0][0]=0;//上面的取成 -1 竟然不行
for(int i=0;i<m;i++){
sort(a[i].begin(),a[i].end());
reverse(a[i].begin(),a[i].end());//相当于从大到小排序，贪心的做法
for(int u=0;u<3&&u<a[i].size();u++){//选择的是最大的三个余数
int x=a[i][u];//当前选择的数字
for(int j=3;j>=1;j--){//选择三个数字
for(int k=0;k<m;k++){//属性是最大值
f[j][k]=max(f[j][k],f[j-1][(k-x%m+m)%m]+x);//状态转移方程
}//j 表示的是选择数字的个数，k 表示的是当前和模除m的余数
}
}
}
cout<<f[3][0]<<endl;
return 0;
}
刚看到那道题太难了，我还是先做一些简单一些的题，做难题性价比太低了一些，我可能也学不会。判断难度的话，只要超过半个小时的视频讲解的那种，我现阶段直接放弃。
代码
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=10010,M=N*2;
int n,m;
int h[N],e[M],w[M],ne[M],idx;
int dist[N];
int p[N];
int res[M*2];
int st[N];
vector<PII> query[N];
void add(int a,int b,int c){
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u ,int fa){
for(int i=h[u];~i;i=ne[i]){
int j=e[i];
if(j==fa){
continue;
}
dist[j]=dist[u]+w[i];
dfs(j,u);
}
}
int find(int x){
if(x!=p[x]){
p[x]=find(p[x]);
}
return p[x];//现在唯一比较熟练的模板。
}
void tarjan(int u){
st[u]=1;
for(int i=h[u];~i;i=ne[i]){
int j=e[i];
if(!st[j]){
tarjan(j);
p[j]=u;
}
}
for(auto item:query[u]){
int y=item.first,id=item.second;
if(st[y]==2){
int anc=find(y);
res[id]=dist[u]+dist[y]-2*dist[anc];
}
}
st[u]=2;
}
int main(){
cin>>n>>m;
memset(h,-1,sizeof h);
for(int i=0;i<n-1;i++){
int a,b,c;
cin>>a>>b>>c;
add(a,b,c),add(b,a,c);
}
for(int i=0;i<m;i++){
int a,b;
cin>>a>>b;
if(a!=b){
query[a].push_back({b,i});
query[b].push_back({a,i});
}
}
for(int i=1;i<=n;i++){
p[i]=i;
}
dfs(1,-1);
tarjan(1);
for(int i=0;i<m;i++){
cout<<res[i]<<endl;
}
return 0;
}
思路
思路还是比较简单的，就是要实现一堆图论的模板函数。这个可能就是熟能生巧。什么并查集，tarjan , dfs ，都是我不熟练的模板，还有链表。之前有一些可能还是比较熟练的，现在完全不熟练了。今天去健身也是狠狠上大重量，其实我们做很多东西都是要熟练度。多练习。
现在自己练习了很长一段时间盲打了，但是敲代码还是不行，因为涉及到一些什么尖括号，井号，括号，还有大小写什么的，比较难受，期待自己快速准确盲打的那一天，希望能坚持坚持。练习盲打还有点上瘾，可能可以帮助逃避压力。
在浏览器里面快捷键切换页面是 ctrl + tab 和 ctrl +shift +tab
今天没有复习算法设计与分析，这个差点也写不了，我们总会因为各种原因坚持不下来，可以理解。今天走了两万多步，也是非常充实。
原文地址：https://blog.csdn.net/L3102250566/article/details/143901876
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！