ABC368 简要题解

D

一眼虚树，对着关键点把虚树建出来然后求一下虚树上的点数（？），这个东西我认为是可以在构建虚树的时候通过树上距离求出来的，如果多组询问然后保证询问的总关键点个数，那么这个做法就是无敌了。

你说得对，但是 ABC D 上虚树还是夸张了一点哦。进一步观察这个包含关键点的最小子图，会发现这个子图的每个叶子都是关键点（无根树中，度数为 $1$ 的节点我们称作叶子）。我们容易想到钦定一个关键点 $v_1$ 为树根，那么我们从 $v_1$ 开始往原树 dfs，那么就可以变成一个删子树的过程。如果一个子树 $sub(u)$ 内没有关键点，那么我们就可以删掉这个子树。所以我们在 dfs 的过程中删掉所有不包含任何关键点的极大子树就好了。

更为简单的想法是考虑哪些点需要保留，这样一遍 dfs 就够了。如果一个点的子树里面有被打了标记的点，那么这个点就得保留。

Fysty

#include <bits/stdc++.h>
#include <random>
#include <chrono>
using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

template<typename T> void _do(T x){cerr<<x<<"\n";}
template<typename T,typename ...U> void _do(T x,U ...y){cerr<<x<<", ";_do(y...);}
#define dbg(...) cerr<<#__VA_ARGS__<<" = ";_do(__VA_ARGS__);

const int MOD1=1e9+7;
const int MOD2=998244353;
const ll INF=4e18;

ll fpow(ll a,ll b,ll m)
{
    if(!b) return 1;
    ll tmp=1;
    for(ll cur=a;b;b>>=1,cur=cur*cur%m) if(b&1) tmp=tmp*cur%m;
    return tmp;
}
ll inv(ll a,ll m) {return fpow(a,m-2,m);}

#define MottoHayaku ios::sync_with_stdio(false);cin.tie(0);
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define F first
#define S second
#define pb push_back
#define uni(c) c.resize(distance(c.begin(),unique(c.begin(),c.end())))
#define unisort(c) sort(c.begin(),c.end()),uni(c)

const int N=2e5+5;

vector<int> ed[N];
bool need[N];
int ans=0;

void dfs(int u,int p)
{
    for(int v:ed[u]) if(v!=p)
    {
        dfs(v,u);
        need[u]|=need[v];
    }
    if(need[u]) ans++;
}

void solve()
{
    int n,k;
    cin>>n>>k;
    rep(i,n-1)
    {
        int u,v;
        cin>>u>>v;
        ed[u].pb(v);
        ed[v].pb(u);
    }
    vector<int> a(k);
    rep(i,k)
    {
        cin>>a[i];
        need[a[i]]=1;
    }
    dfs(a[0],0);
    cout<<ans<<"\n";
}

signed main()
{
    MottoHayaku
    int t;
    //cin>>t;
    t=1;
    while(t--)
    {
        solve();
    }
}

linear 提出了一个另解，虽然和上面的做法本质相同，但是我觉得它更接近本质也很有启发性。重新分析“这个子图的每个叶子都是关键点”这条性质。我们可以直接一点地刻画这条性质：还是采用删点的构造方式，将当前的叶子集合维护出来，每次删掉非关键点的叶子，然后它的邻点又会成为新的叶子，把它放入这个叶子集合。这样的话，每个点最多进入叶子集合一次，被 check 一次，只有 $\mathcal{O}(n)$ 次判断。用 set 来维护这个集合即可。

其实这个做法和 prufer 序列的维护很像的，所以我觉得很有启发性啊！拜谢 linear 被 D 硬控 27min。

yyc：信息学的未来属于 linear！

int WITHERING([[maybe_unused]] unsigned long long int TEST_NUMBER) {
   tp n, k; cin >> n >> k;
   vector<set<tp>> e(n + 1);
   vetp l;
   for (tp i = 2; i <= n; ++i) {
      tp u, v; cin >> u >> v;
      e[u].insert(v);
      e[v].insert(u);
   }
   for (tp i = 1; i <= n; ++i) {
      if (e[i].size() == 1) l.push_back(i);
   }
   set<tp> v;
   while (k--) {
      tp x; cin >> x;
      v.insert(x);
   }
   tp tar = 0;
   while (l.size()) {
      vetp r;
      for (auto& i : l) {
         if (!v.count(i)) {
            ++tar;
            e[*e[i].begin()].erase(i);
            if (e[*e[i].begin()].size() == 1) r.push_back(*e[i].begin());
         } else v.erase(i);
      }
      l.swap(r);
   }
   cout << n - tar << '\n';
   return 0;
}

void MIST() {
}

struct STRUGGLE {
   STRUGGLE() {
      cin.tie(nullptr)->sync_with_stdio(false);
   }
} STRUGGLE;

// :\ */

E

ABC E 特有的脑筋急转弯题。

容易想到一个贪心，就是按照最短路来走，但是这个贪心是不对的，因为一条边可能受多个不同结束时间顺序的点控制。这启发我们按照发生的相对时间来处理这个问题。

考虑维护 $f_u$ 表示到达节点 $u$ 后最晚的下一轮开始时间。那么我们按照每条边 $(u_i,v_i,s_i,t_i)$ 的开始时间，结束时间将其拆为两个事件 $(s_i,i),(t_i,-i)$。考虑按照时间顺序依次考虑这些事件：

如果碰到一个 $(s_i,i)$ 事件，那么将 $x_i\gets f_u-s_i$。
如果碰到一个 $(t_i,-i)$ 事件，那么就是说 $i$ 这条边已经确定好了，所以 $f_u\gets t_i+x_i$。

其中这里的 $\gets$ 表示 checkmax。

void FALLING() {
   int n, m; cin >> n >> m;
   V<int> t(n + 1, 0), ans(m + 1, 0);
   cin >> ans[1];
   V<int> u(m + 1, 0), v(m + 1, 0);
   V<pi> e;
   FOR (i, 1, m) {
      int x, y; cin >> u[i] >> v[i] >> x >> y;
      e.eb(x, i), e.eb(y, -i);
   }
   std::sort(ALL(e));
   for (auto [x, i] : e) {
      if (i > 0) {
         if (i ^ 1) ans[i] = std::max(0, t[u[i]] - x);
      }
      else i = -i, ckmax(t[v[i]], ans[i] + x);
   }
   FOR (i, 2, m) cout << ans[i] << ' ';
   cout << "\n";
   return ;
}

F

一眼丁真 CF2004E，补了那题的话这题就是很简单了！但是由于实现的时候脑抽了被硬控了 30min，从此彻底输掉。

容易想到求出每个数的 SG 函数值，对于每个数 $i$，考虑枚举它的所有约数 $d$，那么 $SG(i)=\text{mex}\{SG(d)\}$，我们可以直接暴力枚举 $d$，因为枚举 $d$ 实际上就是 $\sqrt i$ 级别的。问题在于怎么求这个 $\text{mex}$。

实际上有很多种实现方式。

注意到 $d$ 只有根号种，直接暴力打标记，然后从小到大枚举找到第一个没有标记的数，这样是可以保证根号内的，这是因为最多 ban 掉根号个数，其实我们就有一个性质了：$SG(i)=\mathcal{O}(\sqrt i)$。

qiuzx_

//ANMHLIJKTJIY!
#pragma GCC optimize(2)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline","fast-math","unroll-loops","no-stack-protector")
#pragma GCC diagnostic error "-fwhole-program"
#pragma GCC diagnostic error "-fcse-skip-blocks"
#pragma GCC diagnostic error "-funsafe-loop-optimizations"
#include <bits/stdc++.h>
#define INF 1000000000
#define LINF 1000000000000000000
#define MOD 1000000007
#define mod 998244353
#define F first
#define S second
#define ll long long
#define N 100010
using namespace std;
ll n,f[N];
vector<ll> fac[N];
bool vis[N];
int main(){
    ll i,j;
    for(i=1;i<N;i++)
    {
        for(j=i+i;j<N;j+=i)
        {
            fac[j].push_back(i);
        }
    }
    for(i=2;i<N;i++)
    {
        for(j=0;j<fac[i].size();j++)
        {
            vis[f[fac[i][j]]]=true;
        }
        for(f[i]=0;vis[f[i]];f[i]++);
        for(j=0;j<fac[i].size();j++)
        {
            vis[f[fac[i][j]]]=false;
        }
    }
    scanf("%lld",&n);
    ll ans=0;
    for(i=0;i<n;i++)
    {
        scanf("%lld",&j);
        ans^=f[j];
    }
    puts(ans?"Anna":"Bruno");
    return 0;
}

可以用一个 set 维护没有被打标记的值，这样会多一个 $\log n$，本质和上面的实现是一样的。

void FALLING() {
   int n, m = 0; cin >> n;
   V<int> a(n + 1, 0);
   FOR (i, 1, n) cin >> a[i], ckmax(m, a[i]);
   V<int> sg(m + 2, 0);
   std::set<int> s;
   FOR (i, 1, m + 1) s.insert(i);
   FOR (k, 2, m) {
      int sq = std::sqrt(k);
      V<int> d;
      FOR (i, 2, sq) {
         if (k % i) continue;
         d.eb(sg[i]);
         if (i * i != k) d.eb(sg[k / i]);
      }
      for (auto i : d) if (s.find(i) != end(s)) s.erase(i);
      sg[k] = *begin(s);
      for (auto i : d) s.insert(i);
   }
   int w = 0;
   FOR (i, 1, n) w ^= sg[a[i]];
   cout << (w == 0 ? "Bruno\n" : "Anna\n");
   return ;
}

观察到最终的 SG 值实际上是 $\le \log_2 V$ 的，其中 $V$ 是数的值域，所以可以直接用类似于状压 dp 一样转移，记录每个数的后继中每种 SG 值是否存在了。这个做法需要较强的观察能力。

kotatsugame

#include<iostream>
#include<set>
#include<cassert>
using namespace std;
int Gru[1<<17];
int F[1<<17];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    for(int a=1;a<=(int)1e5;a++)
    {
        while(F[a]>>Gru[a]&1)Gru[a]++;
        for(int v=a+a;v<=(int)1e5;v+=a)F[v]|=1<<Gru[a];
    }
    int N;cin>>N;
    int X=0;
    for(;N--;)
    {
        int a;cin>>a;
        X^=Gru[a];
    }
    cout<<(X?"Anna":"Bruno")<<endl;
}

G

It is guaranteed that the answers to the given type $3$ queries are at most $10^{18}$.

所以说，在询问的区间内，$b_i\ge 2$ 的 $i$ 至多有 $\log_2 10^{18}=60$ 个，除去这些，都是 $b_i=1$，那么肯定选择 $v+a_i$ 更优。所以用一个 set，维护所有 $b_i\ge 2$ 的点，然后找出 $[l,r]$ 内的这些点，相当于把 $[l,r]$ 分段了，点之间的段肯定都是 $+a_i$，所以维护一下 $a$ 的区间和就好了。单点修改 $a$，查询 $a$ 的区间和，差分一下维护前缀和，用树状数组就可以维护了。

kotatsugame

#include<iostream>
#include<set>
#include<cassert>
#include<atcoder/fenwicktree>
using namespace std;
int N,Q;
int A[1<<17],B[1<<17];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>N;
    atcoder::fenwick_tree<long>BIT(N);
    for(int i=0;i<N;i++)
    {
        cin>>A[i];
        BIT.add(i,A[i]);
    }
    set<int>NO;
    for(int i=0;i<N;i++)
    {
        cin>>B[i];
        if(B[i]>1)NO.insert(i);
    }
    cin>>Q;
    for(;Q--;)
    {
        int t;cin>>t;
        if(t==1)
        {
            int i,x;cin>>i>>x;i--;
            BIT.add(i,-A[i]);
            BIT.add(i,x);
            A[i]=x;
        }
        else if(t==2)
        {
            int i,x;cin>>i>>x;i--;
            if(B[i]>1)NO.erase(i);
            B[i]=x;
            if(B[i]>1)NO.insert(i);
        }
        else
        {
            int l,r;cin>>l>>r;l--;
            long v=A[l];
            l++;
            auto it=NO.lower_bound(l);
            while(it!=NO.end()&&*it<r)
            {
                v+=BIT.sum(l,*it);
                v=max(v+A[*it],v*B[*it]);
                l=*it+1;
                it++;
            }
            cout<<v+BIT.sum(l,r)<<"\n";
        }
    }
}

SSRS

#include <bits/stdc++.h>
using namespace std;
struct binary_indexed_tree{
  int N;
  vector<long long> BIT;
  binary_indexed_tree(vector<int> A){
    N = A.size();
    BIT.resize(N + 1, 0);
    for (int i = 0; i < N; i++){
      BIT[i + 1] = A[i];
    }
    for (int i = 1; i < N; i++){
      if (i + (i & -i) <= N){
        BIT[i + (i & -i)] += BIT[i];
      }
    }
  }
  void add(int i, long long x){
    i++;
    while (i <= N){
      BIT[i] += x;
      i += i & -i;
    }
  }
  long long sum(int i){
    long long ans = 0;
    while (i > 0){
      ans += BIT[i];
      i -= i & -i;
    }
    return ans;
  }
  long long sum(int L, int R){
    return sum(R) - sum(L);
  }
};
int main(){
  int N;
  cin >> N;
  vector<int> A(N);
  for (int i = 0; i < N; i++){
    cin >> A[i];
  }
  vector<int> B(N);
  for (int i = 0; i < N; i++){
    cin >> B[i];
  }
  binary_indexed_tree BIT(A);
  set<int> st;
  for (int i = 0; i < N; i++){
    if (B[i] != 1){
      st.insert(i);
    }
  }
  st.insert(N);
  int Q;
  cin >> Q;
  for (int j = 0; j < Q; j++){\
    int t;
    cin >> t;
    if (t == 1){
      int i, x;
      cin >> i >> x;
      i--;
      BIT.add(i, -A[i]);
      A[i] = x;
      BIT.add(i, A[i]);
    }
    if (t == 2){
      int i, x;
      cin >> i >> x;
      i--;
      if (B[i] != 1){
        st.erase(i);
      }
      B[i] = x;
      if (B[i] != 1){
        st.insert(i);
      }
    }
    if (t == 3){
      int l, r;
      cin >> l >> r;
      l--;
      auto itr = st.lower_bound(l);
      long long v = 0;
      int p = l;
      while (p < r){
        int nxt = min(*itr, r);
        v += BIT.sum(p, nxt);
        p = nxt;
        if (p != r){
          v = max(v + A[p], v * B[p]);
          p++;
          itr++;
        }
      }
      cout << v << endl;
    }
  }
}

Z1qqurat's blog

D

E

F

G

仅有 1 条评论

发表新评论