AtCoder Beginner Contest 318

https://atcoder.jp/contests/abc318

F - Octopus

题意

$x$ 坐标轴上有 $n$ 个物品，位置为 $x_1,x_2,\cdots,x_n$。现在有一只章鱼，处于坐标 $k$ 处，有长度为 $l_1,l_2,\cdots,l_n$ 的手臂，第 $i$ 条手臂可以抓取位置在 $[k-l_i,k+l_i]$ 的物品物品，每条手臂只能用于抓取一个物品。问有多少个位置满足能够抓到所有的物品。

数据范围：$1\leq n\leq 200,-10^{18}\leq x_1<x_2<\cdots<x_n\leq 10^{18},1\leq l_1\leq l_2\leq\cdots\leq l_n\leq 10^{18}$。

题解

感觉很educational的题目。

首先，考虑对于一个固定的位置，如何check：答案很容易，每次一定是抓取离它最近的物品，如果当前这条手臂够不到，那么一定不行，否则就可以。只需要将所有物品分为左侧和右侧，每次比较一下是左边最近的离得近还是右边最近的离得近就行了。时间复杂度为 $O(n)$。

但是，由于数据范围很大，不能对每个位置进行检验。可以这样考虑：由于物品的个数不太多，所以位置合法性的变化点不会很多，我们来考虑一下什么时候会变化。也就是下面两种情况：

• $k_0$ 合法，$k_0+1$ 不合法

  则必然有 $k_0-l_j\leq x_i\leq k_0+l_j$，且 $k_0+1-l_j>x_i$ 或 $k_0+l_j+1<x_i$（后一种情况是不可能的）。两个联立，可以得到 $k_0=x_i+l_j$。

• $k_0$ 不合法，$k_0+1$ 合法

  类似地，$k_0=x_i-l_j-1$。

所以我们一共得到了 $2n^2$ 个分界点，只需要对这些点进行check就可以了。若一个分界点合法，则从它左侧一直到前一个分界点的位置都是合法的。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=205;
int n;
ll x[N],l[N],k[2*N*N];
bool check(ll pos)
{
    vector<ll> l0,r0;
    for(int i=1;i<=n;i++)
        if(x[i]<pos) l0.push_back(x[i]);
        else r0.push_back(x[i]);
    reverse(r0.begin(),r0.end());
    for(int i=1;i<=n;i++)
    {
        ll d1=5e18,d2=5e18;
        if(!l0.empty()) d1=pos-l0.back();
        if(!r0.empty()) d2=r0.back()-pos;
        if(d1<d2)
        {
            if(d1>l[i]) return 0;
            l0.pop_back();
        }
        else
        {
            if(d2>l[i]) return 0;
            r0.pop_back();
        }
    }
    return 1;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>x[i];
    for(int i=1;i<=n;i++) cin>>l[i];
    sort(l+1,l+n+1);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) k[(i-1)*n+j]=x[i]+l[j];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) k[(i-1)*n+j+n*n]=x[i]-l[j]-1;
    sort(k+1,k+2*n*n+1);
    ll ans=0;
    for(int i=1;i<2*n*n;i++)
        if(check(k[i+1])) ans+=k[i+1]-k[i];
    cout<<ans<<'\n';
    return 0;
}

G - Typical Path Problem

题意

给出一张 $n$ 个点 $m$ 条边的无向连通图。给出 $a,b,c$ 三个点，询问是否有一条 $a$ 到 $c$ 的简单路径经过点 $b$。

数据范围：$3\leq n\leq 2\times10^5,n-1\leq m\leq \min(\dfrac{n\times(n-1)}{2},2\times 10^5)$。

题解

圆方树板题。建出圆方树以后判断一下 $a$ 到 $c$ 的树上路径经过的方点相邻的圆点是否包含 $b$ 即可。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,m,cnt;
vector<int> g[N],T[N*2];
int dfn[N],low[N],dfc;
int stk[N],tp;
int d[2*N],f[2*N][25];
void dfs(int u,int fa)
{
    d[u]=d[fa]+1;
    f[u][0]=fa;
    for(int i=0;i<20;i++)
        f[u][i+1]=f[f[u][i]][i];
    for(auto v:T[u])
        if(v!=fa) dfs(v,u);
}
int lca(int x,int y)
{
    if(d[x]<d[y]) swap(x,y);
    for(int i=20;i>=0;i--)
    {
        if(d[f[x][i]]>=d[y]) x=f[x][i];
        if(x==y) return x;
    }
    for(int i=20;i>=0;i--)
        if(f[x][i]!=f[y][i])
            x=f[x][i],y=f[y][i];
    return f[x][0];
}
void tarjan(int u) 
{
	low[u]=dfn[u]=++dfc;
	stk[++tp]=u; 
	for(auto v:g[u]) 
    { 
		if(!dfn[v]) 
        { 
			tarjan(v);
			low[u]=min(low[u],low[v]); 
			if(low[v]==dfn[u]) 
            { 
				cnt++;
				for(int x=0;x!=v;tp--) 
                {
					x=stk[tp];
					T[cnt].push_back(x);
					T[x].push_back(cnt);
				}
				T[cnt].push_back(u);
				T[u].push_back(cnt);
			}
		} else low[u]=min(low[u],dfn[v]); 
	}
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m;
    cnt=n;
    int a,b,c;cin>>a>>b>>c;
    for(int i=1;i<=m;i++)
    {
        int u,v;cin>>u>>v;
        g[u].push_back(v),g[v].push_back(u);
    }
    tarjan(1);
    dfs(1,0);
    int l=lca(a,c);
    bool ok=0;
    for(int i=a;i!=l;i=f[i][0])
    {
        if(i>n)
        {
            for(auto v:T[i])
                if(v==b) ok=1;
        }
    }
    for(int i=c;i!=l;i=f[i][0])
    {
        if(i>n)
        {
            for(auto v:T[i])
                if(v==b) ok=1;
        }
    }
    if(l>n)
    {
        for(auto v:T[l])
            if(v==b) ok=1;
    }
    cout<<(ok?"Yes":"No")<<'\n';
    return 0;
}