首页 > 其他分享 >2023蓝桥杯省赛B组真题及解析

2023蓝桥杯省赛B组真题及解析

时间：2024-02-25 16:55:26浏览次数：24  
标签：dep 组真题 return int dfs 蓝桥 fa push 省赛

2023蓝桥杯省赛B组真题及解析

7.子串简写

算法：前缀和

https://www.lanqiao.cn/problems/3514/learning/?subject_code=1&group_code=4&match_num=14&match_flow=1&origin=cup

#include<bits/stdc++.h> using namespace std; int main() {     int K;     cin>>K;     string s;     cin>>s;     char c1,c2;     cin>>c1>>c2;     long long nums=0,ans=0;//nums为此点前面c1的个数的前缀和，ans为答案     for(int i=K-1,j=0;i<s.length();i++,j++)//i右边界，j为左边界，时刻维持区间长度为k     {         if(s[j]==c1) nums++;//j点是c1     //j指向的是是否有与c1匹配的字符串，如果有将nums加1，即使后面的是s[i]不等于c2，     //由于nums已经加1，如果后续有s[i]与c2相匹配的话，就将ans+上nums，     //因为i是由K-1开始的，可以画个图。         if(s[i]==c2) ans+=nums;//nums存放了以i做右边界满足条件c1的个数。     }     cout<<ans;     return 0; }

1.日期统计

https://www.lanqiao.cn/problems/3492/learning/?subject_code=1&group_code=4&match_num=14&match_flow=1&origin=cup

算法：dfs剪枝

//找不同时间（找数据）用搜索

#include <iostream>
using namespace std;
int a[100];
bool vis[20240000];
int ans ;
bool check(int date){
    if(vis[date])return false;
    //如果没访问就访问
    vis[date]=true;
    //前四位2023满足条件，只需考察月份和日子
    int mm=date/100%100;
    int rr=date%100;
    if(mm<1||mm>12) return false;
    if(mm==1||mm==3||mm==5||mm==7||mm==8|mm==10||mm==12){
        if(rr>=1&&rr<=31)return true;
        return false;
    }
    if(mm==4||mm==6||mm==9||mm==11){
            if(rr>=1&&rr<=30)return true;
        return false;
    }
    if(mm==2){
        if(rr>=1&&rr<=28)return true;
    }
    
    
}
void dfs(int x,int pos,int date)//x表示遍历到a数组中的哪一位，pos表示遍历到8位时间的哪一位
//date为所得时间，所得八位时间用八位数表示如：20230101 
{
    if(x==100)return ;//题目中100个数字遍历完
    if(pos==8) {
        //如果8位时间遍历完
        if(check(date)) ans++;//找到一个八位数 
        return ;//递归函数出口
    }
    //当前a[x]选入date 

//前四位有要求2023，后四位月份和日每个都有要求
    if(pos==0&&a[x]==2||pos==1&&a[x]==0||pos==2&&a[x]==2||pos==3&&a[x]==3||
    pos==4&&a[x]>=0&&a[x]<=1||pos==5&&a[x]>=0&&a[x]<=9||pos==6&&a[x]>=0&&a[x]<=3||
    pos==7&&a[x]>=0&&a[x]<=9
    ){
        dfs(x+1,pos+1,date*10+a[x]);//dfs(下一个数,日期中的下一位，日期转化成八位数)
    }
    //当前a[x]不放入date中 ，也就是date不进行到下一位，而x往后一位 
    dfs(x+1,pos,date);//dfs(下一个数，日期中的当前位，当前已经选的数字形成部分日期所组成的数  )
}
int main()
{
  for(int i=0;i<100;i++)cin>>a[i];
  dfs(0,0,0);
  cout<<ans;
  // 请在此输入您的代码
  return 0;
} 

3.冶炼金属

https://www.lanqiao.cn/problems/3510/learning/?subject_code=1&group_code=4&match_num=14&match_flow=1&origin=cup

 

考点是找到公式

(a/(b+1))+1=<V<=a/b

 

#include <iostream> using namespace std; const int N=1e4+6; int a[N],b[N]; int main() {   int n;   cin>>n;   int m=1e9+6;   int s=0;  for(int i=0;i<n;i++){   cin>>a[i]>>b[i];   m=min(m,a[i]/b[i]);//Vmax   s=max(s,(a[i]/(1+b[i]))+1);//Vmin  }  cout<<s<<" "<<m;   // 请在此输入您的代码   return 0; }

2.01的熵

考点：浮点数精度问题

#include<bits/stdc++.h> using namespace std; typedef  long double db; db a=11625907.5798; const int N=23333333; //注意浮点数有精度问题要用绝对值误差 const db p=1e-4; int main(){ for(int i=0;i<=N/2;i++){ int u=i;//0的个数 int v=N-i;//1的个数 db p0=(1.0)*u/N;     db p1=1.0*v/N;//因为要防止整数相除的陷阱所以用1.0改成double型，每一个除法都改！     db sum=(-1.0)*u*p0*log2(p0)+(-1.0)*v*p1*log2(p1);     if(fabs(sum-a)<=p){     cout<<u;     return 0; } } return 0; }

4.飞机降落

dfs

#include<bits/stdc++.h> using namespace std; const int N=1e5+8; int t[N],d[N],l[N]; int m;//本组m架飞机  bool have_ans=true; bool st[N]; void dfs(int a,int b) {   //已降落m架说明降落方案可行   if(a==m){     have_ans=true;     return ;   }   for(int i=1;i<=m;i++){     //最晚开始降落时间t[i]+d[i]      if(!st[i]&&b<=t[i]+d[i]){//降落第i架       st[i] =true; //最早是t[i]+l[i]所以可能不是时间b+l[i]出发，可能要等一会儿       dfs(a+1,max(b,t[i])+l[i]);              st[i]=false;//恢复     }   } //最终如果还没有达到a==m,会自动返回并且have_ans==false } void solve(){   have_ans=false;//默认没答案   cin>>m;   memset(st, 0, sizeof st); //恢复所有元素为没被访问，必须要   for(int i=1;i<=m;i++)cin>>t[i]>>d[i]>>l[i];   dfs(0,0);//运用dfs对所有情况进行搜索,dfs(i,j)已经降落 i架飞机，已经用时 j分钟    if(have_ans) cout<<"YES"<<endl;//有答案   else cout<<"NO" <<endl;//无答案 } int main(){   int m;   cin>>m;   while(m--){     solve();//每一次解决    }      return 0; }

 5.接龙数列

动态规划

  #include<bits/stdc++.h> using namespace std; int dp[10];//以0~9结尾每种情况的个数 int main(){  int n;  cin>>n;  string s;  int m=0;  for(int i=0;i<n;i++){    cin>>s;    int p=s[0]-'0';//最高位    int q=s[s.size()-1]-'0';//最低位    dp[q]=max(dp[q],dp[p]+1);//更新当前数字最低位结尾的数字个数就是max(以当前结尾的数字个数，连接上当前数的个数）      m=max(m,dp[q]);//最长接龙数列  }  cout<<n-m;//删除个数  return 0; }

6.岛屿个数

考点：BFS

https://www.lanqiao.cn/problems/3513/learning/?subject_code=1&group_code=4&match_num=14&match_flow=1&origin=cup

（有点难）

     

  #include<bits/stdc++.h> using namespace std; const int N=60; bool vis[N][N];//在判断岛屿时是否被搜索过 bool used[N][N];//在判断是否为子岛屿是否被使用过 char ma[N][N];//地图 int m,n; int dx[8]={-1,0,0,1,-1,-1,1,1}; int dy[8]={0,-1,1,0,-1,1,-1,1}; //判断岛屿 void bfs_island(int a,int b){   queue<int>qx;   queue<int>qy;   qx.push(a);   qy.push(b);   vis[a][b]=true;//这个点被访问   while(qx.size()){     int x=qx.front();qx.pop();     int y=qy.front();qy.pop();     for(int i=0;i<4;i++){       int nx=x+dx[i];       int ny=y+dy[i];       if(nx<0||ny<0||nx>m-1||ny>n-1||vis[nx][ny]==true||ma[nx][ny]=='0')continue;       qx.push(nx);qy.push(ny);       vis[nx][ny]=true;     }   } } //是否成环-->能否逃出去 bool bfs_out(int a,int b){     memset(used,false,sizeof(used));   queue<int>qx;   queue<int>qy;   qx.push(a);   qy.push(b);   used[a][b]=true;   while(qx.size()){ int x=qx.front();qx.pop(); int y=qy.front();qy.pop(); //已经找着跳出边界 if(x==0||y==0||x==m-1||y==n-1){   return true;//判断不是子岛屿就要ans++ } for(int i=0;i<8;i++){   int nx=x+dx[i];   int ny=y+dy[i];
  if(nx<0||ny<0||nx>m-1||ny>n-1||used[nx][ny]==true||ma[nx][ny]=='1')continue;//不能逃的情况   qx.push(nx);   qy.push(ny);   used[nx][ny]=true; }   }   return false; } void solve(){   int ans=0; cin>>m>>n; //输入地图 for(int i=0;i<m;i++){   for(int j=0;j<n;j++){ cin>>ma[i][j]; vis[i][j]=false;//初始化先所有格子未访问   } } //进行两次bfs，计算岛屿个数 for(int i=0;i<m;i++){   for(int j=0;j<n;j++){ //计算未访问的岛屿     if(ma[i][j]=='1'&&!vis[i][j]){       bfs_island(i,j);//将相邻1组成的岛屿搜索出来       if(bfs_out(i,j))ans++;//判断非子岛屿     }   } } cout<<ans<<endl; } int main(){ int t; cin>>t;//t组 while(t--){   solve(); }   return 0; }  

8.整数删除

考点：优先队列+链表

优先队列：每次方便取最值

链表：此处用的是静态链表且无头结点。方便删除。-->静态链表的删除结点不是真删除而是修改值让这个值不在范围内。

此处的链表为双向链表，开两个数组存放前驱后继下标。

 

#include<bits/stdc++.h>//静态链表 using namespace std; int n,k;//长度为n的数列操作k次 const int N=5e5+6; long long int A[N];//存放A数列 int pre[N];//前驱下标数组 int nex[N];//后继下标数组 typedef pair<long long int ,int>PII; //优先队列 priority_queue<PII,vector<PII> >q; int main(){ cin>>n>>k; for(int i=1;i<=n;i++){ cin>>A[i]; //小根堆，优先按存放值小的优先，然后是存放下标（即second）小的优先 q.push({-A[i],-i});//前面为数列值，后面是下标，小根堆可以用负数放进去（优先队列） //双向链表 pre[i]=i-1; nex[i]=i+1; } //特殊情况的前驱后继两头 pre[1]=-1; nex[n]=-1; //k次操作 while(k--){ PII now; //选择最小结点 //循环的目的，因为每一次要找的结点必须是修改后A中的所以要做检验，位置和值是否对应 do{ now=q.top(); q.pop(); //选最小 now.first=-now.first; now.second=-now.second; }while(A[now.second]!=now.first); int PRE=pre[now.second]; int NXT =nex[now.second]; //前驱存在 if(PRE!=-1){ A[PRE]+=now.first; nex[PRE]=NXT; q.push({-A[PRE],-PRE}); } //后继存在 if(NXT!=-1){ A[NXT]+=now.first; pre[NXT]=PRE; q.push({-A[NXT],-NXT}); } //删除当前结点 A[now.second]=-1; } for(int i=1;i<=n;i++){   if(A[i]!=-1)cout<<A[i]<<" "; } return 0;
}

9.景区导游

考点：   图论   LCA（公共祖先问题）+dfs

 

题目分析：

n个景点对应树上n个结点

n-1条摆渡车对应n-1条树上的边

建树

考点：

树上任意两点的距离path（a,b）=dis[a]+dis[b]-2*dis[lca(a,b)];-->所以手写公共祖先->lca以及配合的dfs->dfs里面在模版基础上增加求到根节点距离

完整代码解析：

  #include<bits/stdc++.h> using namespace std; const int N=1e5+5; //邻接表 vector<int>e[N];//邻接点 vector<int>t[N];//消耗时间 int dep[N];//深度 int fa[N][21];//注意题目中10的五次方所以第二维要开到21因为最大2的20次方即[ ] [20] long long int ans;//存答案可能超int int n,k;//n个景点，选中的游览路线里有k个景点 int A[N];//所选路线 long long int dis[N];//每个顶点到根节点的距离即时间，可能超int

//LCA

void dfs(int u,int Fa){   dep[u]=dep[Fa]+1;   fa[u][0]=Fa;   for(int i=1;i<=20;i++){     fa[u][i]=fa[fa[u][i-1]][i-1];   }   for(int i=0;i<e[u].size();i++){     int v=e[u][i];int p=t[u][i];     if(v==Fa)continue; dis[v]=dis[u]+p;//每个节点都有唯一的父亲，所以用父亲算子节点到根节点的距离，即根节点到u的子节点v的距离等于根节点到u的距离+u与v之间的距离 dfs(v,u);//递归   } } int LCA(int u,int v){   if(dep[u]<dep[v])swap(u,v);   for(int i=20;i>=0;i--){     if(dep[fa[u][i]]>=dep[v]){       u=fa[u][i];     }   }   if(u==v)return u;   for(int i=20;i>=0;i--){     if(fa[u][i]!=fa[v][i]){       u=fa[u][i];       v=fa[v][i];     }   }   return fa[u][0]; } //求相邻两点距离 long long int path(int u,int v){   if(u==0||v==0){     return 0;//看绿下标为0的那种不存在的点，到他的距离为0   }   return dis[u]+dis[v]-2*dis[LCA(u,v)]; } int main(){ cin>>n>>k; //n-1条摆渡车，邻接表 for(int i=1;i<n;i++){   int u,v,w;   cin>>u>>v>>w;   e[u].push_back(v);   t[u].push_back(w);   e[v].push_back(u);   t[v].push_back(w); } //为lca做准备，并求每个所问结点到根节点的距离（时间） dfs(1,0); //所问线路 for(int i=1;i<=k;i++){   cin>>A[i];//存放所问线路   ans+=path(A[i-1],A[i]);//先存放删除前总时间,即相邻点的距离 } //删除第i个结点 for(int i=1;i<=k;i++){   cout<<ans-path(A[i-1],A[i])-path(A[i],A[i+1])+path(A[i-1],A[i+1])<<" "; } return 0; } 删除一点： 距离和变化： ans-path(A[i-1],A[i])-path(A[i],A[i+1])+path(A[i-1],A[i+1])
完整代码 
 #include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
//邻接表
vector<int>e[N];//邻接点
vector<int>t[N];//消耗时间
int dep[N];//深度
int fa[N][21];
long long int ans;//存答案可能超int
int n,k;//n个景点，选中的游览路线里有k个景点
int A[N];//所选路线
long long int dis[N];//每个顶点到根节点的距离即时间
void dfs(int u,int Fa){
  dep[u]=dep[Fa]+1;
  fa[u][0]=Fa;
  for(int i=1;i<=20;i++){
    fa[u][i]=fa[fa[u][i-1]][i-1];
  }
  for(int i=0;i<e[u].size();i++){
    int v=e[u][i];int p=t[u][i];
    if(v==Fa)continue;
dis[v]=dis[u]+p;//每个节点都有唯一的父亲，所以用父亲算子节点到根节点的距离
dfs(v,u);
  }
}
int LCA(int u,int v){
  if(dep[u]<dep[v])swap(u,v);
  for(int i=20;i>=0;i--){
    if(dep[fa[u][i]]>=dep[v]){
      u=fa[u][i];
    }
  }
  if(u==v)return u;
  for(int i=20;i>=0;i--){
    if(fa[u][i]!=fa[v][i]){
      u=fa[u][i];
      v=fa[v][i];
    }
  }
  return fa[u][0];
}
//求相邻两点距离
long long int path(int u,int v){
  if(u==0||v==0){
    return 0;//看绿下标为0的那种不存在的点，到他的距离为0
  }
  return dis[u]+dis[v]-2*dis[LCA(u,v)];
}
int main(){
cin>>n>>k;
//n-1条摆渡车，邻接表
for(int i=1;i<n;i++){
  int u,v,w;
  cin>>u>>v>>w;
  e[u].push_back(v);
  t[u].push_back(w);
  e[v].push_back(u);
  t[v].push_back(w);
}
//为lca做准备，并求每个所问结点到根节点的距离（时间）
dfs(1,0);
//所问线路
for(int i=1;i<=k;i++){
  cin>>A[i];
  ans+=path(A[i-1],A[i]);//先存放删除前总时间,即相邻点的距离
}
//删除第i个结点
for(int i=1;i<=k;i++){
  cout<<ans-path(A[i-1],A[i])-path(A[i],A[i+1])+path(A[i-1],A[i+1])<<" ";
}
return 0;
}

10.砍树

题面解析： n个顶点 n-1条已经给了的边 由以上两个条件画树 问： 给出m个组合要求每个组合里两个顶点不相通！

#include <bits/stdc++.h> using namespace std; const int N=1e5+5; vector<int>e[N],num[N]; int n,m,dep[N],s[N],fa[N][21]; int ans=-1;

//核心找u，v公共祖先LCA算法

void dfs(int u,int Fa){   dep[u]=dep[Fa]+1;   fa[u][0]=Fa;   for(int i=1;i<=20;i++){     fa[u][i]=fa[fa[u][i-1]][i-1];   }   for(auto&v:e[u]){     if(v==Fa)continue;     dfs(v,u);   } } int LCA(int u,int v){   if(dep[u]<dep[v])swap(u,v);   for(int i=20;i>=0;i--){     if(dep[fa[u][i]]>=dep[v]){       u=fa[u][i];     }   }   if(u==v)return u;   for(int i=20;i>=0;i--){     if(fa[u][i]!=fa[v][i]){       u=fa[u][i];       v=fa[v][i];     }   }   return fa[u][0]; } void dfs2(int u,int Fa){   for(int i=0;i<e[u].size();i++){   int v=e[u][i],p=num[u][i];   if(v==Fa)continue;   dfs2(v,u);   s[u]+=s[v];   if(s[v]==m)ans=max(ans,p);   } } //主函数 int main() {   cin>>n>>m;   for(int i=1;i<n;i++){     int x,y;     cin>>x>>y;     e[x].push_back(y);     num[x].push_back(i);     e[y].push_back(x);     num[y].push_back(i);   }   dfs(1,0);   for(int i=1;i<=m;i++){     int a,b;     cin>>a>>b;     s[a]++;     s[b]++;     s[LCA(a,b)]-=2;   } dfs2(1,0); cout<<ans;   // 请在此输入您的代码   return 0; }

分段分析代码

LCA

查看代码 
//LCA算法包含两部分：先dfs在求公共祖先
//所需数组：深度dep[ ],找向上的下标fa[当前结点][向上2的多少次方级],邻接表存边 e[u]表示与u相邻的边的另一个点
void dfs(int u,int Fa){//u是当前点，Fa是他父亲的下标
  dep[u]=dep[Fa]+1;//他自己的深度是他父亲深度加1
  fa[u][0]=Fa;//u的向上2的0次方级是他父亲
    //从下往上找祖先
  for(int i=1;i<=20;i++){//向上最多2的20方级，因为题目给最多10的5次方个结点。
    fa[u][i]=fa[fa[u][i-1]][i-1];//递归：u向上第2的i次方级等价于u向上2的i-1次方所得元素再向上2的i-1次方即2的i-1次方乘2=2的i次方。
  }
  for(auto&v:e[u]){//当前所给顶点u的所有邻结点
    if(v==Fa)continue;
      //相邻的这个点不是它父亲再dfs递归，
    dfs(v,u);//因为是从最上面的点往下搜，不能重复搜它上面的点，所以他父亲不能再搜。
  }
}
//返回值就是u，v的公共祖先
int LCA(int u,int v){//上面dfs是准备工作，下面是核心LCA找u，v公共祖先下标
  if(dep[u]<dep[v])swap(u,v);//保证u更深
  for(int i=20;i>=0;i--){//u大步向上跳跃
    if(dep[fa[u][i]]>=dep[v]){//u的向上2的i次方级的深度大于v的深度
      u=fa[u][i];//那么修改u下标为它向上2的i次方级下标
    }
  }
    //所以出循环后u的深度>=v
  if(u==v)return u;//u跳完与v相遇那么返回u，说明原来v是u的直系祖先
  for(int i=20;i>=0;i--){//两人一起往上大步跳直至祖先相同
    if(fa[u][i]!=fa[v][i]){
      u=fa[u][i];
      v=fa[v][i];
    }
  }
  return fa[u][0];//最终修改的u，v有共同的父亲就是原u，v的公共祖先
}

 砍树，利用dfs看砍哪个边

void dfs2(int u,int Fa){//dfs2(当前节点下标，父节点下标）
  for(int i=0;i<e[u].size();i++){//u的所有邻接点
  int v=e[u][i],p=num[u][i];//v是此时与u相邻的点，p是u此时所在边的编号
  if(v==Fa)continue;//不重复搜父亲
  dfs2(v,u);
  s[u]+=s[v];
  if(s[v]==m)ans=max(ans,p);//p是关键边
  }
}

 

 

主函数

int main()
{
  cin>>n>>m;//n个顶点，m组组合不相通
  for(int i=1;i<n;i++){//n-1条已知边，等会砍的边只能从这里面选
    int x,y;
    cin>>x>>y;//一条边的两个顶点
      //8~11为邻接表存边，因为是按无向图存所以x，y各弄一次
    e[x].push_back(y);//x当前的邻接点y
    num[x].push_back(i);//并存放x当前所在边边的标号，因为题目求满足条件的最大边标号
    e[y].push_back(x);//同理
    num[y].push_back(i);
  }
  dfs(1,0);//先进行LCA的预备工作dfs利用深搜处理每个点的祖先,从第一个结点开始搜他的父节点默认0.
  for(int i=1;i<=m;i++){//核心代码：考察树上差分算法
    int a,b;
    cin>>a>>b;
    s[a]++;
    s[b]++;
    s[LCA(a,b)]-=2;
  }
dfs2(1,0);//从第一个结点开始搜他的父节点默认0.
cout<<ans;//输出答案
  // 请在此输入您的代码
  return 0;
}
 

主函数里的核心算法树上差分

 

树上差分 
for(int i=1;i<=m;i++){//核心代码：考察树上差分算法
    int a,b;
    cin>>a>>b;
    s[a]++;
    s[b]++;
    s[LCA(a,b)]-=2;
  }
/*解析：
因为要使得这m组组合不相通
所以先标记一下原来相通时状态，s[a]表示a到其父亲必须右边，而他们公共祖先往上不一定要边所以要减去2因为a，b各贡献+1





*/
//这个搜索是配合树上差分
void dfs2(int u,int Fa){//dfs2(当前节点下标，父节点下标）
  for(int i=0;i<e[u].size();i++){//u的所有邻接点
  int v=e[u][i],p=num[u][i];//v是此时与u相邻的点，p是u此时所在边的编号
  if(v==Fa)continue;//不重复搜父亲
  dfs2(v,u);
  s[u]+=s[v];
  if(s[v]==m)ans=max(ans,p);//p是关键边
  }
}
//s[v]表示v到其父亲的这条路径在题目中作为关键路径所需要走的次数

例如上图，这两个点之间的有关键路径就对该路径+1，其实就是s[]变化！

完整代码 
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
vector<int>e[N];//vector数组的数组，其实就是邻接矩阵存边，例如e[u]表示与u相邻的点
vector<int>num[N];//边标号
int dep[N];//各结点深度
int fa[N][21];//注意他的第二位是向上2的多少次方级最多21表示2的21次方级，不能开N太大会爆！
int n,m;//n个顶点m种不相通组合
int ans=-1;//没有可行方案默认-1
int s[N];
void dfs(int u,int Fa){
  dep[u]=dep[Fa]+1;
  fa[u][0]=Fa;
  //从下往上找
  for(int i=1;i<=20;i++){
    fa[u][i]=fa[fa[u][i-1]][i-1];
  }
  for(auto &v:e[u]){
    if(v==Fa)continue;
    dfs(v,u);
  }
}
int LCA(int u,int v){//返回u，v的公共祖先下标
  //保证u的深度更深
  if(dep[u]<dep[v])swap(u,v);
//u大步向上跳
for(int i=20;i>=0;i--){
  if(dep[fa[u][i]]>=dep[v]){
    u=fa[u][i];
  }
}
//如果u，v相遇
if(u==v){
  return u;
}
//否则u，v一起大步向上跳
for(int i=20;i>=0;i--){
  if(fa[u][i]!=fa[v][i]){
    //u,v祖先不同就一起往上跳
    u=fa[u][i];
    v=fa[v][i];

  }
}
return fa[u][0];//原u，v公共祖先是修改后u，v的公共父亲
}
//配合树上差分
void dfs2(int u,int Fa){//当前节点下标u，其父节点下标Fa
for(int i=0;i<e[u].size();i++){
  int v=e[u][i];int p=num[u][i];
  if(v==Fa)continue;
  dfs2(v,u);
  s[u]+=s[v];
  if(s[v]==m){//所给这m种组合都要过。
    ans=max(ans,p);
  }
}

}
int main(){
cin>>n>>m;
//邻接表存边((n-1条))
for(int i=1;i<n;i++){
  int x,y;
  cin>>x>>y;
e[x].push_back(y);
num[x].push_back(i);
e[y].push_back(x);
num[y].push_back(i);
}
//为LCA做准备
dfs(1,0);
//m种不相通组合,树上差分：
for(int i=0;i<m;i++){
  int x,y;
  cin>>x>>y;
  s[x]++;
  s[y]++;
  s[LCA(x,y)]-=2;
}
//砍树
dfs2(1,0);
cout<<ans;//输出答案
return 0;
}

 

标签：dep,组真题,return,int,dfs,蓝桥,fa,push,省赛
From： https://www.cnblogs.com/luckyhappyyaoyao/p/18005879

相关文章

  • P8668 [蓝桥杯 2018 省 B] 螺旋折线
    以第四象限的形如(x,-x)的点（它的距离最好算）为基准，来推附近的点的距离。不用怕坐标轴上的点的从属划分问题，例如在A区域和B区域交线上的点，那么它就应该是既满足A区域算法，又满足B区域算法的。#include<bits/stdc++.h>usingnamespacestd;longlongx,y,n,d;intmain(){......
  • 2022 CCPC湖北省赛
    2022CCPC湖北省赛​ 这场打的怎么说，很难受。过年来与几个亲戚家的孩子见了面，被灌了不少白酒，没感觉什么酱香有啥好喝的，脑子倒是快成浆糊了。怒了，加训。题解里签到题的做法会写的简单点，这个[每日一棵splay](2022HubeiProvincialCollegiateProgrammingContest题解ABFJK......
  • P8784 [蓝桥杯 2022 省 B] 积木画
    原题链接太妙了，请移步题解区，有用数学归纳法做的，也有用找规律做的L型积木一定是成对出现的code#include<bits/stdc++.h>usingnamespacestd;constintmod=1e9+7;longlongdp[10000005]={0};intmain(){intn;cin>>n;dp[0]=1;dp[1]=1;dp[2]=2;......
  • P8725 [蓝桥杯 2020 省 AB3] 画中漂流
    原题链接题解1.总共有t秒，每一秒不是上升就是下降2.要在救援队赶来之前把体力全部花光code#include<bits/stdc++.h>usingnamespacestd;intdp[3005][1505]={0};//代表第i秒使用j点体力的方案数intmain(){intd,t,m;cin>>d>>t>>m;dp[0][0]=1;for(i......
  • P8732 [蓝桥杯 2020 国 ABC] 答疑
    原题链接题解存在某种问问题顺序使得答案最小，可是我们不知道排序的规律，遂试探给定一种排序，交换任意相邻同学问问题顺序，对答案的改变如下：code#include<bits/stdc++.h>usingnamespacestd;structunit{ints,a,e,sum;}stu[1005];boolcmp(unita,unitb){ret......
  • P8807 [蓝桥杯 2022 国 C] 取模
    原题链接题解，我觉得讲的足够好了code#include<bits/stdc++.h>usingnamespacestd;intmain(){intt;cin>>t;while(t--){intn,m,i;cin>>n>>m;for(i=2;i<=m;i++){if(n%i!=i-1)......
  • P8786 [蓝桥杯 2022 省 B] 李白打酒加强版
    原题链接题解根据样例，观察到李白总共走\(n+m\)次，每一次不是遇到酒馆就是遇到花故我们可以设\(dp[i][0/1]\)代表第\(i\)次遇到酒馆或花的方案数但是我们发现这样的状态不好转移故我们可以设\(dp[i][0/1][k]\)代表第\(i\)次遇到酒馆或花，还剩下\(k\)斗酒的方案数但......
  • P8783 [蓝桥杯 2022 省 B] 统计子矩阵
    原题链接题解1.当存在某个矩阵符合题意时，所有小于该矩阵的矩阵都符合题意这是我们就可以想到用双指针code#include<bits/stdc++.h>usingnamespacestd;inta[505][505]={0},sum[505][505]={0};intn,m,k;intcheck(intdown,intright,intup,intleft){returnsu......
  • P8667 [蓝桥杯 2018 省 B] 递增三元组
    二分计数#include<iostream>#include<stdio.h>#include<algorithm>#include<string>#defineFor(i,j,n)for(inti=j;i<=n;++i)usingnamespacestd;constintN=1e5+5;intn,arr[3][N],base[N];longlongans;int......
  • P8674 [蓝桥杯 2018 国 B] 调手表
    原题链接题解一道思维题由于闹钟是圆的，所以从任意一个分钟数调到另外任意一个分钟数最多要按多少次相当于从点0调到1~n-1任意一点最多要按多少次可以把1~n看成一个一个点，就相当于单源最短路了md，好巧妙code#include<bits/stdc++.h>usingnamespacestd;structrefresh{......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99