牛客多校第六场题解

B - Eezie and Pie

链式向前星建图 + LCA

代码

#include<bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define debug system("pause")
const int N = 2*1e6+5;   //N点数
const int M = 2*N;       //M边数
//Graph
int n,m;      //输入点数、边数
int idx;      //实际边数
int head[N];  //以i为起点的第一条边的下标
struct Edge{ int to, next;}edge[M];   //to边的终点 w边的权值 next同起点下一条边的下标

void add(int u, int v){
    edge[idx].to = v;
    edge[idx].next = head[u];
    head[u] = idx++;
}

int f[N];   //存答案
int d[N];
int vis[N];
vector<int> v;
int dfs(int cur){  
    vis[cur]=1;
   if(d[cur]<v.size())
   {
     int len = v.size()-d[cur]-1;
     f[v[len]]--;
   }
  v.push_back(cur);
  f[cur]++;
    for(int j = head[cur]; j != -1; j = edge[j].next){
        int to=edge[j].to;
        if(! vis[to]) {
         f[cur]+=dfs(to);
        }
    }
    v.pop_back();
    vis[cur]=0;
    return f[cur];
}


void solve(){
    memset(head,-1,sizeof head);
    idx=0;
    cin>>n; //输入点数
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        add(v,u);
        add(u,v);
    }
    for(int i=1;i<=n;i++){
    cin>>d[i];
    f[i]=0;
    }
    dfs(1);
    for(int i=1;i<=n;i++)
    cout<<f[i]<<" ";
}


int main(){
    js;
    int T=1; 
    while(T--) solve();
    debug;
    return 0;
}

G - Icon Design

找规律 或 暴力打表(1<=n<=5)

J - Number Game

推导公式即可

代码

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define debug system("pause")
#define ll long long
#define endl "n"

void solve(){
  ll a,b,c,x; cin>>a>>b>>c>>x;
  ll x1=x+c+b-a;
  ll x2=x+c-b;
  ll x3=x-c;
   ll u=a-2*b;
  if(u==0){
    if(x1==0) {cout<<"Yesn"; return;}
    if(x2==0) {cout<<"Yesn"; return;}
    if(x3==0) {cout<<"Yesn"; return;}
  cout<<"Non"; return;
  }
  else{
  if(x1%u==0) {cout<<"Yesn"; return;}
  if(x2%u==0) {cout<<"Yesn"; return;}
  if(x3%u==0) {cout<<"Yesn"; return;}
  cout<<"Non"; return;
  }
 }
int main(){
    js;
    int T;cin>>T;
    while(T--) solve();
    debug;
}