题解：CF1907G. Lights-拓冰建站

题解：CF1907G. Lights

今天做数学题忘写圆锥体积的三分之一被骂了，所以心情不好，写得比较短。

题目链接：Problem - G - Codeforces。

本题对于每个灯对其他灯的影响，可以用一个出度均为一的有向图来表示。

对于每个a[i]，就相当于有一条从i连向a[i]的有向边，我们不难证明，一个点只会在最多一个环中出现（否则出度肯定大于1）。

我们可以把所有入读为0的点直接操作成关闭状态，并把变化（也可能没有）传递到它引向的点，最后只剩下若干个环。

遍历每个环，给该环上的每个点编号（记总点数为k），如果环内有奇数个亮灯，我们无法处理它（每次改变灯的亮灭情况不会改变它的总奇偶性，具体证明略），否则把所有亮灯列出来，很显然让相邻的两个灯相互抵消是消耗最小的，代价为他们的距离，那么这相邻的两个只有两种可能：“1和2、3和4、5和6、……、k-1和k”或“2和3、4和5、6和7、……、k和1”，取最优的一个就对了。

至于可以都灭掉时按那些开关，实际上每做一个点扔进vector就行了。

贴代码。

#include<bits/stdc++.h>
#define N 220000
using namespace std;
vector<int>out={};
set<int>st={};
string in="";
int edge[N]={},huan[N]={},sum[N]={},tmp[N]={},zero[N]={},ans=0,ans1=0,ans2=0,bg=0,cnt=0,cnth=0,cntt=0,ed=0,fst=0,lst=0,n=0,now=0,rest=0,t=0,then=0;
bool del[N]={},light[N]={},flag=false;
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        cin>>in;
        in=" "+in;
        for(int i=1;i<=n;i++){
            if(in[i]=='0'){
                light[i]=false;
            }else{
                light[i]=true;
            }
        }
        rest=n;
        for(int i=1;i<=n;i++){
            scanf("%d",&edge[i]);
            sum[i]=0;
            del[i]=false;
        }
        ans=0;
        for(int i=1;i<=n;i++){
            sum[edge[i]]++;
        }
        cnt=0;
        for(int i=1;i<=n;i++){
            if(sum[i]==0){
                cnt++;
                zero[cnt]=i;
            }
        }
        out.clear();
        while(cnt>0){
            cntt=0;
            for(int i=1;i<=cnt;i++){
                now=zero[i];
                then=edge[now];
                del[now]=true;
                rest--;
                sum[then]--;
                if(light[now]==true){
                    out.push_back(now);
                    ans++;
                    light[now]=false;
                    if(light[then]==false){
                        light[then]=true;
                    }else{
                        light[then]=false;
                    }
                }
                if(sum[then]==0){
                    cntt++;
                    tmp[cntt]=then;
                }
            }
            cnt=cntt;
            for(int i=1;i<=cnt;i++){
                zero[i]=tmp[i];
            }
        }
        st.clear();
        for(int i=1;i<=n;i++){
            if(del[i]==false){
                st.insert(i);
            }
        }
        flag=false;
        while(rest>0){
            ans1=0;
            ans2=0;
            bg=*st.begin();
            cnth=1;
            huan[cnth]=bg;
            now=bg;
            while(edge[now]!=bg){
                cnth++;
                huan[cnth]=edge[now];
                now=edge[now];
            }
            lst=-1;
            fst=-1;
            for(int i=1;i<=cnth;i++){
                now=huan[i];
                if(light[now]==true){
                    if(fst==-1){
                        fst=i;
                    }
                    if(lst==-1){
                        lst=i;
                    }else{
                        ans1+=i-lst;
                        lst=-1;
                    }
                }
            }
            if(lst!=-1){
                flag=true;
                break;
            }
            lst=-1;
            ed=0;
            for(int i=fst+1;i<=cnth;i++){
                now=huan[i];
                if(light[now]==true){
                    ed=i;
                    if(lst==-1){
                        lst=i;
                    }else{
                        ans2+=i-lst;
                        lst=-1;
                    }
                }
            }
            ans2+=fst+cnth-ed;
            if(ans1<ans2){
                lst=-1;
                for(int i=1;i<=cnth;i++){
                    now=huan[i];
                    if(light[now]==true){
                        if(lst==-1){
                            lst=i;
                        }else{
                            for(int j=lst;j<i;j++){
                                out.push_back(huan[j]);
                            }
                            lst=-1;
                        }
                    }
                }
                ans+=ans1;
            }else{
                lst=-1;
                ed=0;
                for(int i=fst+1;i<=cnth;i++){
                    now=huan[i];
                    if(light[now]==true){
                        ed=i;
                        if(lst==-1){
                            lst=i;
                        }else{
                            for(int j=lst;j<i;j++){
                                out.push_back(huan[j]);
                            }
                            lst=-1;
                        }
                    }
                }
                for(int i=ed;i<=cnth;i++){
                    out.push_back(huan[i]);
                }
                for(int i=1;i<fst;i++){
                    out.push_back(huan[i]);
                }
                ans+=ans2;
            }
            for(int i=1;i<=cnth;i++){
                st.erase(huan[i]);
                rest--;
            }
        }
        if(flag==true){
            printf("-1\n");
        }else{
            printf("%d\n",ans);
            for(int i:out){
                printf("%d ",i);
            }
            printf("\n");
        }
    }
    return 0;
}