AtCoder ARC 136 pB. Triple Shift 解題心得( 題目 )
解題概念:群論
解題方法:這題我們可以把題目的shift當成三循環，如果有轉過3*3*3的魔術方塊的話應該知道三循環無解的狀況是只有兩個角或兩個邊對調的情況，這種情況照理不可能發生(除非有拆解過)，所以也無解，在這我們把她稱作parity(雖然這是四階特殊情形的稱呼)，在這題同樣也可套用(證明略)，解題流程如下:
先判斷上下內容一不一樣，如果不一樣一定無解，接著找尋有沒有兩個一樣的元素，如果有不管如何一定有解(因為在之後的流程中，如果真的遇到parity，也可以透過兩個一樣的東西交換，以達到解決)，如果沒有的話，再來就是暴力法把前面n-3個元素歸位，檢查剩下能否透過彼此shift解決，如果不行就是parity，也就是無解。
方法複雜度為O(N^2)，另外這題也有O(NlogN)的解，讀者可以想想看!
Java參考程式碼(更好意見可留言於下方，謝謝!):
//Author:En Chi Tsung(欉恩祁)
//Date:2022/03/06
import java.util.*;
import java.io.*;
public class Main {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
public static int ret,rd;
public static int[] A=new int[5005];
public static int[] B=new int[5005];
public static void main(String[] args) throws Exception{
final int n=readint();
int[] a=new int[n];
int[] b=new int[n];
for(int i=0;i<n;i++) {
A[i]=readint();
a[i]=A[i];
}
for(int i=0;i<n;i++) {
B[i]=readint();
b[i]=B[i];
}
int la=-1;
boolean ans=true;
boolean rep=false;
Arrays.parallelSort(a);
Arrays.parallelSort(b);
for(int i=0;i<n;i++) {
if(la==a[i])rep=true;
if(a[i]!=b[i]) {
ans=false;
break;
}
la=a[i];
}
if(!ans) {
System.out.println("No");
}
else {
if(rep) {
System.out.println("Yes");
}
else {
run(n);
}
}
}
public static void run(int n) {
int idx,tem;
for(int i=0;i<n-3;i++) {
idx=0;
while(idx<n-2&&A[idx]!=B[i]) {
idx++;
}
if(A[idx]!=B[i]) {
tem=A[idx];
A[idx]=A[idx+1];
A[idx+1]=A[idx-1];
A[idx-1]=tem;
}
for(;idx>i;idx--) {
A[idx]=A[idx+1];
A[idx+1]=A[idx-1];
A[idx-1]=B[i];
}
}
if(A[n-3]==B[n-3]&&A[n-2]==B[n-2]&&A[n-1]==B[n-1]) {
System.out.println("Yes");
}
else if(A[n-3]==B[n-2]&&A[n-2]==B[n-1]&&A[n-1]==B[n-3]) {
System.out.println("Yes");
}
else if(A[n-3]==B[n-1]&&A[n-2]==B[n-3]&&A[n-1]==B[n-2]) {
System.out.println("Yes");
}
else {
System.out.println("No");
}
}
public static int readint() throws Exception{
ret=0;
rd=br.read();
while(rd>47&&rd<58) {
ret*=10;
ret+=(rd&15);
rd=br.read();
}
return ret;
}
}
文章標籤
全站熱搜
留言列表
