[TIOJ 1455] 切義大利蛋糕問題

作法：

首先可以從題目給的條件得到原始的蛋糕一定有一個地方可以切，所以大概可以想到其實滿足這個條件的蛋糕一定可以把它切完。所以假設現在 a , b , c 是滿足他們顏色不同的三個相鄰頂點，如果 a 的左邊和 b 同色或是 c 的右邊和 b 同色，那就可以安心的把 abc 切掉並滿足剩下的蛋糕還存在可以切的三角形。而如果沒有滿足的話，代表 a 左邊根 c 同色， c 右邊根 a 同色，這時候只要切掉 b c 和 c 的右邊就可以了。

code :

#include<bits/stdc++.h>
#include"lib1455.h"
using namespace std ;
const int maxn=1000+10 ;
 
int las[maxn],nex[maxn],n,head ;
char s[maxn] ;
int a[maxn] ;
 
bool check(int x,int y,int z)
{
    return !(a[x]^a[y]^a[z]) ;
}
 
void CUT(int x)
{
    Cut(las[x]+1,nex[x]+1) ;
    las[nex[x]]=las[x] ;
    nex[las[x]]=nex[x] ;
    if(head==x) head=nex[x] ;
}
 
void solve(int num)
{
    if(num<=3) return ;
    int st ;
    for(st=head;!check(las[st],st,nex[st]);st=nex[st]) ;
    if(!check(st,nex[st],nex[nex[st]])) CUT(st) ;
    else if(!check(st,las[st],las[las[st]])) CUT(st) ;
    else CUT(nex[st]) ;
    solve(num-1) ;
}
 
main()
{
    TakeCake() ;
    scanf("%d%s",&n,s) ;
    for(int i=0;i<n;i++) a[i]= s[i]=='G'?1:(s[i]=='R'?2:3) ;
    How_Many_Cut(max(n-3,0)) ;
    for(int i=0;i<n;i++) las[i]=(i-1+n)%n , nex[i]=(i+1)%n ;
    head=0 ;
    solve(n) ;
    Finish() ;
}