CF_800

2023/3/4 Algorithm CodeForces

800 div 2的6道题，这场全是思维题

A

照着差值最小去构造即可

void solve()
{
  int a,b;
  cin>>a>>b;
  string ans;
  for(int i=0;i<min(a,b);++i)
  {
    ans+='0';
    ans+='1';
  }
  if(a>b)
  {
    ans+=string(a-b,'0');
  }
  else
  {
    ans+=string(b-a,'1');
  }
  cout<<ans<<'\n';
  return;
}

我们有两种操作，第一种 ${01}=1$ 第二种${10}=0$

现在考虑什么样的情况是无解的，我们枚举一下，发现 ${011}$ ${100}$这两种情况都是无解的，而这两种情况的最后两位都相同，直接猜结论，最后两位是否相同等价于一个数组是否有解，证明也很好证

void solve()
{
  int n;cin>>n;
  string s;cin>>s;
  ll ans=1;
  for(int i=1;i<n;++i)
  {
    if(s[i]!=s[i-1])
    {
        ans+=i+1;
    }
    else ans++;
  }
  cout<<ans<<'\n';
  return;
}

很巧妙的一道题，首先由于增加减少的操作数相同，所以如果数组的和不为0肯定无解。

我们最后要返回原点，有一段距离的值需要进行平衡（一段操作是无效的），又因为我们只能够增加当前值，减少后面的值，所以如果有一段的前缀和小于0，那么肯定是无解的

那么最后，对于前缀和等于0的部分，我们进行一个判断，如果当前已经收敛了，那么随后如果还有前缀和>0的段，那么肯定无法构造出来

void solve()
{
  int n;
  cin>>n;
  vector<ll>pre(n+1);
  for(int i=1;i<=n;++i)
  {
    cin>>pre[i];
    pre[i]+=pre[i-1];
  }
  if(pre[n]!=0)
  {
    cout<<"NO\n";
    return;
  }
  bool ispre_zero=false;
  for(int i=1;i<=n;++i)
  {
    if(pre[i]==0)
    {
        ispre_zero=true;
        continue;
    }
    if(ispre_zero)
    {
        if(pre[i]!=0)
        {
            cout<<"NO\n";
            return;
        }
    }
    if(pre[i]<0)
    {
        cout<<"NO\n";
        return;
    }
  }
  cout<<"YES\n";
  return;
}

同样很巧妙的一道题(所以说这场全是智力题)

这道题最关键的部分就是，所有儿子的id都比父母节点的id要大，而原修改序列又是从根到叶结点的

因此我们对于每次询问，可以先把小于l[i]的叶子结点直接设为r[i]，这样做的好处是因为修改序列是递减的，所以我们给了祖先结点们更多的调整空间，当我们修改儿子后，直接把对应的值加到父亲节点中，然后从n->1进行处理。

void solve()
{
  int n;cin>>n;
  vector<int>pa(n+1);
  for(int i=2;i<=n;++i)
  {
    cin>>pa[i];
  }
  vector<int>l(n+1),r(l);
  vector<ll>a(n+1);
  for(int i=1;i<=n;++i)cin>>l[i]>>r[i];
  int ans=0;
  for(int i=n;i>=1;--i)
  {
    if(a[i]<l[i])a[i]=r[i],++ans;
    if(a[i]>r[i])a[i]=r[i];
    a[pa[i]]+=a[i];
  }
  cout<<ans<<'\n';
  return;
}

一开始一点头绪都没有的一道题,本来以为是概率，结果其实是贪心题

首先需要反向建边，因为正向的话处理环更麻烦

首先我们先看应该采取什么样的策略来进行删边，很显然，由于每次我们选择的路是随机的，那么最坏的情况就是我们每次都选择最远的路，那么我们删除的话应该删除最远的边，然后我们思考边权是什么，很显然就是该节点的入度（反向建边），我们每次按照dijistra的方式更新即可

void solve()
{
  priority_queue<pii,vector<pii>,greater<pii>>q;
  int n,m;cin>>n>>m;
  vector<vector<int>>E(n+1);
  vector<int>deg(n+1);
  for(int i=0;i<m;++i)
  {
    int x,y;cin>>x>>y;
    E[y].push_back(x);
    ++deg[x];
  }
  q.push({0,n});
  vector<int>vis(n+1);
  vector<ll>dis(n+1,(ll)MOD);
  dis[n]=0;
  while(!q.empty())
  {
    auto [d,now]=q.top();
    q.pop();
    if(vis[now])continue;
    vis[now]=1;
    for(int v:E[now])
    {
        if(d+deg[v]<dis[v])
        {
            dis[v]=d+deg[v];
            q.push({dis[v],v});
        }
        --deg[v];
    }
  }
  cout<<dis[1]<<'\n';
  return;
}

感觉没完全懂，就不在这瞎jb写了，似懂非懂了属于是，依旧贴一个大佬的解答

(https://blog.csdn.net/weixin_43346722/article/details/127250722)

这场自己做的时候D没做出来（不知道什么时候能稳定出D），最近没那么多时间扑在算法上了，感觉每天一套DIV2可能不太行的通，从明天开始开始做专题吧，每天三道专题,先从dp开始吧！
先从DP开始，之后明天把KV的LSM tree给写了。

（又是没干啥事的一天，我这条懒🐶真是辛苦了呢！）

LOADING

CF_800