暑假集训 加赛1

P145 修仙（restart）

• 题目中的 可以 指 恰好 。

• 考虑计算双休带来的差值。

• 令 \(b_{i}=a_{i}+a_{i+1}-\max(a_{i}+a_{i+1},0)\) ，则需要计算从 \([1,n)\) 中选出 \(k\) 个不相邻的 \(b_{i}\) 的最大价值，同 luogu P1484 种树 | luogu P1792 [国家集训队] 种树 | luogu P3620 [APIO/CTSC2007] 数据备份 | CF958E2 Guard Duty (medium) | SP1553 BACKUP - Backup Files 。

• 然后就是反悔贪心板子了。

  • 基本思想是无论当前的选项是否最优都接受，然后进行比较，如果选择之后不是最优了，则反悔，舍弃掉这个选项，常写作两种决策之间作差的形式；否则，正式接受。如此往复。
  • 容易有在求解最大值/最小值的最优解中，最大值/最小值左右两端的数要么都选要么都不选。
  • \(k\) 的状态能由 \(k-1\) 的状态继承而来，启发我们可以依次处理子问题。
  • 算法流程：先选出 \(\{ b \}\) 中的最小值 \(b_{pos}\) 加入答案集合，然后删除 \(b_{pos-1},b_{pos+1}\) ，用 \(b_{pos-1}+b_{pos+1}-b_{pos}\) 替代原来的 \(b_{pos}\) 。
    • 若选了 \(b_{pos-1}+b_{pos+1}-b_{pos}\) 等价于将原来答案集合里的 \(b_{pos}\) 替代成 \(b_{pos-1}+b_{pos+1}\) 。
    • 否则选择 \(b_{pos}\) 。
  • 双向链表维护动态插入和删除；优先队列维护每次选出最小值，需要懒惰删除法。
  • 边界 \(0\) 和 \(n+1\) 一般需要特殊处理。
  点击查看代码

  priority_queue<pair<ll,ll> >q;
  ll a[200010],b[200010],cha[200010],l[200010],r[200010],vis[200010];
  int main()
  {
      ll n,x,k,ans=0,pos,i;
      cin>>n>>x;
      k=n/2;
      for(i=1;i<=n;i++)
      {
          cin>>a[i];
          ans+=a[i];
      }
      for(i=1;i<=n-1;i++)
      {
          b[i]=a[i]+a[i+1]-max(a[i]+a[i+1]-x,0ll);
          l[i]=i-1;
          r[i]=i+1;
          q.push(make_pair(b[i],i));
      }   
      b[0]=b[n]=-0x3f3f3f3f3f3f3f3f;//因为要保证是恰好，边界需要特殊处理
      for(i=1;i<=k;i++)
      {
          while(q.empty()==0&&vis[q.top().second]==1)
          {
              q.pop();
          }
          if(q.empty()==0)
          {
              ans-=q.top().first;
              pos=q.top().second;
              q.pop();
              vis[l[pos]]=vis[r[pos]]=1;
              b[pos]=b[l[pos]]+b[r[pos]]-b[pos];
              q.push(make_pair(b[pos],pos));
              l[pos]=l[l[pos]];
              r[pos]=r[r[pos]];
              l[r[pos]]=r[l[pos]]=pos;
          }
          cout<<ans<<endl;
      }
      return 0;
  }
  

T3682. 七负我

• 没学最大团，直接贺官方题解了，改了下 \(\LaTeX\) 。

  考虑两个没有边的点 \((u,v)\) ，设与 \(u\) 相连的点 \(t_{i}\) 的和为 \(a\) ，设与 \(v\) 相连的点 \(t_{i}\) 的和为 \(b\) ，那么这两个点原先的贡献为 \(t_u\times a + t_v\times b\) ，容易发现清空贡献较小的点可以使贡献变为 \((t_{u} + t_{v})\times \max(a,b)\) 。

  不断进行这样的操作，最终只剩下一个团。

  设团的大小为 \(n\) ，则边数为 \(\frac{n \times (n - 1)}{2}\) ，显然总贡献为 \((\frac{T}{n})^2 \times \frac{n \times (n - 1)}{2}\) ，简单化简发现 \(n\) 越大越好。
  因此只需要搜索最大团，比较常见的方法是 BK ，大家可以自行学习。

  还有一种折半搜索的方法，我们将所有点分为两个集合 \(A,B\) ，对于 \(A\) 中的所有点，维护 \(f_{S}\) 表示集合 \(S\) 中所有点组成子图中最大团大小。

  之后枚举 \(B\) 中的最大团 \(T\) ，找到最大团中所有节点向 \(S\) 集合连边的交集，显然 \(\operatorname{popcount}(T)+f_S\) 可以更新答案。