526互联

CF1914 G Light Bulbs 题解

发布时间 2023-12-20 12:00:46作者: Martian148

Link

CF1914 G Light Bulbs

Question

有 \(2n\) 盏灯摆放在一条直线上，每盏灯有一个颜色 \(a_i\) ，灯的颜色一共有 \(n\) 种，每个颜色的颜色的灯刚好两盏，灯开始都是熄灭的。你选择几盏灯先打开，然后通过以下规则让其他的灯打开

  • 选择 \(i,j\) 是相同颜色的，一盏亮，一盏不亮，你可以使两盏灯都亮起来
  • 选择 \(i,j,k\) 满足 \(i<j<k\) ，\(i,k\) 是相同颜色的，且 \(i,k\) 都是亮着的，你可以使 \(k\) 亮起来

求要让若有灯都亮起来，先打开的灯的最少数量和方案数

Solution

这道题有两个版本，easy 版是 \(O(n^2)\) 的，hard 版是 \(O(n)\) 的

首先，我们思考一个性质，就是一盏灯亮起来，另外一个相同颜色的灯也可以亮起来，这两个相同颜色的灯的中间的灯也能亮起来

我们可以把一种颜色的颜色的灯抽象成一条线段 \([L,R]\)

如果两条线段相交时，点亮其中一盏灯就可以点亮相交线段中的所有灯

image.png

如果两条线段包含，那么点亮外面的那条线段中的一盏灯即可

image.png

这样的相互关系有点像图论，我们就可以建边了

如果一个线段 \(A\) 的端点在另外一个线段 \(B\) 之中，那么建一条 \(B\Rightarrow A\) 的边，表示只需选择 \(B\) 中的一个端点就可以点亮 \(A\) 了

这个图中可能包含环，例如相交的情况，\(B \Rightarrow A\) 且 \(A \Rightarrow B\)

对于一个强连通分量，我们只需要点亮其中一盏灯就可以了

那么用 Tarjan 缩点，对于缩点后入度为 \(0\) 的点就需要手动点亮了，所以需要提前点亮的灯的数量就是缩点后入度为 \(0\) 的数量，方案数就是入度为 \(0\) 的点所包括灯的数量的乘积

这样做的时间复杂度是 \(O(n^2)\) 的，建边应该可以优化，但是我想不到

考虑另外一种解法

定义 \(F[i]\) 为前 \(i\) 个数的异或和，考虑到一个数异或两次对于没有异或，我们可以利用这个性质来解这道题

我们称一条线段里面的所有灯的种类都出现过两次，称这个线段"完全包含"

例如 1,2,2,1，1,2,3,2,3,1 ，在这两种情况里面 \(1\) 都是完全包含的，如果一个线段完全包含，那么我们只需要取左右两边那个灯，就可以把里面的灯全部点亮了

如果不是完全包含的情况，例如 1,2,1,2 那么，就可以取任意一盏灯

如果要取一盏灯，当且仅当，这盏灯没有 "被包含"，用异或的语言标答，就是前面的异或和为 \(0\)

如果这盏灯对应的线段是 "完全包含" 的，那么直接跳到下一盏一样颜色的灯，否则就往下继续寻找 “完全包含” 的线段，然后跳过找到的 "完全包含" 线段

答案的数量就是没有 "被包含" 的线段数量，方案数就是没有 “被包含” 的线段块 中灯的数量 的乘积

每个数最多被跳 \(1\) 次，所以复杂度为 \(O(n)\)

Code

Tarjan缩点

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL TT=998244353;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

struct Line{
    int L,R;
    Line(int L=0,int R=0):L(L),R(R){}
    bool operator <(const Line B) const{return L<B.L;}
};

vector<vector<int> > E;
struct Tarjan{
    int n;
    vector<int>dfn,low;int dfn_cnt;
    vector<int> scc;int sc; //节点 i 所在 SCC 的编号
    vector<int> siz; //强连通 i 的大小
    stack<int> st;
    vector<int> in_st;//判断是否在栈内

    void init(int n){
        this->n=n;
        dfn.resize(n+1);low.resize(n+1);dfn_cnt=0;
        scc.assign(n+1,0);sc=0;siz.assign(n+1,0);
        while(!st.empty())st.pop();
        in_st.assign(n+1,0);
    }

    void tarjan(int u){
        low[u]=dfn[u]=++dfn_cnt;st.push(u);in_st[u]=1;
        for(int i=0;i<E[u].size();i++){
            int& v=E[u][i];
            if(!dfn[v]){//没有访问过
                tarjan(v);
                low[u]=min(low[u],low[v]);
            }else if(in_st[v]){
                low[u]=min(low[u],dfn[v]);
            }
        }
        if(dfn[u]==low[u]){ //找到双连通分量了
            ++sc; 
            while(st.top()!=u){ //从栈顶到 u 都是这个强连通分量里面的
                scc[st.top()]=sc;siz[sc]++;
                in_st[st.top()]=0;st.pop();
            }
            scc[st.top()]=sc;siz[sc]++;
            in_st[st.top()]=0;st.pop();
        }
        return ;
    }
};

void solve(){
    int n=read();
    LL ans1=0,ans2=1;
    Tarjan F;F.init(n);
    vector<int> a(2*n+1);
    vector<Line> L(n+1,Line(0,0));
    E.assign(n+1,vector<int>());
    for(int i=1;i<=2*n;i++) a[i]=read();
    for(int i=1;i<=2*n;i++){
        if(L[a[i]].L==0) L[a[i]].L=i;
        else L[a[i]].R=i;
    }
    sort(L.begin()+1,L.begin()+1+n);
    for(int i=1;i<=n;i++)
    for(int j=max(1,i-1000);j<=min(n,i+1000);j++){
        if(i==j)continue;
        if((L[i].L<L[j].L&&L[i].R>L[j].L)||(L[i].L<L[j].R&&L[i].R>L[j].R)){ //j in i
            // printf(":%d %d\n",i,j);
            E[i].push_back(j);
        }
    }
    for(int i=1;i<=n;i++) if(!F.dfn[i])
        F.tarjan(i);
    
    vector<int> du(n+1,0);
    for(int u=1;u<=n;u++){
        for(int& v:E[u]){
            if(F.scc[u]!=F.scc[v])
                du[F.scc[v]]++;
        }
    }
    for(int i=1;i<=F.sc;i++){
        if(du[i]==0){
            ans1++;
            ans2=ans2*(F.siz[i]*2)%TT;
        }
    }
    printf("%lld %lld\n",ans1,ans2);
}
int main(){
    freopen("G1.in","r",stdin);
    int t=read();
    while(t--) solve();
}

Xor

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL TT=998244353;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int brand(){return (rand()<<15)|rand();}
LL bbrand(){
    return ((LL)brand()<<30)|brand();
}
void solve(){
    int n=read();LL ans1=0,ans2=1;
    vector<int> a(n*2,0);
    vector<LL> x(n,0);
    vector<LL> F(n*2+1,0);
    for(int i=0;i<n;i++)
        x[i]=bbrand()^2333;
    for(int i=0;i<2*n;i++){
        a[i]=read()-1;F[i+1]=F[i]^x[a[i]];  //F[i] 表示前 i-1 个数的异或和
    }
    map<LL,int> lst;
    for(int i=0;i<2*n;i++)
        lst[F[i]]=i;
    for(int i=0;i<2*n;i++){
        if(F[i]==0){
            LL cnt=1;ans1++;
            int j=i+1;
            while(F[j]!=0){
                cnt++;
                j=lst[F[j]];
                j++;
            }
            ans2=ans2*cnt%TT;
        }
    }
    cout<<ans1<<" "<<ans2<<endl;
}
int main(){
    freopen("G2.in","r",stdin);
    srand(time(0));
    int T=read();
    while(T--) solve();
}