首页 > 其他分享 >CF1956F Nene and the Passing Game 题解

CF1956F Nene and the Passing Game 题解

时间:2024-11-07 20:46:32浏览次数:5  
标签:CF1956F dl Nene 题解 GCC int maxn 区间 fill

处理很妙的题,部分细节请教了 未来姚班zylLYH_cpp,在此鸣谢。

首先考虑把题目给的式子进行转化,设 \(i < j\),那么 \(i\) 和 \(j\) 能传球当且仅当 \(l_i + l_j \le j - i \le r_i + r_j\)。

移项并拆开得到,\(i + l_i \le j - l_i\) 且 \(i + r_i \ge j - r_j\),如果画到数轴上的话就能发现这个条件等价于 \(i\) 的右半区间和 \(j\) 的左半区间相交了。

如果把这种能传球的关系看作是一条边,那么不难发现,一个连通块内的所有点都能在一次计划内完成,那么答案就是连通块的个数。

于是我们有了一个 \(O(n^2\alpha(n))\) 的做法,枚举两两点然后连边查答案。

考虑怎么优化,这里用到了处理连通性问题时常用的方法。

我们转换思路,从枚举人连边变成枚举人然后向它的左右区间连边,通过值域上的虚点保证连通性。

注意到这是一个经典的点 \(x\) 向区间 \([l, r]\) 连边查连通块个数的做法,可行的做法有 \(O(n \log n\alpha(n))\) 的线段树优化建图,以及均摊 \(O(n\alpha(n))\) 的并查集做法。

不过我们忽视了一个问题,如果通过中间点构造联通的话,会出现多个点都通过左区间或者都通过右区间相连的情况。

对于这种情况,我们有这样精妙的处理:
我们考虑只保留同时被某个点的左区间覆盖并且同时被某个点的右区间覆盖的点。

这样为什么是对的呢?我们分情况来考虑。

如果一个点只被左区间或者只被右区间覆盖到了,显然这个时候没有点能够通过该点进行 左-右 的联通。

而如果一个点两种区间都有,那么由于题目提到了 一个人可以在一次训练中重复多次,那么假设覆盖的左区间分别来自 \(L_1, L_2, \cdots, L_n\),右区间至少有一个,设其为 \(R\),有方案 \(L_1RL_2R\cdots L_nR\) 可以是一种合法的方案,并且完成了所有覆盖该点的任务。

于是我们可以用差分维护值域上的每个点是否同时被左右区间覆盖了,时间复杂度 \(O(n\alpha(n))\)。

// 如果命运对你缄默, 那就活给他看。
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast", "inline", "-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include <bits/stdc++.h>
using namespace std;
typedef long long LL; 
// #define int LL
const int maxn = 4e6 + 10;
int dl[maxn], dr[maxn], n;
int l[maxn], r[maxn];
int f[maxn];
int pr[maxn], nx[maxn], tot;
int v[maxn];
inline int find(int x) { return f[x] == x ? f[x] : f[x] = find(f[x]); }
inline void clear() {
  tot = 0;
  fill(v + 1, v + 1 + n, 0);
  fill(dl + 1, dl + 1 + n, 0);
  fill(dr + 1, dr + 1 + n, 0);
  fill(f + 1, f + n + n + 1, 0);
  fill(pr + 1, pr + 1 + n, 0);
  fill(nx + 1, nx + 1 + n, 0);
}
inline void mg(int x, int y) {
  x = find(x), y = find(y);
  if(x ^ y) f[y] = x;
}
inline void solve() {
  cin >> n;
  clear();
  for(int i = 1; i <= n; ++ i) {
    f[i] = i;
    cin >> l[i] >> r[i];
    dl[max(1, i - r[i])] ++ ;
    dl[max(1, i - l[i] + 1)] -- ;
    dr[min(n, i + l[i])] ++ ; 
    dr[min(n, i + r[i] + 1)] -- ;
  }
  for(int i = 1; i <= n; ++ i) {
    dl[i] += dl[i - 1];
    dr[i] += dr[i - 1];
    if(dl[i] && dr[i]) {
      pr[i] = nx[i] = ++ tot;
      f[n + tot] = n + tot;
    } else {
      pr[i] = pr[i - 1];
    }
  }
  nx[n + 1] = INT_MAX;
  for(int i = n; i; -- i) {
    if(!nx[i]) {
      nx[i] = nx[i + 1];
    }
  }
  for(int i = 1, ql, qr; i <= n; ++ i) {
    ql = nx[max(1, i - r[i])];
    qr = pr[max(0, i - l[i])];
    if(ql <= qr) {
      v[ql] ++, v[qr] -- ;
      mg(i, qr + n);
    }
    ql = nx[min(n + 1, i + l[i])];
    qr = pr[min(n, i + r[i])];
    if(ql <= qr) {
      v[ql] ++, v[qr] -- ;
      mg(i, qr + n);
    }
  }
  for(int i = 1; i <= tot; ++ i) v[i] += v[i - 1];
  for(int i = 1; i <= tot; ++ i) {
    if(v[i]) {
      mg(i + n, i + 1 + n);
    }
  }
  int ans = 0;
  for(int i = 1; i <= n + tot; ++ i) {
    ans += f[i] == i;
  }
  cout << ans << '\n';
}
signed main() {
  // freopen(".in", "r", stdin);
  // freopen(".out", "w", stdout);
  ios :: sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  int T;
  cin >> T;
  while(T -- ) solve();
  return 0;
}

标签:CF1956F,dl,Nene,题解,GCC,int,maxn,区间,fill
From: https://www.cnblogs.com/Rainsheep/p/18533961

相关文章

  • 题解:P11253 [GDKOI2023 普及组] 小学生数学题
    所求的式子带除法,模意义下除法计算复杂度带\(\log\)太慢了,先改写成乘法:\(\sum_{i=1}^ni!\timesi^{-k}\)。想求这个式子,最简单的思路就是对于每个整数\(i\in[1,n]\),分别预处理出\(i!\)和\(i^{-k}\)的值,最后乘起来再\(O(n)\)暴力加起来就好了!对于\(i!\),注意到:\[i!=\b......
  • P4621 [COCI2012-2013#6] BAKTERIJE 题解
    一道很好的数学题。首先不难想到每个细菌的移动路线是有循环节的,循环节外的时间最多就是每个格子的四个方向都走一遍,也就是\(4\timesN\timesM\)。可以预处理每个细菌分别通过四个方向第一次到达终点的时间\(b_{i,0/1/2/3}\)和再次回到当前状态的循环节长度\(md_{i,0/1/2/......
  • 题解:[BZOJ2958] 序列染色
    ProblemLinkBZOJ2958序列染色题意给出一个长度为\(n\),由\(\ttB,W,X\)三种字符组成的字符串\(S\),你需要把每一个\(\ttX\)染成\(\ttB\)或\(\ttW\)中的一个。Solution字符串,染色,方案数,一眼\(dp\)。要求前半段是B,后半段是W。考虑容斥。\(f_{i,0/1},g_{i,......
  • IOR的脚本化、版本兼容性及常见问题解答
    脚本化IOR可以使用-f选项在命令行中使用输入脚本。在-f选项之前设置的命令行选项将被视为运行脚本的默认设置。例如:mpirun./ior-W-fscript将使用隐式-W运行脚本中的所有测试。脚本本身可以覆盖这些设置,并且可以设置为在一次执行下运行许多不同的IOR测试,重要的是要注意在-......
  • 【题解】CF1944
    CF1944A简要题意给定完全图删k条边使得从一号点开始的可达点最少Solution注意到最多需要删n-1条边就可以使得任意一个其他点都到达不了又注意到只要删的边少于n-1就可以从一号点走出去,主要走出去就可以走到任何点所以这题答案只有两种如果k≤n-1答案为n否则答案为1......
  • 题解:P11248 [GESP202409 七级] 矩阵移动
    题目传送门题目大意给出一个nnn行mmm列的只包含0、1、?的矩......
  • 【记录】Cordial Sync具身智能协作源码复现及问题解决
    论文简要总结智能体需要合作将家具移动到客厅的指定位置。这个任务与现有的任务不同,它要求智能体在每个时间步都必须进行协调。模型部分1.SYNC-policies(SynchronizeYourActionsCoherently)为了解决智能体在每个时间步都需要协调的问题,研究者提出了SYNC-policies。这......
  • AtCoder Beginner Contest 284题解
    AtCoderBeginnerContest284A没有什么难点,反着输出一遍就可以了。#include<bits/stdc++.h>usingnamespacestd;stringa[2000];intmain(){ intn; cin>>n; for(inti=1;i<=n;i++)cin>>a[i]; for(inti=n;i;i--)cout<<a[i]<<'\n';......
  • 题解:HDU5628 Clarke and math
    数学题可爱捏~HintAnalysis注意到形式很好看,猜测是某种神奇迭代。考虑特殊情况\(k=1\),于是有:\(g(i)=\sum_{i_1\midi}f(i_1)=(f*1)(i)\)$即\(g=f*1\)。于是猜测\(g=f*1^k\),这里的幂运算表示多次Dirichlet卷积。简单证明一下,采用数学归纳法:基本情况\(k=1\),已经证过,......
  • 毕设拯救计划(二)基于QT的智能家居(Onenet云)
    文章目录前言一、效果展示二、设计思路2.1Mqtt的实现2.2音乐播放器的实现2.3虚拟键盘三、问题杂谈免责声明前言  前段时间,笔者觉得以前的STM32的智能家居太low了,于是想对其进行改进,目前的方案有以下两种:一、STM32和Linux开发板构成完整的智能车家系统,即通过MQ......