题解：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;
}