LOADING

加载过慢请开启缓存,浏览器默认开启

daily 2

2023/4/3 daily

CF 780C
按题目的意思搜就好了,因为你dfs的时候本来就要保存一下cur和fa

void solve(){
  int n;cin>>n;
  vector<vector<int>>E(n+1);
  for(int i=0;i<n-1;++i){
    int x,y;cin>>x>>y;
    E[x].push_back(y);
    E[y].push_back(x);
  }
  vector<int>color(n+1);
  int cnt=0;
  function<void(int,int)>dfs=[&](int u,int f){
    int c=0;
    for(int v:E[u]){
        if(v!=f){
            ++c;
            while(c==color[u]||c==color[f])++c;
            color[v]=c;
            cnt=max(cnt,c);
        }
    }
    for(int v:E[u]){
        if(v!=f){
            dfs(v,u);
        }
    }
  };
  color[1]=1;
  dfs(1,1);
  cout<<cnt<<'\n';
  for(int i=1;i<=n;++i){
    cout<<color[i]<<" \n"[i==n];
  }
  return;
}

CF 401D

数位dp板子,但是又感觉像爆搜

把每一位保存下来,对应st存状态,注意不能有前导0并且每一位都要用

ll dp[1<<N][101];
void solve(){
  vector<int>num;
  ll n,m;
  cin>>n>>m;
  memset(dp,-1,sizeof(dp));
  while(n){
    num.push_back(n%10);
    n/=10;
  }
  int len=num.size();
  sort(num.begin(),num.end());
  function<ll(int,int,int)>dfs=[&](int pos,int st,ll mod){
    if(!pos)return (ll)(mod==0);
    if(~dp[st][mod])return dp[st][mod];
    ll res=0;
    for(int i=0;i<len;++i){
        if(!((st&(1<<i)))&&(i==0||num[i]!=num[i-1]||(st&(1<<(i-1))))){
            res+=dfs(pos-1,st|(1<<i),(mod*10+num[i])%m);
        }
    }
    return dp[st][mod]=res;
  };
  ll ans=0;
  for(int i=0;i<len;++i){
    if(num[i]&&(i==0||num[i]!=num[i-1])){
        ans+=dfs(len-1,1<<i,num[i]%m);
    }
  }
  cout<<ans<<'\n';
  return;
}

晚上鹅厂3面了,阿里和字节应该都稳了,等蚂蚁,能不能快点