首先考虑 $c=0$ 的情况。（下称第一行读入为 $l_i$，第二行读入为 $r_i$）

注意到题目中说可以任意排列，所以实际上牛的顺序并不重要，重要的只有他们给出的信息。

所以将一头牛的 $l_i$ 与 $r_i$ 压缩成同一个状态，共有四个（记每种状态的数量为 $num$）。见下表：

状态	对应的 $l_i$ 与 $r_i$
$1$	$l_i=r_i=$ J
$2$	$l_i=r_i=$ N
$3$	$l_i=$ J,$r_i=$ N
$4$	$l_i=$ N,$r_i=$ J

考虑枚举相邻两头牛的状态，得到下表：

相邻牛的状态	左侧牛的 $r_i$	右侧牛的 $l_i$
NN	J
NJ	N
JN
JJ	J

可以发现，每一个上方的 J 都会相应地对应一个下方的 J，所以得到第一个无解条件：上下方的 J 数量不相等。

结合上面对状态的定义，也可以转换成 $num_3 {=}\mathllap{/\,} num_4$。

思考每种状态之后的下一个能接的状态，发现需要满足前者的 $r_i$ 与后者的 $l_i$ 相等。于是有：

状态	下一个状态
$1$	$1,3$
$2$	$2,4$
$3$
$4$	$1,3$

接下来，问题转化为如下问题：

给定四种状态的数量，每种状态后都有下一个能走的状态，求一种放置方案使得最后一个与第一个能连上。

建图，考虑如何跑（交给读者自证，结论还是 $num_3 {=}\mathllap{/\,} num_4$ 时无解）。

我们思考跑的流程，注意到由 NN 建起来的边经过时会导致状态反转，所以将这些边的边权设为 $1$，所以如果跑完并且回到开头时边权和为奇数，则无解。

进一步观察，所有的边权为 $1$ 的边都是 $2$ 状态和 $3$ 状态的出边，所以这两个点每经过一次就会使边权和 $+1$，所以如果 $num_2+num_3∤2$ 则无解。

再想想，前两种情况之后必定有 $num_3=num_4$，所以如果 $num_3=0$ 且 $1$ 与 $2$ 两个都不为 $0$ 的时候，因为两者间的连边断掉，那么必定无解。

于是，我们完成了 $c=0$ 的判断。

对于构造，因为 $3,4$ 之间在图上构成了一个环，又有 $num_3=num_4$，所以消耗掉全部的 $1$ 和 $2$ 之后去一直跑环即可。

对于一个跑出来的状态序列，我们直接假定第一个是 J，后面的根据走的边去填即可。

代码：

#include<bits/stdc++.h>
using namespace std;
bool cnt1[100005];
bool cnt2[100005];
int lx[100005];
int ans[100005];
int num[10];
int main(){
	int t,c;
	cin>>t>>c;
	while(t--){
		memset(num,0,sizeof(num));
		int n;
		cin>>n;
		//0为N，1为J 
		for(int i=1;i<=n;i++){
			char d;
			cin>>d;
			cnt1[i]=d-'N';
		}
		for(int i=1;i<=n;i++){
			char d;
			cin>>d;
			cnt2[i]=d-'N'; 
		}
		queue<int> q[5];
		for(int i=1;i<=n;i++){
			if(cnt1[i]^cnt2[i]){
				if(cnt1[i]){
					//类型3
					lx[i]=3;
					num[3]++;
					q[3].push(i); 
				}
				else{
					//类型4
					lx[i]=4;
					num[4]++;
					q[4].push(i);
				}
			}
			else{
				if(cnt1[i]){
					//类型1
					lx[i]=1;
					num[1]++;
					q[1].push(i);
				}
				else{
					//类型2 
					lx[i]=2;
					num[2]++;
					q[2].push(i);
				}
			}
		}
		if(num[3]!=num[4] || (num[2]+num[3])%2 || (num[3]==0 && num[1]!=0 && num[2]!=0)){
			cout<<"NO\n";
		}
		else{
			cout<<"YES\n";
			if(c==1){
				int ji=0;
				if(num[3]==0){
					while(q[1].size()){
						ans[++ji]=q[1].front();
						q[1].pop();
					}
					while(q[2].size()){
						ans[++ji]=q[2].front();
						q[2].pop();
					}
				}
				else{
					if(num[1]==0){
						ans[1]=q[4].front();
						q[4].pop();
						ans[2]=q[3].front();
						q[3].pop();
						ji=2;
						while(q[2].size()){
							ans[++ji]=q[2].front();
							q[2].pop();
						}
						while(q[4].size()){
							ans[++ji]=q[4].front();
							q[4].pop();
							ans[++ji]=q[3].front();
							q[3].pop();
						}
					}
					else{
						while(q[1].size()){
							ans[++ji]=q[1].front();
							q[1].pop();
						}
						ans[++ji]=q[3].front();
						q[3].pop();
						while(q[2].size()){
							ans[++ji]=q[2].front();
							q[2].pop();
						}
						ans[++ji]=q[4].front();
						q[4].pop();
						while(q[3].size()){
							ans[++ji]=q[3].front();
							q[3].pop();
							ans[++ji]=q[4].front();
							q[4].pop();
						} 
					}
				}
				for(int i=1;i<=n;i++){
					cout<<ans[i]<<" \n"[i==n];
				}
				bool flag=1;
				cout<<"J";
				for(int i=2;i<=n;i++){
					if(lx[ans[i-1]]==3 || lx[ans[i-1]]==2){
						flag=!flag;
					}
					if(flag){
						cout<<"J";
					}
					else{
						cout<<"N";
					}
				}
				cout<<"\n";
			}
		}
	}
} 

题目大意

题目描述清楚，不做赘述

解题思路

一、判断 $YES/NO$

牛分为“真话牛”与“假话牛”两种，不妨记“真话牛”为 $1$ ，“假话牛”为 $0$ 牛对左右的描述便可以归为 {$L[i]，R[i]$} $=$ {$0$ , $0$} 或 {$0$ , $1$} 或 {$1$ , $0$} 或 {$1$ , $1$} 或四种，进行分类讨论

这里有一头牛 $x$ ，ta身边坐着牛 $y$ 若 $x$ 为 $1$ $：①$ $x$ 说 $y$ 是 $1$ ，则 $y$ 会说 $x$ 为 $1$ ；反之，说 $x$ 是 $0$

若 $x$ 为 $0$ $：①$ $x$ 说 $y$ 是 $1$ ，则 $y$ 会说 $x$ 为 $1$ ；反之，说 $x$ 是 $0$

观察到，两头相邻的牛无论本身说不说谎，对对方的描述都是一致的，

故有$:1.$ 对于任意 $1≤i<n$ 有 $R[i]＝L[i+1]$ ，且 $R[n]＝L[1]$；$2.$ 若$1≤i<n$，且 $R[i]=L[i+1]=0$ ，则牛 $i$ 与牛 $i+1$ 的“说谎”属性不同

得出这个结论后，便可以对 $YES/NO$ 进行判断，得到有且仅有的三种 $NO$ 的情况： $①：$ $R$ 与 $L$ 中 $0$ 的数量不同，即 $Σ_{i=1}^{n}R[i]≠Σ_{i=1}^{n}L[i]$

$②：$ $R(L)$ 中的 $0$ 数量不为偶数，即 $(n-Σ_{i=1}^{n}R[i])$ $mod$ $2=1$

$③：$ 仅存在 {$L[i]，R[i]$} $=$ {$0$ , $0$} 与 {$L[i]，R[i]$} $=$ {$1$ , $1$}

其余情况皆为 $YES$

二、进行构造

“故有$:1.$ 对于任意 $1≤i<n$ 有 $R[i]＝L[i+1]$ ，且 $R[n]＝L[1]$；$2.$ 若$1≤i<n$，且 $R[i]=L[i+1]=0$ ，则牛 $i$ 与牛 $i+1$ 的“说谎”属性不同”

根据这一结论，不难想到答案为 “$11...100...011...100...$” 如此循环往复，考虑将牛按对左右描述的不同分为四类，存一个队列，用的时候取出来即可

    ans1[1]=1;ans2[1]=1;
    int lst=1;
    for(int i=2;i<=n;i++){
      for(int j=0;j<=1;j++){
        if(q[R[lst]][j].size()){
          int x=q[R[lst]][j].front();q[R[lst]][j].pop();
          
          if(x==1){
            if(!q[R[lst]][j].size())continue;
            x=q[R[lst]][j].front();q[R[lst]][j].pop();
          }
          
          ans1[i]=x;
          if(ans2[i-1])ans2[i]=R[lst];
          else ans2[i]=R[lst]^1;
          lst=ans1[i];
          break;
        }
      }
    }

直接按上述方法进行构造即可这只能拿56pts

思考下面这组例子

4
JNJN
JNNJ

若前 $3$ 头牛构造出 $1$ $3$ $4$ 显然合法，但考虑到 $2$ 号牛时便不合法

故应尽量减少 $J$ 与 $N$ 间的转换，构造形如 $JJ...JNN...NJJ...J$ 的答案

在循环前增加判断即可，无需修改循环内部内容

修改后代码：

  if(R[lst]==0)for(int j=0;j<=1;j++){
			if(q[R[lst]][j].size()){
				int x=q[R[lst]][j].front();q[R[lst]][j].pop();
				
				if(x==1){
					if(!q[R[lst]][j].size())continue;
					x=q[R[lst]][j].front();q[R[lst]][j].pop();
				}
				
				ans1[i]=x;
				if(ans2[i-1])ans2[i]=R[lst];
				else ans2[i]=R[lst]^1;
				lst=ans1[i];
				break;
			}
		}
		else for(int j=1;j>=0;j--){
			if(q[R[lst]][j].size()){
				int x=q[R[lst]][j].front();q[R[lst]][j].pop();
				
				if(x==1){
					if(!q[R[lst]][j].size())continue;
					x=q[R[lst]][j].front();q[R[lst]][j].pop();
				}
				
				ans1[i]=x;
				if(ans2[i-1])ans2[i]=R[lst];
				else ans2[i]=R[lst]^1;
				lst=ans1[i];
				break;
			}
		}

100pts完整代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 100010
bool C;
int n;
queue<int>q[2][2];
int L[N],R[N];
int ans1[N],ans2[N];
void solve(){
	memset(L,0,sizeof(L));memset(R,0,sizeof(R));
	for(int i=0;i<2;i++)for(int j=0;j<2;j++){
		while(q[i][j].size())q[i][j].pop();
	}
	
	cin>>n;
	for(int i=1;i<=n;i++){
		char c;cin>>c;
		if(c=='J')L[i]=1;
		else L[i]=0;
	}
	for(int i=1;i<=n;i++){
		char c;cin>>c;
		if(c=='J')R[i]=1;
		else R[i]=0;
	}
	
	int L1=0,R1=0;
	for(int i=1;i<=n;i++){
		q[L[i]][R[i]].push(i);
		L1+=L[i],R1+=R[i];
	}
	if(L1!=R1){
		cout<<"NO\n";
		return;
	}
	if((n-L1)%2==1){
		cout<<"NO\n";
		return;
	}
	if(q[0][1].size()==0&&q[0][0].size()&&q[1][1].size()){
		cout<<"NO\n";
		return;
	}
	
	ans1[1]=1;ans2[1]=1;
	int lst=1;
	for(int i=2;i<=n;i++){
		if(R[lst]==0)for(int j=0;j<=1;j++){
			if(q[R[lst]][j].size()){
				int x=q[R[lst]][j].front();q[R[lst]][j].pop();
				
				if(x==1){
					if(!q[R[lst]][j].size())continue;
					x=q[R[lst]][j].front();q[R[lst]][j].pop();
				}
				
				ans1[i]=x;
				if(ans2[i-1])ans2[i]=R[lst];
				else ans2[i]=R[lst]^1;
				lst=ans1[i];
				break;
			}
		}
		else for(int j=1;j>=0;j--){
			if(q[R[lst]][j].size()){
				int x=q[R[lst]][j].front();q[R[lst]][j].pop();
				
				if(x==1){
					if(!q[R[lst]][j].size())continue;
					x=q[R[lst]][j].front();q[R[lst]][j].pop();
				}
				
				ans1[i]=x;
				if(ans2[i-1])ans2[i]=R[lst];
				else ans2[i]=R[lst]^1;
				lst=ans1[i];
				break;
			}
		}
	}
	
	cout<<"YES\n";
	if(C){
		for(int i=1;i<=n;i++)cout<<ans1[i]<<' ';cout<<'\n';
		for(int i=1;i<=n;i++)cout<<(ans2[i]?"J":"N");cout<<'\n';
	}
}
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int _;cin>>_>>C;
	while(_--)solve();
	
	return 0;
}

(结束后10秒AC...)

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int l[N],r[N],L[2],R[2],t[N],p[N];
stack<int>Q[4];
map<pair<int,int>,int>mp;
bool v[N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	mp[{1,1}]=1;
	mp[{0,1}]=0;
	mp[{1,0}]=0;
	mp[{0,0}]=1;
	int T,op;
	int last=0;
	cin>>T>>op;
	while(T--)
	{
		L[0]=0;
		L[1]=0;
		R[0]=0;
		R[1]=0;
		if(last)
		{
			for(int i=1;i<=last;i++)
			{
				v[i]=0;
			}
		}
		int n;
		cin>>n;
		last=n;
		string s1,s2;
		cin>>s1>>s2;
		for(int i=0;i<n;i++)
		{
			if(s1[i]=='J')
			{
				l[i+1]=1;
				L[1]++;
				Q[1].push(i+1);
			}
			else
			{
				l[i+1]=0;
				L[0]++;
				Q[0].push(i+1);
			}
		}
		for(int i=0;i<n;i++)
		{
			if(s2[i]=='J')
			{
				r[i+1]=1;
				R[1]++;
			}
			else
			{
				r[i+1]=0;
				R[0]++;
			}
		}
		bool flag=1;
		for(int i=1;i<=n;i++)
		{
			if(l[i]!=r[i])
			{
				flag=0;
			}
		}
		bool bk=1;
		if(flag&&L[0]&&L[1])
		{
			cout<<"NO\n";
			bk=0;
		}
		else if((L[0]==R[0])&&(L[0]%2==0))
		{
			cout<<"YES\n";
		}
		else
		{
			cout<<"NO\n";
			bk=0;
		}
		if(bk&&op)
		{
			for(int i=0;i<4;i++)
			{
				while(Q[i].size())
				{
					Q[i].pop();
				}
			}
			for(int i=1;i<=n;i++)
			{
				if(l[i]==0&&r[i]==0)
				{
					Q[0].push(i);
				}
				else if(l[i]==0&&r[i]==1)
				{
					Q[1].push(i);
				}
				else if(l[i]==1&&r[i]==0)
				{
					Q[2].push(i);
				}
				else
				{
					Q[3].push(i);
				}
			}
			int m=0;
			while(Q[0].size())
			{
				int x=Q[0].top();
				Q[0].pop();
				p[++m]=x;
				t[x]=mp[{t[p[m-1]],r[p[m-1]]}];
			}
			if(Q[1].size())
			{
				int x=Q[1].top();
				Q[1].pop();
				p[++m]=x;
				t[x]=mp[{t[p[m-1]],r[p[m-1]]}];
			}
			while(Q[3].size())
			{
				int x=Q[3].top();
				Q[3].pop();
				p[++m]=x;
				t[x]=mp[{t[p[m-1]],r[p[m-1]]}];
			}
			while(Q[1].size())
			{
				int x=Q[2].top();
				Q[2].pop();
				p[++m]=x;
				t[x]=mp[{t[p[m-1]],r[p[m-1]]}];
				x=Q[1].top();
				Q[1].pop();
				p[++m]=x;
				t[x]=mp[{t[p[m-1]],r[p[m-1]]}];
			}
			if(Q[2].size())
			{
				int x=Q[2].top();
				Q[2].pop();
				p[++m]=x;
				t[x]=mp[{t[p[m-1]],r[p[m-1]]}];
			}
			for(int i=1;i<=m;i++)
			{
				cout<<p[i]<<" ";
			}
			cout<<"\n";
			for(int i=1;i<=m;i++)
			{
				if(t[p[i]])
				{
					cout<<"J";
				}
				else
				{
					cout<<"N";
				}
			}
			cout<<"\n";
		}
	}
	return 0;
} 

初赛告诉我们，相邻两头牛彼此的看法一定相同。自己列表证吧这里不说明了。

这就说明上下两行的字符集一定要相同。

然后，列完表以后发现一个合法的情况翻转身份依然合法。

于是不妨钦定一号位是好人。

如果 $\texttt N$ 的数量是奇数，那么转一圈回来得出结论一号位是坏人。啊？？？

于是这也无解。

因为第一条，我们注意到这个东西是一个链状物，头尾相接。

如果只有 $\texttt{NN}$ 和 $\texttt{JJ}$ 那么接不起来，也无解。

---

接下来考虑构造。

显然 $\texttt{NN}$ 可以整个放在一起。然后 $\texttt{JJ}$ 同理。

显然满足条件后 $\texttt{NJ}$ 和 $\texttt{JN}$ 数量相同然后这个东西可以两两配对后首尾相接。

于是直接构造就好。

最终的序列是这样的：

$$\texttt{JN,NN,\dots,NN,NJ,JJ,\dots,JJ,JN,NJ,JN,NJ,\dots}$$

然后把标号投射回去。

最后按照构造出来的序列按照一号位为好人为基准把信息顺着推下去就做完了。

注意实现细节和边界问题。

#include<bits/stdc++.h>
#define lowbit(x) x&(-x)
#define mod 998244353
#define int long long
using namespace std;
int op;
vector<int>ve[4];
int a[100005];
void solve(){
    for(int i=0;i<4;i++)
    ve[i].clear();
    int n;
    cin>>n;
    string s,t;
    cin>>s>>t;
    s=" "+s;
    t=" "+t;
    int sum1=0;
    for(int i=1;i<=n;i++)
    sum1+=s[i]=='N';
    int sum2=0;
    for(int i=1;i<=n;i++)
    sum2+=t[i]=='N';
    if(sum1!=sum2||sum1&1){
        cout<<"NO\n";
        return;
    }
    for(int i=1;i<=n;i++){
        int x=0;
        if(s[i]=='J')x=2;
        if(t[i]=='J')x++;
        a[i]=x;
        ve[x].push_back(i);
    }
    if(ve[1].size()==0&&ve[3].size()&&ve[0].size()){
        cout<<"NO\n";
        return;
    }
    cout<<"YES\n";
    if(!op)return;
    vector<int>ret;
    for(int i=0;i<ve[3].size();i++)
    ret.push_back(ve[3][i]);
    if(!ve[2].empty())
    ret.push_back(ve[2][0]);
    for(int i=0;i<ve[0].size();i++)
    ret.push_back(ve[0][i]);
    if(!ve[1].empty())
    ret.push_back(ve[1][0]);
    for(int i=1;i<ve[1].size();i++)
    ret.push_back(ve[2][i]),
    ret.push_back(ve[1][i]);
    cout<<ret[0];
    for(int i=1;i<ret.size();i++)
    cout<<' '<<ret[i];
    cout<<'\n';
    string ans;
    ans+='J';
    char lst='J';
    for(int i=0;i<ret.size()-1;i++){
        if((a[ret[i]]&1)==0)
        lst=(lst=='J'?'N':'J');
        ans+=lst;
    }
    cout<<ans<<'\n';
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int t=1;
    cin>>t>>op;
    while(t--)solve();
    return 0;
}
// 来到这个国家以来，至今为止所做的一切似乎没有任何意义。

// 我点头答应官员先生的委托、带她离开可恶的国家、策划让她获得自由。
// 与此同时，我赋予她能够打猎维生的环境，这才终于让她回到这个家。

// 我原本以为，做到这个地步——
// 只要带她离开那个国家、远离人群，可怜的少女就能恢复正常。

// 但是不行呢。

// 结果，那只不过是我一厢情愿的盼望。

第一次打 USACO 结果 AK 完银组没时间打金组……